此文是本人学习林轩田老师的机器学习技法第六课——Support Vector Regression——的课堂笔记。
这节课介绍两个模型，与之前的 SVM 不同，都采用二次误差，一个是”kernel ridge regression”，另一个比较重要，是”Support Vector Regression”。最后，针对“机器学习基石”及本课程所讲的分类方法做一个总结。
参考
Kernel Ridge Regression
ridge regression，即岭回归，简单地讲，是“在平方误差的基础上增加 L2 正则项的回归”。以下是基本公式，这部分目标是将其 kernel 化。
$$ \min{\mathbf{w}} \frac{\lambda}{N}\mathbf{w^Tw} + \frac{1}{N} \sum{n=1}^{N}{ (y_n - w^T z_n)^2 }
$$
在上节课”“中的“Kernel Logistic Regression”一节，已经讲过“带 L2 正则化的线性模型”可以被 kernel 化，而且 $\mathbf{w}$ 可以被 $\mathbf{z}$ 线性表示，即 $\mathbf{w} = \sum \beta_n z_n$。
因为这部分推导与”Kernel Logistic Regression”的推导相似，在此给出结果：
$$ \min{\beta} { \frac{\lambda}{N} \sum{n=1}^{N}\sum_{n=1}^{M} \beta_n \beta_m K(\mathbf{x_n, xm})
+\frac{1}{N} \sum{n=1}^{N}{ ( yn - \sum{m=1}^N {\beta_m K(\mathbf{x_m, x_n})} )^2 }}
$$
接下来求解。首先矩阵化，代入 $\mathbf{\beta, y}$ 列矩阵，$\mathbf{K{n \times n}}$ 矩阵，$\mathbf{K{m,n}} = K(\mathbf(x_m, xn)$：
$$ \min{\beta} {\frac{\lambda}{N} \mathbf{\beta^T K \beta} + \frac{1}{N} ( \beta^T K \beta K - 2 \beta^T K^Ty + y^T y )}
$$
求导，梯度为：
$$ \nabla = \frac{2}{N} \mathbf{K^T}( (\lambda \mathbf{I} + \mathbf{K}) \mathbf{\beta} - \mathbf{y} )
$$
令梯度为 0, 则解得：
$$ \mathbf{\beta} = (\lambda \mathbf{I} + \mathbf{K})^{-1} \mathbf{y}
$$
推导过程中省略了许多步骤 :-P。需要注意的是，该求解方法时间复杂度为 $O(N^3)$，而且 $\beta$ 内元素值多不为 0。课中讲到，用于分类的”Kernel Ridge Regression”被称作“least squares SVM (LSSVM)”。因为 $\beta_n$ 多数非 0，它求解得到的”Support Vector”非常多。
Support Vector Regression
“Support Vector Regression (SVR)”尝试避免”Kernel Ridge Regression”的“Support Vector” dense 问题，同时保留类似二次误差(least squares error)的形式。
相对于 SVM 的 hinge regression，Support Vector Regression 采用 tube regression（在上节课”“介绍过）。令 $s=w^T z + b$，两者加上 squared error 的 error function 表达式为：
| err type | function |
|---|---|
| squared err | $(s-y)^2$ |
| tube err | $\max(abs(s - y) - \epsilon,\; 0)$ |
| hinge err | $\max(1-ys,\; 0)$ |
（abs 取绝对值函数）很明显，squared err 与 tube err 的变化趋势相近，当 $s \rightarrow +\infty$，$err \rightarrow +\infty$，当 $s \rightarrow -\infty$，$err \rightarrow +\infty$。如果作图，两者都呈一个山谷状。
在 Soft Margin SVM 中，使用了 hinge error，在此将其替换成 tube error 重新推导。
$$ \min{b, \mathbf{w}} \frac{1}{2}\mathbf{w^Tw} + C \sum{n=1}^{N}{\max(0, |w^T z_n + b - y_n| - \epsilon)}
$$
首先，引入松弛变量 $\xi_n^\bigwedge, \xin^\bigvee$，同时去掉绝对值：
$$ \min{b,\mathbf{w},\xi_n^\bigwedge, \xi_n^\bigvee} \frac{1}{2}\mathbf{w^Tw} + C \sum{ (\xi_n^\bigwedge + \xi_n^\bigvee) } \\
s.t.\quad -\epsilon - \xi_n^\bigvee \le y_n - w^T z_n - b \le \epsilon + \xi_n^\bigwedge \\
\xi_n^\bigwedge \ge 0,\quad \xi_n^\bigvee \ge 0
$$
之后，引入拉格朗日乘数 $\alpha_n^\bigwedge, \alphan^\bigvee$，分别对应限制条件的上限与下限，又经过一系列求导、KKT 条件、化简等处理（参考“Soft Margin SVM” :-P），得到最终公式：
$$ \min \frac{1}{2} \sum{n=1}^{n}\sum_{m=1}^{n} (\alpha_n^\bigwedge - \alpha_n^\bigvee)(\alpha_m^\bigwedge - \alpha_m^\bigvee)K(x_n, xm) + \sum{n=1}^N( (\epsilon - y_n) \alpha_n^\bigwedge + (\epsilon ＋ y_n) \alpha_n^\bigvee) \\
s.t.\quad \sum(\alpha_n^\bigwedge - \alpha_n^\bigvee) = 0 \\
0 \le \alpha_n^\bigwedge \le C, 0 \le \alpha_n^\bigvee \le C
$$
同样是 QP 问题，求解得出
$$ \mathbf{w} = \sum(\alpha_n^\bigwedge - \alpha_n^\bigvee)\mathbf{z_n}
$$
Support Vector 为 $\alpha_n^\bigwedge - \alpha_n^\bigvee \ne 0$ 对应的数据点，SVR 保证了 SV 的稀疏性。
分类器小结
目前学习的（二）分类器，可以“线性的”与“kernel化的”，从 error function 看，可分为 “0/1 error”, “hinge error”, “squared/tube error”, “logistic error”。
| linear / kernel | 0/1 or hinge error | squared/tube error | logistic error |
|---|---|---|---|
| linear | PLA/pocket | linear SVR | |
| linear | linear soft-margin SVM | linear ridge regression | regularized logistic regression |
| kernel | kernel ridge regression | kernel regularized logistic regression | |
| kernel | SVM | SVR | probabilistic SVM |
其中第二、四行是最常用的，老师推荐了开源库 LIBLINEAR 与 LIBSVM。