支持向量机的通俗原理 Common Principles for SVM

本文的主要目的是为了配合另一篇文章“我的Libsvm最佳实践”的内容。

支持向量机(support vector machine, SVM)在我看来,是一种原理相当简单,但实现过程相当复杂的模型。台湾大学的林轩田老师在机器学习技法课程中对SVM的原理做了完整细致的说明,十分推荐,不过要完全理解也有一定的难度。本文只关注SVM原理中简单通俗的部分,目的是为了讲清楚两个重要参数(C和gamma),以便在Libsvm中进行调参。本文的许多图示直接来自林老师的课件。

SVM的核心思想无非两点:1)大边缘(margin);2)核函数(kernel)。

大边缘

首先看大边缘。以二元分类问题为例,大边缘是指找到一条最佳直线,在正确区分两种结果的同时,使各数据点到直线的距离的最小值(即边缘)取得最大,下图中,最右边的直线的边缘最大。边缘越大,给数据点留的误差空间就越大,越不容易过拟合。

大边缘的思想就反映在SVM的数学表达式中:

将约束条件(s.t.)的不等式两边同时除以||w||,即wTw,则左边变为yn(wTxn+b)/(wTw),这样的形式就是样本点xn到分类线y=wTx+b的距离;右则变为1/(wTw),是该距离的下限。现在,既然所有的样本点的距离都以1/(wTw)为下限,那么1/(wTw)就可是margin的大小,我们要最大化margin,就相当于最小化它的倒数——wTw,除以2在最小化中不受影响,而且反映了图中“分类线在中间、margin在左右两边(因此是最大化2倍margin,相应地在最小化中除以2)”的感觉。因此,以后就记住对wTw/2的最小化,就是对margin的最大化。

然而,上面的推导是以所有数据点都被正确分类为前提的。实际中,有可能数据点并不是线性可分的,也有可能存在异常数据点,为了追求对该异常的正确分类,会使margin受到很大的影响,容易过拟合。左下图中,分类直线虽不能保证全部分类正确,但看上去是靠谱的;而右下图中,在经过了4次多项式特征变换以后,分类曲线虽然保证全部分类正确,但显然是过拟合了,得不偿失。

因此,实际中需要采用“软间隔”,即允许有的数据点到分类直线的距离小于margin,但是要对这种违反做出惩罚,如下图所示。可以看到,公式中约束条件(s.t.)不等式的右边由“1”变成了“1-ξn”,多出来的ξn就是违反的程度——允许数据点n到分类直线的距离不足margin的程度,也就是右下图中,位于绿色margin带中的蓝点的violation。而公式的最小化目标中,除了之前的wTw/2是针对margin的以外,还收集了所有数据点的违反情况,求和,并做出惩罚,惩罚的程度以参数C表示。这个C参数是在Libsvm中需要调节的第一个关键参数。

到这里就说完了大边缘的问题,下面再来看核函数。

核函数

SVM当然不会局限于原始的特值x,而是会做特征变换(feature transformation),因此如果注意看上图中的公式,里面用的不是xn,而是zn——变换后的新特征。例如我们有两个特征a, b,那么二次多项式变换后,就有了z1=a, z2=b, z3=a2, z4=b2, z5=ab,从二维空间变换到了z的五维空间。这就跟多项式曲线拟合一样,变换得越复杂,拟合能力越强,但过拟合的风险越大。什么叫核函数呢?在SVM的求解中,会把原始问题转换成一个对偶问题,在这个问题中,将会有大量的内积计算——计算两个样本x(1)和x(2)之间的内积。现在既然把x变换成了z,那么相应地是计算z(1)和z(2)之间的内积。可问题是,随着z的维度的增加(这是显然的),z的内积运算的复杂度将快速膨胀。为了解释这一问题,核函数可以将z内积运算表示为x的内积运算——x的维度小,易实现,从而极大减轻运算负担,这就是kernel trick。

SVM中最牛的一种核函数是高斯核,理论上可以证明,它把原来的x变换为无限维的z(即x的一次、二次、三次、……无限次多项式)。显然,像上面所说的先地将x转换为z,再用z的运算的straightforward的方法是行不通的,必须利用核函数。对于两个样本的原始特征向量x1和x2,它们变换后的无限维特征z1和z2的内积表示为高斯核函数(K)的形式如下:

现在又有了一个参数γ,即gamma,它是Libsvm中又一个要调整的重要参数。好吧,其实一般情况下,也就有两个参数要调——C和gamma。

高斯核函数还可以这样理解:样本x1的目标值y1已知,而样本x2的目标值y2未知。x1基于自己的y1为x2的预测任务提供建议,建议被采纳的权重随着它们之间的距离(||x1-x2||2)的增大而衰减,而衰减的程度由参数gamma控制。gamma越大,高斯函数越瘦,衰减得越快,越像左下图,预测会更加拘泥于局部信息,好处是很精细,坏处是容易过拟合;gamma越小,高斯函数越胖,衰减得越慢,越像右下图,预测考虑的信息会更加全局化,好处是更稳健,不易受局部误差的影响,坏处是可能不够精细。

小结

在SVM中,我们主要需要调整两个参数——优化目标中的C和高斯核函数中的gamma。

C越大,则对违反margin的惩罚越大,则越多的点被正确分类,但代价是边界可能会扭曲,margin可能会变得很小,出现过拟合,如下图:

gamma越大,则高斯核函数利用的信息越局部,模型越“精细”,代价是所谓的精细可能只是在拟合误差,容易过拟合,如下图:

支持向量

最后简单解释一下什么是支持向量。SVM的关键是确定margin的边界,而从上面所有看得到margin的图中,我们都能注意到:margin是由特定的一些样本所确定的。这些样本就是support vector(SV),即支持向量。另一方面,上面所说的“软间隔”指出,我们允许一些样本会落在margin里面。所以准确地说,支持向量是所有在margin的边界上或者在margin里面的样本,前者是为free SV(下图中的方框),后者是为bounded SV(下图中的三角形)。除此之外的其他样本就是非支持向量,non-SV。Libsvm在完成训练完成后,会报告SV的数量(nSV),以及落在margin以内,发生margin违反的bounded SV的数量(nbSV)。

发表回复