機器學習文獻翻譯及註解（2）--SVM的SMO演算法（John Platt 1998）

Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines

摘要

1 introduction

1.1 SVM概述

1.2 之前的SVM演算法

2 SMO

2.1 兩個拉格朗日乘數的解法

2.2 選擇待優化的乘數的啟發式方法

2.3 計算閾值

2.4 線性SVM的優化

2.5 代碼詳細

2.6 和之前演算法的關係

3 Benchmarking SMO

4 結論

單詞、短語

Sequential Minimal Optimization:

A Fast Algorithm for Training Support Vector Machines

John C. Platt

Microsoft Research

jplatt@microsoft.com

Technical Report MSR-TR-98-14

April 21, 1998

? 1998 John Platt

摘要

本文提出一種新的訓練支持向量機的演算法：序貫最小優化（SMO，最小優化表示每次優化的時候只優化兩個拉格朗日乘數，每個拉格朗日乘數對應工作集（working set）中的一個點，也就是說每次優化的工作集中只有兩個樣本，此為最小）。訓練一個SVM需要解一個非常大（即變數個數非常多）的二次方程（QP問題）。SMO將這個大QP問題分解為一系列小到不能再小的QP問題。這些小QP問題可以得到解析解，而且解的過程避免了耗時的QP數值優化作為內循環。SMO需要的內存大小隨訓練集的大小線性增長，這就允許SMO處理很大的訓練集。因為避免了矩陣計算，SMO的計算複雜度在多個測試問題（一些經典的問題及數據集）上介於O（訓練集大小）和O（訓練集大小的二次方）之間，而標準的分組SVM演算法的計算複雜度則介於O（訓練集大小）和O（訓練集大小的三次方）之間。SMO的計算時間取決於SVM evaluation,（不知道怎麼翻譯，從上下文看指的是計算複雜度），因此SMO對線性SVM和稀疏數據集來說是最快的。在真實世界裡的稀疏數據集上，SMO可以比分組SVM演算法快1000倍。

1 introduction

在過去的幾年裡，湧起了一股了解SVM的風潮，SVM已經經驗性地表明了在一系列廣闊的問題上（比如手寫字元識別、面部識別、行人識別和文本分類）具有很好的泛化能力。

然而SVM的使用仍然局限於一小群研究者之間。一個可能的原因是SVM訓練起來很慢，尤其對於大型問題。另外一個原因是SVM訓練演算法對一般工程師來說實現起來太複雜、太難。

本文描述了一種新的SVM學習演算法，概念清晰、實現簡單、通常情況下更快，而且比標準的SVM演算法在困難的SVM問題上有更好的scaling properties（不知道怎麼翻譯，結合摘要部分，應該指計算複雜度，即當問題規模增大scale時，計算難度沒有增大scale過快）。新的SVM演算法稱作序貫最小優化演算法，不像之前的SVM演算法使用數值二次規劃作為內循環，SMO使用解析二次規劃步。

本文首先描述一下SVM的全貌和當前的SVM演算法，然後詳細介紹SMO演算法，包括二次規劃步的解析解、在內循環里選擇做優化的變數的啟發式方法、如何設置SVM的閾值、某些特例的優化、演算法的偽代碼、SMO和其他演算法的關係。

SMO已經在兩個真實世界的數據集和兩個人工數據集上做過測試。本文將展示SMO演算法的運算時間和標準分組演算法的運算時間對比。最後有個附錄描述解析優化的推導過程。

1.1 SVM概述

Vladimir Vapnik在1979年發明了SVM，最簡單的情形中，SVM是一個線性超平面，形式如下：

其中w是超平面的法向量，x是輸入向量。分割超平面為u=0的超平面，離超平面最近的點在u=±1的超平面上，因此間隔m可表示為：

最大化間隔可以表示為如下最優化問題（參見文獻4）：

其中xi是第i個訓練樣本，yi是對應的正確輸出（1表示正例，-1表示反例）。

使用拉格朗日乘數，最優化問題可以轉為一個對偶問題（一個QP問題），目標函數Ψ僅僅取決於一系列拉格朗日乘數αi

其中N是訓練樣本的個數，滿足以下不等式約束：

以及一個線性等式約束：

拉格朗日乘數和訓練樣本有一對一的關係。一旦拉格朗日乘數確定了，法向量w和閾值b可以由拉格朗日乘數推導出來：

因為w可以通過（7）從訓練數據中預先計算得出，估算一個SVM的計算量就是非零支持向量的個數。（Because w can be computed via equation (7) from the training data before use，為什麼？即使如此，怎麼得出後面的結論？）

當然，並不是所有的數據集都是線性可分的。在1995年Cortes和Vapnik（見文獻7）建議對原始優化問題（見（3））做些修改，允許樣本沒有達到正確的間隔（即落在間隔內部），但要因此而對目標函數加一個懲罰。

其中εi就是為了樣本允許落在間隔內而引入的鬆弛變數，C是平衡最大化間隔和最小化落在間隔內的樣本個數的參數。當（8）轉為對偶形式的時候，只有不等式約束（5）變成邊界約束：

鬆弛變數εi並沒有出現在對偶形式中。

SVM也可以推廣到非線性分類中（見文獻2）。一個非線性SVM的結果通過拉格朗日乘數直接計算得出：

其中K是核函數，用來度量輸入向量x和存儲的訓練向量xj之間的相似度或距離。K的可選集包括高斯函數、多項式、非線性神經網路（見文獻4）。如果K是線性的，SVM也是線性的（一個有意思的練習）。

拉格朗日乘數αi依然通過二次規劃計算得出。非線性情況下二次規劃形式改變，但對偶目標函數Ψ仍然是α的二次形式：

上述QP問題就是SMO演算法將要解決的。為了使上述QP問題正定。核函數K必須遵守Mercer條件（見文獻4）。

KKT條件是正定QP問題存在最優解的充要條件：

其中ui是第i個訓練樣本的SVM計算結果。注意到KKT條件一個樣本計算一次，這對SMO演算法的構造很有幫助。

1.2 之前的SVM演算法

由於（11）所示的QP問題規模太大，通過標準的二次規劃技術解決起來很難。（11）中包含一個矩陣，矩陣中有一些元素的值等於訓練樣本的個數的平方。這個矩陣在樣本個數大於4000的時候將不小於128M。

Vapnik在文獻19中提出了一個方法，被稱為分組。分組演算法利用以下事實：二次型的值在移除為0的拉格朗日乘數對應的行和列的時候保持不變。因此大的QP問題可以分解為一系列小的QP問題，最終目的是識別出所有的非零乘數、捨棄所有的零乘數。在每一步，分組演算法解決一個包含如下樣本的QP問題：上一步的所有非零乘數、違反KKT條件程度最多的M個樣本（見文獻4），以及某些M值（見圖2）（什麼叫某些M值？）。如果某一步違反KKT條件的樣本少於M個，這些樣本都被加進來。

圖2（圖中一條橫線表示一次訓練過程中的訓練集，方框表示那次訓練過程中的拉格朗日乘數。對於分組演算法，每一次訓練增加固定個數的樣本、捨棄零乘數。因此訓練樣本逐步增加。Osuna的演算法每一次訓練中優化固定數目的樣本，增加和刪除樣本的數目相同。SMO每次訓練只優化兩個樣本，而且是計算解析解（而不是通過數值優化），因此非常快）

每個QP子問題都從上一個子問題的結果開始，在最後一步，所有非零拉格朗日乘數都被識別出，因此最後一步就解決了大QP問題。

分組明顯地減少了矩陣的大小，從訓練樣本個數的平方降低到接近非零乘數個數的平方。但是分組仍然無法處理大型訓練問題，因為瘦身後的矩陣仍然無法裝進內存（估計當時的內存大小就是128M）。

1997年，Osuna等人（見文獻16，也就是上一篇翻譯的文獻）證明了一個理論，為SVM提供了一套新的演算法。這個理論證明大的QP問題可以分解為一系列小的QP子問題。只要每一步有一個違反KKT條件的樣本被加入前一步的子問題的樣本集（在文獻16裡面稱之為工作集，即B）中，整體目標函數值就會降低且得到一個滿足所有條件的可行解。因此逐步增加至少一個違反KKT條件的樣本肯定能收斂。注意到分組演算法也滿足這個理論的條件，因此也會收斂（一個有意思的思考）。

Osuna等人建議對每個QP子問題保持矩陣大小恆定，這就意味著每一步增加和刪除的樣本數相同（見圖2）。使用固定大小的矩陣允許在任意大小的數據集上進行訓練。演算法建議每一步增加和刪除一個樣本。顯然這並不高效，因為他使用整個QP數值優化步來引起一個訓練樣本去滿足KKT條件。在實踐中，研究者增加和減少多個樣本，根據未發布的啟發式方法（見文獻17，文獻17 寫著Osuna, E., Personal Communication，這是跟Osuna個人溝通的意思？個人溝通也可以作為文獻23333）。在任何情況下，一個QP數值解法都需要上述所有的方法。數值解法眾所周知很難得到正確的解法，有很多數值精度問題需要處理。

2 SMO

SMO是一個可以快速解決SVM QP問題而不使用矩陣存儲空間和數值優化步的簡單演算法。SMO使用Osuna的理論分解QP問題以確保收斂。

不像之前的演算法，SMO在每一步選擇儘可能小的優化問題。對標準的SVM QP問題，最小的優化問題涉及到兩個拉格朗日乘數，因為拉格朗日乘數必須遵循一個線性等式約束（也就意味著一個乘數可以通過剩下的乘數表示出來，固定n-1個乘數則剩下那個乘數也就確定了，沒有優化的意義）。在每一步SMO選擇兩個乘數一起優化，尋找最優值，更新SVM體現這些新的最優值。

SMO的優勢源於解那兩個乘數的最優值的時候可以直接計算解析解，而不是通過數值優化。內層循環可以用一段很短的C代碼表示，而不是調用整個QP運行庫。儘管SMO需要解決更多子問題，但每個子問題的解決速度如此之快導致整體上看仍然更快。

此外，SMO不需要額外的空間存儲矩陣。因此非常大規模的SVM訓練問題也可以裝進一台普通個人電腦的內存里。因為沒有涉及到矩陣演算法，SMO演算法不受數值精度問題的影響。

SMO由兩個部分組成：解那兩個拉格朗日乘數的解析解和選擇哪兩個拉格朗日乘數進行優化的啟發式演算法。

2.1 兩個拉格朗日乘數的解法

為了解那兩個拉格朗日乘數，SMO首先計算這些拉格朗日乘數的約束條件然後解這些約束下的最小值。為了方便，所有涉及到第一個乘數的都有個下標1，第二個的有下標2。因為只有兩個乘數，約束條件可以通過圖1（應該是圖3）方便地表示出來（因為都是二維空間）。邊界約束（9）導致乘數位於一個盒子內，線性等式約束（6）導致乘數位於一條斜線上。因此目標函數在約束下的最小值一定位於一條斜線段上（見圖3）。這個約束解釋了為什麼拉格朗日乘數可以被優化的最小數目是2：如果只優化一個乘數，不能在每次優化都滿足線性等式約束。

圖1（應該是圖3）

線段的端點可以很簡單地表示出來。不失一般性，演算法首先計算第二個乘數α2並用

α2表示端點。如果y1不等於y2（每個乘數對應一個樣本，y1、y2即樣本的分類），則α2有以下邊界：（根據等式約束6，y1和y2不等即一個為正一個為負，α1-α2+...=0）

如果y1等於y2，則α2有以下邊界：

伴隨斜線的第二個目標函數的衍生變數表示如下：

在正常情況下，目標函數將是正定的（為什麼？），在線性等式約束的方向上將產生一個最小值（為什麼正定能導致在等式約束上產生最小值？），η將大於0（η有啥含義？）。在這種情況下，SMO在約束的方向上的最小值如下：

其中Ei=ui-yi是第i個訓練樣本的誤差。下一步，約束條件下的最小值通過在上述邊界（14,15）進行截取獲得：

現在，另s=y1y2，α1通過截取後的α2計算可得：

在特別情況下，η小於0，一個負的η將在核函數K不滿足Mercer條件時出現，這導致目標函數變成不確定的（非正定）。如果超過一個訓練樣本有同樣的輸入向量x，一個正確的核函數也會導致η為0的情況出現。在任何情況下SMO都能工作，即使η不為正，這種情況下目標函數Ψ將在線段的兩端計算得到：

SMO將移動乘數到端點（此處目標函數有最小值）。如果目標函數在兩端取值相等（在一個小的舍入誤差ε範圍內）且核函數滿足Mercer條件，那麼優化將不再取得任何進展。這種場景下面會描述。

2.2 選擇待優化的乘數的啟發式方法

只要SMO每一步永遠優化和改變兩個乘數，且至少有一個乘數在優化前違反KKT條件，那麼根據Osuna的理論每一步都能降低目標函數的值，也因此能保證收斂。為了加速收斂，SMO使用啟發式方法來選擇改變哪兩個乘數。

有兩個單獨的啟發式方法：一個選擇第一個乘數，一個選擇第二個乘數。選擇第一個乘數的啟發式方法提供SMO演算法外層循環。外層循環首先在整個訓練集上遍歷，計算每個樣本是否違反KKT條件（12），如果違反就可以用來優化（步驟1）。單次掃描整個訓練集之後，外層循環遍歷所有拉格朗日乘數不為0和C的樣本（非邊界樣本），且每個樣本都檢查是否違反KKT條件，違反的將被用來做優化（步驟2）。外層循環掃描那些非邊界樣本直到所有的非邊界樣本在誤差ε內滿足KKT條件（什麼意思？）。然後外層循環重新遍歷訓練集。外層循環交替進行在整個訓練集上單次掃描和在非邊界子集上多次掃描（步驟1和步驟2），直到整個訓練集在誤差ε內符合KKT條件，此時演算法終止。（為什麼掃描完整個訓練集後再掃描非邊界子集，不是個子集嗎，不是已經被掃描過了嗎？）

上述過程的CPU主要消耗在最可能違反KKT條件的樣本上，即非邊界子集（為什麼？）。隨著SMO演算法的進行，邊界的樣本很可能仍然停留在邊界上，但非邊界樣本則隨著其他樣本被優化而轉移（為什麼邊界樣本停留在邊界上而非邊界樣本會移動？為什麼會移動到自洽？）。SMO演算法將遍歷非邊界子集直到子集自洽（什麼叫子集自洽？）。然後SMO掃描整個數據集來查找任何由於優化非邊界子集而違反KKT條件的邊界樣本（邊界樣本為什麼）。

注意到檢查是否違反KKT條件時使用了ε誤差項，ε的經典取值為 。識別系統一般來說並不需要以很高的精度去滿足KKT條件，對處於正例邊界的樣本來說取值0.999到1.001之間都是可以接受的。如果不要求產生很高精度的結果，SMO演算法（其他SVM演算法也一樣）就不會很快收斂。

一旦第一個乘數選定，SMO開始選擇第二個乘數來最大化優化的步伐。現在，計算核函數很耗時間，所以SMO通過（16）中的|E1-E2|來估計步長。SMO為訓練集的每一個非邊界樣本記錄一個錯誤值E，然後選擇一個錯誤值來估計最大步長。如果E1是正，SMO選擇一個最小錯誤值E2；如果E1是負，SMO選擇一個最大錯誤值E2.

在特殊情況下，SMO並不能通過上述第二個乘數的選擇取得優化效果。舉例來說，如果第一個和第二個訓練樣本有一樣的輸入變數x，這會導致目標函數編程半正定，就不會取得優化效果。在這種情況下，SMO在選擇第二個乘數時有層次地使用啟發式方法直到他找到一對能取得優化效果的乘數。在聯合優化兩個乘數時，如果有一個非零步長，就可以確定優化會取得效果。使用啟發式方法選擇第二個乘數時可以有以下層次：如果之前的啟發式方法沒有取得優化效果，SMO開始遍歷非邊界樣本，尋找第二個可以取得優化效果的樣本。如果非邊界樣本沒有一個能取得優化效果，SMO開始遍歷整個訓練集直到找到一個能取得優化效果的樣本。遍歷非邊界子集和遍歷整個訓練集都是隨機選取起始位置，這是為了不使SMO偏好在數據集開始位置的樣本。在極端環境下，可能找不到一個樣本作為第二個合適的（能取得優化效果的）樣本。這時第一個樣本就被跳過，SMO重新選擇一個樣本。

2.3 計算閾值

閾值b在每一步之後都會重新計算，為了使得兩個被優化的樣本都滿足KKT條件。在新的α1不在邊界時，以下閾值b1有效，因為他能保證輸入x1通過SVM計算輸出y1：

同理：

當b1和b2都有效時他們是相等的。當兩個新乘數都在邊界上而且L不等於H時，b1和b2之間的值就是和KKT條件一致的閾值。SMO選擇b1和b2的中間值作為閾值。

2.4 線性SVM的優化

為了計算線性SVM，只有一個權重向量w（而不是所有非零乘數對應的訓練樣本）需要被存儲。如果聯合優化成功，權重向量需要更新反映新的乘數。更新權重向量很容易，因為SVM的線性特性：

2.5 代碼詳細

以下偽代碼描述了整個SMO演算法：

target = desired output vectorpoint = training point matrixprocedure takeStep(i1,i2) if (i1 == i2) return 0 alph1 = Lagrange multiplier for i1 y1 = target[i1] E1 = SVM output on point[i1] – y1 (check in error cache) s = y1*y2 Compute L, H via equations (13) and (14) if (L == H) return 0 k11 = kernel(point[i1],point[i1]) k12 = kernel(point[i1],point[i2]) k22 = kernel(point[i2],point[i2]) eta = k11+k22-2*k12 if (eta > 0) { a2 = alph2 + y2*(E1-E2)/eta if (a2 < L) a2 = L else if (a2 > H) a2 = H } else { Lobj = objective function at a2=L Hobj = objective function at a2=H if (Lobj < Hobj-eps) a2 = L else if (Lobj > Hobj+eps) a2 = H else a2 = alph2 } if (|a2-alph2| < eps*(a2+alph2+eps)) return 0 a1 = alph1+s*(alph2-a2) Update threshold to reflect change in Lagrange multipliers Update weight vector to reflect change in a1 & a2, if SVM is linear Update error cache using new Lagrange multipliers Store a1 in the alpha array Store a2 in the alpha array return 1endprocedureprocedure examineExample(i2) y2 = target[i2] alph2 = Lagrange multiplier for i2 E2 = SVM output on point[i2] – y2 (check in error cache) r2 = E2*y2 if ((r2 < -tol && alph2 < C) || (r2 > tol && alph2 > 0)) { if (number of non-zero & non-C alpha > 1) { i1 = result of second choice heuristic (section 2.2) if takeStep(i1,i2) return 1 } loop over all non-zero and non-C alpha, starting at a random point { i1 = identity of current alpha if takeStep(i1,i2) return 1 } loop over all possible i1, starting at a random point { i1 = loop variable if (takeStep(i1,i2) return 1 } } return 0endproceduremain routine: numChanged = 0; examineAll = 1; while (numChanged > 0 | examineAll) { numChanged = 0; if (examineAll) loop I over all training examples numChanged += examineExample(I) else loop I over examples where alpha is not 0 & not C numChanged += examineExample(I) if (examineAll == 1) examineAll = 0 else if (numChanged == 0) examineAll = 1 }

2.6 和之前演算法的關係

SMO演算法和之前的SVM演算法有關，SMO演算法可以看做Osuna演算法的一個特例：每次優化的樣本大小是2而且每一步都通過啟發式方法更新拉格朗日乘數。

SMO演算法和叫做Bregman方法（見文獻3）或行操作方法（見文獻5）的優化演算法家族有緊密關係。這些方法解決帶線性約束的凸二次規劃問題。他們都是迭代方法，每一步投射當前初始點到每一個約束條件上。原始的Bregman方法不能直接解決QP問題（見公式11），因為SVM的閾值導致對偶問題中有一個線性等式約束。如果每一步只規劃一個約束，將不滿足線性等式約束。用術語來說，在由所有帶閾值b的權重向量的可能值組成的聯合空間上最小化權重向量的取值範圍這個主要問題產生了一個沒有唯一最小值的Bregman D維投影（見文獻3、6）。

考慮閾值b固定為0的SVM是很有意思的事。一個固定閾值的SVM不會有線性等式約束（6）。因此，每次只有一個乘數需要更新（可以通過一個行操作方法）。不幸的是，傳統的Bregman方法由於（8）中的鬆弛變數的原因不適用於這樣的SVM。鬆弛變數的存在導致Bregman D維投影在權重向量和鬆弛變數組成的空間裡面不是唯一的。

幸運的是，SMO可以稍加修改用來解決固定閾值的SVM。SMO通過更新單個拉格朗日乘數來獲得Ψ在對應維度上的最小值。更新規則如下：

這個更新公式強制SVM的輸出為y1（類似於Bregman方法或Hildreth的QP方法（見文獻10）。在計算出新的α之後，截斷在[0,C]之間（不像之前的方法）。選擇哪個乘數去優化和2.2部分描述的第一個啟發式選擇方法一樣。

用來解決線性SVM的固定閾值的SMO在概念上類似於感知機鬆弛規則（見文獻8），即感知機的輸出在有誤差的時候進行調整，以使輸出正好位於間隔上。但是，固定閾值的SMO演算法有時會減少訓練輸入在權重向量的佔比以最大化間隔。這個鬆弛規則時常會增加訓練輸入在權重向量的數量，這不會最大化間隔。用高斯核函數的固定閾值的SMO也和資源分配網路演算法（RAN，見文獻18）有關。RAN檢測某幾種特定的誤差，分配一個核函數來糾正這個誤差。SMO也做相似的事。但SMO/SVM會調整核函數的高度（什麼叫核函數的高度？the heights of the kernels）來在特徵空間最大化間隔，而RAN只是簡單地使用LMS來調整核函數的高度和寬度。

3 Benchmarking SMO

在幾個問題（收入預測、網頁分類、人造數據集）上的測試和性能對比數據，略過不翻譯了。

4 結論

前面內容的總結，略過不翻譯了。

單詞、短語：

1.solved analytically 有解析解

2.a time-consuming numerical QP optimization 耗時的QP數值優化

3.numerical quadratic programming 數值二次規劃，用數值優化的方法解QP問題

4.analytic QP 解析二次規劃，用二次規劃的解析解來解QP問題

5.margin 間隔

6.margin failure 落在間隔內

7.box constraint 邊界約束

8.neural network non-linearities 非線性神經網路

9.a quadratic program 二次規劃

10.chunking 分組

11.for some value of M 某些M值

12.zero Lagrange multipliers 零乘數，值為0的拉格朗日乘數

13.numerical QP optimization step QP數值優化步

14.self-consistent 自洽

15.uses a hierarchy of second choice heuristics 選擇第二個乘數時有層次地使用啟發式方法

16.make positive progress 取得優化效果

17.valid 有效

18.project the current primal point onto each constraint 投射當前初始點到每一個約束條件上

19.

minimizing the norm of the weight vector 最小化權重向量的取值範圍，norm作「正常水平」解。本句主幹為the primal problem of minimizing xx over xx space of (xx with xx) produces ...

推薦閱讀：