机器学习——SVM的回归形式(SVR)

岭回归(ridge regression)
在前面的一篇博客(机器学习——线性回归(Linear Regression))中提到，线性回归的解析解如下，
$$w=(X^{T}X{)}^{-1}{X}^{T}y$$
其中，X的维数为$N\times (d+1)$。因为大多数情况下样本量(N)是远大于特征数(d)的，所以，$X^{T}X$常常是可逆的。但当X不是列满秩矩阵时，即特征数比样本数还要多，则$X^{T}X$的行列式为0，$X^{T}X$不可逆；或者X的某些列的线性相关性比较大时，$X^{T}X$的行列式接近0，此时$X^{T}X$为病态矩阵，此时计算逆矩阵误差会比较大。

为了解决$X^{T}X$矩阵求逆的问题，给矩阵$X^{T}X$加上一个$\lambda I$，从而使矩阵非奇异，进而能对$X^{T}X+\lambda I$求逆，这就是岭回归。

即岭回归的系数计算式为，
$$W=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$

上式中的$\lambda I$其实是正则化的一种体现，上式是L2-regularized linear regression的解析解，计算过程描述如下：
首先，L2-regularized linear regression的问题可以描述为，
$$\underset{w}{\min }\frac{\lambda }{N}{w}^{T}w+\frac{1}{N}\sum _{n=1}^N{(y_n-w^T{x}_n)}^2$$
写成矩阵形式为，
$$\underset{w}{\min }\frac{\lambda }{N}{w}^{T}w+\frac{1}{N}{\Vert Xw-y\Vert }^2$$
对上式求梯度，
$$\nabla (w)=\frac{2\lambda }{N}w+\frac{1}{N}(2X^{T}Xw-2X^{T}y)=\frac{2}{N}((\lambda I+X^{T}X)w-X^{T}y)=0$$
令梯度为0，求得系数w，为，
$$w=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$

所以，岭回归的系数解析解其实是对线性回归进行L2正则化的一种体现。

在上一篇博客中，提到了Representer Theorem，即对于任意的L2正则化的线性模型，其最佳化的$w$均可表示为资料线性组合的形式，所以可以考虑把Kernel用在岭回归里，叫做kernel ridge regression。

由于$w=\sum _{i=0}^N{\beta }_n{z}_n$，所以一旦把岭回归kernel化之后，实际上就是用参数$\beta$取代了原来的参数$w$，则现在的kernel ridge regression问题可以描述如下，
$$\begin{array}{l}\underset{\beta }{\min }\frac{\lambda }{N}\sum _{n=1}^N\sum _{m=1}^N{\beta }_n{\beta }_{m}K(x_n,x_m)+\frac{1}{N}\sum _{n=1}^N{(y_n-\sum _{m=1}^N{\beta }_{m}K(x_n,x_m))}^2\\ \\ =\frac{\lambda }{N}{\beta }^{T}K\beta +\frac{1}{N}({\Vert y-K\beta \Vert }^2)-转化为矩阵形式\\ \\ =\frac{\lambda }{N}{\beta }^{T}K\beta +\frac{1}{N}({\beta }^T{K}^{T}K\beta -2{\beta }^T{K}^{T}y+y^{T}y)\end{array}$$
求上式的梯度，如下，
$$\begin{array}{l}\nabla E(\beta )=\frac{2}{N}(\lambda K^{T}I\beta +K^{T}K\beta -K^{T}y)\\ \\ =\frac{2}{N}{K}^T((\lambda I+K)\beta -y)\\ \\ (这里的K是一个半正定的对称矩阵)\end{array}$$
让$\nabla \mathrm{E}(\beta )=0$，可以得到如下的解析解，
$$\beta =(\lambda I+K{)}^{-1}y$$
该解一定存在，因为$\lambda >0$，并且K一定是一个半正定矩阵，所以，$\lambda I+K$一定可逆。

上面的是kernel ridge regression的参数求解过程，而LSSVM实际上就是kernel ridge regression用于分类的情况，即，

但LSSVM求解的时间复杂度达到了$O(N^3)$，且求解过程中，矩阵K是稠密的。

下面是linear ridge regression和kernel ridge regression的一个对比，

linear ridge regression	kernel ridge regression
$$w=(X^{T}X+\lambda I{)}^{-1}{X}^{T}Y$$	$$\beta =(\lambda I+K{)}^{-1}y$$
限制更多，形状比较简单	更加灵活，边界可以很复杂
训练复杂度：$O(d^3+d^{2}N)$ 预测复杂度：$O(d)$	训练复杂度：$O(N^3)$ 预测复杂度：$O(N)$
当$N>>d$时，计算很高效	对于样本数多的情况，计算量太大

所以，从上表可以看出，linear与kernel其实就是对efficiency和flexibility的一个取舍。

在介绍Tube Regression之前，首先先对Soft-Margin SVM和LSSVM做一个对比，下面两张图是对同一个案例，分别用这两方法所求得的边界示意，

图中，正方形所框选出的都是支持向量(SVs)，从中可以看出，LSSVM有更多的SVs，这就意味着其参数$\beta$是稠密的，预测起来，也会更慢。但之前说过 ，标准的SVM求得的系数$\alpha$是稀疏的，所以，要找到一种方法，获得一个稀疏的$\beta$——Tube Regression。

• 在tube内(紫色区域内)：没有错误
• 在tube外：计算到tube的距离当作error(红色线为error)

则其误差衡量方式为，
$$err(y,s)=\max (0,\left|s-y\right|-\epsilon )$$
这中误差叫做$\epsilon -\mathrm{i}\mathrm{n}\mathrm{s}\mathrm{e}\mathrm{n}\mathrm{s}\mathrm{i}\mathrm{t}\mathrm{i}\mathrm{v}\mathrm{e}\mathrm{e}\mathrm{r}\mathrm{r}\mathrm{o}\mathrm{r}$，有如下关系，

$\begin{array}{l}当\left|s-y\right|\le \epsilon :误差为0\\ 当\left|s-y\right|>\epsilon :误差为\left|s-y\right|-\epsilon \end{array}$

下面将Tube Regression和Squared Regression做一个对比，

Tube Regression	Squared Regression

误差图像如下，

• 当$\left|s-y\right|$很小时，$tube\approx squared$;
• 当$\left|s-y\right|$越来越小时，即从中间向两边，tube增长缓慢，不容易受noise影响。

加入L2 regularizer之后，即L2-Regularized Tube Regression描述如下，

$$\underset{w}{\min }\frac{\lambda }{N}{w}^{T}w+\frac{1}{N}\sum _{n=1}^N\max (0,\left|w^T{z}_n-y\right|-\epsilon )$$

将上式改写，可得到SVR的原始形式如下，

$$\underset{b,w}{\min }\frac{1}{2}{w}^{T}w+C\sum _{n=1}^N\max (0,\left|w^T{z}_n+b-y_n\right|-\epsilon )——StandardSVRPrimal$$

上述问题的形式，比方便求解，对比之前SVM部分的推导，将其进行改写，改写后的等价最优化问题如下，
$$\begin{array}{l}\underset{b,w,{\xi }^{\wedge },{\xi }^{\vee }}{\min }\frac{1}{2}{w}^{T}w+C\sum _{n=1}^N({\xi }_n^{\vee }+{\xi }_n^{\wedge })\\ \\ s.t.-\epsilon -{\xi }_n^{\vee }\le y_n-w^T{z}_n-b\le \epsilon +{\xi }_n^{\wedge }\\ \\ {\xi }_n^{\vee }\ge 0,{\xi }_n^{\wedge }\ge 0\end{array}$$

其中，参数C的含义：regularization和tube violation的权衡
           参数$\epsilon$的含义：tube的宽度

上述问题可用QP来求解，共有$\tilde{d}+1+2N$个变量，4N条约束，接下来，就是把primal问题转为dual问题，移除对$\tilde{d}$的依赖。

引入拉格朗日乘子${\alpha }^{\wedge }\&{\alpha }^{\vee }$：
$$\begin{array}{l}目标方程\frac{1}{2}{w}^{T}w+C\sum _{n=1}^N({\xi }_n^{\vee }+{\xi }_n^{\wedge })\\ \\ 加入{\alpha }_n^{\wedge }for{y}_n-w^T{z}_n-b\le \epsilon +{\xi }_n^{\wedge }\\ \\ 加入{\alpha }_n^{\vee }for-\epsilon -{\xi }_n^{\vee }\le y_n-w^T{z}_n-b\end{array}$$

KKT条件：
$$\begin{array}{l}\frac{\partial L}{\partial w_i}=0:w=\sum _{n=1}^N(\underset{{\beta }_n}{\underbrace{{\alpha }_n^{\wedge }-{\alpha }_n^{\vee }}})z_n\\ \\ \frac{\partial L}{\partial b}=0:\sum _{n=1}^N({\alpha }_n^{\wedge }-{\alpha }_n^{\vee })=0\\ \\ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{y}\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}:\begin{array}{c}{\alpha }_n^{\wedge }(\epsilon +{\xi }_n^{\wedge }-y_n+w^T{z}_n+b)=0\\ {\alpha }_n^{\vee }(\epsilon +{\xi }_n^{\vee }+y_n-w^T{z}_n-b)=0\end{array}\end{array}$$

推导过程略，下面直接给出SVR Dual：
$$\begin{array}{l}\min \frac{1}{2}\sum _{n=1}^N\sum _{m=1}^N({\alpha }_n^{\wedge }-{\alpha }_n^{\vee })({\alpha }_m^{\wedge }-{\alpha }_m^{\vee })K_{n,m}+\sum _{n=1}^N((\epsilon -y_n)\cdot {\alpha }_n^{\wedge }+(\epsilon +y_n)\cdot {\alpha }_n^{\vee })\\ \\ s.t.\sum _{n=1}^N({\alpha }_n^{\wedge }-{\alpha }_n^{\vee })\\ \\ 0\le {\alpha }_n^{\wedge }\le C,0\le {\alpha }_n^{\vee }\le C\end{array}$$

与QP的形式相似，可以用相似的求解器来求解。

SVR解的稀疏性解释：
根据KKT条件，有如下关系：

$$\begin{array}{l}w=\sum _{n=1}^N(\underset{{\beta }_n}{\underbrace{{\alpha }_n^{\wedge }-{\alpha }_n^{\vee }}})z_n\\ \mathrm{c}\mathrm{o}\mathrm{m}\mathrm{p}\mathrm{l}\mathrm{e}\mathrm{m}\mathrm{e}\mathrm{n}\mathrm{t}\mathrm{a}\mathrm{r}\mathrm{y}\mathrm{s}\mathrm{l}\mathrm{a}\mathrm{c}\mathrm{k}\mathrm{n}\mathrm{e}\mathrm{s}\mathrm{s}:\begin{array}{c}{\alpha }_n^{\wedge }(\epsilon +{\xi }_n^{\wedge }-y_n+w^T{z}_n+b)=0\\ {\alpha }_n^{\vee }(\epsilon +{\xi }_n^{\vee }+y_n-w^T{z}_n-b)=0\end{array}\end{array}$$
而根据tube regression，把数据点分为两部分，即

• 在tube之内的点，有，

$\begin{array}{l}\left|w^T{z}_n+b-y_n\right|<\epsilon \\ \\ \Rightarrow {\xi }_n^{\wedge }=0,{\xi }_n^{\vee }=0\\ \\ \Rightarrow (\epsilon +{\xi }_n^{\wedge }-y_n+w^T{z}_n+b)̸=0,(\epsilon +{\xi }_n^{\vee }+y_n-w^T{z}_n-b)̸=0\\ \\ \Rightarrow {\alpha }_n^{\wedge }=0,{\alpha }_n^{\vee }=0\\ \\ \Rightarrow {\beta }_n=0\end{array}$

• 在tube之外的点，即SVs，则${\beta }_n̸=0$

所以，SVR可以有一个稀疏解$\beta$。