第一次接触SVM(支持向量机)还是四年前的事情了,那时用它做手写体数字识别,参考了一些书和文献,照着人家的步骤用Matlab敲出了PCA+SVM的代码,识别率一般,90都没上,不好意思跟人打招呼。最囧的是,后来参加一个面试,人家问我神马是支持向量,我都答不上来。上了研究生,在各种模式识别和机器学习相关的课上,反复学习了这一经典算法,每次都有新的体会。借此机会做一个总结。

  SVM是一种线性分类器。它针对的也是简单的有监督学习问题:给定m个样本(x(i), y(i)),y(i)=+/-1,确定一个线性分类面。这个问题可以用多种方法解决:感知器、Fisher线性判别分析、Logistic回归等。不同算法的实现和遵循的准则各不相同:感知器算法采用迭代的方法,对样本进行序贯处理,根据新来的样本调整线性分类面函数的系数,所有训练样本被正确划分即完成迭代;Fisher线性判别分析方法遵循的是类内离散度小、类间离散度大的准则,得到线性分类器;Logistic回归将y|x看作服从Bernoulli分布、取值为0或1的离散随机变量,通过最大化后验概率P(y|x)的办法来得到线性分类器。SVM遵循的准则是类间间隔(margin)最大,根据这个准则得到的分类面有以下的特点:属于不同类的、在分类面垂直方向投影距离最近的样本点的距离最小。设这个分类面的方程为:w'x+b=0,gamma为跟margin成正比的一个量,称为函数间隔(function margin),则我们优化的目标为max gamma。约束条件为: (1) y(i)[w'x(i)+b]>=gamma;(2) w模的归一化,即||w||=1。将约束条件改为:y(i)[w'/gamma*x(i)+b]>=1,用w代替w/gamma,则SVM的求解变为二次规划(QP)问题:min ||w|| ; s.t y(i)[w'x(i)+b]>=1。matlab里自带了求解QP问题的quadprog的命令可以求解这个问题。但一般工程实现中不这么干,一方面因为它的实现效率低,另外一方面,这种形式不利于将SVM推广到高维空间,即Kernel SVM。一般工程实现往往选择解决它的对偶问题(Dual Problem),如果一个优化问题满足KKT条件,那么(一般把它叫做原问题Primal Problem)就可以转化为求解它的对偶问题(Dual Problem)。对于上述线性SVM的原问题,它的对偶问题为:Max W(alpha) s.t alpha(i)>=0; y(1)*alpha(1)+y(2)*alpha(2).....+y(m)*alpha(m)=0。得到alpha(i)后,就可以通过w=alpha(1)*y(1)*x(1)+alpha(2)*y(2)*x(2).....+alpha(m)*y(m)*x(m)得到w。由于alpha(i)>=0,alpha(i)>0对应的x(i),满足y(i)[w'x(i)+b]=1,对w的产生做出了“贡献”,为支持向量;对于alpha(i)=0,y(i)[w'x(i)+b]>1,为非支持向量。

 

  上面介绍的SVM为样本线性可分前提下的线性SVM,在实际中的样本往往在线性欧式空间内不可分,解决这个问题的办法有两个:(1)将样本映射到高维空间,即Kernel SVM;(2)采用软间隔(Soft Margin)的SVM。在线性SVM的对偶问题中的目标函数和决策函数表达式中,都会出现内积项<x(i), x(j)>,Kernel SVM的主要思想是:用一个核函数K[x(i), x(j)]=<f[x(i)], f[x(j)]>代替<x(i), x(j)>,f[x(i)]为x(i)向高维空间的映射函数,由于对偶问题的求解中x(i), x(j)之间的所有运算都为内积运算,所以没有必要显示地求出f[x(i)],只要给出K[x(i), x(j)]即可,用得最多的是RBF和多项式核。软间隔SVM的基本思想是对于无法线性可分的情况,引入惩罚项sigma(i)和惩罚系数C。min (||w||^2)/2+C*(sigma(1)+sigma(2)+......sigma(m)); s.t y(i)[w'x(i)+b]>=1-sigma(i)。y(i)[w'x(i)+b]>=1-sigma(i)意味着可以容忍一定错分的情况;目标函数出现C*(sigma(1)+sigma(2)+......sigma(m))一项表明错分会带来惩罚,这样就避免了错分的样本过多,分类性能恶化。求解SVM对偶问题一般采用SMO方法,参考链接给出了具体的实现。

  参考链接:http://v.163.com/movie/2008/1/C/6/M6SGF6VB4_M6SGJVMC6.html

       http://v.163.com/movie/2008/1/9/3/M6SGF6VB4_M6SGJVA93.html

       http://blog.csdn.net/pennyliang/article/details/7103953