支持向量机原理(四)SMO算法原理

支持向量机原理(四)SMO算法原理

           支持向量机原理(一) 线性支持向量机

    支持向量机原理(二) 线性支持向量机的软间隔最大化模型

    支持向量机原理(三)线性不可分支持向量机与核函数

    支持向量机原理(四)SMO算法原理

    支持向量机原理(五)线性支持回归

 

  在SVM的前三篇里,我们优化的目标函数最终都是一个关于αα向量的函数。而怎么极小化这个函数,求出对应的αα向量,进而求出分离超平面我们没有讲。本篇就对优化这个关于αα向量的函数的SMO算法做一个总结。

1. 回顾SVM优化目标函数

    我们首先回顾下我们的优化目标函数:

minα12∑i=1,j=1mαiαjyiyjK(xi,xj)−∑i=1mαimin⏟α12∑i=1,j=1mαiαjyiyjK(xi,xj)−∑i=1mαi

s.t.∑i=1mαiyi=0s.t.∑i=1mαiyi=0

0≤αi≤C0≤αi≤C

    我们的解要满足的KKT条件的对偶互补条件为:

α∗i(yi(wTxi+b)−1+ξ∗i)=0αi∗(yi(wTxi+b)−1+ξi∗)=0

    根据这个KKT条件的对偶互补条件,我们有:

α∗i=0⇒yi(w∗∙ϕ(xi)+b)≥1αi∗=0⇒yi(w∗∙ϕ(xi)+b)≥1

0<α∗i<C⇒yi(w∗∙ϕ(xi)+b)=10<αi∗<C⇒yi(w∗∙ϕ(xi)+b)=1

α∗i=C⇒yi(w∗∙ϕ(xi)+b)≤1αi∗=C⇒yi(w∗∙ϕ(xi)+b)≤1

     由于w∗=∑j=1mα∗jyjϕ(xj)w∗=∑j=1mαj∗yjϕ(xj),我们令g(x)=w∗∙ϕ(x)+b=∑j=1mα∗jyjK(x,xj)+b∗g(x)=w∗∙ϕ(x)+b=∑j=1mαj∗yjK(x,xj)+b∗,则有:

α∗i=0⇒yig(xi)≥1αi∗=0⇒yig(xi)≥1

0<α∗i<C⇒yig(xi)=10<αi∗<C⇒yig(xi)=1

α∗i=C⇒yig(xi)≤1αi∗=C⇒yig(xi)≤1

2. SMO算法的基本思想

    上面这个优化式子比较复杂,里面有m个变量组成的向量αα需要在目标函数极小化的时候求出。直接优化时很难的。SMO算法则采用了一种启发式的方法。它每次只优化两个变量,将其他的变量都视为常数。由于∑i=1mαiyi=0∑i=1mαiyi=0.假如将α3,α4,...,αmα3,α4,...,αm 固定,那么α1,α2α1,α2之间的关系也确定了。这样SMO算法将一个复杂的优化算法转化为一个比较简单的两变量优化问题。

    为了后面表示方便,我们定义Kij=ϕ(xi)∙ϕ(xj)Kij=ϕ(xi)∙ϕ(xj)

    由于α3,α4,...,αmα3,α4,...,αm都成了常量,所有的常量我们都从目标函数去除,这样我们上一节的目标优化函数变成下式:

minα1,α112K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3myiαiKi1+y2α2∑i=3myiαiKi2min⏟α1,α112K11α12+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3myiαiKi1+y2α2∑i=3myiαiKi2

s.t.α1y1+α2y2=−∑i=3myiαi=ςs.t.α1y1+α2y2=−∑i=3myiαi=ς

0≤αi≤Ci=1,20≤αi≤Ci=1,2

3. SMO算法目标函数的优化

    为了求解上面含有这两个变量的目标优化问题,我们首先分析约束条件,所有的α1,α2α1,α2都要满足约束条件,然后在约束条件下求最小。

    根据上面的约束条件α1y1+α2y2=ς0≤αi≤Ci=1,2α1y1+α2y2=ς0≤αi≤Ci=1,2,又由于y1,y2y1,y2均只能取值1或者-1, 这样α1,α2α1,α2在[0,C]和[0,C]形成的盒子里面,并且两者的关系直线的斜率只能为1或者-1,也就是说α1,α2α1,α2的关系直线平行于[0,C]和[0,C]形成的盒子的对角线,如下图所示:

支持向量机原理(四)SMO算法原理

     由于α1,α2α1,α2的关系被限制在盒子里的一条线段上,所以两变量的优化问题实际上仅仅是一个变量的优化问题。不妨我们假设最终是α2α2的优化问题。由于我们采用的是启发式的迭代法,假设我们上一轮迭代得到的解是αold1,αold2α1old,α2old,假设沿着约束方向α2α2未经剪辑的解是αnew,unc2α2new,unc.本轮迭代完成后的解为αnew1,αnew2α1new,α2new

    由于αnew2α2new必须满足上图中的线段约束。假设L和H分别是上图中αnew2α2new所在的线段的边界。那么很显然我们有:

L≤αnew2≤HL≤α2new≤H

    而对于L和H,我们也有限制条件如果是上面左图中的情况,则

L=max(0,αold2−αold1)H=min(C,C+αold2−αold1)L=max(0,α2old−α1old)H=min(C,C+α2old−α1old)

    如果是上面右图中的情况,我们有:

L=max(0,αold2+αold1−C)H=min(C,αold2+αold1)L=max(0,α2old+α1old−C)H=min(C,α2old+α1old)

     也就是说,假如我们通过求导得到的αnew,unc2α2new,unc,则最终的αnew2α2new应该为:

 

αnew2=⎧⎩⎨⎪⎪Hαnew,unc2Lαnew,unc2>HL≤αnew,unc2≤Hαnew,unc2<Lα2new={Hα2new,unc>Hα2new,uncL≤α2new,unc≤HLα2new,unc<L

   

    那么如何求出αnew,unc2α2new,unc呢?很简单,我们只需要将目标函数对α2α2求偏导数即可。

    首先我们整理下我们的目标函数。

    为了简化叙述,我们令

Ei=g(xi)−yi=∑j=1mα∗jyjK(xi,xj)+b−yiEi=g(xi)−yi=∑j=1mαj∗yjK(xi,xj)+b−yi

    其中g(x)g(x)就是我们在第一节里面的提到的

g(x)=w∗∙ϕ(x)+b=∑j=1mα∗jyjK(x,xj)+b∗g(x)=w∗∙ϕ(x)+b=∑j=1mαj∗yjK(x,xj)+b∗

    我们令

vi=∑j=3myjαjK(xi,xj)=g(xi)−∑j=12yjαjK(xi,xj)−bvi=∑j=3myjαjK(xi,xj)=g(xi)−∑j=12yjαjK(xi,xj)−b

    这样我们的优化目标函数进一步简化为:

W(α1,α2)=12K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1v1+y2α2v2W(α1,α2)=12K11α12+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1v1+y2α2v2

    由于α1y1+α2y2=ςα1y1+α2y2=ς,并且y2i=1yi2=1,可以得到α1用α2α1用α2表达的式子为:

α1=y1(ς−α2y2)α1=y1(ς−α2y2)

    将上式带入我们的目标优化函数,就可以消除α1α1,得到仅仅包含α2α2的式子。

W(α2)=12K11(ς−α2y2)2+12K22α22+y2K12(ς−α2y2)α2−(ς−α2y2)y1−α2+(ς−α2y2)v1+y2α2v2W(α2)=12K11(ς−α2y2)2+12K22α22+y2K12(ς−α2y2)α2−(ς−α2y2)y1−α2+(ς−α2y2)v1+y2α2v2

    忙了半天,我们终于可以开始求αnew,unc2α2new,unc了,现在我们开始通过求偏导数来得到αnew,unc2α2new,unc。

 

∂W∂α2=K11α2+K22α2−2K12α2−K11ςy2+K12ςy2+y1y2−1−v1y2+y2v2=0∂W∂α2=K11α2+K22α2−2K12α2−K11ςy2+K12ςy2+y1y2−1−v1y2+y2v2=0

    整理上式有:

(K11+K22−2K12)α2=y2(y2−y1+ςK11−ςK12+v1−v2)(K11+K22−2K12)α2=y2(y2−y1+ςK11−ςK12+v1−v2)

 

=y2(y2−y1+ςK11−ςK12+(g(x1)−∑j=12yjαjK1j−b)−(g(x2)−∑j=12yjαjK2j−b))=y2(y2−y1+ςK11−ςK12+(g(x1)−∑j=12yjαjK1j−b)−(g(x2)−∑j=12yjαjK2j−b))

    将ς=α1y1+α2y2ς=α1y1+α2y2带入上式,我们有:

 

(K11+K22−2K12)αnew,unc2=y2((K11+K22−2K12)αold2y2+y2−y1+g(x1)−g(x2))(K11+K22−2K12)α2new,unc=y2((K11+K22−2K12)α2oldy2+y2−y1+g(x1)−g(x2))

 

=(K11+K22−2K12)αold2+y2(E1−E2)=(K11+K22−2K12)α2old+y2(E1−E2)

    我们终于得到了αnew,unc2α2new,unc的表达式:

αnew,unc2=αold2+y2(E1−E2)K11+K22−2K12)α2new,unc=α2old+y2(E1−E2)K11+K22−2K12)

    利用上面讲到的αnew,unc2α2new,unc和αnew2α2new的关系式,我们就可以得到我们新的αnew2α2new了。利用αnew2α2new和αnew1α1new的线性关系,我们也可以得到新的αnew1α1new。

4. SMO算法两个变量的选择

    SMO算法需要选择合适的两个变量做迭代,其余的变量做常量来进行优化,那么怎么选择这两个变量呢?

4.1 第一个变量的选择

    SMO算法称选择第一个变量为外层循环,这个变量需要选择在训练集中违反KKT条件最严重的样本点。对于每个样本点,要满足的KKT条件我们在第一节已经讲到了: 

α∗i=0⇒yig(xi)≥1αi∗=0⇒yig(xi)≥1

0<α∗i<C⇒yig(xi)=10<αi∗<C⇒yig(xi)=1

α∗i=C⇒yig(xi)≤1αi∗=C⇒yig(xi)≤1

    一般来说,我们首先选择违反0<α∗i<C⇒yig(xi)=10<αi∗<C⇒yig(xi)=1这个条件的点。如果这些支持向量都满足KKT条件,再选择违反α∗i=0⇒yig(xi)≥1αi∗=0⇒yig(xi)≥1 和 α∗i=C⇒yig(xi)≤1αi∗=C⇒yig(xi)≤1的点。

4.2 第二个变量的选择

     SMO算法称选择第二一个变量为内层循环,假设我们在外层循环已经找到了α1α1, 第二个变量α2α2的选择标准是让|E1−E2||E1−E2|有足够大的变化。由于α1α1定了的时候,E1E1也确定了,所以要想|E1−E2||E1−E2|最大,只需要在E1E1为正时,选择最小的EiEi作为E2E2, 在E1E1为负时,选择最大的EiEi作为E2E2,可以将所有的EiEi保存下来加快迭代。

    如果内存循环找到的点不能让目标函数有足够的下降, 可以采用遍历支持向量点来做α2α2,直到目标函数有足够的下降, 如果所有的支持向量做α2α2都不能让目标函数有足够的下降,可以跳出循环,重新选择α1α1 

4.3 计算阈值b和差值EiEi 

    在每次完成两个变量的优化之后,需要重新计算阈值b。当0<αnew1<C0<α1new<C时,我们有

y1−∑i=1mαiyiKi1−b1=0y1−∑i=1mαiyiKi1−b1=0

    于是新的bnew1b1new为:

bnew1=y1−∑i=3mαiyiKi1−αnew1y1K11−αnew2y2K21b1new=y1−∑i=3mαiyiKi1−α1newy1K11−α2newy2K21

    计算出E1E1为:

E1=g(x1)−y1=∑i=3mαiyiKi1+αold1y1K11+αold2y2K21+bold−y1E1=g(x1)−y1=∑i=3mαiyiKi1+α1oldy1K11+α2oldy2K21+bold−y1

    可以看到上两式都有y1−∑i=3mαiyiKi1y1−∑i=3mαiyiKi1,因此可以将bnew1b1new用E1E1表示为:

bnew1=−E1−y1K11(αnew1−αold1)−y2K21(αnew2−αold2)+boldb1new=−E1−y1K11(α1new−α1old)−y2K21(α2new−α2old)+bold

    同样的,如果0<αnew2<C0<α2new<C, 那么有:

bnew2=−E2−y1K12(αnew1−αold1)−y2K22(αnew2−αold2)+boldb2new=−E2−y1K12(α1new−α1old)−y2K22(α2new−α2old)+bold

    最终的bnewbnew为:

bnew=bnew1+bnew22bnew=b1new+b2new2

    得到了bnewbnew我们需要更新EiEi:

Ei=∑SyjαjK(xi,xj)+bnew−yiEi=∑SyjαjK(xi,xj)+bnew−yi

    其中,S是所有支持向量xjxj的集合。

    好了,SMO算法基本讲完了,我们来归纳下SMO算法。

5. SMO算法总结

    输入是m个样本(x1,y1),(x2,y2),...,(xm,ym),(x1,y1),(x2,y2),...,(xm,ym),,其中x为n维特征向量。y为二元输出,值为1,或者-1.精度e。

    输出是近似解αα

    1)取初值α0=0,k=0α0=0,k=0

    2)按照4.1节的方法选择αk1α1k,接着按照4.2节的方法选择αk2α2k,求出新的αnew,unc2α2new,unc。

αnew,unc2=αk2+y2(E1−E2)K11+K22−2K12)α2new,unc=α2k+y2(E1−E2)K11+K22−2K12)

    3)按照下式求出αk+12α2k+1

 

αk+12=⎧⎩⎨⎪⎪Hαnew,unc2LL≤αnew,unc2>HL≤αnew,unc2≤Hαnew,unc2<Lα2k+1={HL≤α2new,unc>Hα2new,uncL≤α2new,unc≤HLα2new,unc<L

    4)利用αk+12α2k+1和αk+11α1k+1的关系求出αk+11α1k+1

    5)按照4.3节的方法计算bk+1bk+1和EiEi

    6)在精度e范围内检查是否满足如下的终止条件:

∑i=1mαiyi=0∑i=1mαiyi=0

0≤αi≤C,i=1,2...m0≤αi≤C,i=1,2...m

αk+1i=0⇒yig(xi)≥1αik+1=0⇒yig(xi)≥1

0<αk+1i<C⇒yig(xi)=10<αik+1<C⇒yig(xi)=1

αk+1i=C⇒yig(xi)≤1αik+1=C⇒yig(xi)≤1

    7)如果满足则结束,返回αk+1αk+1,否则转到步骤2)。

 

    SMO算法终于写完了,这块在以前学的时候是非常痛苦的,不过弄明白就豁然开朗了。希望大家也是一样。写完这一篇, SVM系列就只剩下支持向量回归了,胜利在望!

上一篇:【手撕】支持向量机算法(SVM)


下一篇:关于购买Redis服务器:腾讯云、阿里云还是华为云?