支持向量機原理詳解(七): 序列最小最優化(SMO)演算法(Part II)

接前文序列最小最優化(SMO)演算法(Part I)，本文繼續介紹SMO演算法，內容如下：

閾值的更新
差值的更新，Error Cache
SMO演算法流程總結

10.5 閾值的更新

前文提到，通過求解兩變數QP子問題得到的最優解 $alpha_1^{new}, alpha_2^{new}$ 未必滿足KKT條件：

$egin{align} alpha_i = 0 &Rightarrow y_id_igeq 1\ 0< alpha_i < C &Rightarrow y_id_i = 1\ alpha_i = C &Rightarrow y_id_ileq 1\ end{align}$

為此，在每一步優化完兩個變數 (得到 $alpha_1^{new}, alpha_2^{new}$ )後，都要更新 $d_i=sum_{j=1}^{N}{y_j alpha_j k_{ji}} + b$ 中的閾值 ，目的是使剛才這一步優化的兩個樣本 滿足KKT條件。

關於的更新，需要根據 $alpha_1^{new}, alpha_2^{new}$ 的取值分情況討論，具體如下：

(一)若 $0<alpha_1^{new}<C$

則根據KKT條件 $y_1 d_1 = y_1 left( sum_{j=1}^{N}{y_j k_{j1}alpha_j} + b ight)=1$ 來更新，此時有

$b_1^{new}=y_1-sum_{j=3}^{N}{y_j k_{j1} alpha_j^{old}} - y_1 k_{11} alpha_1^{new}- y_2 k_{21} alpha_2^{new}$

又因為 $E_1^{old} = d_1^{old}-y_1= sum_{j=1}^{N}{y_j k_{j1} alpha_j^{old}} +b^{old}- y_1$ ，代入上式得

$egin{align} b_1^{new}&=-E_1^{old}+ y_1 k_{11} alpha_1^{old}+ y_2 k_{21} alpha_2^{old}- y_1 k_{11} alpha_1^{new}- y_2 k_{21} alpha_2^{new}+b^{old}\ &=-E_1^{old}- y_1 k_{11} left(alpha_1^{new}-alpha_1^{old} ight)- y_2 k_{21} left( alpha_2^{new}- alpha_2^{old} ight)+b^{old} ag{1} \ end{align}$

按(1)式更新後，滿足KKT條件；此時另一個樣本也是滿足KKT條件的。這一點可結合下面第(三)種情況的 $b_1^{new}=b_2^{new}$ 來說明：若 $0<alpha_1^{new}<C, alpha_2^{new}inleft{ 0,C ight}$ ，則根據 $alpha_2^{new}$ 的KKT條件，應有 $b_2^{new}leq b_1^{new}$ 或 $b_2^{new}geq b_1^{new}$ ，也就是說 $b_1^{new}$ 也能使 $alpha_2^{new}$ 對應的樣本滿足KKT條件。所以當 $0<alpha_1^{new}<C$ 時，按(1)式更新即可，不需要再根據 $alpha_2^{new}$ 的值進一步討論。

(二)若 $0<alpha_2^{new}<C$

則根據 $y_2 d_2 = y_2 left( sum_{j=1}^{N}{y_j alpha_j k_{j2}} + b ight)=1$ 來更新，和(一)類似，有

$egin{align} b_2^{new}=-E_2^{old}- y_1 k_{12} left(alpha_1^{new}-alpha_1^{old} ight)- y_2 k_{22} left( alpha_2^{new}- alpha_2^{old} ight)+b^{old} ag{2}\ end{align}$

(三)若 $0<alpha_1^{new}<C quad and quad 0<alpha_2^{new}<C$

則(1)和(2)計算出的 $b_1^{new}=b_2^{new}$ 。

關於 $b_1^{new},b_2^{new}$ 為何相等，參考文獻[1-4]均省略了推導。這裡我們來證明一下。

首先， $alpha_1^{new}, alpha_2^{new}$ 均不在邊界上，說明 $alpha_2^{new}$ 未經過修剪， $alpha_2^{new}=alpha_2^{unclipped}$ ；因為如果修剪過，則 $alpha_1^{new}, alpha_2^{new}$ 至少有一個在邊界上。

然後，由兩變數QP子問題的等式約束(見前文)有：

$alpha_1^{new} - alpha_1^{old}=-y_1y_2left( alpha_2^{new}-alpha_2^{old} ight)$

將上式代入(1)和(2)，同時結合前文的(6)式，有

$egin{align} &b_1^{new}=b_2^{new}\ &Leftrightarrow -E_1^{old}+ y_2 k_{11} left(alpha_2^{new}-alpha_2^{old} ight)- y_2 k_{21} left( alpha_2^{new}- alpha_2^{old} ight)\ & =-E_2^{old}+ y_2 k_{12} left(alpha_2^{new}-alpha_2^{old} ight)- y_2 k_{22} left( alpha_2^{new}- alpha_2^{old} ight)\ &Leftrightarrow y_2left( k_{11}+k_{22}-2k_{12} ight) left(alpha_2^{new}-alpha_2^{old} ight) = E_1^{old}-E_2^{old}\ &Leftrightarrow alpha_2^{new}=alpha_2^{old}+frac{y_2left( E_1^{old}-E_2^{old} ight)}{k_{11}+k_{22}-2k_{12}}\ &Leftrightarrow alpha_2^{new}=alpha_2^{unclipped} ag{3}end{align}$

(3)式成立，所以 $b_1^{new}=b_2^{new}$ 得證。

(四)若 $alpha_1^{new}, alpha_2^{new}in left{ 0, C ight} quad and quad L e H$

則 $b_1^{new},b_2^{new}$ 之間的值都能使兩個樣本滿足KKT條件，取 $b^{new} = frac{1}{2}left( b_1^{new}+b_2^{new} ight)$ 。

至於為什麼 $b_1^{new},b_2^{new}$ 之間的值都能使兩個樣本滿足KKT條件，參考文獻也都沒有解釋。這裡我們來推導一下。

(實際上，Platt1998, 1999里給出的這個條件非常重要，但文獻[3][4]中似乎省略了。)

前文已推導，若，則 $L=maxleft(0, alpha_1^{old}+alpha_2^{old}-C ight), H=minleft( C, alpha_1^{old}+alpha_2^{old} ight)$ ；

若，則 $L=maxleft(0, alpha_2^{old}-alpha_1^{old} ight), H=minleft( C, alpha_2^{old}-alpha_1^{old}+C ight)$ 。

所以分以下四種情況討論：

當 $alpha_1^{new}=alpha_2^{new}=0$ 時，若，則有

$egin{align} &y_1alpha_1^{new} + y_2alpha_2^{new}= y_1alpha_1^{old}+y_2alpha_2^{old}\ &Rightarrow alpha_1^{new}+y_1y_2alpha_2^{new}=alpha_1^{old}+y_1y_2alpha_2^{old}\ &Rightarrow alpha_1^{old}+alpha_2^{old}=alpha_1^{new}+alpha_2^{new}=0\ &Rightarrow L=H=0 end{align}$

所以如果，只能是，異號。由KKT條件

$y_1 d_1 = y_1 left( sum_{j=1}^{N}{y_j k_{j1}alpha_j} + b ight)geq 1\ y_2 d_2 = y_2 left( sum_{j=1}^{N}{y_j k_{j2}alpha_j} + b ight)geq 1$

因為異號，所以上面兩個不等式會形成一個在 $b_1^{new}, b_2^{new}$ 之間的閉區間，這個區間內的值都能使兩個樣本滿足KKT條件。在SMO中，這種情況取 $b^{new} = frac{1}{2}left( b_1^{new}+b_2^{new} ight)$ 。

同理，當 $alpha_1^{new}=alpha_2^{new}=C$ 時，若，則 $alpha_1^{old}+alpha_2^{old}=2CRightarrow L=H=C$ ，

所以，異號，KKT條件同樣形成一個閉區間。

當 $alpha_1^{new}=0, alpha_2^{new}=C$ 時，若，則

$egin{align} &alpha_1^{new}+y_1y_2alpha_2^{new}=alpha_1^{old}+y_1y_2alpha_2^{old}\ &Rightarrow alpha_1^{old}-alpha_2^{old}=alpha_1^{new}-alpha_2^{new}=-C\ &Rightarrow L=H=C end{align}$

所以如果，只能是，同號。KKT條件形成一個在 $b_1^{new}, b_2^{new}$ 之間的閉區間，這個區間內的值都能使兩個樣本滿足KKT條件。

當 $alpha_1^{new}=C, alpha_2^{new}=0$ 時，若，則 $alpha_1^{old}-alpha_2^{old}=CRightarrow L=H=0$ ；

所以，同號，KKT條件形成一個閉區間。

至於為什麼採用這個奇怪的條件，可能是因為這樣程序更簡潔吧。。。

<關於 $alpha_1^{new}, alpha_2^{new}in left{ 0, C ight} quad and quad L= H$ 的情況>

這種情況Platt1998, 1999並沒有提及，但其給出的偽代碼的takeStep()函數中有語句

$Compute L, H\ {f if} (L==H) \ {f return} 0$

說明計算後，先判斷兩者是否相等，如果相等就直接return了，沒有對這兩個變數的QP子問題進行解析求解。

個人猜測：和前面類似可推導，這種情況下兩個樣本的KKT條件形成一個單側無界區間，需根據具體情況比較 $b_1^{new},b_2^{new}$ 的大小，程序上更新略顯繁瑣。所以在Platt的偽代碼中，如果則跳過這一步的子問題。

10.6 差值的更新，Error Cache

在根據啟發式規則選擇第二個優化變數時，需要用到樣本的差值。差值的更新(或者說計算)發生在每一步優化完兩個變數 $alpha_1^{new}, alpha_2^{new}$ 並更新閾值之後。

由定義，有

$egin{align} E_i^{new}=d_i^{new}-y_i&=sum_{j=1}^{N}{y_j k_{ji} alpha_j^{new}} + b^{new} -y_i\ &=sum_{support\vectors}{y_j k_{ji} alpha_j^{new}} + b^{new} -y_i\ end{align}\ ag{4}$

(4)式就是文獻[3][4]中給出的公式。

Platt1999中給出了更新(non-bound樣本的)差值的另一公式，下面進行推導。因為

$egin{align} E_i^{new}=d_i^{new}-y_i&=sum_{j=3}^{N}{y_j k_{ji} alpha_j^{old}} + y_1 k_{1i} alpha_1^{new}+y_2 k_{2i} alpha_2^{new}+b^{new} -y_i\ end{align}\ ag{5}$

又

$egin{align} E_i^{old}=d_i^{old}-y_i&=sum_{j=1}^{N}{y_j k_{ji} alpha_j^{old}}+b^{old} -y_i\&=sum_{j=3}^{N}{y_j k_{ji} alpha_j^{old}} + y_1 k_{1i} alpha_1^{old}+y_2 k_{2i} alpha_2^{old}+b^{old} -y_i ag{6}\ end{align}\$

所以由(5)(6)兩式得，

$egin{align} E_i^{new}=E_i^{old} + y_1 k_{1i} (alpha_1^{new}-alpha_1^{old})+y_2 k_{2i} (alpha_2^{new}-alpha_2^{old})+b^{new}-b^{old} ag{7}\ end{align}$

文獻[3][4]提到，保存所有樣本的可以節省計算時間，按這個意思應該採用(7)式。。。

不過根據Platt1998, 1999，只保存non-bound樣本的，而不保存bound樣本的；當需要用到時，如果是non-bound樣本，就到error cache(誤差緩存)里查找；如果是bound樣本，就用決策函數和當前的來計算(具體公式未給出，推測應該是(4)式)。

在每一步優化之後的兩個變數，如果是non-bound，則將其保存的差值設置為0，因為 $y_id_i^{new}=1Rightarrow d_i^{new} = y_i Rightarrow E_i^{new}=d_i^{new}-y_i=0$ 。而對於未參與這一步優化的其他non-bound樣本，根據(7)式更新其。

個人理解：Platt1998, 1999中，只保存non-bound樣本的是為了節省存儲空間，因為最終non-bound樣本只佔訓練集的一小部分；而bound的樣本，尤其是的樣本(非支持向量)佔大部分。此外，在一次交替遍歷中，non-bound子集會多次遍歷直至收斂，而bound子集只遍歷一次。

10.7 SMO演算法流程總結

根據參考文獻[1-4]，將SMO演算法流程簡單總結如下：

(1)初始化；給定精度，一般可取 $10^{-3}$ ~ $10^{-2}$ ；

初值滿足停機條件中的等式約束，所以接下來每一步優化都會滿足這個等式約束；
關於的初始化，文獻里沒有具體提到，Platt1999的偽代碼中是賦初值為0；
個人認為閾值的初值影響不大，因為是無約束的，第一步優化後就根據KKT條件更新了。

(2)按啟發式規則選取一對優化變數，記為；解析求解兩變數QP子問題，得到最優解並更新；然後更新，；

(3)在精度內檢查是否滿足停機條件；

若滿足，則轉(4)；
若不滿足，則回到(2)，繼續按啟發式規則選擇變數進行優化。

(4)得到問題的最優解，SVM訓練完成，退出程序。

To be continued...

參考文獻

[1] John C. Platt. Sequential minimal optimization: A fast algorithm for training support vector machines. Technical Report MSR-TR-98-14, Microsoft Research, 1998.

[2] John C. Platt. Fast training of support vector machines using sequential minimal optimization. In Advances in Kernel Methods - Support Vector Learning. B. Scholkopf, C. J. C. Burges, and A. J. Smola, Eds. MIT Press, Cambridge, MA, 1999: 185-208.

[3] 李航，統計學習方法，清華大學出版社，北京，2012年。第7章。

[4] 鄧乃揚，田英傑，數據挖掘中的新方法——支持向量機，科學出版社，北京，2004年。

[5] Osuna, E., Freund, R., Girosi, F., An improved training algorithm for support vector machines. Proc. IEEE NNSP 』97, 1997.