支持向量機(SVM)（五）-- SMO算法詳解

一、我們先回顧下SVM問題。

A、線性可分問題

1、SVM基本原理：

SVM使用一種非線性映射，把原訓練            數據映射到較高的維。在新的維上，搜索最佳分離超平面，兩個類的數據總可以被超平面分開。

2、問題的提出：

3、如何選取最優的劃分直線f(x)呢？

4、求解：凸二次規劃

建立拉格朗日函數：


求偏導數：

B、線性不可分問題

1、核函數

如下圖：橫軸上端點a和b之間紅色部分里的所有點定為正類，兩邊的黑色部分里的點定為負類.

設：

g(x)轉化為f(y)=<a,y>
g(x)=f(y)=ay
在任意維度的空間中，這種形式的函數都是一個線性函數（只不過其中的a和y都是多維向量罷了），因為自變量y的次數不大于1。

下圖w，x都是1000維，w’和x’分別是由w，x變換得到的2000維向量
g(x)=K(w,x)+b
K(w,x)被稱作核函數
基本作用：接受兩個低維空間里的向量，能夠計算出經過某個變換后在高維空間里的向量內積值。

2、松弛變量

3、軟間隔C-SVM：

C是一個由用戶指定的系數，表示對分錯的點加入多少的懲罰，當C很大的時候，分錯的點就會更少，但是過擬合的情況可能會比較嚴重，當C很小的時候，分錯的點可能會很多，不過可能由此得到的模型也會不太正確

總結：

SVM算法優點：

(1)非線性映射是SVM方法的理論基礎,SVM利用內積核函數代替向高維空間的非線性映射；

(2)對特征空間劃分的最優超平面是SVM的目標,最大化分類邊際的思想是SVM方法的核心；

(3)支持向量是SVM的訓練結果,在SVM分類決策中起決定性作用。因此，模型需要存儲空間小，算法魯棒性（ Robust ）強。

SVM算法缺點：

(1) SVM算法對大規模訓練樣本難以實施

由于SVM是借助二次規劃來求解支持向量，而求解二次規劃將涉及m階矩陣的計算（m為樣本的個數），當m數目很大時該矩陣的存儲和計算將耗費大量的機器內存和運算時間。

(2) 用SVM解決多分類問題存在困難

經典的支持向量機算法只給出了二類分類的算法，而在數據挖掘的實際應用中，一般要解決多類的分類問題。

基于以上問題，我們現在討論SOM（Sequential Minimal Optimization algorithm）算法。

1、SMO算法的原理

這一被稱為“順次最小優化”的算法和以往的一些SVM改進算法一樣，是把整個二次規劃問題分解為很多易于處理的小問題，所不同的是，只有SMO算法把問題分解到可能達到的最小規模：每

次優化只處理兩個樣本的優化問題，并且用解析的方法進行處理。我們將會看到，這種與眾不同的方法帶來了一系列不可比擬的優勢。

對SVM來說，一次至少要同時對兩個樣本進行優化（就是優化它們對應的Lagrange乘子），這是因為等式約束的存在使得我們不可能單獨優化一個變量。

所謂“最小優化”的最大好處就是使得我們可以用解析的方法求解每一個最小規模的優化問題，從而完全避免了迭代算法。

當然，這樣一次“最小優化”不可能保證其結果就是所優化的Lagrange乘子的最終結果，但會使目標函數向極小值邁進一步。我們再對其它Lagrange乘子做最小優化，直到所有乘子都符合KKT

條件時，目標函數達到最小，算法結束。

這樣，SMO算法要解決兩個問題：一是怎樣解決兩個變量的優化問題，二是怎樣決定先對哪些Lagrange乘子進行優化。

2、兩個Lagrange乘子的優化問題

我們在這里不妨設正在優化的兩個Lagrange乘子對應的樣本正是第一個和第二個，對兩個Lagrange乘子α₁和α₂，在其他乘子不改變的情況下，它們的約束條件應表達為正方形內的一條線段。（如圖）

 

在這條線段上求一個函數的極值，相當于一個一維的極值問題。我們可以把α₁用α₂表示，對α₂求無條件極值，如果目標函數是嚴格上凹的，最小值就一定在這一極值點（極值點在區間內）或在區間端點（極值點在區間外）。α₂確定后，α₁也就確定下來了。因此我們先找到α₂優化區間的上下限制，再在這個區間中對α₂求最小值。

由圖1我們容易得到α₂的上下限應為：

L=max(0,α₂－α₁)，H=min(C,C+α₂ –α₁), 若y₁與y₂異號；

L=max(0,α₂ +α₁－C), H=min(C, α₂ +α₁) ,若y₁與y₂同號；

令s=y₁y₂標志這兩個樣本是否同類，則有

       L=max(0, α₂+sα₁－ 1/2 (s+1)C),  H=min(C, α₂ +sα₁ –1/2 (s－1)C)

而α₁和α₂在本次優化中所服從的等式約束為：

       α₁＋sα₂=α⁰₁+sα⁰₂=d

下面我們推導求最小值點α₂的公式：由于只有α₁，α₂兩個變量需要考慮，目標函數可以寫成

Wolfe(α₁,α₂)=1/2K₁₁α²₁+1/2 K₂₂α²₂  + sK₁₂α₁α₂ + y₁α₁v₁+y₂α₂v₂ －α₁ －α₂+常數

其中K_ij=K(x_i,x_j),   v_i=y₃α⁰₃K_i3+…+y_lα⁰_lK_il = u_i+b⁰－ y₁α⁰₁K_1i – y₂α⁰₁K_2i 

上標為0的量表示是本次優化之前Lagrange乘子的原值。

將α₂用α₁表示并代入目標函數：

Wolfe（α₂）=1/2 K₁₁(d-sα₂)²+1/2K₂₂α²₂+sK₁₂(d-sα₂) α₂

                         +y₁(d-sα₂)v₁– d+sα₂+y₂α₂v₂－α₂+常數

對α₂求導：

dWolfe(α₂)/dα₂=－sK₁₁(d－sα₂)+K₂₂α₂－K₁₂α₂+sK₁₂(d－sα₂)－y₂v₂+s+y₂v₂－1 ＝0

如果Wolfe函數總是嚴格上凹的，即二階導數K₁₁+K₂₂－2K₁₂>0, 那么駐點必為極小值點，無條件的極值點就為

α₂＝[s(K₁₁－K₁₂)d+y₂(v₁－v₂)＋1－s] / (K₁₁＋K₂₂－2K₁₂)

將d,v與α⁰,u之間關系代入，就得到用上一步的α⁰₂，u₁,u₂表示的α₂的無條件最優點：

α₂＝[α⁰₂(K₁₁＋K₂₂－2K₁₂)+y₂(u₁－u₂＋y₂－y₁)] / (K₁₁＋K₂₂－2K₁₂)

令η=K₁₁＋K₂₂－2K₁₂為目標函數的二階導數，E_i=u_i－y_i為第i個訓練樣本的“誤差”，這個式子又可以寫為

        α₂＝α⁰₂＋y₂(E₁－E₂)/η

除非核函數K不滿足Mercer條件（也就是說不能作為核函數），η不會出現負值。但η=0是可以出現的情況。這時我們計算目標函數在線段兩個端點上的取值，并將Lagrange乘子修正到目標函數較小的端點上：

f₁=y₁(E₁+b)－α₁K(x₁,x₁)­－sα₂K(x₁,x₁)

f₂=y₂(E₂+b)－sα₁K(x₁,x₂)­－α₂K(x₂,x₂)

L₁=α₁+s(α₂－L)

H₁=α₁+s(α₂－H)

WolfeL=L₁f₁+Lf₂+1/2 L²₁K(x₁,x₁)+1/2L²K(x₂,x₂)+sLL₁K(x₁,x₂)

WolfeH=H₁f₁+Hf₂+1/2 H²₁K(x₁,x₁)+1/2H²K(x₂,x₂)+sHH₁K(x₁,x₂)

當兩個端點上取得相同的目標函數值時，目標函數在整條線段上的取值都會是一樣的（因為它是上凹的），這時不必對α₁，α₂作出修正。

α₂的無條件極值確定后，再考慮上下限的限制，最終的α₂為

最后，由等式約束確定α₁：

        α₁^*=α₁+s(α₂－α₂^*)

3、SMO算法

這里的ai是拉格朗日乘子(問題通過拉格朗日乘法數來求解)  

對于（a）的情況，表明ai是正常分類，在邊界內部（我們知道正確分類的點yi*f(xi)>=0）    

對于（b）的情況，表明了ai是支持向量，在邊界上     

對于（c）的情況，表明了ai是在兩條邊界之間 而最優解需要滿足KKT條件，即滿足（a）（b）（c）條件都滿足

3.2、以下幾種情況出現將會出現不滿足：

yiui<=1但是ai<C則是不滿足的,而原本ai=C    

yiui>=1但是ai>0則是不滿足的而原本ai=0   

 yiui=1但是ai=0或者ai=C則表明不滿足的，而原本應該是0<ai<C

所以要找出不滿足KKT的這些ai，并更新這些ai，但這些ai又受到另外一個約束，即

通過另一個方法，即同時更新ai和aj，滿足以下等式


       就能保證和為0的約束。

aj表示舊值，然后考慮約束0<=aj<=C可得到a的解析解為：



其中：

輸入是x，是一個數組，組中每一個值表示一個特征。
輸出是A類還是B類。（正類還是負類）

4、SMO算法的特點和優勢
SMO算法和以往流行的SVM優化算法如塊算法、固定工作樣本集法相比，既有共同點，又有自己的獨特之處。

共同點在于它們都是把一個大的優化問題分解為很多小問題來處理。塊算法在每一步中將新加入樣本中違反KKT條件的樣本與原有的支持向量一起組成小問題的樣本集進行優化，優化完畢后

只保留其中的支持向量，再加進來新的樣本進入下一步。固定工作樣本集法是每一步只收集新加入樣本中“最壞”的樣本，并將原來保留的支持向量集中“較好”的替換出去，以保持樣本集大小不

變。SMO則是把每一步的優化問題縮減到了最小，它可以看作是固定工作樣本集法的一種特殊情況：把工作樣本集的大小固定為2，并且每一步用兩個新的Lagrange乘子替換原有的全部乘子。

SMO的最大特色在于它可以采用解析的方法而完全避免了二次規劃數值解法的復雜迭代過程。這不但大大節省了計算時間，而且不會牽涉到迭代法造成的誤差積累（其它一些算法中這種誤差

積累帶來了很大的麻煩）。理論上SMO的每一步最小優化都不會造成任何誤差積累，而如果用雙精度數計算，舍入誤差幾乎可以忽略，于是所有的誤差只在于最后一遍檢驗時以多大的公差要

求所有Lagrange乘子滿足KKT條件。可以說SMO算法在速度和精度兩方面都得到了保證。

SMO在內存的節省上也頗具特色。我們看到，由于SMO不涉及二次規劃數值解法，就不必將核函數矩陣整個存在內存里，而數值解法每步迭代都要拿這個矩陣作運算。（4000個樣本的核函

數矩陣需要128M內存！）于是SMO使用的內存是與樣本集大小成線性增長的，而不象以往的算法那樣成平方增長。在我們的程序中SMO算法最多占用十幾兆內存。SMO使得存儲空間問題不

再是SVM應用中的另一個瓶頸。

SMO算法對線性支持向量機最為有效，對非線性則不能發揮出全部優勢，這是因為線性情況下每次最小優化后的重置工作都是很簡單的運算，而非線性時有一步加權求和，占用了主要的時

間。其他算法對線性和非線性區別不大，因為凡是涉及二次規劃數值解的算法都把大量時間花在求數值解的運算中了。

當大多數Lagrange乘子都在邊界上時，SMO算法的效果會更好。
盡管SMO的計算時間仍比訓練集大小增長快得多，但比起其它方法來還是增長得慢一個等級。因此SMO較適合大數量的樣本。

來自： http://blog.csdn.net//u011067360/article/details/26503719