SVM支持向量机及SMO算法总结

之所以写这篇文章，主要是因为SVM和SMO的算法看了很多遍才看懂，现在网络上也有很多相关的资料，这篇文章主要是记录自己的学习过程，集中在后面的证明求解过程。初学者建议先看底下的参考资料，把相关概念弄清楚了之后，如果在看论文过程中有疑惑的，可以过来看没看有没有参考的地方。

首先对于SVM（support vector machine）的理解为：寻找一个超分类平面，把不同分类的数据分隔开，且两边的最小间距最大。

函数间距与几何间距：

在Andrew Ng的材料中，涉及到两个间距的概念：函数间距与几何间距。

函数间距的定义：γ^(i)=y(i)(wTx+b)${\hat{\gamma }}^{(i)}=y^{(i)}(w^{T}x+b)$, 当w$w$和b$b$成比例变化，函数间距也成比例变化

几何间距的定义：γ(i)=y(i)(wTx+b)||w||${\gamma }^{(i)}=\frac{y^{(i)}(w^{T}x+b)}{||w||}$, 当w$w$和b$b$成比例变化，几何间距不变

最大化间距

SVM目标是最大化最小几何间距，故有：

最小几何间距： γ=mini=1,..,mγ(i)$\gamma =\underset{i=1,..,m}{min}{\gamma }^{(i)}$

maxγ,w,b     γ$\underset{\gamma ,w,b}{max}\gamma$

s.t.        y(i)(wTx+b)≥γ,i=1,...,m$s.t.y^{(i)}(w^{T}x+b)\ge \gamma ,i=1,...,m$

               ||w||=1$||w||=1$

第一个限制条件保证所有例子的函数间距大于我们的最小几何间距γ$\gamma$， ||w||=1$||w||=1$保证了函数间距和几何间距等价。

由于该式子比较难求解，故我们可以考虑转换一下上式为：

maxγ,w,b    γ^||w||$\underset{\gamma ,w,b}{max}\frac{\hat{\gamma }}{||w||}$

s.t.        y(i)(wTx+b)≥γ^,i=1,...,m$s.t.y^{(i)}(w^{T}x+b)\ge \hat{\gamma },i=1,...,m$

考虑到函数间距与w$w$和b$b$成比例变化，故成比例变化w$w$和b$b$不影响该最大式子，故可以考虑令γ^=1$\hat{\gamma }=1$

原式可变为：

maxw,b     1||w||$\underset{w,b}{max}\frac{1}{||w||}$

s.t.        y(i)(wTx+b)≥1,i=1,...,m$s.t.y^{(i)}(w^{T}x+b)\ge 1,i=1,...,m$

最后该式子等价为：

minw,b     12||w||2$\underset{w,b}{min}\frac{1}{2}||w|{|}^2$

s.t.        y(i)(wTx+b)≥1,i=1,...,m$s.t.y^{(i)}(w^{T}x+b)\ge 1,i=1,...,m$

拉格朗日对偶

上面已经列出了我们需要求解w$w$和b$b$的式子，但是由于涉及到限制条件，很难直接求解。这时候就需要我们的朗格朗日乘子和朗格朗日对偶问题的知识了。

对于一般式子：

minw   f(w)$mi{n}_{w}f(w)$

s.t.   gi(w)≤0,i=1,...,k$s.t.g_i(w)\le 0,i=1,...,k$

          hi(w)=0,i=1,...,k$h_i(w)=0,i=1,...,k$

令L(w,α,β)=f(w)+∑i=1kαigi(w)+∑i=1lβihi(w)$\mathcal{L}(w,\alpha ,\beta )=f(w)+\sum _{i=1}^k{\alpha }_i{g}_i(w)+\sum _{i=1}^l{\beta }_i{h}_i(w)$, 该式子称为拉格朗日函数

在满足原式子的限制条件下有：maxα,β:α≥0L(w,α,β)=f(w)$\underset{\alpha ,\beta :\alpha \ge 0}{max}\mathcal{L}(w,\alpha ,\beta )=f(w)$

又有以下对偶式子：

maxα,β:α≥0minwL(w,α,β)≤minwmaxα,β:α≥0L(w,α,β)=minwf(w)$\underset{\alpha ,\beta :\alpha \ge 0}{max}\underset{w}{min}\mathcal{L}(w,\alpha ,\beta )\le \underset{w}{min}\underset{\alpha ,\beta :\alpha \ge 0}{max}\mathcal{L}(w,\alpha ,\beta )=\underset{w}{min}f(w)$

当满足一定条件下时， 我们有该等式成立。该条件称为KKT:

∂∂wiL(w,α,β)=0,i=1,...,n$\frac{\mathrm{\partial }}{\mathrm{\partial }{w}_i}\mathcal{L}(w,\alpha ,\beta )=0,i=1,...,n$

∂∂βiL(w,α,β)=0,i=1,...,l$\frac{\mathrm{\partial }}{\mathrm{\partial }{\beta }_i}\mathcal{L}(w,\alpha ,\beta )=0,i=1,...,l$

αigi(w)=0,i=1,...k${\alpha }_i{g}_i(w)=0,i=1,...k$

gi(w)≤0,i=1,...k$g_i(w)\le 0,i=1,...k$

αi≥0,i=1,...k${\alpha }_i\ge 0,i=1,...k$

在满足以上KKT条件下，原来求f(w)$f(w)$在限制条件下的最小值就可以等价转换为求maxα,β:α≥0minwL(w,α,β)$\underset{\alpha ,\beta :\alpha \ge 0}{max}\underset{w}{min}\mathcal{L}(w,\alpha ,\beta )$

应用拉格朗日求解最小间隙最大值

构造朗格朗日函数：

L(w,b,α)=12||w||2+∑i=1mαi(1−y(i)(wTx(i)+b))$\mathcal{L}(w,b,\alpha )=\frac{1}{2}||w|{|}^2+\sum _{i=1}^m{\alpha }_i(1-y^{(i)}(w^T{x}^{(i)}+b))$

根据KKT条件有：

∂∂wL=0$\frac{\mathrm{\partial }}{\mathrm{\partial }w}\mathcal{L}=0$

∂∂bL=0$\frac{\mathrm{\partial }}{\mathrm{\partial }b}\mathcal{L}=0$

得到以下结果：

w=∑i=1mαiy(i)x(i)$w=\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}$

∑i=1mαiy(i)=0$\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$

以上结果回代入拉格朗日函数得到：

L(w,b,α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj(x(i))Tx(j)$\mathcal{L}(w,b,\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j(x^{(i)}{)}^T{x}^{(j)}$

故原式子可等价为：

maxα    W(α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj<(x(i)),x(j)>$\underset{\alpha }{max}W(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j<(x^{(i)}),x^{(j)}>$

s.t.      αi≥0,i=1,...m$s.t.{\alpha }_i\ge 0,i=1,...m$

             ∑i=1mαiy(i)=0$\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$

<(x(i)),x(j)>$<(x^{(i)}),x^{(j)}>$表示两个向量的内积. 实际上，可以用核函数来表示两个向量的相似度，这样，我们的SVM模型就可以应用在一些非线性可分的问题上。

正则化及不可分情形讨论

实际上的问题经常是，我们无法找到一个线性可分的超分类平面，这样，我们之前的限制条件是无法被满足的。那么前面做的这么多工作都只能应用于可分的情况吗？

之前我们的限制条件是非常严格的y(i)(wTx+b)≥1$y^{(i)}(w^{T}x+b)\ge 1$, 但是我们可以考虑加入一些松弛变量ζ$\zeta$来打破这种情况，同时对于这种情况要加一些惩罚条件，故原先的式子可改写成：

minw,b     12||w||2+C∑i=1mζi$\underset{w,b}{min}\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\zeta }_i$

s.t.        y(i)(wTx+b)≥1−ζi,i=1,...,m$s.t.y^{(i)}(w^{T}x+b)\ge 1-{\zeta }_i,i=1,...,m$

               ζi≥0,i=1,...,m${\zeta }_i\ge 0,i=1,...,m$

还是构造拉格朗日函数:

L(w,b,α)=12||w||2+C∑i=1mζi+∑i=1mαi(1−ζi−y(i)(wTx(i)+b))+∑i=1mri(−ζi)$\mathcal{L}(w,b,\alpha )=\frac{1}{2}||w|{|}^2+C\sum _{i=1}^m{\zeta }_i+\sum _{i=1}^m{\alpha }_i(1-{\zeta }_i-y^{(i)}(w^T{x}^{(i)}+b))+\sum _{i=1}^m{r}_i(-{\zeta }_i)$

w$w$, b$b$, ζ$\zeta$分别对L$\mathcal{L}$偏导可以得到：

w=∑i=1mαiy(i)x(i)$w=\sum _{i=1}^m{\alpha }_i{y}^{(i)}{x}^{(i)}$

b=−∑i=1mαiy(i)=0$b=-\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$

C−αi−ri=0,i=1,..,m$C-{\alpha }_i-r_i=0,i=1,..,m$

由于ri≥0$r_i\ge 0$, αi≥0${\alpha }_i\ge 0$

故由C−αi−ri=0,i=1,..,m$C-{\alpha }_i-r_i=0,i=1,..,m$可得0≤αi≤C,i=1,...,m$0\le {\alpha }_i\le C,i=1,...,m$

把w$w$, b$b$回代回去，原式子可以等价为:

maxα    W(α)=∑i=1mαi−12∑i,j=1my(i)y(j)αiαj<(x(i)),x(j)>$\underset{\alpha }{max}W(\alpha )=\sum _{i=1}^m{\alpha }_i-\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_j<(x^{(i)}),x^{(j)}>$

s.t.       0≤αi≤C,i=1,...m$s.t.0\le {\alpha }_i\le C,i=1,...m$

             ∑i=1mαiy(i)=0$\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$

且再次检查KKT条件，有：

αi(1−ζi−y(i)(wTx(i)+b))=0${\alpha }_i(1-{\zeta }_i-y^{(i)}(w^T{x}^{(i)}+b))=0$

1−ζi−y(i)(wTx(i)+b)≤0$1-{\zeta }_i-y^{(i)}(w^T{x}^{(i)}+b)\le 0$

ri(−ζi)=0$r_i(-{\zeta }_i)=0$

−ζi≤0$-{\zeta }_i\le 0$

ζi≥0${\zeta }_i\ge 0$

αi≥0${\alpha }_i\ge 0$

对αi${\alpha }_i$进行讨论(由KKT条件)有：

αi=0⇒y(i)(wTx(i)+b)≥1${\alpha }_i=0\Rightarrow y^{(i)}(w^T{x}^{(i)}+b)\ge 1$

αi=C⇒y(i)(wTx(i)+b)≤1${\alpha }_i=C\Rightarrow y^{(i)}(w^T{x}^{(i)}+b)\le 1$

0≤αi≤C⇒y(i)(wTx(i)+b)=1$0\le {\alpha }_i\le C\Rightarrow y^{(i)}(w^T{x}^{(i)}+b)=1$

SMO优化

前面已经做了很多工作，现在目标函数已经有了. 接下来就是需要α$\alpha$使得我们的目标函数取到最大值。参考资料中的SMO论文求目标函数的最小值:

minα  Ψ(α)=minα12∑i,j=1my(i)y(j)αiαjK(x(i),x(j))−∑i=1mαi$\underset{\alpha }{min}\mathrm{\Psi }(\alpha )=\underset{\alpha }{min}\frac{1}{2}\sum _{i,j=1}^m{y}^{(i)}{y}^{(j)}{\alpha }_i{\alpha }_{j}K(x^{(i)},x^{(j)})-\sum _{i=1}^m{\alpha }_i$

s.t.       0≤αi≤C,i=1,...m$s.t.0\le {\alpha }_i\le C,i=1,...m$

             ∑i=1mαiy(i)=0$\sum _{i=1}^m{\alpha }_i{y}^{(i)}=0$

取出一对α1,α2${\alpha }_1,{\alpha }_2$我们有α1y(1)+α2y(2)=k=−∑i=3mαiy(i)${\alpha }_1{y}^{(1)}+{\alpha }_2{y}^{(2)}=k=-\sum _{i=3}^m{\alpha }_i{y}^{(i)}$故有如下图关系

分两种情况讨论：y1,y2$y_1,y_2$不同号以及y1,y2$y_1,y_2$同号

其中对应的α2${\alpha }_2$的边界为：

1. 同号情况：L=max(0,α2−α1),H=min(C,C+α2−α1)$L=max(0,{\alpha }_2-{\alpha }_1),H=min(C,C+{\alpha }_2-{\alpha }_1)$
2. 异号： L=max(0,α2+α1−C),H=min(C,α2+α1)$L=max(0,{\alpha }_2+{\alpha }_1-C),H=min(C,{\alpha }_2+{\alpha }_1)$

化简目标函数，把α1,α2${\alpha }_1,{\alpha }_2$提取出来：

令s=y1y2,Kij=K(xi,xj)$s=y_1{y}_2,K_{ij}=K(x_i,x_j)$

Ψ(α)=12α21K11+12α22K22+sα1α2K12−α1−α2+y1α1v1+y2α2v2+Ψconst$\mathrm{\Psi }(\alpha )=\frac{1}{2}{\alpha }_1^2{K}_{11}+\frac{1}{2}{\alpha }_2^2{K}_{22}+s{\alpha }_1{\alpha }_2{K}_{12}-{\alpha }_1-{\alpha }_2+y_1{\alpha }_1{v}_1+y_2{\alpha }_2{v}_2+{\mathrm{\Psi }}_{const}$

其中有：

vi=∑j=3mα∗jyjKij=ui+b∗−y1α∗1K1i−y2α∗2K2i$v_i=\sum _{j=3}^m{\alpha }_j^{\ast }{y}_j{K}_{ij}=u_i+b^{\ast }-y_1{\alpha }_1^{\ast }{K}_{1i}-y_2{\alpha }_2^{\ast }{K}_{2i}$ (α∗1${\alpha }_1^{\ast }$表示旧的值)

则有α1+sα2=−y1∑i=3mαiyi=α∗1+sα∗2=t${\alpha }_1+s{\alpha }_2=-y_1\sum _{i=3}^m{\alpha }_i{y}_i={\alpha }_1^{\ast }+s{\alpha }_2^{\ast }=t$

把α1=t−sα2${\alpha }_1=t-s{\alpha }_2$代入目标函数有：

Ψ(α)=12(t−sα2)2K11+12α22K22+s(t−sα2)α2K12−(t−α2)−α2+y1(t−sα2)v1+y2α2v2+Ψconst$\mathrm{\Psi }(\alpha )=\frac{1}{2}(t-s{\alpha }_2{)}^2{K}_{11}+\frac{1}{2}{\alpha }_2^2{K}_{22}+s(t-s{\alpha }_2){\alpha }_2{K}_{12}-(t-{\alpha }_2)-{\alpha }_2+y_1(t-s{\alpha }_2)v_1+y_2{\alpha }_2{v}_2+{\mathrm{\Psi }}_{const}$

目标函数对α2${\alpha }_2$求导并令其为0：

∂∂α2Ψ(α)=α2(K11+K22−2K12)−st(K11−K12)−y2(v1−v2)+s−1=0$\frac{\mathrm{\partial }}{\mathrm{\partial }{\alpha }_2}\mathrm{\Psi }(\alpha )={\alpha }_2(K_{11}+K_{22}-2K_{12})-st(K_{11}-K12)-y_2(v_1-v_2)+s-1=0$

把t=α∗1+sα∗2,vi=∑j=3mα∗jyjKij=ui+b∗−y1α∗1K1i−y2α∗2K2i$t={\alpha }_1^{\ast }+s{\alpha }_2^{\ast },v_i=\sum _{j=3}^m{\alpha }_j^{\ast }{y}_j{K}_{ij}=u_i+b^{\ast }-y_1{\alpha }_1^{\ast }{K}_{1i}-y_2{\alpha }_2^{\ast }{K}_{2i}$代入上式得:

α2(K11+K22−2K12)=α∗2(K11+K22−2K12)+y2(u1−u2+y2−y1)${\alpha }_2(K_{11}+K_{22}-2K_{12})={\alpha }_2^{\ast }(K_{11}+K_{22}-2K_{12})+y_2(u_1-u_2+y_2-y_1)$

目标函数对α2${\alpha }_2$进行二次求导有:

∂∂2α2Ψ(α)=η=K11+K22−2K12$\frac{\mathrm{\partial }}{{\mathrm{\partial }}^2{\alpha }_2}\mathrm{\Psi }(\alpha )=\eta =K_{11}+K_{22}-2K_{12}$

1. 当η>0$\eta >0$有：

   αnew2=α∗2+y2(E1−E2)η${\alpha }_2^{new}={\alpha }_2^{\ast }+\frac{y_2(E_1-E_2)}{\eta }$

   

   αnew1=α1+s(α2−αnew,clipped2)${\alpha }_1^{new}={\alpha }_1+s({\alpha }_2-{\alpha }_2^{new,clipped})$

2. 当η≤0$\eta \le 0$有， 此时易知α2${\alpha }_2$取到边界时，目标函数最小：

   f1=y1(E1+b)−α1K11−sα2K12,$f_1=y_1(E_1+b)-{\alpha }_1{K}_{11}-s{\alpha }_2{K}_{12},$

   f2=y2(E2+b)−sα1K12−α2K22,$f_2=y_2(E_2+b)-s{\alpha }_1{K}_{12}-{\alpha }_2{K}_{22},$

   L1=α1+s(α2−L)$L_1={\alpha }_1+s({\alpha }_2-L)$

   H1=α1+s(α2−H)$H_1={\alpha }_1+s({\alpha }_2-H)$

   ΨL=L1f1+Lf2+12L21K11+12L2K22+sLL1K12${\mathrm{\Psi }}_L=L_1{f}_1+L{f}_2+\frac{1}{2}{L}_1^2{K}_{11}+\frac{1}{2}{L}^2{K}_{22}+sL{L}_1{K}_{12}$

   ΨH=H1f1+Hf2+12H21K11+12H2K22+sHH1K12${\mathrm{\Psi }}_H=H_1{f}_1+H{f}_2+\frac{1}{2}{H}_1^2{K}_{11}+\frac{1}{2}{H}^2{K}_{22}+sH{H}_1{K}_{12}$

   对比ΨL,ΨH${\mathrm{\Psi }}_L,{\mathrm{\Psi }}_H$, 取值较小的那个

3. 每次更新完α$\alpha$后都需要更新b值：

   当α1${\alpha }_1$不在界上时:

   bnew=b1=E1+y1(αnew1−α1)K11+y2(αnew,clipped2−α2)K12+b$b^{new}=b_1=E_1+y_1({\alpha }_1^{new}-{\alpha }_1)K_{11}+y_2({\alpha }_2^{new,clipped}-{\alpha }_2)K_{12}+b$

   当α2${\alpha }_2$不在界上时:

   bnew=b2=E2+y1(αnew1−α1)K12+y2(αnew,clipped2−α2)K22+b$b^{new}=b_2=E_2+y_1({\alpha }_1^{new}-{\alpha }_1)K_{12}+y_2({\alpha }_2^{new,clipped}-{\alpha }_2)K_{22}+b$

   当双方都在界上时：

   b=b1+b22$b=\frac{b_1+b_2}{2}$

推荐相关参考资料：

1. Andrew Ng在网易公开课的课堂资料，其中part V涉及到SVM. http://cimg3.163.com/edu/open/ocw/jiqixuexikecheng.zip

2. John Platt的SMO论文. https://www.microsoft.com/en-us/research/wp-content/uploads/2016/02/smo-book.pdf

3. JerryLead的博客. http://www.cnblogs.com/jerrylead/archive/2011/03/18/1988415.html#undefined