机器学习技法笔记 – Soft-Margin Support Vector Machine (软间隔支撑向量机)

Motivation and Primal Problem

在上一章中,我们介绍了Kernel Support Vector Machine,通过使用不同的Kernel Function及其不同的\(\zeta, \gamma\),既可以做到高维或者无限维的特征转换,同时简化了\(Q\)矩阵的计算复杂度,但这不是没有代价的,以RBF Kernel为例,如果\(\gamma\)选取的不恰当,很容易造成过拟合。

同时,如果数据集本身含有噪声较多,这时如果我们仍然坚持使用强大Kernel Function使得数据满足硬间隔来使之线性可分,这时也会造成过拟合。

在本章,我们将介绍一种权衡的方法,这种方法将在间隔与噪声之前做一个权衡,即容忍一部分数据集的噪声来避免过强的特征转换造成的过拟合。

我们既希望数据集具有Large-Margin,也希望容忍一部分分类错误的发生,所以我们可以将Hard-Margin Support Vector Machine的Primal Problem改写为以下形式:

通过引入参数\(C\),并使\(C\)乘以分类器在数据集上犯错的次数,直观的看,较大的\(C\)放大了犯错的惩罚效应,希望犯错越少越好,而较小的\(C\)认为缩小了犯错的惩罚效应,具体\(C\)是如何影响原始的最佳化问题的,我们将在下面的推导中说明。

但是“分类器在数据集上犯错的次数”这件事是一个Boolean运算,这不是一个线性的运算,这会使得改写后的最佳化问题不是一个QP问题,这里,我们通过引入\(\xi_n\)来代替“分类器在数据集上犯错的次数”,\(\xi_n\)描述了分类器在数据集上犯错的程度,即犯错数据距间隔的距离:

这样的代替使得原问题成为一个QP问题,改写后的问题具有如下形式:

Dual Problem

为了求解改写后的最佳化问题,我们选择第二章用过的方法,通过写出原最佳化问题的Lagrange Function,然后通过求解其强对偶问题,再通过KKT条件求解出\(w, b\),新的Lagrange Fcuntion具有以下形式:

求解其强对偶问题:

先对\(\xi_n\)求偏微分:

所以,\(\beta_n\)可以用\(\alpha_n\)表示:

$\(\beta_n=C-\alpha_n\)$

又因为\(\alpha>0, \beta>0\),所以\(0≤\alpha_n≤C\),所以原Lagrange Function可以改写为以下形式:

可以发现原Lagrange Function的条件约束全部被隐含在了条件中,之后和第二章一样分别对\(b, w\)求偏微分,就可以用\(\alpha_n\)来表示\(b, w\):

在Soft-Margin中,通过KKT的互不松弛条件\(b\)的计算方法与Hard-Margin有相似和不同:

最后\(b\)可以以如下形式表示:

最后写出原Lagrange Function的QP标准形式,通过QP Solver写出最佳化的\(\alpha\):

该QP问题具有\(N\)个变量,\(2N+1\)个条件。

这即是Soft-Margin Support Vector Machine了。

Messages behind Soft-Margin Support Vector Machine

下图是不同的参数\(C\)对分类器的影响的效果:

可以看出,对于较大的\(C\),有着更少的错误容忍度,但是也会出现过拟合的问题,所以我们仍然需要谨慎选择\(\gamma, C\)来避免过拟合。

接下来我们来讨论\(\alpha\)的物理意义以及\(C\)是如何影响分类器的形状的。

我们先观察对偶松弛条件:

根据不同满足对偶松弛条件对应的\(\alpha_n, \xi_n, C\)的取值,将有以下三种情况:

  1. 如果\(\xi_n=0\),\(\alpha_n=0\),这对应着那些没有犯错误的数据点
  2. 如果\(\xi_n=0\),\(0<\alpha<C\),这对应着那些刚好落在间隔上的点
  3. 如果\(\alpha_n=C\),这对应着那些落在间隔内的犯错误的点

可以看到对应2,3这两种情况,\(\alpha_n\)的上界是\(C\)的取值,而\(\alpha_n\)最终将计算出\(b, w\),这决定了间隔的大小,所以,较大的C会使得间隔越大。

这同样也是Soft-Margin Support Vector Machine中,Soft-Margin的意义。

Model Selection

下图是使用RBF Kernel通过不同的\(\gamma, C\)的取值对分类器形状的影响:

下图是采用交叉验证(Cross Validation)的\(E_{cv}\)值在各个分类器的表现:

所以,有时候\(\gamma, C\)的取值还是得具体问题具体分析。

当我们在用留一法(Leave-One-Out)在SVM上做验证时,有几点有趣的事实,我们很容易发现那些非支持向量对分类器的间隔是没有影响的,所以我们可以通过支持向量的数据来估计误差:

由于这种方法计算复杂度较低,我们通常使用这种方法快速排除一些不好的参数,但是通过这种方法选择的参数,也不一定是最好的,也需要具体问题具体分析。

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

在下一篇文章中,将会讨论Kernel Logistic Regression。

2 thoughts on “机器学习技法笔记 – Soft-Margin Support Vector Machine (软间隔支撑向量机)”

评论已关闭。