[西瓜书]学习笔记三:支持向量机

支持向量机:名字高大上,数学推导也很复杂,也很好用

支持向量

支持向量机是一种经典的二分类模型,基本模型定义为特征空间中最大间隔的线性分类器,其学习的优化目标便是间隔最大化,因此支持向量机本身可以转化为一个凸二次规划求解的问题。

超平面

分类的基本思想就是基于训练集D找到一个划分的超平面,将不同类别的样本划分开。对于二分类学习,假设现在的数据是线性可分的,类似二维平面使用ax+by+c=0来表示,超平面实际上表示的就是高维的平面,如下图所示:

超平面的划分直观上来看,应该是找到两类当中训练样本“正中间”的划分超平面,这个平面应当对局部样本扰动对容忍性最好。如下图中加粗线。

在样本空间中,超平面可用如下线性方程表示:

其中为法向量,决定超平面的方向,b为位移项,决定超平面和原点之间的距离。因此可以得出,空间中任意点x到超平面的距离为:

间隔

函数间隔

假设在超平面确定的情况下,能够正确分类超平面。当式大于1时,被划分为正类,反之为负类。正好能表明数据分类的正确性,于是便引出了函数间隔的定义(functional margin):

而超平面(w,b)关于所有样本点的函数间隔最小值则为超平面在训练数据集T上的函数间隔:

可以看出:这样定义的函数间隔在处理SVM上会有问题,当超平面的两个参数w和b同比例改变时,函数间隔也会跟着改变,但是实际上超平面还是原来的超平面,并没有变化。例如:w1x1+w2x2+w3x3+b=0其实等价于2w1x1+2w2x2+2w3x3+2b=0,但计算的函数间隔却翻了一倍。从而引出了能真正度量点到超平面距离的概念—几何间隔(geometrical margin)。

几何间隔

几何间隔代表的则是数据点到超平面的真实距离,对于超平面w’x+b=0,w代表的是该超平面的法向量,设x为超平面外一点x在法向量w方向上的投影点,x与超平面的距离为r,则有,又x在超平面上,即w’x+b=0,代入即可得:

为了得到r的绝对值,令r呈上其对应的类别y,即可得到几何间隔的定义:

从上述函数间隔与几何间隔的定义可以看出:实质上函数间隔就是,而几何间隔就是点到超平面的距离。

最大间隔与支持向量

由前面的分析可知:函数间隔不适合用来最大化间隔,因此这里我们要找的最大间隔指的是几何间隔,于是最大间隔分类器的目标函数定义为:

两个异类支持向量到超平面到距离之和为:

如下图所示:

这里到几个最近到点被称为支持向量,需要找到最大间隔来划分超平面,即找到参数(w,b)使得最大,重写式

以上被称为支持向量机(support vector machine,SVM)的基本型。

对偶问题

模型本身是一个凸二次规划问题,可以用现成到计算包进行求解。由于SVM的特殊性,一般我们将原问题变换为它的对偶问题,接着再对其对偶问题进行求解。为什么通过对偶问题进行求解,有下面两个原因:

  • 一是因为使用对偶问题更容易求解;
  • 二是因为通过对偶问题求解出现了向量内积的形式,从而能更加自然地引出核函数。

对偶问题,顾名思义,可以理解成优化等价的问题,更一般地,是将一个原始目标函数的最小化转化为它的对偶函数最大化的问题。对于当前的优化问题,首先我们写出它的拉格朗日函数:

对其和b求偏导得:

将上两式代入拉格朗日函数(南瓜书中有详细推导),得到基本型到对偶问题

此问题需要满足KKT条件(这里不深究),这样就将原问题的求最小变成了对偶问题求最大(用对偶这个词还是很形象),接下来便可以先求L对w和b的极小,再求L对α的极大。

α极大值是通过SMO算法进行求解,其基本思路是先固定α之外所有参数,然后求α到极值。因为式子存在约束,若α之外其他所有变量都被固定,则α可被其他变量导出。

最后根据所求α可计算出对应和b,得到分类超平面函数。在对新的点进行预测时,实际上就是将数据点x*代入分类函数f(x)=w’x+b中,若f(x)>0,则为正类,f(x)<0,则为负类,根据前面推导得出的w与b,分类函数如下所示,此时便出现了上面所提到的内积形式。

核函数

对于线性不可分问题(异或问题),这里利用核函数进行推广。一般地,解决线性不可分问题时,常常采用映射的方式,将低维原始空间映射到高维特征空间,使得数据集在高维空间中变得线性可分,从而再使用线性学习器分类。如果原始空间为有限维,即属性数有限,那么总是存在一个高维特征空间使得样本线性可分。

于是在特征空间中划分超平面的模型如下表示:

相应的解法如上节,列出新的拉格朗日函数,写出其对偶问题,求得w和b相应极大值,再利用SMO算法求解。方式如下:

对偶问题:

分类函数:

求解的过程中,涉及到了高维特征空间中的内积运算,由于特征空间的维数可能会非常大,例如:若原始空间为二维,映射后的特征空间为5维,若原始空间为三维,映射后的特征空间将是19维,之后甚至可能出现无穷维,根本无法进行内积运算了,此时便引出了核函数(Kernel)的概念。

可以设想这样一个函数:

这个函数可以直接计算隐式映射到高维特征空间后的向量内积,而不需要显式地写出映射后的结果,它虽然完成了将特征从低维到高维的转换,但最终却是在低维空间中完成向量内积计算,与高维特征空间中的计算等效(低维计算,高维表现),从而避免了直接在高维空间无法计算的问题。这就是核函数,这种方法被称为核方法。

在引入核函数后,原式变为:

对偶问题:

分类函数:

因此挑选合适的核函数成为了svm的最大问题,但是有一系列定理来限制核函数的选取。

对于输入数据而言,其核矩阵K

总是半正定的。换句话说,任何一个核函数都隐式的定义了一个称为“再生核希尔伯特空间”的特征空间(这里真的是没懂,统计学习方法那本书有讲)。

这里列举了一些常用的核函数。

同时,通过核函数的线性组合也能得到新的核函数。

软间隔和正则化

软间隔

我们之前都假定训练集在样本空间中是线性可分的,但是这在实际情况中是很难的,数据总是存在噪声(异常值)。噪声数据(outlier)本身就偏离了正常位置,但是在前面的SVM模型中,我们要求所有的样本数据都必须满足约束,如果不要这些噪声数据还好,当加入这些outlier后导致划分超平面被挤歪了,如下图所示,对支持向量机的泛化性能造成很大的影响。

因此,需要一个可以去除噪声数据的方法,需要允许某一些数据点不满足约束,即可以在一定程度上偏移超平面,同时使得不满足约束的数据点尽可能少。这便引出了软间隔的概念。

  • 允许某些数据点不满足约束y(w’x+b)≥1;
  • 同时又使得不满足约束的样本尽可能少。

于是优化目标改写为:

显然控制C值可以控制样本的不满足约束程度。当C为无穷大时,所有样本满足约束,C值越大可接受越多的样本不满足约束。

如同阶跃函数,0/1损失函数虽然表示效果最好,但是数学性质不佳。因此常用其它函数作为“替代损失函数”。

这里我们带入hinge损失进行推导。

引入松弛变量,目标函数与约束条件可以写为:

其中C为一个参数,控制着目标函数与新引入正则项之间的权重,这样显然每个样本数据都有一个对应的松弛变量,用以表示该样本不满足约束的程度,将新的目标函数转化为拉格朗日函数得到:

继续按照与之前相同的方法,先让L求关于w,b以及松弛变量的极小,再使用SMO求出α,有:

将w代入L化简,便得到其对偶问题:

与前式对比看来,两者的差别在于对偶变量的约束不同,同样的可以引入核方法进行展开。

正则化

如果把对率损失函数作为核函数代替0/1函数,几乎能得到对率回归模型。更深入的说,这些模型的性质与所替代的函数直接相关,但他们具有一定的共性:优化目标中的第一项来描述超平面划分的间隔的大小,第二项来表示训练集当中所存在的误差。一般的形式如下:

其中称为结构风险,用于描述模型f某些性质;第二项称为经验风险,用于描述模型和训练数据的契合度。C值用于将前两者进行折中。上式因此被称为“正则化”问题。

支持向量回归

现在我们来考虑回归问题。

对样本(x,y)而言,传统回归模型通常基于模型输出f(x)值与真实值y之间的差值作为损失值,当且仅当f(x)=y时损失才为0。支持向量回归(Support Vector Regression,SVR)假设f(x)与y之间能容忍的最大偏差,当损失大于才开始计算损失值。

如下图所示,以f(x)为中心建立了一个宽度为的间隔带。

因此将SVR形式化为

解法和以上的解放完全相同。引入拉格朗日乘子,构造拉格朗日函数;求偏导;求对偶问题;满足KKT条件;带入化简可得:

引入核方法,可得:

总结

以上就是支持向量机的总结,SVM的确是十分好用的算法,分类和回归都是对它而言可用的。其中的公式推导的确很复杂,但是基本流程都是一样的,拉格朗日->偏导->回带->对偶问题。

西瓜书当中关于SVM的部分还有好多没有理解透彻的点,希望将来再读的时候能有更多收获。