第一次接触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