支援向量機總結

機器學習總結——支援向量機

現在介紹支援向量機的文檔很多，以下隻是我個人對于支援向量機算法的認識，有認識不到位的地方請各位大牛多指正。支援向量機屬于一種二類分類模型，它的模型是定義在特征空間上的間隔最大的分類器。支援向量機的本質在于在特征空間尋求一個間隔最大的超平面。算法的核心思想在于以下兩點：1.線上性可分的情況下，利用間隔最大化的學習政策尋求一個間隔最大的超平面。2線上性不可分的情況下，通過核函數将低維的特征向量空間映射到高維來尋求線性可分。      

支援向量機有如下優缺點。優點：1對于線性不可分的情況可以通過核函數，映射到高維特征空間實作線性可分。2.SVM學習問題可以表示為凸優化問題，是以可以利用已知的有效算法發現目标函數的全局最小值。而其他分類方法（如基于規則的分類器和人工神經網絡）都采用一種基于貪心學習的政策來搜尋假設空間，這種方法一般隻能獲得局部最優解。3.小叢集分類效果好。      

缺點：1 SVM僅僅隻限于一個二類分類問題，對于多分類問題解決效果并不好。2.僅局限于小叢集樣本，對于觀測樣本太多時，效率較低。3.尋求合适的核函數相對困難。      

支援向量機學習基礎：      

Logistic回歸： Logistic回歸目的是從特征學習出一個0/1分類模型，而這個模型是将特性的線性組合作為自變量，由于自變量的取值範圍是負無窮到正無窮。是以，使用logistic函數（或稱作sigmoid函數）将自變量映射到(0,1)上，映射後的值被認為是屬于y=1的機率。
    假設函數

          
 
 
 
 
  
           
     
     
     
         
  
       其中x是n維特征向量，函數g就是logistic函數。
  
  
       而
        
  
             
的圖像是
  
          
 
 
 
  
         
     
     
      
  
         
  
       可以看到，将無窮映射到了(0,1)。
  
  
       而假設函數就是特征屬于y=1的機率。
  
          
 
 
 
  
         
     
     
         
    進而，當我們要判别一個新來的特征屬于哪個類時，隻需求
        
  
             
即可，若
        
  
             
大于0.5就是y=1的類，反之屬于y=0類。

    此外，
        
  
             
隻和
        
  
             
有關，
        
  
             
>0，那麼
        
  
             
，而g(z)隻是用來映射，真實的類别決定權還是在于
        
  
             
。再者，當
        
  
             
時，
        
  
             
=1，反之
        
  
             
=0。如果我們隻從
        
  
             
出發，希望模型達到的目标就是讓訓練資料中y=1的特征
        
  
             
，而是y=0的特征
        
  
             
。Logistic回歸就是要學習得到
        
  
             
，使得正例的特征遠大于0，負例的特征遠小于0，而且要在全部訓練執行個體上達到這個目标。

    接下來，嘗試把logistic回歸做個變形。首先，将使用的結果标簽y = 0和y = 1替換為y = -1,y = 1，然後将
        
  
             
（
        
  
             
）中的
        
  
             
替換為b，最後将後面的
        
  
             
替換為
        
  
             
（即
        
  
             
）。如此，則有了
        
  
             
。也就是說除了y由y=0變為y=-1外，線性分類函數跟logistic回歸的形式化表示
        
  
             
沒差別。

    進一步，可以将假設函數
        
  
             
中的g(z)做一個簡化，将其簡單映射到y=-1和y=1上。映射關系如下：

          
 
 
 
  
         
     
     
    

經驗風險最小化、過拟合現象和結構風險最小化：      

經驗風險最小化：在假設空間、損失函數以及訓練資料集确定的情況下模型f（x）關于訓練資料集的平均損失，記作：      

經驗風險是模型關于訓練樣本集的平均損失。根據大數定理（随機變量互相獨立，服從同一分布且有數學期望u,則序列
        
  
             
依機率收斂于u）.當樣本容量N趨于無窮時經驗風險趨于期望風險。是以可以用經驗風險去估計期望風險，然後現實情形是訓練樣本數目往往有限，甚至很小。用經驗風險估計期望風險往往不太理想，是以要對經驗風險進行一定的矯正，如下兩個政策：經驗風險最小化和結構風險最小化。根據經驗風險最小化政策認為，經驗風險最小化的模型是最優的模型，根據這一政策，按照經驗風險最小化求最優模型就是求最優化解（諸如在損失函數為對數損失函數時，利用極大似然估計求經驗風險最小化）。      

過拟合現象：在樣本容量很小時，容易産生過拟合現象：是指在學習時選擇的模型所包含的參數過多，以至于出現這一模型對于已知資料預測很好，而對于未知資料預測很差的現象。也就是訓練誤差小于測試誤差時發生的現象。      

結構風險最小化：為了防止過拟合現象，提出了結構風險最小化政策。結構風險是經驗風險加上表示模型複雜度的正則化項或罰項。在假設空間、損失函數以及訓練資料集确定的情況下，結構風險定義為：      

結構風險小的模型往往對訓練資料以及未知的測試資料都有很好的預測。貝葉斯估計中的最大後驗機率估計就是結構風險最小化的一個例子，當模型複雜度由模型的先驗機率表示時，結構風險最小化就等價于最大後驗機率估計。      

 KKT條件：KKT 條件的介紹，一般地，一個最優化數學模型能夠表示成下列标準形式：       
      
 
 
  
         
     
         
 

    其中，f(x)是需要最小化的函數，h(x)是等式限制，g(x)是不等式限制，p和q分别為等式限制和不等式限制的數量。同時，我們得明白以下兩個定理：

 

        

• 凸優化的概念：

  

   為一凸集， 

  

   為一凸函數。凸優化就是要找出一點 

  

   ，使得每一 

  

   滿足 

  

   。
• KKT條件的意義：它是一個非線性規劃（Nonlinear Programming）問題能有最優化解法的必要和充分條件。

    那到底什麼是所謂Karush-Kuhn-Tucker條件呢？KKT條件就是指上面最優化數學模型的标準形式中的最小點 x* 必須滿足下面的條件：

    經過論證，我們這裡的問題是滿足 KKT 條件的（首先已經滿足Slater condition，再者f和gi也都是可微的，即L對w和b都可導），是以現在我們便轉化為求解第二個問題。也就是說，現在，咱們的原問題通過滿足一定的條件，已經轉化成了對偶問題。而求解這個對偶學習問題，分為3個步驟，首先要讓L(w，b，a) 關于w w 和 bb 最小化，然後求對α的極大，最後利用SMO算法求解對偶因子。

拉格朗日對偶：
來看看存在等式限制的極值問題求法，比如下面的最優化問題：

    
        
  
             
  



目标函數是f(w)，下面是等式限制。通常解法是引入拉格朗日算子，這裡使用
        
  
             
來表示算子，得到拉格朗日公式為

    
        
  
             
    

L是等式限制的個數。



然後分别對w和
        
  
             
求偏導，使得偏導數等于0，然後解出w和
        
  
             
。至于為什麼引入拉格朗日算子可以求出極值，原因是f(w)的dw變化方向受其他不等式的限制，dw的變化方向與f(w)的梯度垂直時才能獲得極值，而且在極值處，f(w)的梯度與其他等式梯度的線性組合平行，是以他們之間存線上性關系。（參考《最優化與KKT條件》）

然後我們探讨有不等式限制的極值問題求法，問題如下



    
        
  
             
    

    我們定義一般化的拉格朗日公式


        
  
             


    這裡的
        
  
             
和
        
  
             
都是拉格朗日算子。如果按這個公式求解，會出現問題，因為我們求解的是最小值，而這裡的
        
  
             
已經不是0了，我們可以将
        
  
             
調整成很大的正值，來使最後的函數結果是負無窮。是以我們需要排除這種情況，我們定義下面的函數：

    
        
  
             


    這裡的P代表primal。假設
        
  
             
或者
        
  
             
，那麼我們總是可以調整
        
  
             
和
        
  
             
來使得
        
  
             
有最大值為正無窮。而隻有g和h滿足限制時，
        
  
             
為f(w)。這個函數的精妙之處在于
        
  
             
，而且求極大值。

    是以我們可以寫作

    
        
  
             


    這樣我們原來要求的min f(w)可以轉換成求
        
  
             
了。    

    
        
  
             


    我們使用
        
  
             
來表示
        
  
             
。如果直接求解，首先面對的是兩個參數，而
        
  
             
也是不等式限制，然後再在w上求最小值。這個過程不容易做，那麼怎麼辦呢？



我們先考慮另外一個問題
        
  
             


    D的意思是對偶，
        
  
             
将問題轉化為先求拉格朗日關于w的最小值，将
        
  
             
和
        
  
             
看作是固定值。之後在
        
  
             
求最大值的話：


        
  
             


    這個問題是原問題的對偶問題，相對于原問題隻是更換了min和max的順序，而一般更換順序的結果是Max Min(X) <= MinMax(X)。然而在這裡兩者相等。用
        
  
             
來表示對偶問題如下：

    
        
  
             


    下面解釋在什麼條件下兩者會等價。假設f和g都是凸函數，h是仿射的（affine，
        
  
             
）。并且存在w使得對于所有的i，
        
  
             
。在這種假設下，一定存在
        
  
             
使得
        
  
             
是原問題的解，
        
  
             
是對偶問題的解。還有
        
  
             
另外，
        
  
             
滿足庫恩-塔克條件（Karush-Kuhn-Tucker, KKT condition），該條件如下：

    
        
  
             


    是以如果
        
  
             
滿足了庫恩-塔克條件，那麼他們就是原問題和對偶問題的解。讓我們再次審視公式（5），這個條件稱作是KKT dual complementarity條件。這個條件隐含了如果
        
  
             
，那麼
        
  
             
。也就是說，
        
  
             
時，w處于可行域的邊界上，這時才是起作用的限制。而其他位于可行域内部（
        
  
             
的）點都是不起作用的限制，其
        
  
             
。這個KKT雙重補足條件會用來解釋支援向量和SMO的收斂測試。

    KKT的總體思想是将極值會在可行域邊界上取得，也就是不等式為0或等式限制裡取得，而最優下降方向一般是這些等式的線性組合，其中每個元素要麼是不等式為0的限制，要麼是等式限制。對于在可行域邊界内的點，對最優解不起作用，是以前面的系數為0。

	SVM算法：

線性可分的支援向量機：學習的目标是在特征空間中找到一個分離超平面，能将執行個體分到不同的類。在給定線性可分訓練資料集的情形下，通過間隔最大化學習分離超平面，而分離超平面對應于方程w.x+b=0,隻要求得法向量w和截據b就可以得到分離超平面，以及相應的分類決策函數

		f(x)=sign(w*x+b)  (1)

函數間隔：上述提到間隔最大化，何為間隔了。在超平面确定的情況下：由點到平面的距離公式（點(x0,y0,z0)到了平面Ax+By+Cz+D=0的距離為：d=|Ax0+By0+Cz0+D|/√(A^2+B^2+C^2)），是以可得|w*x+b|能夠相對的表示向量點到超平面的遠近。而距離的遠近可以表示分類預測的确信程度。是以可以用y（w*x+b）來表示分類的正确性以及确信度。

幾何間隔：我們将w和b改變為2w和2b超平面沒有發生改變而間隔卻變成了原來的兩倍。是以我們需要對分離超平面的法向量進行限制，使得間隔固定成為幾何間隔。



假定對于一個點 x ，令其垂直投影到超平面上的對應點為 x0 ，w 是垂直于超平面的一個向量，
        
  
             
為樣本x到分類間隔的距離，如下圖所示：
            
 
 
 
 
 
 
  
         
     
     
     
     
     
         
    有
        
  
             
，其中||w||表示的是範數。

    又由于 
     x0 是超平面上的點，滿足 
     f(x0)=0 ，代入超平面的方程
        
  
             
即可算出： 

 
        
  
             
 （2）


間隔最大化（Maximum Margin Classifier）：間隔最大化的直覺解釋是：對于訓練資料集找到幾何間隔最大的超平面意味着以充分大的确信度對訓練資料進行分類，也就是說不但可以将正負執行個體點分開，而且對最難分的執行個體點也有足夠大的确信度将他們分開。可以得到如下限制最優化問題：


        
  
             
 （3）


上述最優化問題可以等價于：


        
  
             
         （4）




  我們将限制條件改寫為：

    
        
  
             


    從KKT條件得知隻有函數間隔是1（離超平面最近的點）的線性限制式前面的系數
        
  
             
，也就是說這些限制式
        
  
             
，對于其他的不線上上的點(
        
  
             
)，極值不會在他們所在的範圍内取得，是以前面的系數
        
  
             
.注意每一個限制式實際就是一個訓練樣本。

    看下面的圖：


        
  
             


    實線是最大間隔超平面，假設×号的是正例，圓圈的是負例。在虛線上的點就是函數間隔是1的點，那麼他們前面的系數
        
  
             
，其他點都是
        
  
             
。這三個點稱作支援向量。構造拉格朗日函數如下：    

    
        
  
             


    注意到這裡隻有
        
  
             
沒有
        
  
             
是因為原問題中沒有等式限制，隻有不等式限制。

    下面我們按照對偶問題的求解步驟來一步步進行，

    
        
  
             


    首先求解
        
  
             
的最小值，對于固定的
        
  
             
，
        
  
             
的最小值隻與w和b有關。對w和b分别求偏導數。

    
        
  
          
  
             


    并得到

    
        
  
             


    将上式帶回到拉格朗日函數中得到，此時得到的是該函數的最小值（目标函數是凸函數）

    代入後，化簡過程如下：


        
  
          
  
             


　　最後得到


        
  
             


     由于最後一項是0，是以簡化為

    
        
  
             


    這裡我們将向量内積
        
  
             
表示為
        
  
             


    此時的拉格朗日函數隻包含了變量
        
  
             
。然而我們求出了
        
  
             
才能得到w和b。

    接着是極大化的過程
        
  
             
，


        
  
             


    前面提到過對偶問題和原問題滿足的幾個條件，首先由于目标函數和線性限制都是凸函數，而且這裡不存在等式限制h。存在w使得對于所有的i，
        
  
             
。是以，一定存在
        
  
             
使得
        
  
             
是原問題的解，
        
  
             
是對偶問題的解。在這裡，根據SMO算法（文章最後會有所介紹）求
        
  
             
就是求
        
  
             
了。

    如果求出了
        
  
             
，根據
        
  
             
即可求出w（也是
        
  
             
，原問題的解）。然後

    
        
  
             


    即可求出b。即離超平面最近的正的函數間隔要等于離超平面最近的負的函數間隔。

    關于上面的對偶問題如何求解，将留給下一篇中的SMO算法來闡明。

    這裡考慮另外一個問題，由于前面求解中得到

    
        
  
             


    我們通篇考慮問題的出發點是
        
  
             
，根據求解得到的
        
  
             
，我們代入前式得到

    
        
  
             


是以我們利用拉格朗日對偶法求得最大間隔的超平面。

支援向量和間隔邊界：主要分為以下三種情形，線上性可分的情形下、線上性不可分的情形下，利用核函數進行空間映射轉換的前提下。

線性可分的情形下：訓練資料集的樣本點中與分離超平面最近的樣本點的執行個體稱為支援向量。支援向量在數學方面解釋為是使限制條件等号成立的點：


        
  
             



對于正例點y=1,支援向量在超平面  H ： w*x+b= 1

對于負例點y =-1,支援向量在超平面 H： w*x+b = -1

例如在藍色虛線上的藍色實點和粉色虛線上的紅心實點。


        
  
             



線上性不可分的情形下：


        
  
             


如圖所示，分離超平面用實線表示正負例的支援向量點分别是“。”和"x"。可以得知在間隔邊界（也就是限制條件為等式的）情形下得到的執行個體點，作為支援向量。非線性的情形下，同理可知。

松弛變量：


        
  
             



在如圖所示的情形下：被圈起來的藍色的點是線性不可分的。是以需要對每個樣本點引入松馳變量，是以我們可以得到線上性不可分的情形下變為如下凸二次規劃問題：


        
  
             
         （5）




  
   
     用之前的方法将限制或限制條件加入到目标函數中，得到新的拉格朗日函數，如下所示：
   
  
          
 
  
         
         


     分析方法和前面一樣，轉換為另一個問題之後，我們先讓
        
  
             
針對
        
  
             
、
    
        
  
             
和
        
  
             
最小化：

          
 
 
 
 
  
         
     
     
     
         
     将 
    
        
  
             
 帶回 
    
        
  
             
 并化簡，得到和原來一樣的目标函數：

          
 
 
 
  
         
     
     
         
     不過，由于我們得到
        
  
             
而又有
        
  
             
（作為 Lagrange multiplier 的條件），是以有
        
  
             
，是以整個 dual 問題現在寫作：

          
 
 
 
  
         
     
     
         
    把前後的結果對比一下（錯誤修正：圖中的Dual formulation中的Minimize應為maxmize）：

          
 
  
         
         
    可以看到唯一的差別就是現在 dual variable 
        
  
             
 多了一個上限 
    
        
  
             
 。

核技巧：

用線性分類的方法解決非線性分類的問題分為兩步：1首先使用一個變換将原空間的資料映射到新空間。2在新空間裡用線性分類的學習方法從訓練資料中學習分類模型。


        
  
             



核技巧的想法是，在學習與預測中隻定義核函數K（x,z），而不是顯式定義映射函數。如果有一種方式可以在特征空間中直接計算内積〈φ(xi · φ(x)〉，就像在原始輸入點的函數中一樣，就有可能将兩個步驟融合到一起建立一個非線性的學習器，這樣直接計算法的方法稱為核函數方法：

  
    核函數：如何處理非線性資料
   
     來看個核函數的例子。如下圖所示的兩類資料，分别分布為兩個圓圈的形狀，這樣的資料本身就是線性不可分的，此時咱們該如何把這兩類資料分開呢(下文将會有一個相應的三維空間圖)
    

        
  
             



    
    事實上，上圖所述的這個資料集，是用兩個半徑不同的圓圈加上了少量的噪音生成得到的，是以，一個理想的分界應該是一個“圓圈”而不是一條線（超平面）。如果用 
       X1 和 
       X2 來表示這個二維平面的兩個坐标的話，我們知道一條二次曲線（圓圈是二次曲線的一種特殊情況）的方程可以寫作這樣的形式：

   
           
 
 
 
  
         
     
     
         
   
    
    
    注意上面的形式，如果我們構造另外一個五維的空間，其中五個坐标的值分别為 
       Z1=X1, 
       Z2=X21, 
       Z3=X2, 
       Z4=X22, 
       Z5=X1X2，那麼顯然，上面的方程在新的坐标系下可以寫作：

   
           
 
 
 
 
  
         
     
     
     
         
   
    
    關于新的坐标 
       Z ，這正是一個 hyper plane 的方程！也就是說，如果我們做一個映射 
       ϕ:R2→R5 ，将 
       X 按照上面的規則映射為 
       Z ，那麼在新的空間中原來的資料将變成線性可分的，進而使用之前我們推導的線性分類算法就可以進行處理了。這正是 Kernel 方法處理非線性問題的基本思想。

    
    再進一步描述 Kernel 的細節之前，不妨再來看看這個例子映射過後的直覺例子。當然，你我可能無法把 5 維空間畫出來，不過由于我這裡生成資料的時候就是用了特殊的情形，具體來說，我這裡的超平面實際的方程是這個樣子（圓心在 
       X2 軸上的一個正圓）：

   
           
 
 
 
 
  
         
     
     
     
         
   
    
    是以我隻需要把它映射到 
       Z1=X21, 
       Z2=X22, 
       Z3=X2 這樣一個三維空間中即可，下圖即是映射之後的結果，将坐标軸經過适當的旋轉，就可以很明顯地看出，資料是可以通過一個平面來分開的(pluskid：下面的gif 動畫，先用 Matlab 畫出一張張圖檔，再用 Imagemagick 拼貼成)：

   
           
 
 
  
         
     
         
   
    核函數相當于把原來的分類函數：

           
 
 
  
         
     
         
   
    映射成：

           
 
 
  
         
     
         
   
    而其中的
        
  
             
可以通過求解如下 dual 問題而得到的：

           
 
 
  
         
     
         
   
    這樣一來問題就解決了嗎？似乎是的：拿到非線性資料，就找一個映射 
      
        
  
          
  
          
  
          
  
             
 ，然後一股腦把原來的資料映射到新空間中，再做線性 SVM 即可。不過事實上沒有這麼簡單！其實剛才的方法稍想一下就會發現有問題：在最初的例子裡，我們對一個二維空間做映射，選擇的新空間是原始空間的所有一階和 二階的組合，得到了五個次元；如果原始空間是三維，那麼我們會得到 19 維的新空間，這個數目是呈爆炸性增長的，這給 
      
        
  
          
  
          
  
          
  
             
 的計算帶來了非常大的困難，而且如果遇到無窮維的情況，就根本無從計算了。是以就需要 Kernel 出馬了。

   
    不妨還是從最開始的簡單例子出發，設兩個向量
        
  
             
和
        
  
             
，而
        
  
             
即是到前面說的五維空間的映射，是以映射過後的内積為：

           
 
 
 
  
         
     
     
         
   
        （公式說明：上面的這兩個推導過程中，所說的前面的五維空間的映射，這裡說的前面便是文中2.2.1節的所述的映射方式，回顧下之前的映射規則，再看那第一個推導，其實就是計算x1，x2各自的内積，然後相乘相加即可，第二個推導則是直接平方，去掉括号，也很容易推出來）

   
    另外，我們又注意到：

           
 
 
 
  
         
     
     
         
   
     二者有很多相似的地方，實際上，我們隻要把某幾個次元線性縮放一下，然後再加上一個常數次元，具體來說，上面這個式子的計算結果實際上和映射

           
 
 
 
  
         
     
     
         
   
     之後的内積
        
  
             
的結果是相等的，那麼差別在于什麼地方呢？

           
 
 一個是映射到高維空間中，然後再根據内積的公式進行計算；       
      
 而另一個則直接在原來的低維空間中進行計算，而不需要顯式地寫出映射後的結果。       
     
         
   
    （公式說明：上面之中，最後的兩個式子，第一個算式，是帶内積的完全平方式，可以拆開，然後，通過湊一個得到，第二個算式，也是根據第一個算式湊出來的）

   
    回憶剛才提到的映射的次元爆炸，在前一種方法已經無法計算的情況下，後一種方法卻依舊能從容處理，甚至是無窮次元的情況也沒有問題。也就是說在核函數給定的條件下，可以利用解決線性分類問題的方法求解非線性分類的支援向量機。學習是隐式的在特征空間中進行。不需要顯式定義特征空間和映射函數這樣的技巧稱為核技巧

   
    我們把這裡的計算兩個向量在隐式映射過後的空間中的内積的函數叫做核函數 (Kernel Function) ，例如，在剛才的例子中，我們的核函數為：

           
 
 
 
 
  
         
     
     
     
         
   
    核函數能簡化映射空間中的内積運算——剛好“碰巧”的是，在我們的 SVM 裡需要計算的地方資料向量總是以内積的形式出現的。對比剛才我們上面寫出來的式子，現在我們的分類函數為：

           
 
 
 
 
  
         
     
     
     
         
   
    其中 
      
        
  
             
 由如下 dual 問題計算而得：

           
 
 
 
  
         
     
     
         
   
    這樣一來計算的問題就算解決了，避開了直接在高維空間中進行計算，而結果卻是等價的！當然，因為我們這裡的例子非常簡單，是以我可以手工構造出對應于
        
  
             
的核函數出來，如果對于任意一個映射，想要構造出對應的核函數就很困難了。

  

核函數的作用：1.在現實情況中經常遇到線性不可分的非線性分類問題，需要将将樣例映射到高維空間中去，達到線性可分的目的。2.核函數的價值在于雖然實作了将特征從低維空間到高維空間的轉換，但核函數事先在低維空間中進行計算，實質分類效果展現在高維空間，直接避免了高維空間中的複雜計算。      

核函數的選擇：

        

• 多項式核，顯然剛才我們舉的例子是這裡多項式核的一個特例（R = 1，d = 2）。雖然比較麻煩，而且沒有必要，不過這個核所對應的映射實際上是可以寫出來的，該空間的次元是

  

  ，其中

  

  是原始空間的次元。
• 高斯核

  

  ，這個核就是最開始提到過的會将原始空間映射為無窮維空間的那個家夥。不過，如果

  

  選得很大的話，高次特征上的權重實際上衰減得非常快，是以實際上（數值上近似一下）相當于一個低維的子空間；反過來，如果

  

  選得很小，則可以将任意的資料映射為線性可分——當然，這并不一定是好事，因為随之而來的可能是非常嚴重的過拟合問題。不過，總的來說，通過調控參數

  

  ，高斯核實際上具有相當高的靈活性，也是使用最廣泛的核函數之一。下圖所示的例子便是把低維線性不可分的資料通過高斯核函數映射到了高維空間：

  

• 線性核

  

  ，這實際上就是原始空間中的内積。這個核存在的主要目的是使得“映射後空間中的問題”和“映射前空間中的問題”兩者在形式上統一起來了

實際應用較多的是高斯核和線性核。

SMO算法：      

 
 第一步選取一對        
  
                      和                 
  
             ，選取方法使用啟發式方法；       
      
 第二步，固定除        
  
                      和                 
  
             之外的其他參數，确定W極值條件下的        
  
                      ，                 
  
             由        
  
                      表示。       
     
         
    
         假定在某一次疊代中，需要更新
     
        
  
             
，
     
        
  
             
對應的拉格朗日乘子
     
        
  
             
，
     
        
  
             
，那麼這個小規模的二次規劃問題寫為：
    
   
   
            
 
  
         
         
       那麼在每次疊代中，如何更新乘子呢？引用
   這裡的兩張PPT說明下：

           
 
  
          
  
         
         
   
    
    知道了如何更新乘子，那麼選取哪些乘子進行更新呢？具體選擇方法有以下兩個步驟：

            
 
 步驟1：先“掃描”所有乘子，把第一個違反KKT條件的作為更新對象，令為a2；       
      
 步驟2：在所有不違反KKT條件的乘子中，選擇使|E1 −E2|最大的a1進行更新，使得能最大限度增大目标函數的值（類似于梯度下降。此外        
  
             ，而        
  
             ，求出來的E代表函數ui對輸入xi的預測值與真實輸出類标記yi之差）。       
     
         
    
         最後，每次更新完兩個乘子的優化後，都需要再重新計算b，及對應的Ei值。
    
   
  
  
   
    綜上，SMO算法的基本思想是将Vapnik在1982年提出的Chunking方法推到極緻，SMO 算法每次疊代隻選出兩個分量ai和aj進行調整，其它分量則保持固定不變，在得到解ai和aj之後，再用ai和aj改進其它分量。與通常的分解算法比較， 盡管它可能需要更多的疊代次數，但每次疊代的計算量比較小，是以該算法表現出整理的快速收斂性，且不需要存儲核矩陣，也沒有矩陣運算。

   除了在這篇論文《fast training of support vector machines using sequential minimal optimization》中platt給出了SMO算法的邏輯代碼之外，這裡也有一份SMO的實作代碼。
      

參考文獻：      

http://www.cnblogs.com/liqizhou/archive/2012/05/11/2495788.html
      

http://www.cnblogs.com/haore147/p/3619046.html
      

http://www.cnblogs.com/zhangchaoyang/articles/4306833.html      

http://blog.csdn.net/liukun321/article/details/41574617
      

《統計機器學習》  李航