SVM原理简介
- 格式:pdf
- 大小:175.93 KB
- 文档页数:3
SVM原理简介
SVM是我在做模式识别的时候⽤得最多的⼀种分类器。以下是我通过学习后对SVM原理的理解与总结,记录下来以便⾃⼰复习。
1、SVM原理概述
SVM是从线性可分情况下的最优分类⾯发展⽽来的,图⼀中三⾓形点和圆形点分别代表两类样本,假设:
,i=1,...,n,
我们要寻找⼀个分类超平⾯H:,使得:
假设 分别为过各类中离分类超平⾯最近的样本并且平⾏于分类超平⾯的超平⾯,它们之间的距离叫做分类间隔。最优分类超平⾯要求不但能把两类样本正确分开,⽽且要求分类间隔最⼤。易知分类间隔为2/||W||,使分类间隔最⼤,等价于与使||W||最⼩。所以求最优分类超平⾯求解下例问题:
H1,H2上的训练样本点就称作⽀持向量。
图⼀
利⽤Lagrange优化⽅法可以把上述最优分类⾯问题转化为其对偶问题:
其中αi为与每个样本对应的Lagrange乘⼦,容易证明解中有⼀部分(通常是少部分),若αi不为零,对应的样本就是⽀持向量。解上述问题后得到的最优分类函数是:在线性不可分的情况下,可以增加⼀个松弛项,使求解最优分类超平⾯变为下述问题:
即折衷考虑最少分错样本与最⼤分类间隔,得到⼴义最优分类超平⾯,其中C为惩罚系数。对应的对偶问题变为:
对于⾮线性问题,可以通过⾮线性变换转化为某个⾼维空间中的线性问题,在变换空间求解最优分类⾯。
在最优分类⾯中采⽤适当的内积函数K(xi,xj)就可以实现某⼀⾮线性变换后的线性分类:
分类函数变为:
这就是⽀持向量机。
总结起来,SVM的基本思想如图⼆所⽰:
图⼆
2、核函数
⽬前研究最多的核函数主要有四类:
通常来讲,RBF核函数可以作为⼀个SVM模型的最佳选择。RBF核通过⾮线性映射将样本映射到⼀个⾼维空间中,因此,相较于线性核函数,它能很好地处理类别标签与属性之间为⾮线性关系的情况。⽽且,线性核可以看做RBF核的⼀种特殊情况,在某些参数下,线性核具有与RBF核相同的表现。另外,研究显⽰sigmoid核在某些参数下也与RBF核具有相同表现。选择RBF核的第⼆个理由是超参数的数量影响着模型选择的复杂性,多项式核的超参数⽐RBF核更多,因此复杂性也会相应提⾼。最后,RBF核在数值计算上难度较⼩。这些都使得RBF核在SVM中有着更好的表现。然⽽,并⾮所有情况下RBF核都是最适合的。特别地,当特征维数⾮常⼤时,我们可以考虑线性核数。
3、多类分类SVM
(1)⼀对⼀组合分类 :
设共有k个类,各类之间两两构造分类函数(共k(k-1)/2个)。预测样本经过每个分类器投票,判定为得票数最多的类。但是如果k过⼤,k(k-1)/2会⾮常庞⼤,使预测过程变慢。libsvm使⽤的就是这种策略。
(2)⼀对余组合分类
设共有k个类,每⼀类和余类之间构造分类函数(共k个),取分类函数输出值最⼤的类别为预测类别。这种⽅法推⼴能⼒⽐较差,训练时间很长,效率⽐较低,存在决策盲区。
还有其他的多类分类法,如决策树。
4、SVM的概率输出
在分类模型中,P(y|x)是在样本为X的条件下标签为y的概率也就是样本的后验概率。我们知道 ,SVM并不是概率模型 ,⽆法直接输出样本的后验概率。可以使⽤sigmoid函数估计样本Xi标签为的后验概率:
其中,A、B是估计值,是SVM的决策函数值。
在多类分类问题中,可以使⽤⼀对⼀的策略,构造k(k-1)/2个⼆类SVM,设之间的⼆类SVM的后验概率为,则对于⼀个样本xi,标签为的概率可⽤下式计算:
参考⽂献:[1]Hsu C W, Chang C C, Lin C J. A Practical Guide to Support Vector Classication[J]. 臺北市:國⽴臺灣⼤學資訊⼯程學系, 2003, 67(5).
[2]Platt J C. Probabilistic Outputs for Support Vector Machines and Comparisons to Regularized Likelihood Methods[J]. Advances in LargeMargin Classifiers, 2000, 10:61--74.