上一篇讲到了基于核函数的岭回归，既然SVM可以用来进行分类，基于核函数的岭回归自然也可以用来进行分类了。
这一篇，我们将把SVM用于解决回归问题。

所以，基于核函数的岭回归(Kernel Ridge Regression)用于分类时，也叫做最小均方支持向量机(least_squares SVM,LSSVM)

与Soft-margin SVM相比，LSSVM通常会有更多的支持向量SV，如图所示：

之所以如此，是因为LSSVM求的参数是$\beta$，$\beta$与样本数成正比，数量很大，非常dense(密度很高)。而SVM求的则是$\alpha​$，很sparse​稀疏。支持向量过多会引起许多问题，所以如何让Regression的参数变得sparce​，是我们要解决的问题。

这个说来话长。首先，引入一个新的Regression，Tube Regression。之所以叫Tube(管道)，是与SVM有关，首先看张图：

这张图中的蓝色区域的边界，就是SVM的支持向量所在的边界，这个蓝色区域就像个管道(Tube)一样。

上一篇讲了软间隔SVM计算误差的时候，即使分类正确，只要落在这个边界中，都会扣分(也就是$\max(1-ys,0)$)。而Tube Regression则更容忍错误，只要在"管道"区域中，不论分类正确与否，都不会计算误差，只有误分类，并且在管道外，才会计算误差，而且误差值扣除掉管道的部分，假设管道的宽度为$\epsilon$，那么它的error则是

$$ err(y,s)=\max(0,|s-y|-\epsilon) $$

这个误差通常叫做$\epsilon$-insensitive error，通常$\epsilon>0$。

tube回归的损失函数，与普通的均方误差对比如下图所示：

可见，tube的容忍度更高，只算误差值与管道的距离，而均方误差则算整个距离。

最终的损失曲线如下，其中最低点的$ys​$为实际要预测的值

可以看出，tube回归的误差在预测值与实际值距离更远的时候，损失增加的速度没有均方误差快，这是一个优点，不容易受到异常值，或者噪音(noise)的影响。而在近处，tube回归与均方差回归几乎是一样的。

所以，下面就是要解的Tube回归问题

$$ \min_{w}\frac{\lambda}{N}w^Tw+\frac{1}{N}\sum_{i=1}^N\max(0,|w^T\Phi(x)-y|-\epsilon) $$

这个问题是没有约束条件的，可是$\max​$函数是不可微的。

之前的解决软间隔SVM无法微分的方法，是将其转换为QP问题，并转换为对偶问题，满足KKT条件，这样就很稀疏(sparsity)了。

于是，问题的公式被转换成了这样：

$$ \min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N\max(0,|w^T\Phi(x)+b-y|-\epsilon) $$

式中，把$b$从$w$中独立出来，作为一个单独的参数。

之前解决软间隔SVM的方法，是引入了$\xi_i$，这里也如此：

$$ \min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N\xi_i\\ s.t. \quad |w^T\Phi(x)+b-y|\le\epsilon+\xi_i\\ \xi_i\ge0 $$

可是绝对值不是个线性运算，所以依然要把它拆开：

$$ \min_{w,b}\frac{1}{2}w^Tw+C\sum_{i=1}^N(\breve\xi_i+\hat\xi)\\ -\epsilon-\breve\xi_i\le y_i-w^T\Phi(x_i)-b\le \epsilon +\hat\xi_i $$

这就是标准的支持向量回归(Support Vector Regression,SVR)的原始问题(Primal)。

有了原始问题，就可以将其转换为对偶问题并解决了。

转换为对偶问题的一整个过程，之前的文章中已经写过了支持向量机SVM 系列(2)——对偶方法(Dual Method)，这里就不赘述了。

这里直接给出结果。

$$ \begin{aligned} \text{目标函数} \quad&\frac{1}{2}w^Tw+C\sum_{i=1}^N(\breve\xi_i+\hat\xi)\\ \text{拉格朗日乘子}&\hat\alpha\quad y_i-w^T\Phi(x_i)-b\le \epsilon +\hat\xi_i\\ \text{拉格朗日乘子}&\breve\alpha\quad -\epsilon-\breve\xi_i\le y_i-w^T\Phi(x_i)-b \end{aligned} $$

根据KKT条件，可以推出：

$$ \frac{\partial L}{\partial w_i}\Rightarrow w=\sum\limits_{i=1}^N(\hat\alpha_i-\breve\alpha_i)\Phi(x)\\ \frac{\partial L}{\partial b}=\sum\limits_{i=1}^N(\hat\alpha_i-\breve\alpha_i)=0 $$

以及互补条件(必须有一个为0)：

$$ \hat\alpha_i(\epsilon+\hat\xi_i-y_i+w^T\Phi(x_i)+b)=0 \\ \breve\alpha_i(\epsilon+\breve\xi_i+y_i-w^T\Phi(x_i)-b)=0 $$

最终，得到的结果是：

$$ \begin{aligned} \min&\frac{1}{2}\sum\limits_{i=1}^N\sum\limits_{j=1}^N(\hat\alpha_i-\breve\alpha_i)(\hat\alpha_j-\breve\alpha_j)K_{i,j}\\ &+\sum\limits_{i=1}^N\Big( (\epsilon-y_n)\cdot\hat\alpha+ (\epsilon+y_n)\cdot\breve\alpha \Big)\\ &s.t. \quad\sum\limits_{i=1}^N(\hat\alpha_i-\breve\alpha_i)=0\\ &0\le \hat\alpha_i\le C,0\le \hat\alpha_i\le C \end{aligned} $$

这个公式需要时间来推导，其实除了计算更复杂些，跟最初了对偶问题解决方法没有任何区别。

现在开始考虑稀疏性问题。根据互补条件以及$w$的结果：

$$ \hat\alpha_i(\epsilon+\hat\xi_i-y_i+w^T\Phi(x_i)+b)=0 \\ \breve\alpha_i(\epsilon+\breve\xi_i+y_i-w^T\Phi(x_i)-b)=0\\ w=\sum\limits_{i=1}^N(\hat\alpha_i-\breve\alpha_i)\Phi(x) $$

可以知道$\hat\alpha_i-\breve\alpha_i$就是我们之前要求的$\beta_i$。

当点落在tube的范围里面，没有任何违反，所以互补条件公式中的$\hat\xi_i$与$\breve\xi_i$为0。

而且，因为在tube中，可知$|w^T\Phi(x_i)+b-y_i|<\epsilon$，而且是严格小于$\epsilon$ 。

也就是说

$$ \epsilon+0-y_i+w^T\Phi(x_i)+b)\ne0 \\ \epsilon+0+y_i-w^T\Phi(x_i)-b)\ne0\\ $$

那么也就是说，$\hat\alpha_i,\breve\alpha_i$均为0，也就是说$\beta_i$也是0。也就是说只有落在tube外面的，才是"支持向量"，这样终于就得到稀疏的$\beta$。