支持向量機(SVM)——SMO演算法

03-06

接著上一篇的原理推導，SVM最後要求解以下二次規劃問題（線性支持向量機 $Kleft( oldsymbol{x}_{oldsymbol{i}},oldsymbol{x}_{oldsymbol{j}} ight) =oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}}$ ）

$underset{oldsymbol{alpha }}{min} frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jKleft( oldsymbol{x}_{oldsymbol{i}},oldsymbol{x}_{oldsymbol{j}} ight)}}-sum_{i=1}^N{alpha _i}$

$s.t. sum_{i=1}^N{alpha _iy_i}=0$

$0le alpha _ile C, i=1,2,...,N$

關於這種二次規劃問題求解的方法有很多，SMO演算法就是其中一種。SMO演算法是一種啟發式演算法，基本思路是：如果所有變數的解都滿足此最優化問題的KKT條件，那麼這麼最優化問題的解就得到了。

令

$u=sum_{i=1}^N{y_j}alpha _jKleft( oldsymbol{x}_{oldsymbol{j}},oldsymbol{x} ight) -b$

根據KKT條件可以得出二次規劃問題中 $alpha _i$ 取值的意義為

$alpha _i=0Rightarrow xi _i>0Rightarrow y_iu_ige 1$

$alpha _i=CRightarrow y_iu_i-1+xi _i=0Rightarrow y_iu_ile 1$

$0<alpha _i<CRightarrow egin{cases} xi _i=0\ y_iu_i-1+xi _i=0\ end{cases}Rightarrow y_iu_i=1$

第一種情況表示對應實例點在邊界內，即被正確分類的點；第二種情況表示在兩條邊界線之間；第三種情況表示對應實例點在邊界上，為支持向量。

而最優解需要滿足KKT條件，即上述3個條件都得滿足，也就是說，如果存在不能滿足KKT條件的 $alpha _i$ ， $alpha _i$ 那麼需要更新這些，這是第一個約束條件。這些違背KKT條件的 $alpha _i$ 可以根據以下條件判斷：

$alpha _i==0 and y_iu_i<0$

$alpha _i==C and y_iu_i>0$

$alpha _i>0 and alpha _i<xi _i and y_iu_i e 0$

此外，更新的同時還要受到第二個約束條件的限制，即：

$sum_{i=1}^N{alpha _iy_i}=0$

因為這個條件，我們同時更新兩個 $alpha$ 值，因為只有成對更新，才能保證更新之後的值仍然滿足和為0的約束，假設我們選擇的兩個乘子為 $alpha _1$ 和 $alpha _2$ ，其他變數 $alpha _ileft( i=3,4,...,N ight)$ 是固定的，於是SMO的最優化問題可以寫成

$underset{alpha _1,alpha _2}{min} Wleft( alpha _1,alpha _2 ight) =frac{1}{2}K_{11}alpha _{1}^{2}+frac{1}{2}K_{22}alpha _{2}^{2}+y_1y_2K_{12}alpha _1alpha _2$

$-left( alpha _1+alpha _2 ight) +y_1alpha _1sum_{i=3}^N{y_ialpha _iK_{i1}+}y_2alpha _2sum_{i=3}^N{y_ialpha _iK_{i2}}$

$s.t. alpha _1y_1+alpha _2y_2=-sum_{i=3}^N{y_ialpha _i}=zeta$

其中， $K_{ij}=Kleft( oldsymbol{x}_{oldsymbol{i}},oldsymbol{x}_{oldsymbol{j}} ight)$ ， $zeta$ 是常數，目標函數中省略了不含 $alpha _1$ 和 $alpha _2$ 的常數項（因為求導以後會等於0）。

為了求解兩個變數的二次規劃問題，先分析約束條件，再在此約束條件下求極小值。

如圖，約束條件使最優解 $left( alpha _1,alpha _2 ight)$ 位於與對角線平行的直線上，這使得兩個變數的最優化問題成為實質上單變數的最優化問題，不妨考慮為變數 $alpha _2$ 的最優化問題。假設初始可行解為 $alpha _{1}^{old},alpha _{2}^{old}$ ，最優解為 $alpha _{1}^{new},alpha _{2}^{new}$ 。而 $alpha _{2}^{new}$ 需滿足

$Lle alpha _{2}^{new}le H$

由上圖可知

$egin{cases} L=max left( 0,alpha _{2}^{old}-alpha _{1}^{old} ight) ,H=min left( C,C+alpha _{2}^{old}-alpha _{1}^{old} ight) , y_1 e y_2\ L=max left( 0,alpha _{2}^{old}+alpha _{1}^{old}-C ight) ,H=min left( C,alpha _{2}^{old}+alpha _{1}^{old} ight) , y_1=y_2\ end{cases}$

設 $E_i$ 為誤差項， $eta$ 為學習率

$E_i=left( sum_{i=1}^N{alpha _jy_jKleft( oldsymbol{x}_{oldsymbol{j}},oldsymbol{x}_{oldsymbol{i}} ight) +b} ight) -y_i, i=1,2$

$eta =K_{11}+K_{22}-2K_{12}=lVert phi left( oldsymbol{x}_1 ight) -phi left( oldsymbol{x}_2 ight) Vert ^2$

可得（具體證明可見《統計學習方法》定理7.6的證明）為經剪輯的解為

$alpha _{2}^{new,unc}=alpha _{2}^{old}+frac{y_2left( E_1-E_2 ight)}{eta}$

考慮約束以後，得到最終經剪輯過得解為

$alpha _{2}^{new}=egin{cases} H, alpha _{2}^{new,unc}>H\ alpha _{2}^{new,unc},Lle alpha _{2}^{new,unc}le H\ L, alpha _{2}^{new,unc}<L\ end{cases}$

進一步，可以得到

$alpha _{1}^{new}=alpha _{1}^{old}+y_1y_2left( alpha _{2}^{old}-alpha _{2}^{new} ight)$

至此，我們得到了SMO演算法中一個子問題的最優解 $left( alpha _{1}^{new},alpha _{2}^{new} ight)$ ,而SMO演算法就是由若干個這種子問題組成的。但是，我們該如何選擇每個子問題中的兩個變數呢？這裡有兩種方法，分別對應了簡化版的SMO演算法和完整版的SMO演算法：

簡化版SMO演算法：

檢查訓練樣本中每個點 $left( oldsymbol{x}_{oldsymbol{i}},y_i ight)$ 是否滿足KKT條件，如果不滿足，則它對應的 $alpha _i$ 可以被優化，然後隨機選擇另一個變數 $alpha _j$ 進行優化。

完整版SMO演算法:

簡化版的SMO演算法在小數據集上沒什麼問題，但遇到大數據集速度就會變得很慢。完整版的演算法與簡化版的演算法唯一不同的就是 $alpha$ 的選擇。具體地，先通過一個外循環來選擇第一個 $alpha _i$ ，並且其選擇過程會再兩種方式之間進行交替：一種方式是在所有數據集上進行單遍掃描，另一種方式則是在非邊界 $alpha$ 中實現單遍掃描。所謂非邊界 $alpha$ 即那些 $alpha e 0$ 或 $alpha e C$ 的 $alpha$ 。對整個數據集掃描很容易，而實現非邊界掃描，首先要建立這些 $alpha$ 的列表，然後再對這個表進行遍歷。同時，該步驟會跳過那些已知的不會改變的 $alpha$ 值。

在選擇第一個 $alpha _i$ 後，演算法會通過一個內循環來選擇第二個 $alpha _j$ 。優化過程中會通過最大化步長的方式來獲取第二個 $alpha _j$ 。

每次優化完兩個變數以後，都需要重新計算閾值 $b$ ，當 $0<alpha _{1}^{new}<C$ 時，由KKT條件可知

$sum_{i=1}^N{alpha _{_i}y_iK_{i1}}+b=y_1$

於是，

$b_{1}^{new}=y_1-sum_{i=3}^N{alpha _iy_iK_{i1}}-alpha _{1}^{new}y_1K_{11}-alpha _{2}^{new}y_2K_{21}$

又

$E_1=sum_{i=3}^N{alpha _iy_iK_{i1}}+alpha _{1}^{old}y_1K_{11}+alpha _{2}^{old}y_2K_{21}+b^{old}-y_1$

所以

$b_{1}^{new}=-E_1-y_1K_{11}left( alpha _{1}^{new}-alpha _{1}^{old} ight) -y_2K_{21}left( alpha _{2}^{new}-alpha _{2}^{old} ight) +b^{old}$

同理

$b_{2}^{new}=-E_2-y_1K_{12}left( alpha _{1}^{new}-alpha _{1}^{old} ight) -y_2K_{22}left( alpha _{2}^{new}-alpha _{2}^{old} ight) +b^{old}$

當 $alpha _{1}^{new}$ 和 $alpha _{2}^{new}$ 同時滿足條件 $0<alpha _{i}^{new}<C,i=1,2$ ，那麼 $b_{1}^{new}=b_{2}^{new}$ 。如果 $alpha _{1}^{new}$ 和 $alpha _{2}^{new}$ 是0或 $C$ ，那麼 $b_{1}^{new} ext{，}b_{2}^{new}$ 和它們之間的數都是滿足KKT條件的閾值，這是選擇它們的中點，即