首页 > 代码库 > 统计学习笔记之支持向量机

统计学习笔记之支持向量机

  支持向量机(SVM)是一种二分类模型,跟之前介绍的感知机有联系但也有区别。简单来讲,感知机仅仅是找到了一个平面分离正负类的点,意味着它是没有任何约束性质的,可以有无穷多个解,但是(线性可分)支持向量机和感知机的区别在于,支持向量机有一个约束条件,即利用间隔最大化求最优分离超平面,这时,支持向量机的解就是唯一存在的。

  首先来看线性可分的支持向量机,对于给定的数据集,需要学习得到的分离超平面为:

技术分享

以及对应的分类决策函数:

技术分享

  一般而言,一个点距离分离超平面的远近可以表示分类预测的确信程度。如果超平面确定,那么技术分享能够相对的表示点到超平面的距离,而技术分享技术分享的符号是否一致能表示分类是否正确。所以用技术分享来表示分类的正确性及确信度,这就是函数间隔。对于给定的数据集,需要寻找的是函数间隔的最小值,但是这仍然不够,假如成比例的改变技术分享技术分享,那么函数间隔也会随之改变,那么需要使技术分享,使得间隔确定,这时函数间隔变成了几何间隔。

  从而函数间隔和几何间隔有下面的关系:

技术分享

  那么要寻找一个超平面的问题首先是转化为求几何间隔最大的问题,然后由几何间隔和函数间隔的关系,可以改写为:

技术分享

技术分享

可以看出,技术分享的取值并不影响最优化问题的解,那么可以取技术分享。并且最大化技术分享和最小化技术分享是等价的,于是得到线性可分支持向量机的最优化问题:

 技术分享

技术分享

  在线性可分情况下,训练数据集的样本点中与分离超平面距离最近的样本点的实例称为支持向量,支持向量是使上面的约束条件取等号的点。为了求解上述问题,利用拉格朗日对偶性,通过求解对偶问题得到原始问题的最优解。首先,构建拉格朗日函数,对每一个不等式约束引进拉格朗日乘子技术分享,定义拉格朗日函数:

技术分享

根据拉格朗日对偶性,原始问题的对偶问题是极大极小问题:

技术分享

先求技术分享,可得:

技术分享

技术分享

带入拉格朗日函数,再求技术分享技术分享的极大,即是对偶问题:

技术分享

                                                                              技术分享

                                                                                     技术分享

将目标函数由极大转化为极小,就得到了下面与之等价的对偶函数的最优化问题:

技术分享

                                                                                技术分享

                                                                                       技术分享

   线性可分问题的支持向量机学习方法(硬间隔最大化),对线性不可分训练数据是不适用的,线性不可分意味着某些样本点不能满足函数间隔大于等于1的约束条件。为了解决这一问题,可以对每个样本点引进一个松弛变量技术分享,使函数间隔加上松弛变量大于等于1。这样,约束条件变为:

技术分享

同时,对每个松弛变量技术分享,支付一个代价技术分享。目标函数由原来的技术分享变成

技术分享

这里,技术分享称为惩罚函数,起到了调和误分类惩罚和间隔的关系,一般由应用问题决定。

  于是,线性不可分的线性支持向量机的学习问题变成如下凸二次规划问题(原始问题):

  技术分享  

技术分享

技术分享

同样的,利用拉格朗日的对偶性,可以求得上述原始问题的对偶问题:

技术分享

                                                                                技术分享

                                                                                        技术分享

解出技术分享之后,按照技术分享技术分享技术分享的关系,对其进行求解,既可得出超平面。

  上面介绍的两种方法都是解线性分类问题,但是,有时分类问题是非线性的,这时可以用非线性支持向量机,非线性支持向量机主要是利用核技巧,核技巧不仅应用于支持向量机还应用于其他的统计学问题。

  核技巧应用到支持向量机,其基本想法就是通过一个非线性变换将输入空间(欧式空间或者离散集合)对应于一个特征空间(希尔伯特空间),使得在输入空间中的超曲面模型对应于特征空间中的超平面模型,这样,便将非线性问题转化为了线性问题求解。常用的核函数有多项式核技术分享,高斯核技术分享等。

  对偶问题中的内积技术分享可以用技术分享表示,此时,非线性支持向量机的最优化问题可以表示为:

技术分享

                                                                              技术分享

                                                                                      技术分享

而为了解决上述问题,便需要SMO算法,其基本思路是:如果所有变量的解都满足此最优化问题的KKT条件,那么这个最优化问题的解就得到了。因为KKT条件是该最优化问题的充分必要条件。否则,选择两个变量,固定其他的变量,针对这两个变量构建一个二次规划问题。

  不失一般性,假设选择的两个变量是技术分享,其它变量是固定的。于是SMO的最优化问题的子问题可以写成:

技术分享

                                                        技术分享

                                                               技术分享

  为了求解两个变量的二次规划问题,首先分析约束条件,然后在此约束条件下求极小;由于只有两个变量,约束可以用二维空间的图形表示。假设上述问题的初始可行解为技术分享,最优解为技术分享,并且假设在沿着约束方向未经剪辑时技术分享的最优解为技术分享。并且技术分享的取值范围必须满足条件:

技术分享

如果技术分享,则

技术分享

如果技术分享,则

技术分享

  下面先求沿着约束方向未经剪辑时技术分享的最优解技术分享;然后再求剪辑后的技术分享的解技术分享。为了方便叙述,记:

技术分享

技术分享

技术分享时,技术分享为函数技术分享对输入技术分享的预测值与真实值技术分享之差。

  上述最优化问题沿着约束方向未经剪辑时的解是:

技术分享

 其中,

技术分享

经过剪辑之后的技术分享的解是:

技术分享

技术分享求得技术分享是:

技术分享

为了更加高效的选择两个变量使得目标函数下降最快,即SMO算法中启发式选择:

   SMO称选择第一个变量的过程为外层循环。外层循环在训练样本中选取违反KKT条件最严重的样本点,并将其对应的变量作为第一个变量,其中优先选择间隔边界上的支持向量的点,检验它们是否满足KKT条件;第二个过程为内层循环,即寻找第二个变量,标准是希望能使第二个变量有足够大的变化。

统计学习笔记之支持向量机