实例结果对比

• 左边是$linear\ ridge\ regression$的解
  
  • $w = (\lambda I + X^TX)^{-1}X^Ty$
• 右边是$kernel\ ridge\ regression$的解
  
  • $\beta = (\lambda I + K)^{-1}y$

在$linear\ ridge\ regression$中$(\lambda I + X^TX)$是$d\times d$的，该算法时间复杂度可以记为$O(d^3+d^2N)$；在$kernel\ ridge\ regression$中$(\lambda I + K)$是$N\times N$的。时间复杂度为$O(N^3)$。

小结

所以当$N>d$的时候，使用$linear\ ridge\ regression$比较有效；当资料量$N$很大的时候，$kernel\ ridge\ regression$是比较难做的，但是它有很大的自由度，可以做出复杂的曲线。所以使用线性的模型，通常关注的是模型的复杂度和效率；但是当问题很复杂的时候，通常会使用$kernel$来对数据进行建模，只是缺点就是要付出计算上的复杂度。

Support Vector Regression Primal

软间隔SVM和LSSVM

$linear\ regression$可以用来做$classification$，所以$kernel\ ridge\ regression$也可以用来做$classification$。用于$classification$的$kernel\ ridge\ regression$有一个特别的名字叫做$least\ squares\ SVM(LSSVM)$，$least\ squares$在强调的是，它所使用的是$error$是$square\ error$。

对同样的资料分别利用使用$soft\ margin\ Gaussian\ SVM$和$Gaussian\ LSSVM$进行分类的结果如下：

从图中可以看出，分隔边界没有几乎是一致的，但是相比$soft\ margin\ Gaussian\ SVM$来说，$Gaussian\ LSSVM$得到的支持向量$SV$（使用方框框起来的点）会更多一些，右图中的每一个都是$support\ vector$。为什么会有这样的结果呢？$kernel\ ridge\ regression$中的$\beta$是使用$\beta = (\lambda I+K)^{-1}y$算出来，并没有通过加什么限制条件使得这些$\beta$很稀疏。所以得到的每一个$\beta$几乎都不是0，那么所有的点就都是$support\ vector$。当$support\ vector$很多的时候，在做$predict$的时候，靠的是和每一个$SV$算出$kernel$然后和$\beta$的乘积和，即，$g(x) = \sum_{n=1}^{N}\beta_nK(x_n, x)$， 会多花很多的时间。
$kernel\ logistic\ regression$和$kernel\ ridge\ regression$求出来的都是很$dense$的$\beta$。而$soft\ margin\ SVM$就具有比较好的性质，最后得到的$\alpha$就是$sparse$的，即很多是0，只有少数不是0。这是从$KKT\ condition$得到的结果。

现在我们想要做的事情是，$regression$能不能像$SVM$一样得到比较$sparse$的解？

Tube Regression

在使用平方误差$square\ error$的时候，不管真实值$y$和预测值$s=w^Tx$相差多远，哪怕只是相差一点点，也要记录在$error$中。现在我们对真实值和预测值之间的误差给一个容忍阈值$\epsilon$，也把这个称为$tube$，当真实值和预测值的差值不超过这个容忍阈值的时候，就不记录该差值。 结合下图就是说：假设容忍阈值的大小为紫色的宽度，那么所有出现在紫色中的点，虽然真实值和预测值之间存在差距，但是不予计较。

也就是说：

• 如果$|s - y| \le \epsilon, \longrightarrow error = 0$
• 如果$|s - y| > \epsilon, \longrightarrow error = |s-y|-\epsilon$

结合以上的讨论得到，如果错的超过了我们的阈值，不计较，此时$|s - y| - \epsilon < 0$，即$err = 0$；如果错的超过了我们的阈值，就将$err$记为超过的部分。

这个$error$通常被称为$\epsilon\ insensitive\ error$，形式很像在$SVM$中的$hinge\ error$。这样做也是为了让$regression$和有$sparse$解的$SVM$取得关联。

我们现在要做的事情是，将带有$L2\ regularized$的$tube\ regression$进行一系列的推到得到它的稀疏的解$\beta$。

Tube和Squared Regression对比

• $tube：err(y, s) = max(0, |y-s|-\epsilon)$
  
• $squared：err(u, s) = (s - y)^2$
  

将两种$error$画在下图中，可以看出，当$|y-s|$比较小的时候，$tube$和$squared$的$error$其实是很接近的。当$|y-s|$比较大的时候，$squared$会上升的比较快，而$tube$则比较平缓。所以$squared$更容易受到噪音的影响，相对来说可能$tube$会好一点。稍后会看到，使用$\epsilon\ insensitive\ error$这样的方式会让我们得到稀疏的解。

L2-Regularized Tube Regression

现在我们要求解的是一个带有$L2$-$regularize$正则化因子的$tube\ regression$问题。

回想一下$soft\ margin\ SVM$问题的求解过程，$SVM$问题解决的是$L2$-$Regularize$加上$margin\ violation$的最小化问题：$min \frac12w^Tw + C\sum margin\ violation$，我们发现直接解决这样的一个问题是困难的，因为同样也会碰到$max$函数无法微分的问题，所以我们重新将其写成了一个$quadratic\ programming$的问题，这样就比较容易求解。然后通过求解该问题的对偶问题可以使用$kernel$技巧。同时$KKT\ conditional$会保证解的稀疏性。

所以我们现在要做的事情就是模仿$SVM$的解法来解决$tube\ regression$。所以先要将$tube\ regression$表示成一个$quadratic\ programming$的问题。

所以为了使得$tube\ regression$问题和$SVM$长的比较像，首先做如下的效的调整，$SVM$中习惯用的参数是$C$而不是$\lambda$，将$w_0$独立出来写作$b$。这样就得到了如下的问题：

Standard Support Vector Regression Primal

SVR Primal

变成一个二次规划问题的关键是将$max$变形，为此我们引进了一个新的变量$\xi_n$，$\xi_n$记录了真实值和预测值的差值比$\epsilon$大多少，且$\xi_n\ge0$。

还不是$QP$问题，因为条件不是线性的，需要去掉绝对值。

现在就得到了一个标准的$QP$问题。我们将这个问题成为称为标准的$Support\ Vector\ Regression(SVR)$的$Primal$问题。

$SVR：minimize \quad regularizer + (upper\ tube\ violation\ \xi_n^{\land} and\ lower\ tube\ violations\ \xi_n^{\lor})$

$SVR$的$Primal$问题如下：

从图中可以看出，就是通过最小化所有的红线长度的和加上规则化因子来得到一条比较好的分割线。

• 参数$C$用来衡量对误差的重视程度，越大则表明想要更小的误差，与此同时就会带来更大的模型复杂度；$C$越小相对来说$\frac12w^Tw$占有的比重就越大，正则化起到的作用就越大，即想要更加简单的模型复杂度。
• 参数$\epsilon$用来决定$tube$的宽度，$tube$的宽度是2$\epsilon$。所以可以用来调节容忍的程度，越大表明对预测值和真实值的差值有越大的容忍度。

所以$SVR$和$SVM$相比来说多一个可以调节的参数 $\epsilon$。
这个二次规划问题的变数有$2N+1+\tilde{d}$，约束的个数$2N+2N$个。那么接下来我们关心的问题是怎么把$\tilde{d}$的影响移除掉。和$SVM$的做法一样，需要把这个问题转换成一个对偶问题，在转换为一个对偶问题之后，就可以使用$kernel\ trick$避免在$Z$空间中的运算，也就是说就和$Z$空间的维度$\tilde{d}$没有关系了。

Support Vector Regression Dual

$SVR$的$Primal$问题如下：

现在有了$SVR$的$Primal$形式，接下来我们希望可以得到$SVR$的$Dual$形式。所以我们引入$Lagrange\ multiplier$，

• 针对条件：$y_n-w^Tz_n - b \le \epsilon + \xi_n^{\land}$，引入乘子$\alpha_n^{\land}$；
• 针对条件：$-\epsilon - \xi_n^{\lor} \le y_n-w^Tz_n - b$，引入乘子$\alpha_n^{\lor}$。

那么接下来就是写出$Lagrange$函数，然后对里面的变量求微分，使用KKT条件对$Lagrange$函数做替换得到一个新的问题，这个新的问题就是我们想要得到的对偶问题。类似于SVM的对偶问题的推导。

这里只给出一些最后推到的结果：

• 利用$KKT$条件对$w_i$进行求导并令结果为0可以得到：
  $$\frac{\partial L}{\partial w_i} = 0 \longrightarrow w = \sum_{n=1}^{N}(\alpha_n^{\land} - \alpha_n^{\lor})z_n$$ 这个和在$SVM$得到的结果是一样的， 即$w$会是$z$的线性组合。
• 利用$KKT$条件对$b$进行求偏导并令结果为0可以得到：
  $$\frac{\partial L}{\partial b} = 0 \longrightarrow \sum_{n=1}^{N}(\alpha_n^{\land} - \alpha_n^{\lor}) = 0$$
• 利用$KKT$条件得最佳解满足：
  $$\alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0, \quad \alpha_n^{\land}(\epsilon+\xi_{n}^{\lor}-y_n+w^Tz_n+b) = 0$$

经过推导之后，SVR的对偶形式如下：

我们推导$SVR$的最初的目的是为了得到稀疏的解。现在我们就来看看我们有没有达到目的。现在我们已经知道了最佳的解$w$可以表示为 $z$ 的线性组合，那么在什么情况下$\beta_n$是 $0$ 呢？

从$KKT$条件告诉我们的如下的两个$complementary\ slackness$出发，

我们考虑严格位于$tube$中的数据点：$|w^Tz_n + b - y_n| < \epsilon$

Summary of Kernel Models

线性模型

本系列中涉及的线性模型主要有三个

• $PLA/pocket$用于分类，直接优化$err_{0/1}$；
• $Logistic\ Regression$用于$soft$分类，其方法是最小化$cross\ entropy\ error$或者说是$logistic\ error$-$err_{CE}$，通常使用$SGD$或者$GD$。如果加上正则化项就是$regularized\ logistic\ regression$。
• $Linear\ Regression$用于对实数的回归分析，通过最小化$err_{square}$可以得到解析解。如果加上正则化项就是$linear\ ridge\ regression$。
• 之后介绍了另外一种线性模型$linear\ soft\ margin\ SVM$，也是用于解决线性的分类问题，使用的$error\ function$被称为是$hinge\ error$，通过求解一个$QP$问题得到最优解。
• $Regression$的另一种做法是$linear\ SVR$，同样是使用二次规划最小化$err_{tube}$。

$LIBLINEAR$中实现了第二行的三种模型。

---

以上线性的模型只要加上$regularizer$都可以延伸成$kernel$的模型。

$linear\ soft\ margin\ SVM$延伸成$SVM$，$SVM$解决的不再是$primal$问题，而是对偶问题；
$linear\ SVR$的$kernel$延伸是$SVR$，同样也是解决对偶问题；
通过$representer\ theorem$可以将$linear\ ridge\ regression$变为$kernel\ ridge\ regression$；
可以将$regularized\ logistic\ regression$变为$kernel\ logistic\ regression$；
$kernel\ logistic\ regression$通常会被$Probabilistic\ SVM$，也就是$two\ level\ learning$取代；

$LIBSVM$实现了最后一行的所有的三种模型。

---

针对上图中模型的实用度做简单的记录：第一行$PLA/pocket$和$linear\ SVR$很少被使用，通常会被它们下面的两个模型分别取代；第三行的$kernel\ ridge\ regression$和$kernel\ logistic\ regression$也比较少用，因为这两个模型的解不是稀疏的，通常会被它们下面的两个模型分别取代。

总结

本篇主要讲解了$Support\ Vector\ Regression$，我们一开始的出发点是如何将$Ridge\ Regression$变为$kernel$的形式， $representer\ theorem$理论帮助我们完成了这个工作，但是通过这样的方法得到的解不是稀疏的，我们想要的$sparse$的解，所以我们通过推导带有$regularizer$的$tube\ error$得出了$SVR$的原始问题，进一步推导了$SVR$的对偶问题。最后根据$KTT$条件得到了稀疏的解。

回顾

• SVM学习笔记-线性支撑向量机
• SVM学习笔记-对偶形式的SVM
• SVM学习笔记-核函数与非线性SVM
• SVM学习笔记-软间隔SVM
• Kernel Logistic Regression
• Support Vector Regression(SVR)