支持向量机（SVM ）简明学习教程一、最优分类超平面给定训练数据),(,),,(11l l y x y x ，其中n i R x ∈，}1,1{-∈i y 。

若1=i y ，称i x 为第一类的，I ∈i x ；若1-=i y ，称i x 为第二类的，II ∈i x 。

若存在向量ϕ和常数b ，使得⎪⎩⎪⎨⎧II∈<-I∈>-i i T i i T x if b x x if b x ,0,0ϕϕ （1），则该训练集可被超平面0=-b x T ϕ分开。

（一）、平分最近点法求两个凸包集中的最近点d c ,'，做d c ,'的垂直平分面x ，即为所求。

02)(2222=---⇒-=-dc xd c x d xc T，则d c -=ϕ，2)()(d c d c b T +-=。

求d c ,，⎪⎩⎪⎨⎧≥==≥==∑∑∑∑-=-===.0,1,.0,1,1111i y iy i i i y iy i i i i i i x d x c αααααα所以2112∑∑-==-=-i i y iiy ii xx dc αα，只需求出最小的T l ),,(1ααα =。

算法：1）求解.0,1,1..2121min 1121211≥===-∑∑∑∑∑-===-==i y i y i li i i i y i i y i i i i i i t s x y x x αααααα；2）求最优超平面0=-b x T ϕ。

（二）、最大间隔法附加条件1=ϕ，加上（1）式。

记C x C i T x i >=I∈ϕϕmin )(1，C x C i T x i <=I I∈ϕϕmax )(2。

使⎪⎩⎪⎨⎧II∈<-I∈>-=-=i i Ti i Tx if b x x if b x t s C C ,0,0,1..2)()()(max 21ϕϕϕϕϕϕρ （2） 可以说明在（2）下可以得到一个最优超平面，且该超平面是唯一的。

如何快速生成一个最优超平面？？？ 考虑等价问题：求权向量w 和b ，使⎪⎩⎪⎨⎧II∈-<-I∈>-i i T i i T x if b x w x if b x w ,1,1，且ϕ最小。

这种写法已经包含最大间隔。

事实上b C C C x if C b x w x if C b x w i i T i i T=+=⇒⎪⎩⎪⎨⎧II∈=+-<I∈=+>))()((21),(1),(121021ϕϕϕϕ中心，而w w =ϕ，故w b C =，wC C 12)()()(21=-=ϕϕϕρ。

所以（2）式可以转化为求解：1)(..min≥-b x w y t s wi Ti （3）总结，求最优超平面，只需求解：1)(..21)(min ≥-=Φb x w y t s w w w i T i T （QP1）对（QP1）构造lagrange 函数：令∑=---=li i T i i b x w y w b w L 12]1)([21),,(αα，其中0),,(1≥=T l ααα 为lagrange 乘子。

下求L 的鞍点：1=i =i 1将2）代入L 中，且目标改为)(αW 。

则∑∑∑===+-=li i l i l j j Ti j i j i x x y y W 11121)(αααα所以，（QP1）的对偶问题为：,0..)(max =≥∑iiyt s W ααα （DQP1）由KKT 条件，0]1)([=--b x w y i T i i α。

若存在0*>j α时，有01)(=--b x w y j Tj ，此时，SV j ∈，则∑+-=+-=ij T i i i j j T j x x y y x w y b α*几何意义：i x ，SV i ∈是与超平面距离最近的向量，称其为支持向量。

他在构造超平面中起到及其重要的作用。

SVM 算法1（线性可分SVM 分类机） 1）、求解规划问题（DQP1）2）、求∑==li i i i x y w 1*α和∑+-=ij T i i i j x x y y b α*，得到分类超平面0**=-b x w T 。

3）、分类器：)()(**b x w sign x f T -=。

（三）、软间隔分类超平面针对样本数据线性不可分的情况。

此时02)()()(21<-=ϕϕϕρC C 。

解决方案：软化约束（通过添加松弛因子）。

i j T j b x w y ξ-≥-1)(，其中，0≥i ξ。

显然，当i ξ充分大时，软约束总是成立的，但i ξ不应该取太大。

所以将i ξ加入到目标中，得到(QP2)：.0,1)(..21)(min ≥-≥-+=Φ∑i i i T i ii Tb x w y t s C w w w ξξξ （QP2）其中，C 为正的惩罚参数。

显然，QP2包含了QP1的，（取∞→C ）。

另外，QP2的鲁棒性好（稳定性好） 同样，对（QP2）构造lagrange 函数：令∑∑∑----+==i i li i T i i i b x w y C w b w L ξβαξβαξ12]1)([21),,,,(。

1=i =i 13）、C C C L i i i i ≤-=≤⇒=--⇒=∇βαβαξ000。

代入L 中，得∑∑---+-)(212i i i i i i C w ξβξαξα。

所以，（QP2）的对偶问题为：0,0..21min 111=≥≥-∑∑∑∑===iili i l i l j j Ti j i j i yC t s x x y y ααααα （DQP2） 对于b ，由KKT 条件⎩⎨⎧=-=+--0)(0]1)([C b x w y i i i i T i i αξξα。

当0*>>j C α时，0=j ξ，则∑+-=+-=ij T i i i j j T j x x y y x w y b α*。

（四）、支持向量机对于本质线性不可分问题，有两种方法：（1）构造非线性分类器；（2）将样本点射到高维特征空间，再用线性分类器。

例1：)}1,3(),1,1(),1,1{(--=T 不可分映射：T x x x ),(2→，则)}1,93(),1,11(),1,11{(~⎪⎪⎭⎫ ⎝⎛-⎪⎪⎭⎫ ⎝⎛⎪⎪⎭⎫ ⎝⎛-=T 可分。

基本思想：Z x x x x T m ==→))(,),(()(1ϕϕϕ ，),(),(i i i i y Z y x → 例2：对于圆0)()(21222122221=++++⇒=-+-E Dx Cx Bx Ax r b x a x ，故Z x x x x x x x x T ==→=)1,,,,()(),(21222121ϕ。

但复杂性增大，如n R x ∈，则二次特征空间n n n N ++=2/)1(。

（问题：推广性如何评价，技术上如何处理高维数据？？？）1）、核函数设Z X Z →:，n R X x ⊂∈∀，N N T N R z z x Z x Z x Z ∈==),,())(,),(()(11 。

（注N 可为无穷）考虑在Hilbert 空间中内积的一个一般表达式：),()(i i x x K z z =•。

根据Hilbert-Schmidt 理论，),(i x x K 可以是满足下面一般条件的任意对称函数（Courant andHilbert,1953）定理（Mercer ）要保证2l 中的对称连续函数),(v u K 能以正的系数0>k a 展开成),()()(),(1v u K v u a v u K k k k k ⇔⋅⋅=∑∞=ϕϕ正定。

（⎰⎰>⋅⋅⇔0)()(),(v g u g v u K K 正定）2）支持向量机 训练样本)},(,),,{(11l l y x y x T =，Nn R x z R x ∈=→∈)(ϕ，则)}),((,),),({(~11l l y x y x T ϕϕ =。

求Z ~上的超平面将T ~分开（若可分），则最大间隔超平面： 1))((..21)(min ≥-=Φb x w y t s w w w i T i Tϕ （QP3）其对偶问题为：,0..),(21min 111=≥-∑∑∑∑===iili i l i lj j i j i j i yt s x x K y y ααααα （DQP3） 设（DQP3）有解*α，则∑==li i i i x y w 1**)(ϕα，∑+-=+-=ij i i i j j T j x x K y y x w y b ),()(*αϕ，（}0|{*>∈i i j α）。

从而，决策函数为))()(())(()(*1***b x x y sign b x w sign x f li T i i i T-=-=∑=ϕϕαϕ)),((*1*b x x K y sign li i i i -=∑=α。

算法（可分的SVM ）（1）、选样本)},(,),,{(11l l y x y x T =； （2）、选核函数，用Mercer 定理判断； （3）、计算*α，由（DQP3）； （4）、代入决策函数应用。

（错误率高可转（2）重来）同样，对特征映射后的样本点T ~线性可分难于判断，可引人松弛变量：.0,1)(..21)(min ≥-≥-+=Φ∑i i i T i ii Tb x w y t s C w w w ξξξ （QP4）其对偶问题为：0,0..),(21min 111=≥≥-∑∑∑∑===iili i l i lj j i j i j i yC t s x x K y y ααααα （DQP4） 则∑+-=+-=ij i i i j j T j x x K y y x w y b ),()(*αϕ，（}0|{*>>∈i C i j α）。

决策函数为)(x f )),((*1*b x x K y sign li i i i -=∑=α。

（存在问题：1、C 的选择；2、K 的选择？？？？）3）常用的核函数d 阶多项式核：d T y x y x K )1(),(+=；Gauss 核：}exp{)(),(2y x r y x K y x K r --=-=；))((),(c y x v S y x K T +=，其中)(u S 为Sigmoid 函数，但他不满足Mercer 定理。

二、估计实值函数的支持向量机 （一）、回归分析已知)},(,),,{(11l l y x y x T =，R y R x i n i ∈∈,，最小二乘：εα+=),(x f y ，),0(2σεN ∈。

其定义损失函数为：2)),(()),(,(ααx f y x f y L -=，使得经验风险最小：∑-ii ix f y2)),((minα。