Learn R | SVM of Data Mining（四）

01-31

今天進行到支持向量機系列的第四篇，在前面的三篇文章中，我們講述了SVM的來龍去脈，使用拉格朗日對偶理論進行參數的求解，運用向量內積與核函數將SVM從線性可分拓展到線性不可分。那麼，在使用R進行實際案例分析前，我們的工作只剩下第二篇文章末尾的遺留問題：使用SMO高效優化演算法來求解拉格朗日乘子 $alpha$ 。

一、鬆弛變數與軟間隔最大化

還記得第三篇文章中曾提到，當遇到非線性數據時，我們通常的做法是通過映射將原始數據映射到高維空間，這樣能夠使線性分隔的概率大大增加，然後再使用核函數簡化計算過程。但如果數據本身並不是非線性的，而僅僅是有噪音（異常值）影響呢？

（圖片來源：支持向量機：Outliers " Free Mind）

觀察上圖，左上角被黑色邊框圈住的藍點就是一個異常值（outlier），如果不考慮這個點的話，所建立的超平面是非常理想的，但由於這個異常值的存在，超平面不得不進行調整，變為圖中的黑色虛線，同時間隔也相應的變小。這樣的異常值尚且可以進行線性可分，但假設該點向右上側進行移動的話，那我們就無法找到區分兩類數據的超平面了。

僅僅因為一兩個少數點就進行映射是非常不值的，為了解決這一情況，我們應該考慮允許個別異常值的存在，例如在上圖中，黑色實線所對應的距離就是該異常值所偏離的距離，如果把該點按照這個距離移動回來，這樣就不會使得超平面發生變形了，用數學的話來講就是加入了可以「容忍」的鬆弛變數（slack variable），原有的約束條件則為：

$y_i(w^Tx_i+b)geq 1-xi _i,i=1,2,...,n$ （鬆弛變數 $xi_igeq 0$ ，對應數據點 $x_i$ 允許偏離最大間隔超平面的量）

因此就有以下一系列的改變：

最大間隔分類器： $min~frac{1}{2}left | w right |^2+Csum_{i=1}^{n}{xi_i} ,s.t.y_i(w^Tx_i+b)geq 1-xi_i,xi_igeq 0,i=1,2,...,n$

其中 $C$ 是一個參數，用於控制目標函數中兩項（「尋找間隔最大的超平面」和「保證數據點偏差量最小」）之間的權重。注意，其中 $xi$ 是需要優化的變數（之一），而 $C$ 是一個事先根據實際問題確定好的常量。

拉格朗日函數： $F(w,b,alpha ,xi,r)=min~frac{1}{2}left | w right |^2+Csum_{i=1}^{n}{xi_i}-sum_{i=1}^{n}{alpha_ileft[ y_i(w^Tx_i+b)-1+xi_i right] } -sum_{i=1}^{n}{r_ixi_i}$ （ $alpha _i$ 與 $r_i$ 為拉格朗日乘子，對應上面的兩個約束條件）

使 $F(w,b,alpha ,xi,r)$ 分別對 $w,b,xi$ 最小化：

$frac{partial F}{partial w}=0Rightarrow w=sum_{i=1}^{n}{alpha _iy_ix_i}$

$frac{partial F }{partial b}=0Rightarrow sum_{i=1}^{n}{alpha _iy_i}=0$

$frac{partial F}{partial xi_i}=0 Rightarrow C-alpha _i-r_i=0$

構造對偶問題：（將 $w$ 帶入 $F(w,b,alpha ,xi,r)$ 化簡且考慮 $r_igeq 0$ 的約束條件） $max_alpha (sum_{i=1}^{n}{alpha _i}-frac{1}{2}sum_{i,j=1}^{n}{alpha_i alpha_jx_i^Tx_jy_iy_j } ),s.t.Cgeq alpha _igeq 0,i=1,2,...,n,sum_{i=1}^{n}{alpha _iy_i=0}$

有了以上的思路，我們就可以和訓練數據集線性可分時一樣，考慮數據集線性不可分情況下的線性可分SVM的學習問題，相對於線性可分的硬間隔最大化，這裡的近似線性可分被稱之為軟間隔最大化（soft margin maximization）。

二、SMO的演算法推導

經過前面一系列的講述與推導，我們把要解決的問題打造成如下形式：

$begin{eqnarray*}n&&max_alpha[sum_{i=1}^{n}{alpha _i}-frac{1}{2}sum_{i,j=1}^{n}{alpha_i alpha_jK(x_i,x_j)y_iy_j } ] n&&s.t.Cgeq alpha _igeq 0,i=1,2,...,n,sum_{i=1}^{n}{alpha _iy_i=0} nend{eqnarray*}$

如何求解這個式子呢？這時候序列最小優化演算法（Sequential minimal optimization SMO）就派上用場了。

SMO演算法由Microsoft Research的John C. Platt在1998年提出，並成為最快的二次規劃優化演算法，特別在針對線性SVM和數據稀疏時具有更優的性能。

按照原先的求解思路，我們需要首先固定除 $alpha _1$ 以外的所有參數，然後求 $alpha _1$ 的極值。但這個思路在這裡就不適用了，為什麼呢？

觀察約束條件，裡面有一個 $sum_{i=1}^{n}{alpha _iy_i=0}$ ，這意味著，如果固定了除 $alpha _1$ 以外的所有參數，那麼 $alpha _1$ 也就固定下來了，畢竟 $alpha_1y_1=-sum_{i=2}^{n}{alpha _iy_i}$ 。

所以，僅固定一個參數是不行的，SMO要每一次選取兩個參數做優化，假設選取 $alpha _1$ 和 $alpha_2$ 為需要計算的參數值，固定 $left{ alpha _3,alpha _4,...alpha _n right}$ 。這樣，在參數初始化後，SMO不斷執行以下兩個步驟直至收斂：

選取一對需要更新的變數 $alpha _i,alpha _j$ ；
固定除 $alpha _i,alpha _j$ 以外的參數，求解在構造的對偶問題下獲得更新的 $alpha _i,alpha _j$ 。

如何選取所需的 $alpha _i,alpha _j$ ，這個問題留在下一節再說，現在先假設參數已選取好。

由於除 $alpha _1$ 和 $alpha_2$ 外都已是固定值，那麼就有： $alpha _1y_1+alpha _2y_2=zeta$ （ $zeta$ 為一實數值）

所以 $alpha _1=(zeta -alpha _2y_2)/y_1=(zeta -alpha _2y_2)y_1$ （因為 $y$ 的取值要麼是 $+1$ ，要麼是 $-1$ ）

進一步的，假設更新之前的 $alpha _1$ 和 $alpha_2$ 為 $alpha _1^{old}$ 和 $alpha_2^{old}$ ，更新之後的為 $alpha _1^{new}$ 和 $alpha_2^{new}$ ，那麼更新前後的值需要滿足以下等式才能保證和為 $0$ 的約束：

$alpha _1^{old}y_1+alpha _2^{old}y_2=alpha _1^{new}y_1+alpha _2^{new}y_2=zeta$

又因為有著約束條件 $Cgeq alpha _1geq 0,Cgeq alpha _2geq 0$ ，將這兩個信息匯總考慮可以進一步縮小 $alpha _1$ 和 $alpha_2$ 的取值範圍，接下來進行分情況討論：

1. 當 $y_1$ 與 $y_2$ 異號時：

$alpha _1-alpha _2=zeta$ 或 $alpha _2-alpha _1=zeta$ ，且 $Cgeq alpha _igeq 0,i=1,2,...,n$ 。此時 $alpha _1$ 與 $alpha _2$ 該如何取值呢？觀察下圖：

（圖片來源：SMO演算法 - JerryLead - 博客園；另更正：右下側的直線應為 $alpha _2-alpha _1=zeta$ ）

此時， $alpha _i(i=1,2)$ 的取值範圍既要在矩形方框內，也要在直線上。

首先以 $alpha _2$ 為例，很明顯，它的上限要麼是 $(C+zeta ,C)$ 中的 $C$ ，要麼是 $(C,C-zeta )$ 中的 $C-zeta$ ，用 $H$ 表示上限，具體為：

$alpha _1>alpha _2$ ， $H=C-zeta =C+alpha _2-alpha _1$
$alpha _1<alpha _2$ ， $H=C$

綜上所述， $H=min(C,C+alpha _2-alpha _1)$

繼續看 $alpha _2$ 的下限，無非是在 $-xi$ 與 $0$ 中二選一，用 $L$ 表示下限，具體為：

$alpha _1>alpha _2$ ， $L=0$
$alpha _1<alpha _2$ ， $L=-zeta =alpha _2-alpha _1$

綜上所述， $L=max(0,alpha _2-alpha _1)$

總結起來，當 $y_1$ 與 $y_2$ 異號時，有：

$L=max(0,alpha _2-alpha _1)leq alpha _2leq min(C,C+alpha _2-alpha _1)=H$

2. 當 $y_1$ 與 $y_2$ 同號時：

$alpha _1+alpha _2=zeta$ 或 $alpha _1+alpha _2=-zeta$ ，且 $Cgeq alpha _igeq 0,i=1,2,...,n$

與前面相同的方法，可以推出 $alpha _2$ 的取值範圍為：

$L=max(0,alpha _2+alpha _1-C)leq alpha _2leq min(C,alpha _2+alpha _1)=H$

接著，把一開始的式子 $max_alpha (sum_{i=1}^{n}{alpha _i}-frac{1}{2}sum_{i,j=1}^{n}{alpha_i alpha_jK(x_i,x_j)y_iy_j } )$ 進行化簡，把 $alpha _1$ 與 $alpha _2$ 分離出來，做一個等價變形（設 $K_{ij}=K(x_i,x_j)$ ）：

$begin{eqnarray*}n&&max_alpha (sum_{i=1}^{n}{alpha _i}-frac{1}{2}sum_{i,j=1}^{n}{alpha_i alpha_jK(x_i,x_j)y_iy_j } )=min_alpha(frac{1}{2}sum_{i,j=1}^{n}{alpha_i alpha_jK(x_i,x_j)y_iy_j }-sum_{i=1}^{n}{alpha _i}) n&&=min_alpha left[ frac{1}{2}K_{11}alpha _1^2+frac{1}{2}K_{22}alpha _2^2+y_1y_2K_{12}alpha _1alpha _2-(alpha _1+alpha _2)+y_1alpha _1sum_{i=3}^{n}{y_ialpha _iK_{i1}}+y_2alpha _2sum_{i=3}^{n}{y_ialpha _iK_{i2}} right] nend{eqnarray*}$

（此式不建議推導，了解並直接使用即可）

繼續化簡，設 $v_j=sum_{i=3}^{n}{y_ialpha _ik_{ij}}$ ，原式化簡為：

$J(alpha _1,alpha _2)=min_alpha left[ frac{1}{2}K_{11}alpha _1^2+frac{1}{2}K_{22}alpha _2^2+y_1y_2K_{12}alpha _1alpha _2-(alpha _1+alpha _2)+y_1alpha _1v_1+y_2alpha _2v_2 right]$

又因為 $alpha _1=(zeta -alpha _2y_2)/y_1=(zeta -alpha _2y_2)y_1$ ，所以用含 $alpha _2$ 的式子代替 $alpha _1$ ，變形為： $J(alpha _2)=frac{1}{2}K_{11}(zeta -alpha _2y_2)^2+frac{1}{2}K_{22}alpha _2^2+y_1y_2K_{12}(zeta -alpha _2y_2)^2alpha _2-(zeta -alpha _2y_2)+alpha _2)+(zeta -alpha _2y_2)v_1+y_2alpha _2v_2$

對 $alpha _2$ 求導，令其為 $0$ ，得：

$frac{partial F}{partial alpha _2}=K_{11}alpha _2+K_{22}alpha _2-2K_{12}alpha _2-K_{11}zeta y_2+K_{12}zeta y_2+y_1y_2-v_1y_2+v_2y_2-1=0$

整理得： $(K_{11}+K_{22}-2K_{12})alpha _2=y_2(zeta K_{11}-zeta K_{12}+v_1-y_1-v_2+y_2)$

將 $v_j=sum_{i=3}^{n}{y_ialpha _ik_{ij}} =f(x_i)-sum_{j=1}^{2}{alpha _iy_iK(x_i,x_j)-b}$ 帶入其中（這裡使用了SVM分類函數的表達式： $f(x_i)=sum_{i=1}^{n}{alpha _iy_iK(x_i,x_j)+b}$ ），原式進一步化簡為：

$(K_{11}+K_{22}-2K_{12})alpha _2=y_2left{ y_2-y_1+zeta K_{11}-zeta K_{12}+[f(x_1)-sum_{j=1}^{2}{alpha _iy_iK(x_i,x_j)-b} ]-[f(x_2)-sum_{j=1}^{2}{alpha _iy_iK(x_i,x_j)-b} ] right}$

又因為 $alpha _1^{old}y_1+alpha _2^{old}y_2=alpha _1^{new}y_1+alpha _2^{new}y_2=zeta$ ，帶入其中，經過一系列化簡得：

$(K_{11}+K_{22}-2K_{12})alpha _2^{new~ unc}=alpha _2^{old}(K_{11}+K_{22}-2K_{12})+y_2[(f(x_1)-y_1)-(f(x_2)-y_2)]$

（ $unc$ 表示暫未考慮 $Lleq alpha _2leq H$ 的上下限約束條件，等到考慮了這個範圍後就可以去掉了）

令 $E_i=f(x_i)-y_i$ ，原式等價於 $(K_{11}+K_{22}-2K_{12})alpha _2^{new~ unc}=alpha _2^{old}(K_{11}+K_{22}-2K_{12})+y_2[E_1-E_2]$

因此 $alpha _2^{new~ unc}=alpha _2^{old}+frac{y_2(E_1-E_2)}{(K_{11}+K_{22}-2K_{12})}$ 。接著考慮上下限的約束條件，去掉 $unc$ ：

$alpha _2^{new}=left{begin{matrix}nH,~~~~~ifalpha _2^{new~unc}>Halpha _2^{new~unc},ifLleq alpha _2^{new~unc}leq H n nL,~~~~~ifalpha _2^{new~unc}<Lnend{matrix}right.$

得到 $alpha _2^{new}$ 的值後，我們也就能得到 $alpha _1^{new}$ 的值了，具體公式為 $alpha _1^{new}=alpha _1^{old}+y_1y_2(alpha _2^{old}-alpha _2^{new})$

接著進行 $b$ 值的更新：首先 $b$ 需要滿足這樣的約束條件： $b=left{begin{matrix}nb_1~~~~,if0<alpha _1^{new}<Cb_2~~~~,if0<alpha _2^{new}<Cn n(b_1+b_2)/2,otherwisenend{matrix}right.$ 。

（如果 $0<alpha_1^{new},alpha _2^{new}<C$ ，那麼就有 $b=b_1=b_2$ ）。然後：

$b_1^{new}=b^{old}-E_1-y_1(alpha _1^{new}-alpha _1^{old})k(x_1,x_1)-y_2(alpha _2^{new}-alpha _2^{old})k(x_1,x_2)$

$b_2^{new}=b^{old}-E_2-y_1(alpha _1^{new}-alpha _1^{old})k(x_1,x_2)-y_2(alpha _2^{new}-alpha _2^{old})k(x_2,x_2)$

當然，每次更新完 $alpha _i$ 與 $alpha _j$ 後，總要更新 $b$ 值及相應的 $E_i$ 值。

迭代結束後，我們也就獲得了所有需要更新的參數，自然也就得到了最終的分類函數。

三、SMO中拉格朗日乘子的選擇

關於這一部分的內容，借鑒和引用自博客SMO演算法 - JerryLead與支持向量機通俗導論 - 結構之法演算法之道 - CSDN.NET中的相關內容。

首先先來明確一下KKT條件對於 $alpha _i$ 取值的意義： $begin{eqnarray*}n&&alpha _i=0Leftrightarrow y_if(x_i)geq1 n&&0<alpha _i<CLeftrightarrow y_if(x_i)=1 n&&alpha _i =CLeftrightarrow y_if(x_i)leq 1nend{eqnarray*}$

對於第一種情況，表明 $alpha _i$ 是正常分類，在間隔邊界內部（因為正常分類的點滿足 $y_if(x_i)geq0$ ）；
對於第二種情況，表明 $alpha _i$ 是支持向量，在間隔邊界上；
對於第三種情況，表明 $alpha _i$ 在兩條間隔邊界之中。

最優解需要滿足KKT條件，即滿足上述的三個條件，如果存在以下三種情況則表示未滿足KKT條件，具體為：

$y_if(x_i)geq1$ 但 $alpha _i>0$
$y_if(x_i)=1$ 但 $alpha_i =0$ 或 $alpha _i=C$
$y_if(x_i)leq 1$ 但 $alpha _i<C$

而 $alpha _1$ 的選取就與這些違反條件有關，先「掃描」所有的 $alpha _i$ ，把違反KKT條件程度最大的變數作為更新對象，令其為 $alpha _1$ 。

不過 $alpha _2$ 的選取並不按照此方法，這是因為：

有一個Osuna定理，這個定理告訴我們只要選擇出來的 $alpha _i,alpha _j$ 只要有一個違背了KKT條件，那麼目標函數在一步迭代後值會減小，迭代就有意義。

接著，在所有不違反KKT條件的乘子中，選擇能夠使 $left| E_1-E_2 right|$ 最大（即使目標函數值減小最快）的乘子，定義為 $alpha _2$ ，原因在於：

由於比較各變數所對應得目標函數值減幅的複雜度過高，因此SMO採用了一個啟發式：使選取的兩變數所對應樣本之間的間隔最大。直觀來看，相比較於選取相似的兩個變數進行更新，選取有很大差別的兩個變數進行更新將會給目標函數值帶來更大的變化。

當然，在每次更新完兩個乘子的優化後，都需要再重新計算相應的 $E_i$ 值。

滿足迭代結束的條件可為以下兩種：

KKT條件對所有向量均滿足；
目標函數 $J(alpha _2)$ 增長率小於某個預設的閾值，即 $frac{J(alpha _2^{t+1})-J(alpha _2^{t})}{J(alpha _2^{t})} <T$

至此，SMO演算法的基本內容簡單介紹完畢。

未完待續

References：

統計學習方法 (豆瓣)
機器學習 (豆瓣)
序列最小優化演算法 - Wikipedia
支持向量機：Outliers " Free Mind
SMO演算法 - JerryLead - 博客園
【分類戰車SVM】第六話：SMO演算法
支持向量機通俗導論 - 結構之法演算法之道 - CSDN.NET
Sequential Minimal Optimization - John C. Platt
Sequential Minimal Optimization for SVM