SVM(supportvectormachine )最早由Vladimir N.Vapnik和Alexey Ya.Chervonenkis于1963年提出, 现在的版本) soft margin )在Corinna Cortes和Vapnik深度学习(2012 )出现之前,SVM被认为是机器学习中近十几年来最成功的表现的算法。
举个例子:
图1
在一个平面上,里面有两种点。 怎么画直线很好地把两种点分开? 很明显,图中H1不能划分两种点,但H2和H3做到了。 在二维平面中可以用一条直线划分两种,但是扩展到n维的超平面怎么样?SVM的主要内容就是找一个n维超平面将n维的两类样例分开,当一个新的n维点输入时根据其在超平面的哪一侧将其归为那一类
如果用二维的情况进行分析,从上图可以看出,有无数条这样的直线。 SVM找到极限最大的东西后使用。 极限是什么呢? 介绍边距(margin )的概念。
图2图3
绘制分区边界,并计算两种示例中距离最近的点和边界之间的距离。 两者的距离之和是极限。 上图的第二张画法可以得到更大的边界线。 为什么要选择极限最大的超平面呢? 这是为了在输入新的测试点时,能够更准确地判断在超平面的哪一侧测试点属于什么类型的样品。
用于区分的超平面两侧通过最近的两点可以画出两个超平面,边界超平面位于距离两侧超平面距离相等的中间。 两侧的两个超平面平行。
在详细说明SVM如何构建极限最大的超平面mmh(maxmarginhyperplane )之前,介绍两种情况:线性可分辨和线性不可分辨。
图4、图5
前面几张图例都是比较完美的例子,可以用一条直线将两种样品分开,称为线性可区分,但是在图的情况下,不能直接用一条直线将两种样品分开,用http://www 后者更复杂,所以这里讨论一下可以用线性区别的情况。
关于超平面的公式可定义如下:
W*X b=0
其中x是n维训练样本
w为n维的权重W={W1,W2,W3,…,Wn}
b偏于bias
类似于二维直线的方程y=kx b。 这里只是扩展到了n维,点的坐标为(X1,X2,X3,…,Xn ),w与扩展到n维的斜率k相似。
在图3中,假设二维特征向量: x=(x1,x2 )超平面方程式如下。
W1*X1 W2*X2 b=0
所有超平面上的点都满足
W1*X1 W2*X2 b 0
所有超平面下的点都满足
W1*X1 W2*X2 b 0
将两种样品的线性不可区分分别用值1和-1、文字y表示,用H1和H2表示超平面两侧边缘的两个平行超平面,将两侧边缘线上的点代入结果=1和-1,即为H1、H2的外侧
H1: W1*X1 W2*X2 b=1,y= 1
H2: W1*X1 W2*X2 b=-1,y=-1
综合以上2式,可以得到
y*(w1*x1w2*x2b )=1 分类标记classlabel,即所有训练集中的点都满足此公式
SVM被称为支持向量机。 那么,什么是支持向量呢? 位于极限H1,H2超平面上的所有点或向量称为支持向量。 可以看到,支持向量至少是一边一个。 当然,只要在边界线上,有很多也没关系。
假设边界的超平面与H1,H2上的任意一点的距离=1/(||W||是向量的范数,则最大极限距离=2/(||W|| )
SVM如何找到最大极限的超平面(MMH )进行使用呢? 这个过程很复杂,需要从一系列的公式和定义中推导出来。 这里省略了过程,直接得出结论。
上式(1)成为有制约的凸最优化问题,利用KKT条件和拉格朗日式,可以导出MMH或"边界决定"
其中,l是向量维,Xi是支持向量点,XT是需要测试的实例,yi是支持向量Xi的分类标记,alpha I和b0是刚才一系列计算中得到的具体值。
通过此表达式,可以对实例进行分类。 如果需要测试某个实例,将其代入表达式,所得结果可按其正负分类,为正类,为负类。
一个例子是,我熟悉SVM的计算过程。
如图所示,已知训练集(2,3 )、(1,1 )、(2,0 )这3个点,(2,3 )为第1类,(1,1 )、(2,0 )为第2类,如何确定SVM
首先,可知支持向量为[ 2,3 ]和[ 1,1 ],向量w=[ 2,3 ]-[ 1,1 ]=[ a,2a]
从公式两侧极限线上的点W1*X1 W2*X2 b=1和-1开始,可以列出以下内容
2*a 3*2a b=1
1*a 1*2a b=-1
得到a=0.4,
b= - 2.2则向量W为(0.4, 0.8)
g(向量x) = 0.4*x1 + 0.8*x2 - 2.2
通过这个方程就可以对平面中的点进行判断,凡是第一类的点也就是是分界线上方的点坐标代入,结果必然大于0,第二类的点代入结果必然小于0。这样也就建立了SVM的方程。
另外我们可以看出SVM可以解决两类实例的分类问题,但一般问题中,样例的类别往往不止两类,这时候SVM是怎么处理的的呢?比如有10类的样例,怎么进行分类判断?只需要建立10个SVM方程就能得到结果。比如第一个是类别1,第二个是类别2到10的集合这样就能建立一个SVM方程,第一个是类别2,第二个是类别1和类别3到10的集合这样建立第二个SVM方程,以此类推。
最后总结一下SVM的特点:
1.训练好的模型的算法复杂度是由支持向量的个数决定的而不是由数据的维度决定的,所以SVM不太容易产生overfitting。
2.SVM训练出的模型完全依赖于支持向量,即便训练集里所有非支持向量全部除去,训练出的模型也完全一样。
3.一个SVM如果训练得出的支持向量个数较少,SVM训练出的模型比较容易被泛化。可以适用于更多的例子,而如果支持向量过多,那么可能支持针对这个例子区分的比较好,其它情况区分的并不是很好。
下一篇通过Python对SVM进行实践。