-
原文
-
SVM是一种线性分类器（Linear Classification）
-
针对有监督的学习问题：给m个样本，记作(x(i), y(i)), 其中y(i)=1/-1，确定一个线性分类面。
-
除SVM之外的解决方法：感知机、Fisher线性判别分析、Logistic回归……
-
感知器算法采用迭代的方法，对样本进行序贯处理，根据新来的样本调整线性分类面函数的系数，所有训练样本被正确划分即完成迭代
-
Fisher线性判别分析方法遵循的是类内离散度小、类间离散度大的准则，得到线性分类器
-
Logistic回归将y|x看作服从Bernoulli分布、取值为0或1的离散随机变量，通过最大化后验概率P(y|x)的办法来得到线性分类器
-
线性可分SVM详解：
-
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，有两种解决方法：
-
将样本映射到高维空间，即Kernel 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和多项式核
-
采用软间隔(Soft Margin)的SVM
-
软间隔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方法，参考链接给出了具体的实现
Page created on 2020-12-06