机器学习技法笔记 – Support Vector Regression (支撑向量回归)

Kernel Ridge Regression

在上一章中,我们将Kernel的思想运用于Logistic Regression,在本章,我们将介绍Kernel的思想在Ridge Regression与Support Vector Regression上的运用。

在上一章中,我们介绍了Representer Theorem(表示定理),这个定理指出,对于任何L2 Regularized的问题,其最佳的\( w_* = \sum_{n=1}^{N} \beta_{n}Z_{n}\),即任何最佳的\(w_*\)都可以表示为\(\beta_n\)与\(Z_n\)的线性组合,如下图:

如果原始问题带有L2 Regularized的正则项,且\(err(y_n, w^Tz_n) = (y_n-w^Tz_n)^2\),则该问题是一个Ridge Regression问题,如下图:

将\(w_*\)用\(\sum^{N}_{n=1}\beta_nZ_n\)表示并运用Kenel Trick后,原始问题具有以下形式:

用矩阵乘法的形式替代求和符号后,可以将原问题改写为以下形式:

上式即Kernel Ridge Regression的标准形式,之后求上式梯度,并令其梯度为\(0\),然后可以求得\(\beta\)的解析解:

其解析解具有以下形式:

其中,因为\(K\)是半正定的,所以,当\(\lambda > 0\)矩阵\((\lambda I+K)^{-1}\)的逆一定存在的。

对于Kernel Ridge Regression相比于Linear Ridge Regression,他们的解析解和复杂度总结如下:

易见,当Linear Ridge Regression的泛华能力有限,难以做比较复杂的数据拟合,而Kernel Ridge Regression由于使用了Kernel Function,具有更强的泛华能力,但是同时也带来了更高的计算复杂度。

Support Vector Regression Primal

接下来,我们将介绍Support Vector Regression(支撑向量回归),首先介绍它的原始问题。

在上文介绍的Kernel Ridge Regression的别名即Least-Squares Support Vector Machine(最小二乘支撑向量机),对比于Soft-Margin Support Vector Machine(软间隔支撑向量机),具有以下问题:

即LSSVM的解析解的\(\beta\)矩阵不是Sparse(稀疏)的,这会导致计算复杂度增加,我们希望\(\beta\)是Sparse的,而不是dense(稠密)的。

为解决这个问题,接下来我们介绍Tube Regression:

对于Regression问题,与Soft-Margin Support Vector Machine类似,Support Vector Regression同样容忍犯错,并记录犯错的程度,然后试图最小化犯错。

它的Error Measure函数如下:

之所以又叫Tube Regression,是因为在二维数据集上,这种Error Measure的方式划分了一个形似Tube(管道)的区域,这个Tube具有\(2\epsilon\)的高度,超平面容忍在\(2\epsilon\)内数据集,同时记录不在Tube中的数据集偏离Tube的距离,如下图:

Tube Regression与Squared Regression的的Error Measure曲线如下图所示:

可以看出,当\(\vert{s-y}\vert\)很小时,两者相近。

接下来,我们用Tube Regression与L2 Regularized项构造Support Vector Regression的原始问题:

与推导Soft-Margin Support Vector Machine的原始问题时相同,上式不是一个QP问题,不能用QP Solver求解,所以需要使用一个或者多个变量替代\(max(0, \vert{w^Tz_n-y}\vert-\epsilon)\)。

仿照Soft-Margin Support Vector Machine的思路,我们可以对上式进行如下改写:

我们通过引入\(\xi^∨_n\)和\(\xi^∧_n\),分别描述了给定数据在Tube上的偏离程度,将原始问题改写为一个QP问题,然后通过构造Lagrange Function,从而进一步通过求解其强对偶问题,然后使用QP Solver求解。

Support Vector Regression Dual

由于Support Vector Regression同样满足KKT条件,我们通过构造Lagrange Function:

然后对\(w, b\)求偏微分,结果如下:

 

最终,其强对偶问题具有以下形式:

之后可以便可以使用QP Solver求解。

然后考虑结合对偶松弛条件:

对于在Tube内,即\(\vert{w^Tz_n+b-y_n}\vert  < \epsilon\)的数据集,将有以下结论:

由于\(w=\sum^{N}_{n=1}(\alpha^∨_n-\alpha^∧_n)z_n\),由于对偶松弛条件,\(\xi^∨_n=0\)和\(\xi^∧_n=0\),所以\((\epsilon+\xi^∨_n-y_n+w^Tz_n+b)≠0\)且\((\epsilon+\xi^∧_n-y_n+w^Tz_n+b)≠0\),所以\(\alpha^∨_n=0\)且\(\alpha^∧_n=0\),所以\(\beta_n=0\)

这说明了\(\beta\)矩阵是可能是稀疏的。

Summary of Kernel Models

对于线性模型:

其中,第二行所展示的方法较为常用,在数据量较少,不需要强大的泛化能力时,可以尝试使用线性模型。

对于核模型:

其中,第二行较为常用,第三行由于\(\beta\)矩阵是dense的,在数据量较大时计算复杂度较高。

以上是对Kernel Support Vector Regression在台湾大学机器学习技法课程的笔记总结。

在下一篇文章中,将会讨论Blending and Bagging。