博客

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

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

SVM的核心思想无非两点：1）大边缘（margin）；2）核函数（kernel）。

大边缘

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

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

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

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

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

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

核函数

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

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

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

高斯核函数还可以这样理解：样本x₁的目标值y₁已知，而样本x₂的目标值y₂未知。x₁基于自己的y₁为x₂的预测任务提供建议，建议被采纳的权重随着它们之间的距离（||x₁-x₂||²）的增大而衰减，而衰减的程度由参数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）。