Question

红色石头的个人网站： redstonewill.com

上节课我们主要介绍了 Kernel Logistic Regression，讨论如何把 SVM 的技巧应用在 soft-binary classification 上。方法是使用 2-level learning，先利用 SVM 得到参数 b 和 w，然后再用通用的 logistic regression 优化算法，通过迭代优化，对参数 b 和 w 进行微调，得到最佳解。然后，也介绍了可以通过 Representer Theorem，在 z 空间中，引入 SVM 的 kernel 技巧，直接对 logistic regression 进行求解。本节课将延伸上节课的内容，讨论如何将 SVM 的 kernel 技巧应用到 regression 问题上。

Kernel Ridge Regression

首先回顾一下上节课介绍的 Representer Theorem，对于任何包含正则项的 L2-regularized linear model，它的最佳化解 w 都可以写成是 z 的线性组合形式，因此，也就能引入 kernel 技巧，将模型 kernelized 化。

那么如何将 regression 模型变成 kernel 的形式呢？我们之前介绍的 linear/ridge regression 最常用的错误估计是 squared error，即。这种形式对应的解是 analytic solution，即可以使用线性最小二乘法，通过向量运算，直接得到最优化解。那么接下来我们就要研究如何将 kernel 引入到 ridge regression 中去，得到与之对应的 analytic solution。

我们先把 Kernel Ridge Regression 问题写下来：

其中，最佳解必然是 z 的线性组合。那么我们就把代入到 ridge regression 中，将 z 的内积用 kernel 替换，把求的问题转化成求的问题，得到：

ridge regression 可以写成矩阵的形式，其中第一项可以看成是的正则项，而第二项可以看成是的 error function。这样，我们的目的就是求解该式最小化对应的值，这样就解决了 kernel ridge regression 问题。

求解的问题可以写成如下形式：

是关于的二次多项式，要对求最小化解，这种凸二次最优化问题，只需要先计算其梯度，再令梯度为零即可。已经在上式中写出来了，令其等于零，即可得到一种可能的的解析解为：

这里需要关心的问题是的逆矩阵是否存在？答案是肯定的。因为我们之前介绍过，核函数 K 满足 Mercer’s condition，它是半正定的，而且，所以一定是可逆的。从计算的时间复杂上来说，由于是 NxN 大小的，所以时间复杂度是。还有一点，是由两项乘积构成的，另一项是 K，会不会出现 K=0 的情况呢？其实，由于核函数 K 表征的是 z 空间的内积，一般而言，除非两个向量互相垂直，内积才为零，否则，一般情况下 K 不等于零。这个原因也决定了是 dense matrix，即的解大部分都是非零值。这个性质，我们之后还会说明。

所以说，我们可以通过 kernel 来解决 non-linear regression 的问题。下面比较一下 linear ridge regression 和 kernel ridge regression 的关系。

如上图所示，左边是 linear ridge regression，是一条直线；右边是 kernel ridge regression，是一条曲线。大致比较一下，右边的曲线拟合的效果更好一些。这两种 regression 有什么样的优点和缺点呢？对于 linear ridge regression 来说，它是线性模型，只能拟合直线；其次，它的训练复杂度是，预测的复杂度是，如果 N 比 d 大很多时，这种模型就更有效率。而对于 kernel ridge regression 来说，它转换到 z 空间，使用 kernel 技巧，得到的是非线性模型，所以更加灵活；其次，它的训练复杂度是，预测的复杂度是，均只与 N 有关。当 N 很大的时候，计算量就很大，所以，kernel ridge regression 适合 N 不是很大的场合。比较下来，可以说 linear 和 kernel 实际上是效率（efficiency）和灵活（flexibility）之间的权衡。

Support Vector Regression Primal

我们在机器学习基石课程中介绍过 linear regression 可以用来做 classification，那么上一部分介绍的 kernel ridge regression 同样可以来做 classification。我们把 kernel ridge regression 应用在 classification 上取个新的名字，叫做 least-squares SVM（LSSVM）。

先来看一下对于某个问题，soft-margin Gaussian SVM 和 Gaussian LSSVM 结果有哪些不一样的地方。

如上图所示，如果只看分类边界的话，soft-margin Gaussian SVM 和 Gaussian LSSVM 差别不是很大，即的到的分类线是几乎相同的。但是如果看 Support Vector 的话（图中方框标注的点），左边 soft-margin Gaussian SVM 的 SV 不多，而右边 Gaussian LSSVM 中基本上每个点都是 SV。这是因为 soft-margin Gaussian SVM 中的大部分是等于零，的点只占少数，所以 SV 少。而对于 LSSVM，我们上一部分介绍了的解大部分都是非零值，所以对应的每个点基本上都是 SV。SV 太多会带来一个问题，就是做预测的矩，如果非零值较多，那么 g 的计算量也比较大，降低计算速度。基于这个原因，soft-margin Gaussian SVM 更有优势。

那么，针对 LSSVM 中 dense 的缺点，我们能不能使用一些方法来的得到 sparse ，使得 SV 不会太多，从而得到和 soft-margin SVM 同样的分类效果呢？下面我们将尝试解决这个问题。

方法是引入一个叫做 Tube Regression 的做法，即在分类线上下分别划定一个区域（中立区），如果数据点分布在这个区域内，则不算分类错误，只有误分在中立区域之外的地方才算 error。

假定中立区的宽度为，,那么 error measure 就可以写成：，对应上图中红色标注的距离。

通常把这个 error 叫做-insensitive error，这种 max 的形式跟我们上节课中介绍的 hinge error measure 形式其实是类似的。所以，我们接下来要做的事情就是将 L2-regularized tube regression 做类似于 soft-margin SVM 的推导，从而得到 sparse 。

首先，我们把 tube regression 中的 error 与 squared error 做个比较：

然后，将 err(y,s) 与 s 的关系曲线分别画出来：

上图中，红色的线表示 squared error，蓝色的线表示 tube error。我们发现，当|s-y|比较小即 s 比较接近 y 的时候，squared error 与 tube error 是差不多大小的。而在|s-y|比较大的区域，squared error 的增长幅度要比 tube error 大很多。error 的增长幅度越大，表示越容易受到 noise 的影响，不利于最优化问题的求解。所以，从这个方面来看，tube regression 的这种 error function 要更好一些。

现在，我们把 L2-Regularized Tube Regression 写下来：

这个最优化问题，由于其中包含 max 项，并不是处处可微分的，所以不适合用 GD/SGD 来求解。而且，虽然满足 representer theorem，有可能通过引入 kernel 来求解，但是也并不能保证得到 sparsity 。从另一方面考虑，我们可以把这个问题转换为带条件的 QP 问题，仿照 dual SVM 的推导方法，引入 kernel，得到 KKT 条件，从而保证解是 sparse 的。

所以，我们就可以把 L2-Regularized Tube Regression 写成跟 SVM 类似的形式：

值得一提的是，系数和 C 是反比例相关的，越大对应 C 越小，越小对应 C 越大。而且该式也把即 b 单独拿了出来，这跟我们之前推导 SVM 的解的方法是一致的。

现在我们已经有了 Standard Support Vector Regression 的初始形式，这还是不是一个标准的 QP 问题。我们继续对该表达式做一些转化和推导：

如上图右边所示，即为标准的 QP 问题，其中和分别表示 upper tube violations 和 lower tube violations。这种形式叫做 Support Vector Regression（SVR） primal。

SVR 的标准 QP 形式包含几个重要的参数：C 和。C 表示的是 regularization 和 tube violation 之间的权衡。large C 倾向于 tube violation，small C 则倾向于 regularization。表征了 tube 的区域宽度，即对错误点的容忍程度。越大，则表示对错误的容忍度越大。是可设置的常数，是 SVR 问题中独有的，SVM 中没有这个参数。另外，SVR 的 QP 形式共有个参数，2N+2N 个条件。

Support Vector Regression Dual

现在我们已经得到了 SVR 的 primal 形式，接下来将推导 SVR 的 Dual 形式。首先，与 SVM 对偶形式一样，先令拉格朗日因子和，分别是与和不等式相对应。这里忽略了与和对应的拉格朗日因子。

然后，与 SVM 一样做同样的推导和化简，拉格朗日函数对相关参数偏微分为零，得到相应的 KKT 条件：

接下来，通过观察 SVM primal 与 SVM dual 的参数对应关系，直接从 SVR primal 推导出 SVR dual 的形式。（具体数学推导，此处忽略！）

最后，我们就要来讨论一下 SVR 的解是否真的是 sparse 的。前面已经推导了 SVR dual 形式下推导的解 w 为：

相应的 complementary slackness 为：

对于分布在 tube 中心区域内的点，满足，此时忽略错误，和都等于零。则 complementary slackness 两个等式的第二项均不为零，必然得到和，即。

所以，对于分布在 tube 内的点，得到的解，是 sparse 的。而分布在 tube 之外的点，。至此，我们就得到了 SVR 的 sparse 解。

Summary of Kernel Models

这部分将对我们介绍过的所有的 kernel 模型做个概括和总结。我们总共介绍过三种线性模型，分别是 PLA/pocket，regularized logistic regression 和 linear ridge regression。这三种模型都可以使用国立台湾大学的 Chih-Jen Lin 博士开发的 Liblinear 库函数来解决。

另外，我们介绍了 linear soft-margin SVM，其中的 error function 是，可以通过标准的 QP 问题来求解。linear soft-margin SVM 和 PLA/pocket 一样都是解决同样的问题。然后，还介绍了 linear SVR 问题，它与 linear ridge regression 一样都是解决同样的问题，从 SVM 的角度，使用，转换为 QP 问题进行求解，这也是我们本节课的主要内容。

上图中相应的模型也可以转化为 dual 形式，引入 kernel，整体的框图如下：

其中 SVM，SVR 和 probabilistic SVM 都可以使用国立台湾大学的 Chih-Jen Lin 博士开发的 LLibsvm 库函数来解决。通常来说，这些模型中 SVR 和 probabilistic SVM 最为常用。

总结

本节课主要介绍了 SVR，我们先通过 representer theorem 理论，将 ridge regression 转化为 kernel 的形式，即 kernel ridge regression，并推导了 SVR 的解。但是得到的解是 dense 的，大部分为非零值。所以，我们定义新的 tube regression，使用 SVM 的推导方法，来最小化 regularized tube errors，转化为对偶形式，得到了 sparse 的解。最后，我们对介绍过的所有 kernel 模型做个总结，简单概述了各自的特点。在实际应用中，我们要根据不同的问题进行合适的模型选择。

注明：

文章中所有的图片均来自台湾大学林轩田《机器学习技法》课程

更多 AI 资源请关注公众号：红色石头的机器学习之路（ID：redstonewill）