1.宽容的支持向量回归（SVR）

一种“宽容的”回归模型：支持向量回归（Support Vector Regression，SVR）。

支持向量回归模型的模型函数也是一个线性函数： $y=wx+b$ 。看起来和线性回归的模型函数一样！但 SVR 和线性回归，却是两个不同的回归模型。

这两个模型不同点学习过程，就是：计算损失的原则不同，目标函数和最优化算法也不同。

1.1.原理

SVR 在线性函数两侧制造了一个“间隔带”，对于所有落入到间隔带内的样本，都不计算损失；只有间隔带之外的，才计入损失函数。之后再通过最小化间隔带的宽度与总损失来最优化模型。如下图这样，只有那些圈了红圈的样本（或在隔离带边缘之外，或落在隔离带边缘上），才被计入最后的损失：

image

1.2.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$ 值的差。用公式来反应：

image

对于任意样本 $x_i$ ，如果它在隔离带里面或者隔离带边缘上，则 $\xi$ 和 $\xi^*$ 都为 $0$ ；如果它在隔离带上边缘上方，则 $\xi_i > 0，\xi_i^*=0$ ；如果它在下边缘下方，则 $\xi_i = 0，\xi_i^* > 0$ 。

2.SVR 的主问题和对偶问题

2.1.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.$

2.2.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^*)$

2.3.求解 SVR 对偶问题

首先要求最小化部分：
$min_{w,b,\xi,\xi^*}L(w,b,\xi,\xi^*, \alpha,\alpha^*, \mu,\mu^*)$
分别对 $w$ ， $b$ ， $\xi$ 和 $\xi^*$ 求偏导，并令偏导为 $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.$

2.4.用 SMO 算法求解 SVR

SMO 算法针对的是任意样本 $x_i$ 只对应一个参数 $\alpha_i$ 的情况，而此处，这个样本却对应两个参数 $\alpha_i$ 和 $\alpha_i^*$ 。有没有办法把 $\alpha_i$ 和 $\alpha_i^*$ 转化为一个参数呢？办法还是有的！

我们整个求解过程采用的是拉格朗日对偶法，对偶问题有解的充要条件是满足** KKT 条件**。那么对于 SVR 的对偶问题，它的 KKT 条件是什么呢？它的 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$ ，于是有 : $|\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 算法还是有所差异的。

3.支持向量与求解线性模型参数

因为 $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$ 则是位于隔离带下边缘的支持向量集合。

4.SVR 的核技巧

SVR 核技巧的实施办法和 SVM 一样，也是将输入空间的 $x$ 通过映射函数 $\phi(x)$ 映射到更高维度的特征空间。然后再在特征空间内做本文前面所述的一系列操作。因此，在特征空间中的线性模型为：
$f(x) = w\phi(x) + b$
其中：
$w = \sum_{i=1}^{m}(\alpha_i^* - \alpha_i)\phi(x_i)$