支持向量机/09. 支持向量回归.ipynb

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "支持向量机模型也可以处理回归问题，假设我们能容忍 $f(x)$ 和 $y$ 之间最多有 $\\epsilon$ 的偏差，只有当 $f(x)$ 和 $y$ 之间的偏差大于 $\\epsilon$ 时才计算损失，如下图所示：\n",
    "\n",
    "<img src=\"../images/svr.png\" width=\"500px\" />\n",
    "\n",
    "这被称为 **支持向量回归**（Support Vector Regression，简称 SVR），它的基本形式为：\n",
    "\n",
    "$$\n",
    "\\mathop \\min_{w,b} \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^m \\ell_{\\epsilon} (f(x_i)-y_i)\n",
    "$$\n",
    "\n",
    "其中 $\\ell_{\\epsilon}$ 表示 $\\epsilon-$不敏感损失（$\\epsilon-$ insensitive loss）函数：\n",
    "\n",
    "$$\n",
    "\\ell_{\\epsilon}(z) =\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "&0, &|z| \\leq \\epsilon \\\\\n",
    "&|z| - \\epsilon, &|z| > \\epsilon \\\\\n",
    "\\end{align}\n",
    "\\right.\n",
    "$$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "由于回归线两侧的松弛程度可以不同，可以引入两个松弛变量，将 SVR 的基本形式改写为：\n",
    "\n",
    "$$\n",
    "\\mathop \\min_{w,b,\\xi,\\hat{\\xi}} \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^m (\\xi_i + \\hat{\\xi_i})\n",
    "$$\n",
    "\n",
    "约束条件为：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "s.t. &f(x_i) - y_i \\leq \\epsilon + \\xi_i \\\\\n",
    "&y_i - f(x_i) \\leq \\epsilon + \\hat{\\xi_i} \\\\\n",
    "&\\xi_i \\geq 0, \\hat{\\xi_i} \\geq 0, i = 1,2,\\dots,m\n",
    "\\end{align}\n",
    "$$\n",
    "\n",
    "引入拉格朗日乘子得到拉格朗日函数：\n",
    "\n",
    "$$\n",
    "L(w,b,\\xi,\\hat{\\xi},\\alpha,\\hat{\\alpha},\\mu,\\hat{\\mu})\n",
    "= \\frac{1}{2} \\|w\\|^2 + C \\sum_{i=1}^m (\\xi_i + \\hat{\\xi_i}) - \\sum_{i=1}^m \\mu_i \\xi_i - \\sum_{i=1}^m \\hat{\\mu_i} \\hat{\\xi_i} + \\sum_{i=1}^m \\alpha_i(f(x_i) - y_i - \\epsilon - \\xi_i) + \\sum_{i=1}^m \\hat{\\alpha_i}(y_i - f(x_i) - \\epsilon - \\hat{\\xi_i})\n",
    "$$\n",
    "\n",
    "对 $w, b, \\xi_i, \\hat{\\xi_i}$ 求偏导并令其为 0 得到：\n",
    "\n",
    "$$\n",
    "\\left\\{\n",
    "\\begin{align}\n",
    "w &= \\sum_{i=1}^m (\\hat{\\alpha_i} - \\alpha_i)x_i \\\\\n",
    "0 &= \\sum_{i=1}^m (\\hat{\\alpha_i} - \\alpha_i) \\\\\n",
    "C &= (\\alpha_i + \\mu_i) \\\\\n",
    "C &= (\\hat{\\alpha_i} + \\hat{\\mu_i}) \\\\\n",
    "\\end{align}\n",
    "\\right .\n",
    "$$\n",
    "\n",
    "将其带入拉格朗日函数，得到 SVR 的对偶形式：\n",
    "\n",
    "$$\n",
    "\\begin{align}\n",
    "\\mathop \\min_{\\alpha,\\hat{\\alpha}} &\\frac{1}{2} \\sum_{i=1}^m \\sum_{j=1}^m (\\hat{\\alpha_i} - \\alpha_i)(\\hat{\\alpha_j} - \\alpha_j) x_i x_j - \\sum_{i=1}^m y_i(\\hat{\\alpha_i} - \\alpha_i) + \\epsilon(\\hat{\\alpha_i} - \\alpha_i) \\\\\n",
    "s.t. &\\sum_{i=1}^m (\\hat{\\alpha_i} - \\alpha_i) = 0 \\\\\n",
    "& 0 \\leq \\alpha_i, \\hat{\\alpha_i} \\leq C\n",
    "\\end{align}\n",
    "$$"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.1"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}