失眠网 > SVM：通俗易懂的SMO算法

SVM：通俗易懂的SMO算法

时间：2018-07-21 10:55:49

相关推荐

SVM：通俗易懂的SMO算法

前言

SVM算法中目标函数最终是一个关于aaa向量的函数。本文将通过SMO算法来极小化这个函数。

SMO算法

首先我们再写一下带核函数的优化目标：

min⏟a12∑i=1m∑j=1maiajyiyjK(xi,xj)−∑i=1mais.t∑i=1mai=00≤ai≤C\underbrace{min}_{a} \frac{1}{2}\sum_{i=1}^m \sum_{j=1}^m a_ia_jy_iy_jK(x_i,x_j)-\sum_{i=1}^ma_i\\ s.t \sum_{i=1}^ma_i=0\\ 0\le a_i \le C amin21i=1∑mj=1∑maiajyiyjK(xi,xj)−i=1∑mais.ti=1∑mai=00≤ai≤C

SMO算法则采用了一种启发式的方法。它每次只优化两个变量，将其他的变量都视为常数。由于∑i=1mai=0\sum_{i=1}^ma_i=0∑i=1mai=0.假如将a3,a4,...,ama_3,a_4,...,a_ma3,a4,...,am固定，那么a1a_1a1，a2a_2a2之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。为了后面表示方便，定义：Kij=ϕ(xi)⋅ϕ(xj)K_{ij}=\phi(x_i) \cdot \phi(x_j)Kij=ϕ(xi)⋅ϕ(xj)

所以假设我们选择了两个变量：a1,a2a_1,a_2a1,a2来作为第一个选择的变量来迭代更新，当然怎么选择也有有原因的，这个后面会讲解。于是其他变量都是常量，那么公式就变为：

min⏟ai,aja1a2y1y2K12+12a12K11+12a22K22+12a1y1∑j=3majyjK1,j+12a2y2∑j=3majyjK2,j−a1−a2−∑j=3majs.ta1y1+a2y2=−∑i=3mai=ε0≤ai≤C，i=1,2\underbrace{min}_{a_i,a_j}\qquad a_1a_2y_1y_2K_{12}+\frac{1}{2}a_1^2K_{11}+\frac{1}{2}a_2^2K_{22}+\frac{1}{2}a_1y_1\sum_{j=3}^m a_jy_jK_{1,j}+\frac{1}{2}a_2y_2\sum_{j=3}^m a_jy_jK_{2,j}-a_1-a_2-\sum_{j=3}^ma_j\\ s.t \qquad a_1y_1+a_2y_2=-\sum_{i=3}^ma_i=\varepsilon \\ 0\le a_i \le C，i=1,2 ai,ajmina1a2y1y2K12+21a12K11+21a22K22+21a1y1j=3∑majyjK1,j+21a2y2j=3∑majyjK2,j−a1−a2−j=3∑majs.ta1y1+a2y2=−i=3∑mai=ε0≤ai≤C，i=1,2

因为a1y1+a2y2=εa_1y_1+a_2y_2=\varepsilona1y1+a2y2=ε，所以得到：a1=εy1−a2y2y1a_1=\varepsilon y_1-a_2y_2y_1a1=εy1−a2y2y1，把a1a_1a1代入上式，并且为来简单描述，我们必须还用到一些变量来替换公式中的某一类变量：

g(x)=wϕ(xi)+b=∑j=1majyjK(x,xj)+bvi=∑j=3majyjKij=g(x)−∑j=12ajyjKij−b=g(x)−a1y1Ki1−a2y2Ki2−bg(x)=w\phi(x_i) +b=\sum_{j=1}^ma_jy_jK(x,x_j)+b \\ v_i=\sum_{j=3}^m a_jy_jK_{ij}=g(x)-\sum_{j=1}^2 a_jy_jK_{ij}-b=g(x)-a_1y_1K_{i1}-a_2y_2K_{i2}-b g(x)=wϕ(xi)+b=j=1∑majyjK(x,xj)+bvi=j=3∑majyjKij=g(x)−j=1∑2ajyjKij−b=g(x)−a1y1Ki1−a2y2Ki2−b

这样a1a_1a1、v1v_1v1、v2v_2v2代入上式，得到W(a1,a2)W(a_1,a_2)W(a1,a2)：

W(a1,a2)=(εy1−a2y2y1)a2y1y2K12+12(εy1−a2y2y1)2K11+12a22K22+12(εy1−a2y2y1)y1v1+12a2y2v2−(εy1−a2y2y1)−a2−∑j=3majW(a_1,a_2)=(\varepsilon y_1-a_2y_2y_1)a_2y_1y_2K_{12}+\frac{1}{2}(\varepsilon y_1-a_2y_2y_1)^2K_{11}+\frac{1}{2}a_2^2K_{22}+\frac{1}{2}(\varepsilon y_1-a_2y_2y_1)y_1v_1+\frac{1}{2}a_2y_2v_2-(\varepsilon y_1-a_2y_2y_1)-a_2-\sum_{j=3}^ma_j W(a1,a2)=(εy1−a2y2y1)a2y1y2K12+21(εy1−a2y2y1)2K11+21a22K22+21(εy1−a2y2y1)y1v1+21a2y2v2−(εy1−a2y2y1)−a2−j=3∑maj

现在W(a1,a2)W(a_1,a_2)W(a1,a2)公式中只有一个变量a2a_2a2，求最小值，于是，我们求导：

∂W∂a2=K11a2+K12a2−2K12a2−K11εy2+K12εy2+y1y2−1−v1y2+y2v2\frac{\partial W}{\partial a_2}=K_{11}a_2+K_{12}a_2-2K_{12}a_2-K_{11}\varepsilon y_2+K_{12}\varepsilon y_2+y_1 y_2 -1- v_1y_2+y_2v_2 ∂a2∂W=K11a2+K12a2−2K12a2−K11εy2+K12εy2+y1y2−1−v1y2+y2v2

让∂W∂a2=0\frac{\partial W}{\partial a_2}=0∂a2∂W=0，得到：

a2=y2(y2−y1+K11ε−K12ε+v1−v2)K11+K22+2K12a_2=\frac{y_2(y_2-y_1+K_{11}\varepsilon -K_{12}\varepsilon+v_1-v_2)}{K_{11}+K_{22}+2K_{12}} a2=K11+K22+2K12y2(y2−y1+K11ε−K12ε+v1−v2)

这样似乎也算是完事了，但变换一下似乎更好一些，于是，提出一个假设变量EiE_iEi：

Ei=g(xi)−yi=∑j=1majyjK(xi,xj)+b−yiE_i=g(x_i)-y_i=\sum_{j=1}^ma_jy_jK(x_i,x_j)+b-y_i Ei=g(xi)−yi=j=1∑majyjK(xi,xj)+b−yi

将变量EiE_iEi以及a1y1+a2y2=εa_1y_1+a_2y_2=\varepsilona1y1+a2y2=ε代入公式中，有了如下的变换结果：

(K11+K22+2K12)a2=(K11+K22+2K12)a2old+y2(E1−E2)(K_{11}+K_{22}+2K_{12})a_2=(K_{11}+K_{22}+2K_{12})a_2^{old}+y_2(E_1-E_2) (K11+K22+2K12)a2=(K11+K22+2K12)a2old+y2(E1−E2)

于是a2new,unca_2^{new,unc}a2new,unc：

a2new,unc=a2old+y2(E1−E2)K11+K22+2K12a_2^{new,unc}=a_2^{old}+\frac{y_2(E_1-E_2)}{K_{11}+K_{22}+2K_{12}} a2new,unc=a2old+K11+K22+2K12y2(E1−E2)

a2new,unca_2^{new,unc}a2new,unc及L和H的定义

a2new,unca_2^{new,unc}a2new,unc的值并不是最终的更新函数值，因为由于a1a_1a1、a2a_2a2的关系被限制在盒子里的一条线段上，所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是a2a_2a2的优化问题。由于我们采用的是启发式的迭代法，假设我们上一轮迭代得到的解是a1olda_1^{old}a1old、a2olda_2^{old}a2old，假设沿着约束方向a2a_2a2未经剪辑的解是a2new,unca_2^{new,unc}a2new,unc，本轮迭代完成后的解为a1newa_1^{new}a1new、a2newa_2^{new}a2new，a2newa_2^{new}a2new必须满足上图中的线段约束：

首先 L 的定义是a2a_2a2的下限：图中红线处(0,-k)点出表示a2a_2a2的红线处的最小值，于是L=−kL=-kL=−k，因为a1−a2=ka_1-a_2=ka1−a2=k，−k=a2−a1-k=a_2-a_1−k=a2−a1，所以L=−k=a2−a1L=-k=a_2-a_1L=−k=a2−a1，

同理对于H，图中黑线(C,C-k)，所以H=C−kH=C-kH=C−k，由于a1−a2=ka_1-a_2=ka1−a2=k，所以H=C−k=C−a1+a2H=C-k=C-a_1+a_2H=C−k=C−a1+a2

同时是由于在迭代过程中更新，所以换成上一轮的值：L=a2old−a1oldL=a_2^{old}-a_1^{old}L=a2old−a1old、H=C−k=C−a1old+a2oldH=C-k=C-a_1^{old}+a_2^{old}H=C−k=C−a1old+a2old。综合这两种情况，最终得到：

L=max(0,a2old−a1old)H=min(C,C−a1old+a2old)L=max(0,a_2^{old}-a_1^{old}) \\ H=min(C,C-a_1^{old}+a_2^{old}) L=max(0,a2old−a1old)H=min(C,C−a1old+a2old)

L相关的值在红色线上的点(C,k-C)，和黑色线的点(k,0)，所以：

L=max(0,a1old+a2old−C)L=max(0,a_1^{old}+a_2^{old}-C) L=max(0,a1old+a2old−C)

H相关的值在红色线的点(k-C,C)和黑色线的点(0,k)，所以：

H=min(C,a1old+a2old)H=min(C,a_1^{old}+a_2^{old}) H=min(C,a1old+a2old)

这其实就是限制了aia_iai的范围，所以选取了两个变量更新之后，某个变量的值更新都满足这些条件，假设求导得到a2new,unca_2^{new,unc}a2new,unc，于是得到了：

a2new={Ha2new,unc>Ha2new,uncL<a2new,unc<HLa2new,unc<La_2^{new} = \begin{cases} H& a_2^{new,unc}>H\\ a_2^{new,unc}& L<a_2^{new,unc}<H\\ L& a_2^{new,unc}<L \end{cases} a2new=⎩⎪⎨⎪⎧Ha2new,uncLa2new,unc>HL<a2new,unc<Ha2new,unc<L

其中

更新b向量

得到a1newa_1^{new}a1new和a2newa_2^{new}a2new之后，我们可以来计算bbb，我们先用a1newa_1^{new}a1new来得到最新的bnewb^{new}bnew，当0<ainew≤C0<a_i^{new} \le C0<ainew≤C时，

y1−∑i=1maiyiKi1−b1=0y_1-\sum_{i=1}^{m}a_iy_iK_{i1}-b_1=0\\ y1−i=1∑maiyiKi1−b1=0

转换后得到：

b1=y1−∑i=3maiyiKi1−a1newy1K11−a2newy2K21b_1=y_1-\sum_{i=3}^{m}a_iy_iK_{i1}-a_1^{new}y_1K_{11}-a_2^{new}y_2K_{21} b1=y1−i=3∑maiyiKi1−a1newy1K11−a2newy2K21

同时由于E1=g(x1)−y1=∑j=1majyjK(xi,xj)+b−yi=∑j=3majyjKj1+a1oldy1K11+a2oldy2K21+bold−y1E_1=g(x_1)-y_1=\sum_{j=1}^ma_jy_jK(x_i,x_j)+b-y_i=\sum_{j=3}^{m}a_jy_jK_{j1}+a_1^{old}y_1K_{11}+a_2^{old}y_2K_{21}+b^{old}-y_1E1=g(x1)−y1=∑j=1majyjK(xi,xj)+b−yi=∑j=3majyjKj1+a1oldy1K11+a2oldy2K21+bold−y1，替代上述得到更新后的b1newb_1^{new}b1new：

b1new=−E1−y1K11(a1new−a1old)−y2K21(a2new−a2old)+boldb_1^{new}=-E_1-y_1K_{11}(a_1^{new}-a_1^{old})-y_2K_{21}(a_2^{new}-a_2^{old})+b^{old} b1new=−E1−y1K11(a1new−a1old)−y2K21(a2new−a2old)+bold

同理可以得到b2newb_2^{new}b2new：

b2new=−E2−y1K12(a1new−a1old)−y2K22(a2new−a2old)+boldb_2^{new}=-E_2-y_1K_{12}(a_1^{new}-a_1^{old})-y_2K_{22}(a_2^{new}-a_2^{old})+b^{old} b2new=−E2−y1K12(a1new−a1old)−y2K22(a2new−a2old)+bold

那么问题来了，有两个bbb，这怎么弄？

bnew={b1new+b2new2a2对应的点是支持向量b1newa2对应的点不是支持向量b^{new} = \begin{cases} \frac{b_1^{new}+b_2^{new}}{2}& a_2对应的点是支持向量 \\ b_1^{new}& a_2对应的点不是支持向量 \end{cases} bnew={2b1new+b2newb1newa2对应的点是支持向量a2对应的点不是支持向量

为什么这么选择？

具体情况参考李航书130页，选择bnew=(b1+b2)/2b^{new}=(b_1+b_2)/2bnew=(b1+b2)/2这只是一个工程上的选择而已，因为没有一个确定的b，得到了bnewb^{new}bnew之后利用其来更新EiE_iEi，公式上述其实有提供，这里再明确一下：

Einew=∑SyjajK(xi,xj)+bnew−yiE_i^{new}=\sum_{S}y_ja_jK(x_i,x_j)+b^{new}-y_i Einew=S∑yjajK(xi,xj)+bnew−yi

这里的SSS是所有的支持向量xix_ixi的集合，这里每一个样本xix_ixi都对应一个EiE_iEi，利用bnewb^{new}bnew和EinewE_i^{new}Einew迭代更新。这里的E跟更新aia_iai的表达式场景不同，E1是用于某次迭代中，SMO选中的aaa对应的计算过程的，而EiE_iEi是迭代完毕后，尝试优化更新所有的EiE_iEi值的时候。如果只是计算，都是用的这个公式。为什么不用所有支持向量，因为不是支持向量的样本，其𝛼值为0，就算放在式子里面也是0，所以可以去掉。

为什么求解bnewb^{new}bnew用E1E^1E1表示？

用E1表示，是为了求出最终的bnew, 并求出Ei。

如何选择两个变量

1、外层变量

SMO算法称选择第一个变量为外层循环，这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点，解要满足的KKT条件的对偶互补条件：ai(yi(wTxi+b)−1+ξi)=0a_i(y_i(w^Tx_i+b)-1+\xi_{i})=0ai(yi(wTxi+b)−1+ξi)=0

KKT条件我们在第一节已经讲到了：

ai=0⇒yig(xi)≥00<ai<C⇒yig(xi)=1ai=C⇒yig(xi)≤1a_i=0 \Rightarrow y_ig(x_i)\ge0 \\ 0<a_i<C \Rightarrow y_ig(x_i)=1 \\ a_i=C \Rightarrow y_ig(x_i)\le1 ai=0⇒yig(xi)≥00<ai<C⇒yig(xi)=1ai=C⇒yig(xi)≤1

这三个KKT条件，那么一般我们取违反0<ai<C⇒yig(xi)=10<a_i<C \Rightarrow y_ig(x_i)=10<ai<C⇒yig(xi)=1最严重的点，如果没有，再选择其他ai=0a_i=0ai=0、ai=Ca_i=Cai=C的条件。2、内层变量

SMO算法称选择第二一个变量为内层循环，假设我们在外层循环已经找到了a1a_1a1，第二个变量a2a_2a2的选择标准是让∣E1−E2∣|E_1−E_2|∣E1−E2∣有足够大的变化。由于a1a_1a1定了的时候，E1E_1E1也确定了，所以要想∣E1−E2∣|E_1−E_2|∣E1−E2∣最大，只需要在E1E_1E1为正时，选择最小的EiE_iEi作为E2E_2E2，在E1E_1E1为负时，选择最大的EiE_iEi作为E2E_2E2，可以将所有的EiE_iEi保存下来加快迭代。如果内存循环找到的点不能让目标函数有足够的下降，可以采用以下步骤：

（1）遍历支持向量点来做 a2a_2a2 , 直到目标函数有足够的下降；

（2）如果所有的支持向量做 a2a_2a2 都不能让目标函数有足够的下降，可以在整个样本集上选择 a2a_2a2；

（3）如果整个样本集依然不存在，则跳回外层循环重新选择 a1a_1a1。

这其中的EiE_iEi也在上面的更新aia_iai、bbb的代码里有提到，这里不详细介绍，大家参考博客来详细了解。

问题

为什么每次更新Ei时只用支持向量的样本？在上面优化的时候例如E1使用的是全部的样本。Ei= g(xi)-yi=wx+b-y不是这个公式吗？

这里两个E的表达式场景不同，E1是用于某次迭代中，SMO选中的aaa对应的计算过程的，而EiE_iEi是迭代完毕后，尝试优化更新所有的EiE_iEi值的时候。如果只是计算，都是你说的那个公式。回顾一下，w与αi,xi,yi的关系式为:

w = ∑ αiyixi ，其中i = 1,2,3,…,N

我们初始化的α是一个全为0的向量，即α1=α2=α3=…=αN=0，w的值即为0.我们进行SMO算法时，每轮挑选出两个变量αi，固定其他的α值，也就是说，那些从来没有被挑选出来过的α，值始终为0，而根据前面所学，支持向量对应的αi是一定满足 0<αi<=C的.有了这个认识之后，为什么不用全集呢，因为不是支持向量的样本点，对应的αi值为0啊，加起来也没有意义，对w产生不了影响，只有支持向量对应的点 (xi,yi)与对应的αi相乘，产生的值才对w有影响啊。从这里也能理解，为什么李航书中，认为支持向量不仅仅是处于间隔边界上的点，还包括那些处于间隔边界和分类超平面之间、分类超平面之上、分类超平面错误的一侧处的点了，因为后面所说的那些点，对应的αi为C，对w的计算可以起到影响作用，换句话说，就是能对w起到影响作用的点，都属于支持向量!

关于惩罚项C

C是一个超参数，需要调参的。后面我有一篇文章专门讲到了C这个参数的调参。支持向量机高斯核调参小结： /pinard/p/6126077.html选择两个变量的流程参见我4.1节和4.2节。最开始所有样本的alpha都是初始化为0的，后面按4.1节和4.2节的流程每轮选择2个样本的alpha进行迭代。