Sequential Minimal Optimization:
A Fast Algorithm for Training Support Vector Machines
John C. Platt
Microsoft Research
[email protected]
Technical Report MSR-TR-98-14
April 21, 1998
? 1998 John Platt
摘要（ABSTRACT）
本文提出了一種新的支持向量機（Support Vector Machines）演算法：序列最小優化演算法(Sequential Minimal Optimization，SMO)，訓練支持向量機需要解決一個非常大的二次規劃（Quadratic Programming，QP）優化問題，SMO將這個非常大的QP問題分成了一系列盡可能少的QP問題，對這些小的QP問題使用決議解，避免使用耗時間的數值型QP優化問題作為內部回圈，SMO所需的記憶體量在訓練集大小上是線性的，這允許SMO處理非常大的訓練集，由于避免了矩陣計算，對于各種測驗問題，SMO在訓練集大小上的縮放在線性和二次之間，而標準的分塊SVM演算法在訓練集大小上的縮放在線性和三次之間，SMO演算法的計算時間主要受SVM演算法計算時間的影響，因此對于線性支持向量機和稀疏資料集，SMO演算法的計算速度最快，在真實世界的稀疏資料集上，SMO演算法可以比分塊演算法快1000倍以上，
1 引言（INTRODUCTION）
在過去的幾年里，人們對支持向量機(SVMs)的興趣激增[1][2][3]，經驗表明，支持向量機在各種各樣的問題上都具有良好的泛化性能，如手寫字符識別[4]、人臉檢測[5]、行人檢測[6]和文本分類[7]，
然而，支持向量機的使用仍然局限于一小部分研究人員，一個可能的原因是支持向量機的訓練演算法很慢，特別是對于大問題，另一種解釋是，SVM訓練演算法復雜、精細，一般工程師難以實作，
本文描述了一種新的支持向量機學習演算法，該演算法概念簡單，易于實作，通常速度更快，與標準的支持向量機訓練演算法相比，對困難的支持向量機問題具有更好的縮放特性，新的SVM學習演算法被稱為SMO，與以前使用數值QP作為內環的SVM學習演算法不同，SMO使用決議QP步驟，
本文首先對支持向量機進行了概述，并對現有的支持向量機訓練演算法進行了綜述，然后詳細介紹了SMO演算法，包括，決議QP步驟的求解，選擇內環優化變數的啟發式演算法，如何設定SVM的閾值，一些特殊情況下的優化，演算法的偽代碼，以及SMO與其他演算法的關系，
SMO已經在兩個真實資料集和兩個人工資料集上進行了測驗，本文給出了這些資料集定時SMO與標準“分塊”演算法的對比結果，并給出了基于這些定時的結論，最后，有一個附錄，描述了決議優化的推導，
1.1 支持向量機概述
圖1 線性支持向量機
Vladimir Vapnik在1979年發明了支持向量機[1:1]，在最簡單的線性形式中,支持向量機是一種超平面，它將一組正例與一組反例分隔開，并具有最大的邊界(見圖1)，在線性情況下，邊界\(m\)由超平面到最近的正例和反例的距離定義，線性支持向量機的輸出公式為
\[u=\vec{w} \cdot \vec{x} - b \tag{1} \]其中\(w\)為超平面的法向量， \(x\)為輸入向量，分離超平面是平面 \(u=0\)，最近的點位于\(u =±1\)平面上，邊界\(m\)是這樣的
\[m=\frac{1}{||\vec{w}||^2}\tag{2} \]邊界最大化可以通過以下優化問題[3:1]表示:
\[\begin{align*} \min_{\vec{w},b} \quad &\frac{||\vec{w}||^2}{2} ,\\ s.t \quad &\ y_i(\vec{w} \cdot x_i-b)\geq 1,\forall i \tag{3} \end{align*} \]式中，\(x_i\)為第\(i\)個訓練示例，\(y_i\)為第\(i\)個訓練示例的SVM正確輸出，\(y_i\)的值對于類中的正例子是+1，對于反例子是-1，
使用拉格朗日量，這個優化問題可以轉換成對偶形式，這是一個QP問題，其中目標函式\(Ψ\)單獨依賴于一組拉格朗日乘子\(α_i\)，
\[\min_{\vec{α}}Ψ(\vec{α})=\min_{\vec{α}}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_j(\vec{x_i} \cdot \vec{x_j})α_iα_j-\sum_{i=1}^{N}α_i \tag{4} \](N為訓練例數)，受不等式約束,
\[α_i\geq 0,\forall i \tag{5} \]一個線性等式約束，
\[\sum_{i=1}^N y_iα_i =0 \tag{6} \]在每個拉格朗日乘數和每個訓練示例之間有一個一對一的關系，一旦確定了拉格朗日乘子，就可以由拉格朗日乘子求出法向量 \(\vec{w}\) 和閾值 \(b\):
\[\vec{w}=\sum_{i=1}^{N}y_iα_i\vec{x_i} ,\\\\ b=\vec{w}\cdot\vec{x_k}-y_k\ for \ some \ α_k > 0 \tag{7} \]因為\(\vec{w}\) 在使用之前可以通過公式(7)從訓練資料中計算出來，所以評估一個線性支持向量機所需的計算量在非零支持向量的數量上是恒定的，
當然，不是所有的資料集都是線性可分的，可能沒有超平面把正面的例子和負面的例子分開，在上面的公式中，不可分離的情況將對應一個無窮解，然而，在1995年，Cortes & Vapnik[8]建議對原始優化陳述句(3)進行修改，對未能達到正確的邊界進行懲罰，修改成:
\[\begin{align*} \min_{\vec{w},b,\vec{ξ} }& \quad \frac{1}{2}||\vec{w}||^2+C\sum_{i=1}^{N}ξ_i \\ s.t. & \quad y_i(\vec{w}\cdot\vec{x_i}-b)\geq1-ξ_i,\forall i,\tag{8} \end{align*} \]其中\(ξ_i\)是松弛變數，允許邊界失效，而\(C\)是一個引數，它權衡了大范圍邊界與少量邊界失效之間的關系，當這個新的優化問題轉化為對偶形式時，只需將約束(5)變為框約束:
\[0\leq α\leq C,\forall i \tag{9} \]變數\(ξ_i\)在對偶公式中根本沒有出現，
支持向量機甚至可以進一步推廣到非線性分類器[9]，非線性的輸出
SVM由拉格朗日乘數顯式計算:
其中\(K\)是核函式，用于度量輸入向量\(\vec{x}\)和存盤的訓練向量\(\vec{x_j}\)之間的相似度或距離，\(K\)的例子包括高斯、多項式和神經網路非線性[3:2]，如果\(K\)是線性的，則恢復線性支持向量機(1)的方程，
拉格朗日乘子\(α_i\)仍然通過二次程式計算，非線性改變了二次形式，但對偶目標函式\(Ψ\)在\(α\)中仍然是二次的:
\[\begin{align*} \min_{\vec{α}}Ψ(\vec{α})=&\min_{\vec{α}}\frac{1}{2}\sum_{i=1}^{N}\sum_{j=1}^{N}y_iy_jK(\vec{x_i} \cdot \vec{x_j})α_iα_j-\sum_{i=1}^{N}α_i \\ &0\leq α\leq C,\forall i \\ &\sum_{i=1}^N y_iα_i =0 \tag{11} \end{align*} \]上式(11)中的QP問題就是SMO演算法要解決的QP問題，為了使上述QP問題是正定的，核函式K必須服從Mercer條件[3:3]，
KKT(Karush-Kuhn-Tucker)條件是正定QP問題最優點的充分必要條件，QP問題(11)的KKT條件特別簡單，當對于所有i:
式中，\(u_i\)是第\(i\)個訓練例的SVM輸出，注意，KKT條件可以一次在一個示例上求值，這在構建SMO演算法時很有用，
1.2 支持向量機的訓練方法
由于其巨大的規模，支持向量機產生的QP問題(11)不能輕易地通過標準的QP技術來解決，(11)中的二次形式涉及到一個矩陣，其元素的數量等于訓練示例數量的平方，這個矩陣不能容納,如果有超過4000個訓練示例，則為128兆位元組，
Vapnik[1:2]描述了一種解決SVM QP的方法，自此被稱為“分塊”，分塊演算法利用了這樣一個事實:如果去掉拉格朗日乘子為0的矩陣的行和列，那么二次型矩陣的值是相同的，因此，大的QP問題可以分解為一系列小的QP問題，這些小問題的最終目標是識別所有非零的拉格朗日乘數，并丟棄所有的零，拉格朗日乘數法，在每個步驟中，分塊解決由以下內容組成的QP問題，示例:上一步的每個非零拉格朗日乘子，以及M個違反KKT條件的最差示例(12)[3:4]，對于M的某個值(參見圖2)，如果在某一步中違反KKT條件的示例少于M個，則添加所有違反KKT條件的示例，每個QP子問題都使用前一個子問題的結果進行初始化，最后一步確定了整個非零拉格朗日乘子集合，從而解決了大型QP問題，
分塊嚴重地將矩陣的大小從訓練樣本數量的平方降低到近似于非零拉格朗日乘子數量的平方，然而，分塊仍然無法處理大規模訓練問題，因為即使是這個簡化矩陣也無法裝入記憶體，
圖2
圖2，訓練支持向量機的三種替代方法:分塊、Osuna演算法和SMO，對于每種方法，說明了三個步驟，每一步的水平細線代表訓練集，而厚框代表在這一步優化的拉格朗日乘數，對于分塊，每一步添加固定數量的示例，而每一步丟棄零拉格朗日乘數，因此，每一步訓練的例子數量趨于增長，對于Osuna的演算法，每一步優化固定數量的示例:添加相同數量的示例
1997年，Osuna等人[10]證明了一個定理，提出了一套新的支持向量機QP演算法，該定理證明了大QP問題可以分解為一系列小QP子問題，只要在前一個子問題的樣例中添加至少一個違反KKT條件的樣例，每一步都會降低總體目標函式，并保持一個滿足所有約束條件的可行點，因此，一個序列如果QP子問題中總添加至少一個違例者，則保證收斂，注意，分塊演算法服從定理的條件，因此會收斂，
Osuna等人建議為每個QP子問題保持一個固定大小的矩陣，這意味著在每一步[10:1]添加和洗掉相同數量的示例(見圖2)，使用固定大小的矩陣將允許在任意大小的資料集上進行訓練，Osuna的論文[10:2]中給出的演算法建議每一步增加一個示例并減去一個示例，顯然，這是低效的，因為它將使用整個數值QP優化步驟來使一個訓練示例遵守KKT條件，在實踐中，研究人員根據未發表的啟發式演算法[11]對多個實體進行加減運算，無論如何，所有這些方法都需要一個數值QP求解器，眾所周知，QP數值很難正確計算;有許多數值精度問題需要解決，
2 序列最小優化演算法
序列最小優化(SMO)是一種簡單的演算法，可以快速求解SVM QP問題，不需要任何額外的矩陣存盤，也完全不需要使用數值QP優化步驟，SMO將整個QP問題分解為QP子問題，利用Osuna定理保證演算法的收斂性，
與以往方法不同，SMO在每一步都選擇解決盡可能小的優化問題，對于標準的SVM QP問題，最小可能的優化問題包含兩個拉格朗日乘子，因為拉格朗日乘子必須服從一個線性等式約束，在每一步，SMO選擇兩個拉格朗日乘子進行聯合優化，找到這些乘子的最優值，并更新SVM以反映新的最優值(見圖2)，
SMO的優點在于可以決議地求解兩個拉格朗日乘子，因此，完全避免了數值QP優化，演算法的內部回圈可以用少量的C代碼來表示，而不是呼叫整個QP庫例程，即使在演算法的程序中解決了更多的優化子問題，但每個子問題的速度都非常快，從而快速地解決了整個QP問題，
此外，SMO完全不需要額外的矩陣存盤，因此，非常大的SVM訓練問題可以放在普通個人計算機或作業站的記憶體中，由于SMO演算法沒有使用矩陣演算法，因此不易受到數值精度問題的影響，
SMO有兩個組成部分:用于求解兩個拉格朗日乘子的決議方法，以及用于選擇優化哪些乘子的啟發式方法，
圖3
圖3所示，兩個拉格朗日乘數必須滿足整個問題的所有約束條件，不等式約束導致拉格朗日乘數在方框中，線性等式約束使它們位于一條對角線上，因此，SMO演算法的第一步必須在對角線上找到目標函式的最優解，
2.1 求解兩個拉格朗日乘數
為了求解這兩個拉格朗日乘子，SMO首先計算對這兩個乘子的約束，然后求解約束最小值，為了方便起見，所有指向第一個乘數的量的下標都是1，而指向第二個乘數的量的下標都是2，因為只有兩個乘數，約束可以很容易地在二維中顯示(參見圖3)，邊界約束(9)導致拉格朗日乘子位于方框中，而線性等式約束(6)使得拉格朗日乘子位于對角線上，因此，目標函式的約束最小值必須位于對角線段上(如圖3所示)，這個約束解釋了為什么可以優化的拉格朗日乘子的最小數量是2:如果SMO只優化一個乘子，它就不能在每一步都滿足線性等式約束，
對角線段的端點可以很簡單地表示出來，該演算法在不失一般性的前提下，首先計算第二個拉格朗日乘子\(α_2\)，然后根據\(α_2\)計算對角線段的端點，如果目標\(y_1\)不等于目標\(y_2\)，則適用于\(α_2\):
\[L=max(0,α_2-α_1),\qquad H=min(C,C+α_2-α_1) \tag{13} \]如果目標\(y_1\)等于目標\(y_2\)，那么下面的邊界適用于\(α_2\):
\[L=max(0,α_2+α_1-C),\qquad H=min(C,α_2+α_1) \tag{14} \]目標函式沿對角線的二階導數可以表示為:
\[η=K(\vec{x_1} \cdot \vec{x_1})+K(\vec{x_2} \cdot \vec{x_2})-2K(\vec{x_1} \cdot \vec{x_2}) \tag{15} \]通常情況下，目標函式是正定的，沿著線性等式約束的方向會有一個最小值，\(η\)會大于零，在這種情況下，SMO會計算約束方向上的最小值:
\[α_2^{new}=α_2+\frac{y_2(E_1-E_2)}{η} \tag{16} \]其中\(E_i=u_i-y_i\)為第\(i\)個訓練樣本的誤差，下一步，通過將無約束最小值裁剪到線段的末端來找到有約束的最小值:
\[α_2^{new,clipped}= \begin{cases} H \quad \ \ \ \ if\quad α_2^{new}\geq H \\ α_2^{new} \quad if \quad L<α_2^{new}<H \\ L \quad \ \ \ \ \ if \quad α_2^{new}\leq L \end{cases} \tag{17} \]現在令\(s=y_1y_2\)，\(α_1\)的值是根據裁剪后的新\(α_2\)計算得到的:
\[α_1^{new}=α_1+s(α_2^{new}-α_2^{new,clipped}) \tag{18} \]在不尋常的情況下，\(η\)不會是正的，如果核函式\(K\)不符合Mercer條件，則η為負，從而導致目標函式變得不確定，即使有一個正確的內核，如果多個訓練示例具有相同的輸入向量\(x\)， \(η\)也可以為零，在任何情況下，即使\(η\)不是正的，SMO也將作業，在這種情況下，目標函式\(Ψ\)應該在線段的每個端點進行評估:
\[\begin{align*} f_1 &= y_1(E_1+b)-α_1K(\vec{x_1} \cdot \vec{x_1})-sα_2K(\vec{x_1} \cdot \vec{x_2})\\ f_2 &= y_2(E_2+b)-sα_1K(\vec{x_1} \cdot \vec{x_2})-α_2K(\vec{x_2} \cdot \vec{x_2})\\ L_1 &= α_1+s(α_2-L)\\ H_1 &= α_1+s(α_2-H)\\ Ψ_L &= L_1f_1+Lf_2+\frac{1}{2}L_1^2K(\vec{x_1} \cdot \vec{x_1})+\frac{1}{2}L^2K(\vec{x_1} \cdot \vec{x_2})+sLL_1K(\vec{x_1} \cdot \vec{x_2}) \\ Ψ_H &= H_1f_1+Hf_2+\frac{1}{2}H_1^2K(\vec{x_1} \cdot \vec{x_1})+\frac{1}{2}H^2K(\vec{x_1} \cdot \vec{x_2})+sHH_1K(\vec{x_1} \cdot \vec{x_2}) \tag{19} \end{align*} \]SMO將拉格朗日乘子移動到目標函式值最小的端點，如果兩端的目標函式相同(四舍五入誤差在一個很小的\(ε\)內)，且核函式符合Mercer條件，則聯合最小化無法取得進展，該場景描述如下，
2.2 選擇優化乘數的啟發式
只要SMO總是在每一步優化和改變2個拉格朗日乘子，并且至少有一個拉格朗日乘子在這一步之前違反了KKT條件，那么每一步都會根據Osuna[10:3]定理減小目標函式，因此收斂性得到了保證，為了加快收斂速度，SMO使用啟發式方法選擇兩個拉格朗日乘子進行聯合優化，
有兩個獨立的選擇啟發式演算法:一個用于第一個拉格朗日乘子，另一個用于第二個，SMO演算法的外回圈由第一種啟發式演算法構成，外回圈首先遍歷整個訓練集，確定每個樣本是否違反KKT條件(12)，如果一個例子違反了KKT條件，那么它就有資格進行優化，在遍歷整個訓練集之后，外回圈迭代拉格朗乘子既不為0也不為C的所有示例(非邊界示例)，同樣，每個示例都根據KKT條件進行檢查，違反條件的示例有資格進行優化，外回圈對非邊界樣本進行重復遍歷，直到所有的非邊界樣本都滿足\(ε\)內的KKT條件，然后，外回圈回傳并遍歷整個訓練集，外回圈在對整個訓練集的單遍遍歷和對非邊界子集的多遍遍歷之間交替進行，直到整個訓練集服從\(ε\)內的KKT條件，此時演算法終止，
第一選擇啟發式演算法將CPU時間集中在最可能違反KKT條件的例子上:非邊界子集，隨著SMO演算法的進行，在邊界處的樣例很可能會停留在邊界處，而不在邊界處的樣例會隨著其他樣例的優化而移動，因此，SMO演算法將遍歷非邊界子集，直到該子集是自洽的，然后SMO演算法將掃描整個資料集，尋找因優化非邊界子集而違反KKT的邊界樣本，
注意，KKT條件被檢查為滿足ε，通常情況下，\(ε\)被設定為\(10^{-3}\)，識別系統通常不需要滿足高精度的KKT條件:對于正余量的例子，輸出在0.999到1.001之間是可以接受的，如果需要產生非常高的精度輸出，SMO演算法(和其他SVM演算法)將無法快速收斂，
一旦選擇了第一個拉格朗日乘子，SMO就會選擇第二個拉格朗日乘子來最大化聯合優化程序中所采取的步長，現在，計算核函式\(K\)是耗時的，因此SMO用公式(16)中的分子的絕對值近似步長:\(|E_1-E_2|\)，SMO為訓練集中的每個非邊界樣本保存一個快取的誤差值\(E\)，然后選擇一個誤差來近似最大化步長，如果\(E_1\)為正，SMO選擇一個誤差最小的樣本\(E_2\)，當\(E_1\)為負時，SMO選擇誤差最大的\(E_2\)，
在特殊情況下，SMO無法使用上述第二選擇啟發式演算法取得積極進展，例如，如果第一個和第二個訓練樣本共享相同的輸入向量x，則無法取得積極的進展，這導致目標函式變得半定，在這種情況下，SMO使用一層第二選擇啟發式演算法，直到找到一對可以取得積極進展的拉格朗日乘數，通過對兩個拉格朗日乘子進行聯合優化，使步長不為零，可以確定取得了積極進展，第二選擇啟發式的層次結構包括以下內容，如果上述啟發式方法沒有取得積極進展，那么SMO就開始迭代非邊界樣例，尋找第二個可以取得積極進展的樣例，如果沒有一個非邊界樣本取得正進展，那么SMO開始迭代整個訓練集，直到找到一個取得正進展的樣本，對非邊界樣本的迭代和對整個訓練集的迭代都是從隨機位置開始的，以便使SMO不偏向訓練集開始時的樣本，在極端墮落的情況下，沒有一個例子可以作為第二個例子，當發生這種情況時，第一個示例將被跳過，SMO將繼續使用另一個選擇的第一個示例，
2.3 閾值計算
每一步后重新計算閾值\(b\)，以便兩個優化示例都滿足KKT條件，當新的\(α_1\)不在邊界處時，下面的閾值\(b_1\)是有效的，因為當輸入為\(x_1\)時，它強制SVM的輸出為\(y_1\):
\[b_1=E_1+y_1(α_1^{new}-α_1)K(\vec{x_1} \cdot \vec{x_1})+y_2(α_2^{new,clipped}-α_2)K(\vec{x_1} \cdot \vec{x_2})+b \tag{20} \]當新的\(α_2\)不在邊界處時，下面的閾值\(b_2\)是有效的，因為當輸入為\(x_2\)時，它強制SVM的輸出為\(y_2\):
\[b_2=E_2+y_1(α_1^{new}-α_1)K(\vec{x_1} \cdot \vec{x_2})+y_2(α_2^{new,clipped}-α_2)K(\vec{x_2} \cdot \vec{x_2})+b \tag{21} \]當\(b_1\)和\(b_2\)都有效時，它們是相等的，當新的拉格朗日乘子都有界且\(L\)不等于\(H\)時，\(b_1\)和\(b_2\)之間的區間都是符合KKT條件的閾值，SMO選擇閾值在\(b_1\)和\(b_2\)之間，
2.4 線性支持向量機的優化
要計算一個線性SVM，只需要存盤一個權重向量\(\vec{w}\)，而不是對應于非零拉格朗日乘子的所有訓練樣本，如果聯合優化成功，則需要更新存盤的權重向量以反映新的拉格朗日乘子值，由于SVM是線性的，權重向量的更新很容易:
\[\vec{w^{new} }=\vec{w}+y_1(α_1^{new}-α_1)\vec{x_1}+y_2(α_2^{new}-α_2)\vec{x_2} \tag{22} \]2.5 代碼的細節
下面的偽代碼描述了整個SMO演算法:
target = desired output vector
point = training point matrix
procedure 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 1
endprocedure
procedure 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 0
endprocedure
main 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,Lagrange乘子在每一步都被通過良好的啟發式選擇的新乘子替換，
SMO演算法與一系列優化演算法密切相關，這些演算法被稱為Bregman方法[12]或row-action方法[13]，這些方法用于求解具有線性約束的凸規劃問題，它們是迭代方法，其中每個步驟都將當前原始點投影到每個約束上，未修改的Bregman方法不能直接解決QP問題(11)，因為SVM中的閾值在對偶問題中產生了線性等式約束，如果每一步只投影一個約束，就會違反線性等式約束，用更專業的術語來說，在具有閾值b的所有可能權重向量\(\vec{w}\)的組合空間上最小化權重向量\(\vec{w}\)的范數的原始問題產生了一個Bregman-D投影，該投影沒有唯一的最小[12:1][14]，
有趣的是，考慮一個SVM，其閾值b固定為零，而不是被求解，固定閾值的SVM不具有線性等式約束(6)，因此，一次只需要更新一個拉格朗日乘子，可以使用行動作方法，然而，由于等式(8)中有松弛變數\(ξ_i\)，傳統的Bregman方法仍然不能適用于這類支持向量機，由于松弛變數\(ξ_i\)的存在，使得Bregman-D投影在權向量\(\vec{w}\)和松弛變數\(ξ_i\)的組合空間中變得非唯一
幸運的是，SMO可以被修改以解決固定閾值的SVM，SMO將每個拉格朗日乘子更新為對應維度上Ψ的最小值，更新規則為:
\[α_1^{new} = α_1 + \frac{y_1E_1}{K(\vec{x_1} \cdot \vec{x_1})} \tag{23} \]這個更新方程強制SVM的輸出為\(y_1\)(類似于Bregman方法或Hildreth的QP方法[15])，在計算出新的\(α\)后，它會被裁剪到\([0,C]\)區間(與之前的方法不同)，選擇優化拉格朗日乘子的方法與2.2節中描述的第一種啟發式方法相同，
線性SVM的固定閾值SMO在概念上類似于感知器放松規則[16]，其中感知器的輸出在出現錯誤時進行調整，以便輸出準確地位于邊界上，然而，固定閾值的SMO演算法有時會減少訓練輸入在權重向量中的比例，以最大化間隔，松弛規則不斷增加權重向量中的訓練輸入量，因此不是最大間隔，高斯核的固定閾值SMO也與資源分配網路(resource allocating network，RAN[17])演算法有關，當RAN檢測到某些型別的錯誤時，它將分配一個內核來精確地修復錯誤，SMO的表現類似，然而，SMO/SVM將調整核的高度以最大化特征空間中的間隔，而RAN將簡單地使用LMS來調整核的高度和權重，
3 基準測驗SMO
將SMO演算法與標準的分塊SVM學習演算法在一系列基準上進行了測驗，這兩個演算法都是用c++撰寫的，使用的是微軟的Visual c++ 5.0編譯器，兩種演算法都在一個未加載的266mhz Pentium II處理器上運行，該處理器運行Windows NT 4，
兩種演算法都利用了輸入向量的稀疏性，更具體地說，內核函式在內部回圈中依賴于點積，如果輸入是稀疏向量，那么輸入可以存盤為稀疏陣列，并且點積只會迭代非零輸入，將非零輸入乘以相應的權重累加，如果輸入是一個稀疏的二進制向量，那么可以存盤輸入中“1”的位置，并且點積將對輸入中“1”的位置對應的權重求和，
chunking演算法采用Burges[3:5]提出的投影共軛梯度演算法[18]作為QP求解器，為了確保分塊演算法是一個公平的基準，Burges比較了他在運行Solaris的200mhz Pentium II上分塊代碼的速度和基準分塊代碼的速度(關閉稀疏點積代碼)，測驗結果表明，測驗速度相當，表明分塊代碼是一個合理的基準測驗，
要確保分塊代碼和SMO代碼具有相同的精度，需要一定的注意，如果輸出值與正確值或半空格的距離大于\(10^{-3}\)，則SMO代碼和分塊代碼都將判定該示例違反了KKT條件，在分類任務中，閾值\(10^{-3}\)被選擇為一個微不足道的錯誤，投影共軛梯度碼有一個停止閾值，它描述了目標函式在每一步的最小相對改進[3:6]，如果投影的共軛梯度的改進值小于這個最小值，則共軛梯度碼終止，并進行另一個分塊步驟，Burges[3:7]建議使用常數\(10^{-10}\)作為這個最小值，
在下面的實驗中，在精度為\(10^{-10}\)時停止投影的共軛梯度，通常會使KKT違例大于\(10^{-3}\)，特別是對于非常大規模的問題，因此，基準分塊演算法使用以下啟發式方法設定共軛梯度停止閾值，閾值從3x\(10^{-10}\)開始，在每個分塊步驟之后，計算拉格朗日乘子不受限制的所有示例的輸出，計算這些輸出是為了計算閾值(參見[3:8])，每個例子都表明了一個建議的閾值，如果最大的建議閾值比最小的建議閾值高2x\(10^{-3}\)，那么在\(10^{-3}\)內不可能滿足KKT條件，因此，從下一個塊開始，共軛梯度閾值減小了3倍，這種啟發式方法將優化共軛梯度的速度:它只在最困難的問題上使用高精度，對于下面描述的大多數測驗，閾值保持在3x\(10^{-10}\)，使用的最小閾值為3.7x\(10^{-12}\)，這發生在最大的網頁分類問題分塊的最后，
SMO演算法在一個收入預測任務、一個網頁分類任務和兩個不同的人工資料集上進行了測驗，所有表中列出的所有時間的單位都是CPU秒，
3.1 收入預測
用于測驗SMO速度的第一個資料集是UCI“adult”資料集，可以在 ftp://ftp.ics.uci.edu/pub/machine-learning-databases/adult 上找到，SVM從一個家庭的人口普查表格中得到14個屬性，SVM的任務是預測該家庭的收入是否大于5萬美元，在14個屬性中，8個是類別屬性，6個是連續屬性，為了便于實驗，將6個連續屬性離散化為五分位數，總共產生123個二進制屬性，其中14>個為真，在"adult"訓練集中有32562個樣本，在該問題上訓練了兩種不同的SVM:線性SVM和使用方差為10的高斯核的徑向基函式SVM，選擇這個方差是為了最小化驗證集上的錯誤率，線性SVM的C極限值取0.05,RBF/SVM的C極限值取1，同樣，選擇這個限定值是為了最小化驗證集上的錯誤，
在adult資料集上，SMO演算法與線性SVM分塊演算法的時序性能對比如下表所示:
表1
通過隨機選取完整訓練集的子集來改變訓練集的大小，這些子集是嵌套的，分塊時間列中的“N/A”項的矩陣太大，無法裝入128兆位元組，因此由于記憶體抖動而無法計時，通過SMO來確定非邊界支持向量的數量和邊界支持向量的數量:由于在KKT條件下對誤差的容忍，分塊結果會有少量的變化，
通過對訓練時間與訓練集大小的對數圖擬合直線，可以推匯出SMO和分塊的經驗尺度，SMO訓練時間為~ \(N^{1.9}\)，而塊組訓練時間為~ \(N^{3.1}\)，因此，SMO將該問題的經驗擴展提高了不止一階，
使用高斯支持向量機進行SMO和分塊的時序性能如下圖所示:
表2
SMO演算法處理非線性支持向量機的速度要比線性支持向量機慢，因為時間主要取決于對支持向量機的評價，其中，SMO訓練時間尺度為~ \(N^{2.1}\)，而塊組尺度為~ \(N^{2.9}\)，同樣，SMO的擴展速度大約比分塊快一個訂單，收益預測檢驗表明，對于在邊界上有許多支持向量的真實稀疏問題，SMO比分塊要快得多
3.2 網頁分類
SMO的第二個測驗是文本分類:對網頁是否屬于某個類別進行分類，訓練集由49749個網頁組成，每個網頁提取300個稀疏的二進制關鍵字屬性，在這個問題上嘗試了兩種不同的支持向量機:線性支持向量機和非線性高斯支持向量機，其方差為10，線性支持向量機的C值取1，非線性支持向量機的C值取5，同樣，選擇這些引數是為了最大化驗證集的性能，
SMO與線性支持向量機分塊的時間如下表所示:
表3
對于該資料集上的線性支持向量機，SMO訓練時間尺度為~ \(N^{1.6}\)，塊集尺度為~ \(N^{2.5}\)，這個實驗是SMO在計算時間上優于分塊的另一種情況，
SMO與非線性支持向量機分塊的時間如下表所示:
表4
對于該資料集上的非線性支持向量機，SMO訓練時間尺度為~ \(N^{1.7}\)，塊集尺度為~ \(N^{2.0}\)，在這種情況下，SMO的可伸縮性比分塊要好:SMO比分塊快2到6倍，非線性檢驗表明，當非定界支持向量數量較大且輸入資料集稀疏時，SMO演算法仍然比分塊演算法更快，
3.3 人工資料集
SMO還在人工生成的資料集上進行了測驗，以探索SMO在極端場景下的性能，第一個人工資料集是完全線性可分的資料集，輸入資料是隨機的二元300維向量，輸入“1”的比例為10%，在[-1,1]中隨機生成一個300維的權重向量，如果權重與輸入點的點積大于1，則該輸入點被賦予一個正標簽，如果點積小于-1，則賦一個負標簽，如果點積的值在-1到1之間，則該點被丟棄，用線性SVM對該資料集進行擬合，
對于線性SVM來說，線性可分的資料集是最簡單的問題，毫不奇怪，訓練集大小的擴展對于SMO和分塊都很好，運行時間如下表所示:
表5
這里，SMO運行時間的尺度為~ \(N\)，略優于分塊的尺度，分塊的尺度為~ \(N^{1.2}\)，因此，對于這個簡單的稀疏問題，分塊和SMO通常是可以比較的，兩種演算法都在C設定為100的情況下進行訓練，用于分塊的塊大小設定為500，
在這個簡單的資料集上，可以測量出SMO演算法和分塊演算法由于稀疏點積編碼而帶來的加速，使用稀疏點積編碼和不使用稀疏點積編碼對相同的資料集進行了測驗，對于非稀疏實驗，每個輸入點存盤為一個300維的浮點向量，稀疏/非稀疏實驗結果如下表所示:
表6
對于SMO，使用稀疏資料結構可以使代碼速度提高10倍以上，這表明SVM的評估時間完全支配SMO的計算時間，稀疏點積代碼對分塊計算的速度僅提高了1.1倍左右，這表明數值QP步驟的計算在分塊計算中占主導地位，對于線性可分的情況，在有界處絕對沒有拉格朗日乘子，這是SMO的最壞情況，因此，應該考慮到本實驗中非稀疏SMO相對于非稀疏分塊的性能較差
稀疏與非稀疏實驗表明，SMO演算法相對于分塊演算法的部分優勢來自于對稀疏點積碼的利用，幸運的是，許多現實世界的問題都有稀疏輸入，除了3.1節和3.2節中描述的真實資料集之外，任何量化或模糊隸屬編碼問題都將是稀疏的，此外，光學字符識別[4:1]、手寫字符識別[19]和自然影像[20][6:1]的小波變換系數都傾向于自然地表達為稀疏資料，
第二個人工資料集與第一個簡單資料集形成了鮮明的對比，第二組是由隨機300維二進制輸入點(10%“1”)和隨機輸出標簽生成的，因此支持向量機是擬合純噪聲的，C值被設定為0.1，因為這個問題根本無法解決，將SMO和chunking應用于線性SVM的結果如下所示:
表7
在第二個資料集上，SMO和分塊的擴展性要高得多，這反映了問題的難度，SMO演算法的計算時間為~ \(N^{1.8}\)，而chunking演算法的計算時間為~ \(N^{3.2}\)，第二個資料集表明，當大多數支持向量都處于邊界時，SMO的效果更好，因此，為了確定稀疏點積編碼帶來的速度提升，我們在沒有稀疏點積編碼的情況下測驗了SMO和chunking:
表8
在線性支持向量機的情況下，稀疏點積代碼使SMO的速度提高了約6倍，而分塊演算法的速度只提高了最小，在這個實驗中，即使對于非稀疏的資料，SMO也比分塊更快，
第二個資料集也使用方差為10的高斯svm進行了測驗，C值仍然被設定為0.1，高斯svm的結果如下表所示:
表9
表10
當高斯SVM適合純噪聲時，SMO的計算時間約為~ \(N^{2.2}\)，而chunking的計算時間約為~ \(N^{3.4}\)，到目前為止，純噪聲情況下的擴展效果最差，但SMO比分塊擴展效果好不止一個數量級，即使應用于非稀疏資料，SMO的總運行時間仍然優于分塊，輸入資料的稀疏性使得非線性情況下SMO的計算速度提高了約4倍，這表明對于非線性支持向量機而言，點積速度仍然是SMO計算速度的主要因素
4 結論
SMO是一種改進的svm訓練演算法，與其他SVM訓練演算法一樣，SMO將一個大的QP問題分解為一系列小的QP問題，與其他演算法不同的是，SMO演算法利用了盡可能小的QP問題，能夠快速決議地求解，極大地提高了演算法的可擴展性和計算時間，
SMO在現實問題和人工問題上都進行了測驗，通過這些測驗，可以得出以下結論:
- 當用戶不容易訪問二次編程包和/或不希望調整該QP包時，可以使用SMO，
- SMO在許多拉格朗日乘子有界的svm上表現非常好，
- SMO在線性SVM上表現良好，這是因為SMO的計算時間主要由SVM的計算時間決定，而線性SVM的計算可以表示為單個點積而不是線性核的和，
- SMO對于稀疏輸入的svm表現良好，甚至對于非線性的svm，因為可以減少核計算時間，直接加快SMO的速度，由于分塊的大部分時間都花在QP代碼上，它不能利用SVM的線性和輸入資料的稀疏性，
- SMO對于大型問題表現良好，因為對于迄今為止嘗試過的所有測驗問題，SMO隨著訓練集大小的擴展比分塊要好，
對于不同的測驗集，SMO的訓練時間在 ~ \(N\) 到 ~ \(N^{2.2}\)之間，組塊分析的訓練時間在 ~ \(N^{1.2}\) ，~ \(N^{3.4}\) 之間，SMO的擴展性可以比chunking好不止一個訂單，對于真實世界的測驗集，對于線性svm, SMO的速度可以提高1200倍，對于非線性svm可以提高15倍，
由于SMO易于使用，并且可以隨著訓練集的大小而更好地擴展，因此很有可能成為標準的SVM訓練演算法，在得出最終結論之前，還需要對其他QP技術和最佳Osuna啟發式演算法進行更多的基準實驗，
致謝
感謝Lisa Heilbron協助撰寫案文，感謝Chris Burges使用他的投影共軛梯度代碼運行了一個資料集，感謝Leonid Gurvits指出SMO與Bregman方法的相似性，
附錄:兩例最小化的推導
SMO的每一步都會優化兩個拉格朗日乘子，不失一般性，這兩個乘數是 \(α_1\) 和 \(α_2\) ，式(11)的目標函式 \(Ψ\) 可以寫成:
\[Ψ=\frac{1}{2}K_{11}α_1^2+\frac{1}{2}K_{22}α_2^2+sK_{12}α_1α_2+y_1α_1v_1+y_2α_2v_2-α_1-α_2+Ψ_{constant} \tag{24} \]\[\begin{align*} K_{ij} =& K(\vec{x_i} \cdot \vec{x_j}),\\ v_i =& \sum_{j=3}^Ny_jα_j^*K_{ij}\\ =&u_i+b^*-y_1α_1^*K_{1i}-y_2α_2^*K_{2i}\tag{25} \end{align*} \]星號變數表示上一個迭代結束時的值，\(Ψ_constant\) 是不依賴于 \(α_1\) 或 \(α_2\) 的項，
每一步都要沿著線性等式約束(6)定義的直線找到最小值，該線性等式約束可以表示為
\[α_1+sα_2=α_1^*=w \tag{26} \]沿著線性等式約束的目標函式可以用 \(α_2\) 單獨表示:
\[\begin{align*} Ψ=&\frac{1}{2}K_{11}(w-sα_2)^2+\frac{1}{2}K_{22}α_2^2+sK_{12}(w-sα_2)α_2 \\ &+y_1(w-sα_2)v_1-w+sα_2+y_2α_2v_2-α_2+Ψ_{constant} \tag{27} \end{align*} \]目標函式的極值為
\[\begin{align*} \frac{dΨ}{dα_2}=&-sK_{11}(w-sα_2)+K_{22}α_2-K_{12}α_2+sK_{12}(w-sα_2) \\ &-y_2v_1+s+y_2v_2-1=0 \tag{28} \end{align*} \]如果二階導是正的，這是通常的情況，那么 \(α_2\) 的最小值可以表示為
\[α_2(K_{11}+K_{22}-2K_{12})=s(K_{11}-K_{12})w+y_2(v_1-v_2)+1-s) \tag{29} \]將 \(w\) 和 \(v\) 的方程展開
\[α_2(K_{11}+K_{22}-2K_{12})=α_2^*(K_{11}+K_{22}-2K_{12})+y_2(u_1-u_2+y_2-y_1) \tag{30} \]更多的代數運算得到方程(16)，
Vapnik, V., Estimation of Dependences Based on Empirical Data, Springer-Verlag, (1982). ?? ?? ??
Vapnik, V., The Nature of Statistical Learning Theory, Springer-Verlag, (1995). ??
Burges, C. J. C., "A Tutorial on Support Vector Machines for Pattern Recognition,"submitted to Data Mining and Knowledge Discovery, http://svm.research.bell-labs.com/SVMdoc.html, (1998). ?? ?? ?? ?? ?? ?? ?? ?? ??
LeCun, Y., Jackel, L. D., Bottou, L., Cortes, C., Denker, J. S., Drucker, H., Guyon, I., Muller,U. A., Sackinger, E., Simard, P. and Vapnik, V., "Learning Algorithms for Classification: A Comparison on Handwritten Digit Recognition," Neural Networks: The Statistical Mechanics Perspective, Oh, J. H., Kwon, C. and Cho, S. (Ed.), World Scientific, 261-276, (1995). ?? ??
Osuna, E., Freund, R., Girosi, F., "Training Support Vector Machines: An Application to Face Detection," Proc. Computer Vision and Pattern Recognition ’97, 130-136, (1997). ??
Oren, M., Papageorgious, C., Sinha, P., Osuna, E., Poggio, T., "Pedestrian Detection Using Wavelet Templates," Proc. Computer Vision and Pattern Recognition ’97, 193-199, (1997). ?? ??
Joachims, T., "Text Categorization with Support Vector Machines", LS VIII Technical Report, No. 23, University of Dortmund, ftp://ftp-ai.informatik.uni-dortmund.de/pub/Reports/report23.ps.Z, (1997). ??
ortes, C., Vapnik, V., "Support Vector Networks," Machine Learning, 20:273-297, (1995). ??
Boser, B. E., Guyon, I. M., Vapnik, V., "A Training Algorithm for Optimal Margin Classifiers", Fifth Annual Workshop on Computational Learning Theory, ACM, (1992). ??
Osuna, E., Freund, R., Girosi, F., "Improved Training Algorithm for Support Vector Machines," Proc. IEEE NNSP ’97, (1997). ?? ?? ?? ??
Osuna, E., Personal Communication. ??
Bregman, L. M., "The Relaxation Method of Finding the Common Point of Convex Sets and Its Application to the Solution of Problems in Convex Programming," USSR Computational Mathematics and Mathematical Physics, 7:200-217, (1967). ?? ??
ensor, Y., "Row-Action Methods for Huge and Sparse Systems and Their Applications",SIAM Review, 23(4):444-467, (1981). ??
ensor, Y., Lent, A., "An Iterative Row-Action Method for Interval Convex Programming,"J. Optimization Theory and Applications, 34(3):321-353, (1981). ??
Hildreth, C., "A Quadratic Programming Procedure," Naval Research Logistics Quarterly,4:79-85, (1957). ??
uda, R. O., Hart, P. E., Pattern Classification and Scene Analysis, John Wiley & Sons,(1973). ??
Platt, J. C., "A Resource-Allocating Network for Function Interpolation," Neural Computation, 3(2):213-225, (1991). ??
Gill, P. E., Murray, W., Wright, M. H., Practical Optimization, Academic Press, (1981). ??
Bengio, Y., LeCun, Y., Henderson, D., "Globally Trained Handwritten Word Recognizer using Spatial Representation, Convolutional Neural Networks and Hidden Markov Models,"Advances in Neural Information Processing Systems, 5, J. Cowan, G. Tesauro, J. Alspector,eds., 937-944, (1994). ??
Mallat, S., A Wavelet Tour of Signal Processing, Academic Press, (1998). ??
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/502711.html
標籤：其他
上一篇：通過部署流行 Web 框架掌握 Serverless 技術
下一篇：向量距離與相似度函式