严格的线性回归
线性回归是在向量空间里用线性函数去拟合样本。
该模型以所有样本实际位置到该线性函数的综合距离为损失，通过最小化损失来求取线性函数的参数。参见下图：
对于线性回归而言，一个样本只要不是正好落在最终作为模型的线性函数上，就要被计算损失。
宽容的支持向量回归（SVR）
模型函数
==支持向量回归（Support Vector Regression，SVR）==模型的模型函数也是一个线性函数： y = wx + b。
看起来和线性回归的模型函数一样
但 SVR 和线性回归，却是两个不同的回归模型。
不同在哪儿呢？不同在学习过程。
说得更详细点，就是：计算损失的原则不同，目标函数和最优化算法也不同。
原理
SVR 在线性函数两侧制造了一个“间隔带”，对于所有落入到间隔带内的样本，都不计算损失；只有间隔带之外的，才计入损失函数。之后再通过最小化间隔带的宽度与总损失来最优化模型。
如下图这样，只有那些圈了红圈的样本（或在隔离带边缘之外，或落在隔离带边缘上），才被计入最后的损失：
SVR 的两个松弛变量
SVR 看起来很像 SVM
不过有一点 SVR 和 SVM 正相反，那就是：SVR 巴不得所有的样本点都落在“隔离带”里面，而 SVM 则恰恰希望所有的样本点都在“隔离带”之外。
正是这一点区别，导致 SVR 要同时引入两个而不是一个松弛变量。
SVR 引入两个松弛变量：$\xi$ 和 $\xi^* $
上图显示了 SVR 的基本情况：
$f(x) = wx +b$ 是我们最终要求得的模型函数；
$wx + b + \epsilon$ 和 $wx +b – \epsilon$（也就是 $f(x) + \epsilon$ 和 $f(x) - \epsilon$）是隔离带的上下边缘；
$\xi$ 是隔离带上边缘之上样本点的 $y$ 值，与对应 $x$ 坐标在“上边缘超平面”上投影的差；
而 $\xi^* $ 则是隔离带下边缘之下样本点，到隔离带下边缘上的投影，与该样本点 $y$ 值的差。
这样说有些绕，我们用公式来反应：
$ \begin{Bmatrix} \begin{array}{lr}
\xi_i=y_i-(f(x_i)+\epsilon),& if \ y_i>f(x_i)+\epsilon \\
\xi_i=0, & otherwise
\end{array} \end{Bmatrix}$
$\begin{Bmatrix} \begin{array}{lr}
\xi_i^{* }=(f(x_i)-\epsilon)-y_i,& if \ y_i>f(x_i)-\epsilon \\
\xi_i^{* }=0, & otherwise
\end{array}\end{Bmatrix}$
对于任意样本 $x_i$，如果它在隔离带里面或者隔离带边缘上，则 $\xi_i$ 和 $\xi_i^* $ 都为$0$； 如果它在隔离带上边缘上方，则 $\xi_i > 0，\xi_i^* =0$；如果它在下边缘下方，则 $\xi_i = 0，\xi_i^* > 0$。
SVR 的主问题和对偶问题
SVR 的主问题
SVR 主问题的数学描述如下：
$min_{w,b,\xi,\xi^* }\frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^* )$
$ s.t. \ \ f(x_i) - y_i \leqslant \epsilon + \xi_i;\ \ y_i - f(x_i) \leqslant \epsilon + \xi_i^* ;\ \ \xi_i \geqslant 0; \ \ \xi_i^* \geqslant 0,\ \ i = 1,2, ..., m.$
SVR 的拉格朗日函数和对偶问题
我们引入拉格朗日乘子 $\mu_i \geqslant 0，\mu_i^* \geqslant 0， \alpha_i \geqslant 0$ 和 $\alpha_i^* \geqslant 0$，来针对上述主问题构建拉格朗日函数，得到拉格朗日函数如下：
$L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) = \frac{1}{2}||w||^2 + C\sum_{i=1}^{m}(\xi_i +\xi_i^* ) + \sum_{i=1}^{m}\alpha_i(f(x_i) - y_i -\epsilon - \xi_i) + \sum_{i=1}^{m}\alpha_i^* (y_i - f(x_i) -\epsilon - \xi_i^* ) + \sum_{i=1}^{m}\mu_i(0 - \xi_i) + \sum_{i=1}^{m}\mu_i^* (0 - \xi_i^* ) $
它对应的对偶问题是：
$max_{\alpha, \alpha^* , \mu, \mu^* }min_{w,b,\xi,\xi^* }L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) $
求解 SVR 对偶问题
首先要求最小化部分：
$min_{w,b,\xi,\xi^* }L(w,b,\xi,\xi^* , \alpha,\alpha^* , \mu,\mu^* ) $
分别对 $w，b，\xi_i 和 \xi_i^* $ 求偏导，并令偏导为0，可得：
$ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i, $
$ 0 = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i),$
$ C = \alpha_i + \mu_i ,$
$ C = \alpha_i^* + \mu_i .$
将上述4个等式带回到对偶问题中，在通过求负将极大化问题转化为极小化问题，得到如下结果：
$min_{\alpha,\alpha^* }[\sum_{i=1}^{m}y_i(\alpha_i - \alpha_i^* ) + \epsilon\sum_{i=1}^{m}(\alpha_i + \alpha_i^* ) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}(\alpha_i -\alpha_i^* )(\alpha_j -\alpha_j^* )x_i^Tx_j ]$
$s.t. \sum_{i=1}^{m}(\alpha_i^* - \alpha_i) = 0; \ \ 0 \leqslant \alpha_i, \alpha_i^* \leqslant C. $
用 SMO 算法求解 SVR
SMO 算法针对的是任意样本 $x_i$ 只对应一个参数 $\alpha_i$ 的情况，而此处，这个样本却对应两个参数 $\alpha_i 和 \alpha_i^* $。
可以把 $\alpha_i$ 和 $\alpha_i^* $ 转化为一个参数。
整个求解过程采用的是拉格朗日对偶法，对偶问题有解的充要条件是满足 KKT 条件。
对于 SVR 的对偶问题，它的 KKT 条件是：
$ \alpha_i(f(x_i) - y_i - \epsilon - \xi_i) = 0, $
$ \alpha_i^* (y_i - f(x_i) - \epsilon - \xi_i^* ) = 0, $
$ \alpha_i\alpha_i^* =0, $
$\xi_i\xi_i^* = 0, $
$(C - \alpha_i)\xi_i = 0, $
$ (C - \alpha_i^* )\xi_i^* = 0. $
由 KKT 条件可见，当且仅当 $f(x_i) - y_i - \epsilon - \xi_i = 0$ 时，$\alpha_i$ 才可以取非0值；当且仅当 $y_i - f(x_i) - \epsilon - \xi_i^* = 0$ 时，$\alpha_i^* $ 才可以取非0值。
$f(x_i) - y_i - \epsilon - \xi_i = 0 => y_i = f(x_i) - \epsilon - \xi_i$ 对应的是在隔离带下边缘以下的样本。
而 $y_i - f(x_i) - \epsilon - \xi_i^* = 0 => y_i = f(x_i) + \epsilon + \xi_i^* $ 对应的是在隔离带上边缘之上的样本。
一个样本不可能同时既在上边缘之上，又在上边缘之下，所以这两个等式最多只有一个成立，相应的 $\alpha_i$ 和 $\alpha_i^* $ 中至少有一个为0。
我们设：$\lambda_i = \alpha_i – \alpha_i^* $。
既然 $\alpha_i$ 和 $\alpha_i^* $ 中至少有一个为0，且 $0 \leqslant \alpha_i，\alpha_i^* ，\leqslant C $ （参见文章上节“求解 SVR 对偶问题”结尾），于是有 : $|\lambda_i| = \alpha_i + \alpha_i^* $。
将 $\lambda_i$ 和 $|\lambda_i|$ 带入对偶问题，则有：
$min_{\lambda}[\sum_{i=1}^{m}y_i(\lambda_i) + \epsilon( |\lambda_i|) + \frac{1}{2}\sum_{i=1}^{m}\sum_{j=1}^{m}\lambda_i \lambda_j x_i^Tx_j ]$
$s.t. \sum_{i=1}^{m}(\lambda_i) = 0; \ \ -C \leqslant \lambda_i \leqslant C. $
接下来就可以用 SMO 求解了
当然，这样一个推导过程仅仅用于说明 SMO 也可以应用于 SVR，具体的求解过程和 SVM 的 SMO 算法还是有所差异的。
支持向量与求解线性模型参数
因为 $f(x) = wx + b$，又因为前面已经求出 $ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i $，因此：
$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)x_i^Tx + b$
由此可见，只有满足 $\alpha_i^* - \alpha_i \ne 0$ 的样本才对 $w$ 取值有意义，才是 SVR 的支持向量。
也就是说，只有当样本满足下列两个条件之一时，它才是支持向量：
$f(x_i) - y_i - \epsilon - \xi_i = 0$
或
$ y_i - f(x_i) - \epsilon - \xi_i^* = 0$
换言之，这个样本要么在隔离带上边缘以上，要么在隔离带下边缘以下（含两个边缘本身）。
也就是说，落在 $\epsilon$-隔离带之外的样本，才是 SVR 的支持向量！
可见，无论是 SVM 还是 SVR，它们的解都仅限于支持向量，即只是全部训练样本的一部分。因此 SVM 和 SVR 的解都具有稀疏性。
通过最优化方法求解出了 $w$ 之后，我们还需要求 $b$。
$f(x_i) = wx_i + b => b = f(x_i) – wx_i $
而且，对于那些落在隔离带上边缘上的支持向量，有 $f(x_i)= y_i+\epsilon$，落在隔离带下边缘上的支持变量有 $f(x_i) = y_i -\epsilon$。
因此，$ b = \frac{1}{|S_u| + |S_d|}[\sum_{s\in S_u}(y_s + \epsilon - w x_s) + \sum_{s\in S_d}(y_s - \epsilon - w x_s)]$
其中 $S_u$ 是位于隔离带上边缘的支持向量集合，而 $S_d$ 则是位于隔离带下边缘的支持向量集合。
SVR 的核技巧
前面讲到的适用于 SVM 的核技巧也同样适用于 SVR。
SVR 核技巧的实施办法和 SVM 一样，也是将输入空间的 $x$ 通过映射函数 $\phi(x)$ 映射到更高维度的特征空间。然后再在特征空间内做本文前面所述的一系列操作。
因此，在特征空间中的线性模型为：
$f(x) = w\phi(x) + b$
其中：
$ w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)\phi(x_i) $
对照 SVM 核函数的做法，我们也令：
$k(x_i,x_j) = \phi(x_i)^T \phi(x_j)$
则：
$f(x) = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)k(x,x_i) + b$
具体核技巧的实施过程，也对照 SVM 即可。
