一．SMO算法的原理

SMO算法和以往的一些SVM改進(jìn)算法一樣，是把整個(gè)二次規(guī)劃問(wèn)題分解為很多較易處理的小問(wèn)題，所不同的是，只有SMO算法把問(wèn)題分解到可能達(dá)到的最小規(guī)模：每次優(yōu)化只處理兩個(gè)樣本的優(yōu)化問(wèn)題，并且用解析的方法進(jìn)行處理。我們將會(huì)看到，這種與眾不同的方法帶來(lái)了一系列不可比擬的優(yōu)勢(shì)。

對(duì)SVM來(lái)說(shuō)，一次至少要同時(shí)對(duì)兩個(gè)樣本進(jìn)行優(yōu)化（就是優(yōu)化它們對(duì)應(yīng)的Lagrange乘子），這是因?yàn)榈仁郊s束的存在使得我們不可能單獨(dú)優(yōu)化一個(gè)變量。

所謂“最小優(yōu)化”的最大好處就是使得我們可以用解析的方法求解每一個(gè)最小規(guī)模的優(yōu)化問(wèn)題，從而完全避免了迭代算法。

當(dāng)然，這樣一次“最小優(yōu)化”不可能保證其結(jié)果就是所優(yōu)化的Lagrange乘子的最終結(jié)果，但會(huì)使目標(biāo)函數(shù)向極小值邁進(jìn)一步。我們?cè)賹?duì)其它Lagrange乘子做最小優(yōu)化，直到所有乘子都符合KKT條件時(shí)，目標(biāo)函數(shù)達(dá)到最小，算法結(jié)束。

這樣，SMO算法要解決兩個(gè)問(wèn)題：一是怎樣解決兩個(gè)變量的優(yōu)化問(wèn)題，二是怎樣決定先對(duì)哪些Lagrange乘子進(jìn)行優(yōu)化。

二．兩個(gè)Lagrange乘子的優(yōu)化問(wèn)題（子程序takeStep）

我們?cè)谶@里不妨設(shè)正在優(yōu)化的兩個(gè)Lagrange乘子對(duì)應(yīng)的樣本正是第一個(gè)和第二個(gè)，對(duì)兩個(gè)Lagrange乘子α₁和α₂，在不改變其他乘子的情況下，它們的約束條件應(yīng)表達(dá)為正方形內(nèi)的一條線段。如圖所示：

在這條線段上求一個(gè)函數(shù)的極值，相當(dāng)于一個(gè)一維的極值問(wèn)題。我們可以把α₁用α₂表示，對(duì)α₂求無(wú)條件極值，如果目標(biāo)函數(shù)是嚴(yán)格上凹的，最小值就一定在這一極值點(diǎn)（極值點(diǎn)在區(qū)間內(nèi)）或在區(qū)間端點(diǎn)（極值點(diǎn)在區(qū)間外）。α₂確定后，α₁也就確定下來(lái)了。因此我們先找到α₂優(yōu)化區(qū)間的上下限制，再在這個(gè)區(qū)間中對(duì)α₂求最小值。

由圖1我們?nèi)菀椎玫溅?sub>2的上下限應(yīng)為：

L=max(0,α₂－α₁)，H=min(C,C+α₂ –α₁) , 若y₁與y₂異號(hào)；

L=max(0,α₂ +α₁－C), H=min(C, α₂ +α₁) ,若y₁與y₂同號(hào)；

令s=y₁y₂標(biāo)志這兩個(gè)樣本是否同類(lèi)，則有

L=max(0, α₂+sα₁－ 1/2 (s+1)C), H=min(C, α₂ +sα₁ –1/2 (s－1)C)

而α₁和α₂在本次優(yōu)化中所服從的等式約束為：

α₁＋sα₂=α⁰₁+sα⁰₂=d

下面我們推導(dǎo)求最小值點(diǎn)α₂的公式：由于只有α₁，α₂兩個(gè)變量需要考慮，目標(biāo)函數(shù)可以寫(xiě)成

Wolfe(α₁,α₂)=1/2 K₁₁α²₁+1/2 K₂₂α²₂+ sK₁₂α₁α₂ + y₁α₁v₁ +y₂α₂v₂ －α₁ －α₂+常數(shù)

其中K_ij=K(x_i,x_j) , v_i=y₃α⁰₃K_i3+…+y_lα⁰_lK_il = u_i+b⁰－ y₁α⁰₁K_1i – y₂α⁰₁K_2i

上標(biāo)為0的量表示是本次優(yōu)化之前Lagrange乘子的原值。

將α₂用α₁表示并代入目標(biāo)函數(shù)：

Wolfe（α₂）=1/2 K₁₁(d-sα₂)²+1/2 K₂₂α²₂+sK₁₂(d-sα₂) α₂

+y₁(d-sα₂)v₁ – d+sα₂+y₂α₂v₂－α₂+常數(shù)

對(duì)α₂求導(dǎo)：

dWolfe(α₂)/dα₂

=－sK₁₁(d－sα₂)+K₂₂α₂－K₁₂α₂+sK₁₂(d－sα₂)－y₂v₂+s+y₂v₂－1 ＝0

如果Wolfe函數(shù)總是嚴(yán)格上凹的，即二階導(dǎo)數(shù)K₁₁+K₂₂－2K₁₂>0, 那么駐點(diǎn)必為極小值點(diǎn)，無(wú)條件的極值點(diǎn)就為

α₂＝[s(K₁₁－K₁₂)d+y₂(v₁－v₂)＋1－s] / (K₁₁＋K₂₂－2K₁₂)

將d,v與α⁰,u之間關(guān)系代入，就得到用上一步的α⁰₂，u₁,u₂表示的α₂的無(wú)條件最優(yōu)點(diǎn)：

α₂＝[α⁰₂(K₁₁＋K₂₂－2K₁₂) +y₂(u₁－u₂＋y₂－y₁)] / (K₁₁＋K₂₂－2K₁₂)

令η=K₁₁＋K₂₂－2K₁₂為目標(biāo)函數(shù)的二階導(dǎo)數(shù)，E_i=u_i－y_i為第i個(gè)訓(xùn)練樣本的“誤差”，這個(gè)式子又可以寫(xiě)為

α₂＝α⁰₂＋y₂(E₁－E₂)/η

除非核函數(shù)K不滿足Mercer條件（也就是說(shuō)不能作為核函數(shù)），η不會(huì)出現(xiàn)負(fù)值。但η=0是可以出現(xiàn)的情況。這時(shí)我們計(jì)算目標(biāo)函數(shù)在線段兩個(gè)端點(diǎn)上的取值，并將Lagrange乘子修正到目標(biāo)函數(shù)較小的端點(diǎn)上：

f₁=y₁(E₁+b)－α₁K(x₁,x₁)-－sα₂K(x₁,x₁)

f₂=y₂(E₂+b)－sα₁K(x₁,x₂)-－α₂K(x₂,x₂)

L₁=α₁+s(α₂－L)

H₁=α₁+s(α₂－H)

WolfeL=L₁f₁+Lf₂+1/2 L²₁K(x₁,x₁)+1/2 L²K(x₂,x₂)+sLL₁K(x₁,x₂)

WolfeH=H₁f₁+Hf₂+1/2 H²₁K(x₁,x₁)+1/2 H²K(x₂,x₂)+sHH₁K(x₁,x₂)

當(dāng)兩個(gè)端點(diǎn)上取得相同的目標(biāo)函數(shù)值時(shí)，目標(biāo)函數(shù)在整條線段上的取值都會(huì)是一樣的（因?yàn)樗巧习嫉?#xff09;，這時(shí)不必對(duì)α₁，α₂作出修正。

α₂的無(wú)條件極值確定后，再考慮上下限的限制，最終的α₂為

最后，由等式約束確定α₁：

α₁^*=α₁+s(α₂－α₂^*)

三．選擇待優(yōu)化Lagrange乘子的試探找點(diǎn)法

事實(shí)上即使我們不采用任何找點(diǎn)法，只是按順序抽取α_i，α_j的所有組合進(jìn)行優(yōu)化，目標(biāo)函數(shù)也會(huì)不斷下降，直到任一對(duì)α_i，α_j都不能繼續(xù)優(yōu)化，目標(biāo)函數(shù)就會(huì)收斂到極小值。我們采取某種找點(diǎn)方法只是為了使算法收斂得更快。

這種試探法先選擇最有可能需要優(yōu)化的α₂，再針對(duì)這樣的α₂選擇最有可能取得較大修正步長(zhǎng)的α₁。這樣，我們?cè)诔绦蛑惺褂脙蓚€(gè)層次的循環(huán)：

內(nèi)層循環(huán)（子程序examineExample）針對(duì)違反KKT條件的樣本選擇另一個(gè)樣本與它配對(duì)優(yōu)化（指優(yōu)化它們的Lagrange乘子），選擇的依據(jù)是盡量使這樣一對(duì)樣本能取得最大優(yōu)化步長(zhǎng)。對(duì)其中一個(gè)Lagrange乘子α₂來(lái)說(shuō)優(yōu)化步長(zhǎng)為|(E₁－E₂)/η|,但由于核函數(shù)估算耗時(shí)較大，我們只用|E₁－E₂|來(lái)大致估計(jì)有可能取得的步長(zhǎng)大小。也就是說(shuō)，選出使得|E₁－E₂|最大的樣本作為第二個(gè)樣本。需要注意的是，這樣的步長(zhǎng)估計(jì)是比較粗略的，選擇出來(lái)的一對(duì)樣本有時(shí)非但不能“一勞永逸”地“一步到位”，反而不能作出進(jìn)一步調(diào)整，（例如η=0的情況，最小優(yōu)化問(wèn)題的二次型只是半正定的）。這時(shí)我們遍歷所有非邊界樣本（非邊界樣本就是Lagrange乘子不在邊界0或C上的樣本），繼續(xù)尋找能與α₂配對(duì)優(yōu)化的α₁，如果這樣的樣本在非邊界樣本中找不到，再遍歷所有樣本。這兩次遍歷都是從隨機(jī)位置開(kāi)始的，以免算法總是在一開(kāi)始遍歷就向固定的方向偏差。在極端退化的情形，找不到與α₂配對(duì)能作出進(jìn)一步調(diào)整的α₁，這時(shí)我們放棄第一個(gè)樣本。

外層循環(huán)（主程序smo）遍歷非邊界樣本或所有樣本：優(yōu)先選擇遍歷非邊界樣本，因?yàn)榉沁吔鐦颖靖锌赡苄枰{(diào)整，而邊界樣本常常不能得到進(jìn)一步調(diào)整而留在邊界上（可以想象大部分樣本都很明顯不可能是支持向量，它們的Lagrange乘子一旦取得零值就無(wú)需再調(diào)整）。循環(huán)遍歷非邊界樣本并選出它們當(dāng)中違反KKT條件的樣本進(jìn)行調(diào)整，直到非邊界樣本全部滿足KKT條件為止。當(dāng)某一次遍歷發(fā)現(xiàn)沒(méi)有非邊界樣本得到調(diào)整時(shí)，就遍歷所有樣本，以檢驗(yàn)是否整個(gè)集合也都滿足KKT條件。如果在整個(gè)集合的檢驗(yàn)中又有樣本被進(jìn)一步優(yōu)化，就有必要再遍歷非邊界樣本。這樣，外層循環(huán)不停地在“遍歷所有樣本”和“遍歷非邊界樣本”之間切換，直到整個(gè)訓(xùn)練集都滿足KKT條件為止。

以上用KKT條件對(duì)樣本所作檢驗(yàn)都是達(dá)到一定精度就可以了，例如正側(cè)的非邊界樣本的輸出u_i可以在1的一定公差范圍之內(nèi)，通常這一公差（tolerance）取0.001，如果要求十分精確的輸出算法就不能很快收斂。

四．每次最小優(yōu)化后的重置工作

每做完一次最小優(yōu)化，必須更新每個(gè)樣本的誤差（Error Cache），以便用修正過(guò)的分類(lèi)面對(duì)其它樣本再做KKT檢驗(yàn)，以及選擇第二個(gè)配對(duì)優(yōu)化樣本時(shí)估計(jì)步長(zhǎng)之用。

更新Error Cache首先要重置閾值b 。我們可直接利用剛剛被優(yōu)化的兩個(gè)樣本的信息在原閾值b₀基礎(chǔ)上作簡(jiǎn)單修正，而不需要調(diào)用所有支持向量重新計(jì)算b 。最小優(yōu)化后的α₁^*如果不在邊界上，b的計(jì)算公式為：

b₁=E₁+y₁(α₁^*－α₁⁰)K(x₁,x₁)+y₂(α₂^*－α₂⁰)K(x₁,x₂)+b₀

最小優(yōu)化后的α₂^*如果不在邊界上，b的計(jì)算公式為：

b₂=E₂+y₁(α₁^*－α₁⁰)K(x₁,x₂)+y₂(α₂^*－α₂⁰)K(x₂,x₂)+b₀

α₁^*，α₂^*都不在邊界上時(shí)，b₁和b₂是相等的。兩個(gè)Lagrange乘子都在邊界上時(shí)，b₁和b₂以及它們之間的數(shù)都可作為符合KKT條件的閾值。這時(shí)SMO算法選擇最安全的b₁ ，b₂之中點(diǎn)作為閾值。

非線性的情況，誤差的計(jì)算要用到所有已找到的支持向量及它們的Lagrange乘子：

線性的情況則是先重置分類(lèi)超平面的法向量w，再根據(jù)u_j=w’x_j-b計(jì)算輸出u_j和誤差E_j=u_j－y_j 。同閾值的重置一樣，法向量的重置也不需要調(diào)用所有的支持向量，只需在原來(lái)的法向量基礎(chǔ)上作改動(dòng)：

w^*=w+y₁(α₁^*－α₁)x₁+y₂(α₂^*－α₂)x₂

大部分重置工作都是以簡(jiǎn)單的非循環(huán)計(jì)算來(lái)完成的，這使得需要做很多次最小優(yōu)化的SMO算法不必在每次優(yōu)化后的重置中花費(fèi)太多時(shí)間。但是我們也看到，非線性的情況誤差的重置必須與所有支持向量逐個(gè)計(jì)算核函數(shù)，而且核函數(shù)的計(jì)算本身就比點(diǎn)積復(fù)雜，于是非線性的情況誤差的重置將成為算法速度的瓶頸。

四、算法的流程圖

五、Platt大神的邏輯代碼

六、源代碼的實(shí)現(xiàn)

未完，待續(xù)……

轉(zhuǎn)載于:https://www.cnblogs.com/machinelearner/archive/2013/03/28/2987509.html

總結(jié)

以上是生活随笔為你收集整理的手把手教你实现SVM算法（二）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。