在SVM的前三篇裡，我們優化的目标函數最終都是一個關于 α α 向量的函數。而怎麼極小化這個函數，求出對應的 α α 向量，進而求出分離超平面我們沒有講。本篇就對優化這個關于 α α 向量的函數的SMO算法做一個總結。
回顧SVM優化目标函數
我們首先回顧下我們的優化目标函數：
minα12∑i=1m∑j=1mαiαjyiyjK(xi,xj)−∑i=1mαis.t.∑i=1mαiyi=00≤αi≤C m i n ⏟ α 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j K ( x i , x j ) − ∑ i = 1 m α i s . t . ∑ i = 1 m α i y i = 0 0 ≤ α i ≤ C
我們的解要滿足的KKT條件的對偶互補條件為：
α∗i(yi(wTxi+b)−1)=0(1) (1) α i ∗ ( y i ( w T x i + b ) − 1 ) = 0
根據這個KKT條件的對偶互補條件，我們有：
α∗i=0⇒yi(w∗∙ϕ(xi)+b)−1)≥10<α∗i<C⇒yi(w∗∙ϕ(xi)+b)−1)=1α∗i=C⇒yi(w∗∙ϕ(xi)+b)−1)≤1(2) (2) α i ∗ = 0 ⇒ y i ( w ∗ ∙ ϕ ( x i ) + b ) − 1 ) ≥ 1 0 < α i ∗ < C ⇒ y i ( w ∗ ∙ ϕ ( x i ) + b ) − 1 ) = 1 α i ∗ = C ⇒ y i ( w ∗ ∙ ϕ ( x i ) + b ) − 1 ) ≤ 1
由于 w∗=∑j=1mα∗jyjϕ(xj) w ∗ = ∑ j = 1 m α j ∗ y j ϕ ( x j ) ，我們令 g(x)=w∗∙ϕ(x)+b=∑j=1mα∗iyjK(x,xj)+b∗ g ( x ) = w ∗ ∙ ϕ ( x ) + b = ∑ j = 1 m α i ∗ y j K ( x , x j ) + b ∗ ，則有：
α∗i=0⇒yig(xi)≥10<α∗i<C⇒yig(xi)=1α∗i=C⇒yig(xi)≤1(3) (3) α i ∗ = 0 ⇒ y i g ( x i ) ≥ 1 0 < α i ∗ < C ⇒ y i g ( x i ) = 1 α i ∗ = C ⇒ y i g ( x i ) ≤ 1
SMO算法的基本思想
上面這個優化式子比較複雜，裡面有m個變量組成的向量 α α 需要在目标函數極小化的時候求出。直接優化時很難的。SMO算法則采用了一種啟發式的方法。它每次隻優化兩個變量，将其他的變量都視為常數。由于 ∑i=1mαiyi=0 ∑ i = 1 m α i y i = 0 .假如将 α3,α4,...,αm α 3 , α 4 , . . . , α m 固定，那麼 α1,α2 α 1 , α 2 之間的關系也确定了。這樣SMO算法将一個複雜的優化算法轉化為一個比較簡單的兩變量優化問題。
為了後面表示友善，我們定義 Kij=ϕ(xi)∙ϕ(xj) K i j = ϕ ( x i ) ∙ ϕ ( x j )
由于 α3,α4,...,αm α 3 , α 4 , . . . , α m 都成了常量，所有的常量我們都從目标函數去除，這樣我們上一節的目标優化函數變成下式：
minα1,α212K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3myiαiKi1+y2α2∑i=3myiαiKi2s.t.α1y1+α2y2=−∑i=3myiαi=常數ς0≤αi≤Ci=1,2(1)(2)(3) m i n ⏟ α 1 , α 2 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 m y i α i K i 1 (1) + y 2 α 2 ∑ i = 3 m y i α i K i 2 (2) s . t . α 1 y 1 + α 2 y 2 = − ∑ i = 3 m y i α i = 常 數 ς (3) 0 ≤ α i ≤ C i = 1 , 2
SMO算法目标函數的優化
本部分的總體思路：首先将目标函數看作是一個關于 α1,α2 α 1 , α 2 的二進制二次函數 W(α1,α2) W ( α 1 , α 2 ) ，然後通過條件 α1y1+α2y2=ς α 1 y 1 + α 2 y 2 = ς 将目标函數轉化為一個關于 α2 α 2 的一進制二次函數 W(α2) W ( α 2 ) ，我們的最終目标是求出 W(α2) W ( α 2 ) 在參數 α2 α 2 可行域範圍内的函數最小值。
下文第一部分先求出 W(α2) W ( α 2 ) 的極值點 αnew,unclipped2 α 2 n e w , u n c l i p p e d 。下文第二部分根據限制條件
( α1y1+α2y2=ς,0≤αi≤Ci=1,2 α 1 y 1 + α 2 y 2 = ς , 0 ≤ α i ≤ C i = 1 , 2 ）求出 α2 α 2 的可行域。下文第三部分，分類讨論一進制二次函數 W(α2) W ( α 2 ) 的最優解 α∗2 α 2 ∗ 在 α2 α 2 的可行域邊界取得還是在極值點取得。第四部分通過 α1,α2 α 1 , α 2 的關系，由 α2 α 2 求出 α1 α 1 .
1. 不考慮限制條件（ α1y1+α2y2=ς,0≤αi≤Ci=1,2 α 1 y 1 + α 2 y 2 = ς , 0 ≤ α i ≤ C i = 1 , 2 ），對目标函數求極值點
首先我們的目标函數是一個二進制二次函數：
W(α1,α2)=12K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3myiαiKi1+y2α2∑i=3myiαiKi2=12K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1v1+y2α2v2(4)(5)(6) (4) W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) (5) + y 1 α 1 ∑ i = 3 m y i α i K i 1 + y 2 α 2 ∑ i = 3 m y i α i K i 2 (6) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 − ( α 1 + α 2 ) + y 1 α 1 v 1 + y 2 α 2 v 2
其中
⎧⎩⎨⎪⎪⎪⎪⎪⎪⎪⎪vi=∑j=3myjαjKij=g(xi)−∑j=12yjajkij−b,i=1,2g(x)=w∙ϕ(x)+b=∑j=1mαiyjK(x,xj)+b(4) (4) { v i = ∑ j = 3 m y j α j K i j = g ( x i ) − ∑ j = 1 2 y j a j k i j − b , i = 1 , 2 g ( x ) = w ∙ ϕ ( x ) + b = ∑ j = 1 m α i y j K ( x , x j ) + b
由于 α1y1+α2y2=ς α 1 y 1 + α 2 y 2 = ς ，并且 y2i=1 y i 2 = 1 ，可以得到用 α2 α 2 表達 α1 α 1 的式子：
α1=y1(ς−α2y2)(7) (7) α 1 = y 1 ( ς − α 2 y 2 )
将上式帶入我們的目标優化函數，就可以消除 α1 α 1 ，得到僅僅包含 α2 α 2 的式子為：
W(α2)=12K11(ς−a2y2)2+12K22α22+y2K12(ς−a2y2)α2−(y1(ς−α2y2)+α2)+(ς−a2y2)v1+y2α2v2(8)(9) (8) W ( α 2 ) = 1 2 K 11 ( ς − a 2 y 2 ) 2 + 1 2 K 22 α 2 2 + y 2 K 12 ( ς − a 2 y 2 ) α 2 − ( y 1 ( ς − α 2 y 2 ) + α 2 ) (9) + ( ς − a 2 y 2 ) v 1 + y 2 α 2 v 2
顯然 W(α2) W ( α 2 ) 是一個一進制二次方程，最優解 α∗2 α 2 ∗ 隻能是限制條件（ 0≤αi≤C 0 ≤ α i ≤ C ）規定的可行域的邊界值，或者是 W(α2) W ( α 2 ) 的極值點。現在我們先對其求極值點，即對 α2 α 2 求導并令為0得：
∂W(α2)∂α2=(K11+K22−2K12)α2−K11ςy2+K12ςy2+y1y2−1−v1y2+v2y2=0(10)(5) (10) ∂ W ( α 2 ) ∂ α 2 = ( K 11 + K 22 − 2 K 12 ) α 2 − K 11 ς y 2 + K 12 ς y 2 + y 1 y 2 − 1 (5) − v 1 y 2 + v 2 y 2 = 0
這時候我們定義 Ei E i 表示預測值 g(xi) g ( x i ) 與真實值 yi y i 之差：
Ei=g(xi)−yi(6) (6) E i = g ( x i ) − y i
這時我們記優化前的解為 αold1,αold2 α 1 o l d , α 2 o l d ，優化後的解為 αnew1,αnew2 α 1 n e w , α 2 n e w ，由限制條件 ∑i=1myiαi=0 ∑ i = 1 m y i α i = 0 ，有 αold1y1+αold2y2=αnew1y1+αnew1y2=ς α 1 o l d y 1 + α 2 o l d y 2 = α 1 n e w y 1 + α 1 n e w y 2 = ς ，即
αnew1y1+αnew1y2=ς(7) (7) α 1 n e w y 1 + α 1 n e w y 2 = ς
進行下一步化簡，将式子（4）（6）（7）代入式子（5），此時求解出的 αnew2 α 2 n e w 未考慮限制條件（ 0≤αi≤C 0 ≤ α i ≤ C ），先記為 αnew,unclipped2 α 2 n e w , u n c l i p p e d ：
(K11+K22−2K12)αnew,unclipped2=(K11+K22−2K12)αold2+y2(E1−E2)(8) (8) ( K 11 + K 22 − 2 K 12 ) α 2 n e w , u n c l i p p e d = ( K 11 + K 22 − 2 K 12 ) α 2 o l d + y 2 ( E 1 − E 2 )
我們終于得到了 αnew,unclipped2 α 2 n e w , u n c l i p p e d 的表達式：
αnew,unclipped2=αold2+y2(E1−E2)K11+K22−2K12(9) (9) α 2 n e w , u n c l i p p e d = α 2 o l d + y 2 ( E 1 − E 2 ) K 11 + K 22 − 2 K 12
2. 由限制條件（ α1y1+α2y2=ς,0≤αi≤Ci=1,2 α 1 y 1 + α 2 y 2 = ς , 0 ≤ α i ≤ C i = 1 , 2 ）求出 α2 α 2 的可行域
上面求出的 αnew,unclipped2 α 2 n e w , u n c l i p p e d 沒考慮到的限制條件為：
{0≤αi=1,2≤Cα1y1+α2y2=ς { 0 ≤ α i = 1 , 2 ≤ C α 1 y 1 + α 2 y 2 = ς
在二維平面上直覺表達上述兩個限制條件 ：
根據式子 α1y1+α2y2=ς α 1 y 1 + α 2 y 2 = ς ，和 y1,y2 y 1 , y 2 隻能取值 +1或−1 + 1 或 − 1 ，共有四種情況：
（1）當 y1=1,y2=1 y 1 = 1 , y 2 = 1 ，此時的表達式為 α1y1+α2y2=ς α 1 y 1 + α 2 y 2 = ς ，那麼對應上圖中的右邊情況。根據 ς ς 的不同取值，我們可以分為下面幾種情況來求 α2 α 2 的可行域：
- ς<0 ς < 0 ，因為 0≤αi≤C 0 ≤ α i ≤ C ，是以此時 α1y1+α2y2=ς α 1 y 1 + α 2 y 2 = ς 與方形區域一定沒有任何交集，是以此時 α2 α 2 的可行域為空集.
- ς=0 ς = 0 ，此時 α1y1+α2y2=0 α 1 y 1 + α 2 y 2 = 0 ，此時與方形區域的交點就是(0,0)，那麼可行域就是 α2=0 α 2 = 0 .
- 0≤ς≤C 0 ≤ ς ≤ C 時，此時對應上圖中右邊的靠下的那種直線的情況，是以根據直線和方形區域的相交情況，此時可以求出 α2 α 2 的可行區間為 [0,ς] [ 0 , ς ] ，即 [0,α1+α2] [ 0 , α 1 + α 2 ] .
- 當 C≤ς≤2C C ≤ ς ≤ 2 C 時，可以求出此時對應上圖右邊情況靠上的那種直線，是以此時可以求出的可行區間為 [ς−C,C]，即[α1+α2−C,C] [ ς − C , C ] ， 即 [ α 1 + α 2 − C , C ]
- 當 ς≥2C ς ≥ 2 C 時，可行域為空寂，且這種情況也不會發生。
綜上所述，當 y1=1且y2=1 y 1 = 1 且 y 2 = 1 時，此時的 α2 α 2 可行域在存在的情況下（即不考慮 ς<0、ς≥2C ς < 0 、 ς ≥ 2 C ），其實可以這樣表示它的區間：
[max(0,α1+α2−C),min(C,α1+α2)] [ m a x ( 0 , α 1 + α 2 − C ) , m i n ( C , α 1 + α 2 ) ]
（2）當 y1=−1且y2=−1 y 1 = − 1 且 y 2 = − 1 時，此時的表達式是 α1+α2=−ς α 1 + α 2 = − ς ，那麼首先此時的 ς≤0 ς ≤ 0 ，此時的各種分類其情況和上面的（1）類似。
（3）當 y1=1且y2=−1 y 1 = 1 且 y 2 = − 1 時，此時的表達式是 α1−α2=ς α 1 − α 2 = ς ，根據 ς ς 的不同取值，我們可以分為下面幾種情況來求 α2 α 2 的可行域：
- ς>C或者ς<−C ς > C 或 者 ς < − C 時，此時直線與方形區域沒有交點，是以此時 α2 α 2 可行域為空集.
- 0<ς≤C 0 < ς ≤ C 時，此時對應上面的左圖中的靠下的那種直線的情況，此時可以計算出 α2的可行域為[0，C−α1+α2] α 2 的 可 行 域 為 [ 0 ， C − α 1 + α 2 ] .
- 當 −C≤ς≤0 − C ≤ ς ≤ 0 時，此時對應左圖中靠上的那種直線的情況，此時可計算出 alpha2的可行域為[α2−α1,C] a l p h a 2 的 可 行 域 為 [ α 2 − α 1 , C ]
綜上所述， α2的可行域為[max(0,α1−α2),min(C,C−α2+α2)] α 2 的 可 行 域 為 [ m a x ( 0 , α 1 − α 2 ) , m i n ( C , C − α 2 + α 2 ) ]
（4）當 y1=−1且y2=1 y 1 = − 1 且 y 2 = 1 時，情況和（3）類似。
我們設 α2 α 2 的可行域為 α2∈[L,H] α 2 ∈ [ L , H ] ，結合上述（1）~（4）種情況，我們得出不同情況下 α2 α 2 可行域的邊界值L、H：
- 當y1≠y2時，L=max（0,αold2−αold1）；H=min(C,C+αold2−αold1) 當 y 1 ≠ y 2 時 ， L = m a x （ 0 , α 2 o l d − α 1 o l d ） ； H = m i n ( C , C + α 2 o l d − α 1 o l d )
- 當y1=y2時，L=max（0,αold1+αold2−C）；H=min(C,αold2+αold1) 當 y 1 = y 2 時 ， L = m a x （ 0 , α 1 o l d + α 2 o l d − C ） ； H = m i n ( C , α 2 o l d + α 1 o l d )
3. 對 αnew,unclipped2 α 2 n e w , u n c l i p p e d 進行修剪
好了，目前為止我們手頭上有一進制二次函數 W(α2) W ( α 2 ) 的極值點 αnew,unclipped2 α 2 n e w , u n c l i p p e d ，和 α2 α 2 的可行域的邊界值L，H。
下文根據 α2 α 2 的可行域和一進制二次函數 W(α2) W ( α 2 ) 的開口方向，讨論 W(α2) W ( α 2 ) 在何處取得最小值，共分為3種情況：
（1）無論一進制二次函數 W(α2) W ( α 2 ) 的開口向上還是向下，隻要極值點不在可行域内，該函數的最小值就在可行域的邊界值取得，這種情況我們隻需要比較 W(L)和W(H) W ( L ) 和 W ( H ) 的大小，然後取小者就是函數的最小值。
（2）如果 W(α2) W ( α 2 ) 的開口向上，且極值點在可行域内，則函數最小值為極值點。
（3）如果 W(α2) W ( α 2 ) 的開口向下，該函數的最小值就在可行域的邊界值取得，這種情況我們隻需要比較 W(L)和W(H) W ( L ) 和 W ( H ) 的大小，然後取小者就是函數的最小值。
綜合上述三種情況，就可以對 αnew,unclipped2 α 2 n e w , u n c l i p p e d 進行修剪了，最優解就可以記為 αnew2 α 2 n e w ：
αnew2=⎧⎩⎨⎪⎪⎪⎪Hαnew,unclipped2Lαnew,unclipped2>HL≤αnew,unclipped2≤Hαnew,unclipped2<L α 2 n e w = { H α 2 n e w , u n c l i p p e d > H α 2 n e w , u n c l i p p e d L ≤ α 2 n e w , u n c l i p p e d ≤ H L α 2 n e w , u n c l i p p e d < L
4. 通過 αnew2 α 2 n e w 求解 αnew1 α 1 n e w
由 αold1y1+αold2y2=αnew1y1+αnew2y2=ς α 1 o l d y 1 + α 2 o l d y 2 = α 1 n e w y 1 + α 2 n e w y 2 = ς 得：
αnew1=αold1+y1y2(αold2−αnew2)(11) (11) α 1 n e w = α 1 o l d + y 1 y 2 ( α 2 o l d − α 2 n e w )
SMO算法兩個變量的選擇
1.第一個變量的選擇
第一個變量的選擇稱為外循環，首先周遊整個樣本集，選擇違反KKT條件的 αi α i 作為第一個變量，接着依據相關規則選擇第二個變量(見下面分析),對這兩個變量采用上述方法進行優化。當周遊完整個樣本集後，周遊非邊界樣本集 (0<αi<C) ( 0 < α i < C ) 中違反KKT的 αi α i 作為第一個變量，同樣依據相關規則選擇第二個變量，對此兩個變量進行優化。當周遊完非邊界樣本集後，再次回到周遊整個樣本集中尋找，即在整個樣本集與非邊界樣本集上來回切換，尋找違反KKT條件的 αi α i 作為第一個變量。直到周遊整個樣本集後，沒有違反KKT條件 αi α i ，然後退出。
邊界上的樣本對應的 αi=0 α i = 0 或者 αi=C α i = C ，在優化過程中很難變化。然而非邊界樣本 (0<αi<C) ( 0 < α i < C ) 會随着對其他變量的優化會有大的變化。
2.第二個變量的選擇
SMO稱第二個變量的選擇過程為内循環，假設在外循環中找個第一個變量記為 α1 α 1 ，第二個變量的選擇希望能使 α2 α 2 有較大的變化，由于 α1 α 1 是依賴于 |E1−E2| | E 1 − E 2 | ，當 E1 E 1 為正時，那麼選擇最小的 Ei E i 作為 E2 E 2 。如果 E1 E 1 為負，選擇最大 Ei E i 作為 E2 E 2 ，通常為每個樣本的 Ei E i 儲存在一個清單中，選擇最大的 |E1−E2| | E 1 − E 2 | 來近似最大化步長。
有時按照上述的啟發式選擇第二個變量，不能夠使得函數值有足夠的下降，這時按下述步驟:
首先在非邊界集上選擇能夠使函數值足夠下降的樣本作為第二個變量；
如果非邊界集上沒有，則在整個樣本集上選擇第二個變量；
如果整個樣本集依然不存在，則重新選擇第一個變量；
計算門檻值 bnew b n e w 、內插補點 Ei E i
每完成對兩個變量的優化後，要對b的值進行更新，因為b的值關系到預測值 g(x) g ( x ) 的計算，即關系到下次優化時 Ei E i 的計算。
求解 bnew b n e w 的4種情況
1. 如果 0<αnew1<C 0 < α 1 n e w < C ，由KKT條件 y1(wTx1+b)=1 y 1 ( w T x 1 + b ) = 1 ，且 y2i=1 y i 2 = 1 ，得到 ∑i=1mαiyiKi1+b=yi ∑ i = 1 m α i y i K i 1 + b = y i ，所有有：
bnew1=y1−∑i=3mαiyiKi1−αnew1y1K11−αnew2y2K21(12) (12) b 1 n e w = y 1 − ∑ i = 3 m α i y i K i 1 − α 1 n e w y 1 K 11 − α 2 n e w y 2 K 21
将式子（6）代入上式子，得：
bnew1=−E1−y1K11(αnew1−αold1)−y2K21(αnew2−αold2)+bold(13) (13) b 1 n e w = − E 1 − y 1 K 11 ( α 1 n e w − α 1 o l d ) − y 2 K 21 ( α 2 n e w − α 2 o l d ) + b o l d
2. 如果 0<αnew2<C 0 < α 2 n e w < C ，則：
bnew2=−E2−y1K12(αnew1−αold1)−y2K22(αnew2−αold2)+bold(14) (14) b 2 n e w = − E 2 − y 1 K 12 ( α 1 n e w − α 1 o l d ) − y 2 K 22 ( α 2 n e w − α 2 o l d ) + b o l d
3. 如果 α1,α2 α 1 , α 2 同時滿足 0<αnewi<C 0 < α i n e w < C ，則：
bnew1=bnew2(15) (15) b 1 n e w = b 2 n e w
4. 如果 α1,α2 α 1 , α 2 同時不滿足 0<αnew1,2<C 0 < α 1 , 2 n e w < C ，那麼 bnew1 b 1 n e w 和 bnew2 b 2 n e w 以及它們之間的數都是符合KKT條件的門檻值，這時選擇它們的中點作為 bnew b n e w
更新內插補點 Ei E i
根據式子(4),(6），得到：
Ei=g(xi)−yi=∑j=1mαiyjK(x,xj)+bnew−yi(16) (16) E i = g ( x i ) − y i = ∑ j = 1 m α i y j K ( x , x j ) + b n e w − y i
SMO算法總結
輸入是m個樣本 (x1,y1),(x2,y2),...,(xm,ym) ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) ，其中 x x 為 n n 維特征向量。y為二進制輸出，值為+1或-1。精度e.
輸出值是近似解，向量 α α .
1) 取初值 α0=0,k=0 α 0 = 0 , k = 0 ， α α 的上标表示疊代輪數， k k 表示目前疊代為第 k k 輪.
2) 按照上文的方法依次選取兩個參數 αk1,αk2 α 1 k , α 2 k ，求出新的 αk+1,unclipped2 α 2 k + 1 , u n c l i p p e d .
αk+1,unclipped2=αk2+y2(E1−E2)K11+K22−2K12 α 2 k + 1 , u n c l i p p e d = α 2 k + y 2 ( E 1 − E 2 ) K 11 + K 22 − 2 K 12
3)求出 α2 α 2 可行域的邊界值 L，H：
L,H={當y1≠y2時，L=max（0,αk2−αk1）；H=min(C,C+αk2−αk1)當y1=y2時，L=max（0,αk1+αk2−C）；H=min(C,αk2+αk1) L , H = { 當 y 1 ≠ y 2 時 ， L = m a x （ 0 , α 2 k − α 1 k ） ； H = m i n ( C , C + α 2 k − α 1 k ) 當 y 1 = y 2 時 ， L = m a x （ 0 , α 1 k + α 2 k − C ） ； H = m i n ( C , α 2 k + α 1 k )
3)對 αk+1,unclipped2 α 2 k + 1 , u n c l i p p e d 進行修剪：
αk+12=⎧⎩⎨⎪⎪⎪⎪Hαk+1,unclipped2Lαk+1,unclipped2>HL≤αk+1,unclipped2≤Hαk+1,unclipped2<L α 2 k + 1 = { H α 2 k + 1 , u n c l i p p e d > H α 2 k + 1 , u n c l i p p e d L ≤ α 2 k + 1 , u n c l i p p e d ≤ H L α 2 k + 1 , u n c l i p p e d < L
4)求出 αk+11 α 1 k + 1 ：
αk+11=αk1+y1y2(αk2−αk+12)(17) (17) α 1 k + 1 = α 1 k + y 1 y 2 ( α 2 k − α 2 k + 1 )
5)按照上文的規則，求出 bk+1 b k + 1 ，并更新 Ei E i ：
Ei=g(xi)−yi=∑j=1mαiyjK(x,xj)+bk+1−yi(18) (18) E i = g ( x i ) − y i = ∑ j = 1 m α i y j K ( x , x j ) + b k + 1 − y i
6)轉至步驟2)，進入下一輪優化。直到周遊整個樣本集後，沒有違反KKT條件 αi α i ，然後退出算法。
參考資料
1.支援向量機原理(四)SMO算法原理
2.第三部分：SMO算法的個人了解
3.【機器學習詳解】SMO算法剖析