關於smo算法的python實現的信息

本文目錄一覽：

• 1、如何用python實現smo算法
• 2、如何利用 Python 實現 SVM 模型
• 3、如何用Python實現支持向量機
• 4、支持向量機—從推導到python手寫

如何用python實現smo算法

在ml中常見的優化算法基本都是： sgd 這種對每個單變量進行同步更新 als(交替最小二乘）/smo(序列最小優化）這種交替（固定一個單變量，優化另一個單變量）思路。如果你熟悉smo，那麼als就也可以理解了。 其它（希望更多的人補充）

如何利用 Python 實現 SVM 模型

我先直觀地闡述我對SVM的理解，這其中不會涉及數學公式，然後給出Python代碼。

SVM是一種二分類模型，處理的數據可以分為三類：

線性可分，通過硬間隔最大化，學習線性分類器

近似線性可分，通過軟間隔最大化，學習線性分類器

線性不可分，通過核函數以及軟間隔最大化，學習非線性分類器

線性分類器，在平面上對應直線；非線性分類器，在平面上對應曲線。

硬間隔對應於線性可分數據集，可以將所有樣本正確分類，也正因為如此，受噪聲樣本影響很大，不推薦。

軟間隔對應於通常情況下的數據集（近似線性可分或線性不可分），允許一些超平面附近的樣本被錯誤分類，從而提升了泛化性能。

如下圖：

實線是由硬間隔最大化得到的，預測能力顯然不及由軟間隔最大化得到的虛線。

對於線性不可分的數據集，如下圖：

我們直觀上覺得這時線性分類器，也就是直線，不能很好的分開紅點和藍點。

但是可以用一個介於紅點與藍點之間的類似圓的曲線將二者分開，如下圖：

我們假設這個黃色的曲線就是圓，不妨設其方程為x^2+y^2=1，那麼核函數是幹什麼的呢？

我們將x^2映射為X，y^2映射為Y，那麼超平面變成了X+Y=1。

那麼原空間的線性不可分問題，就變成了新空間的（近似）線性可分問題。

此時就可以運用處理（近似）線性可分問題的方法去解決線性不可分數據集的分類問題。

—————————————————————————————————————————

以上我用最簡單的語言粗略地解釋了SVM，沒有用到任何數學知識。但是沒有數學，就體會不到SVM的精髓。因此接下來我會用盡量簡潔的語言敘述SVM的數學思想，如果沒有看過SVM推導過程的朋友完全可以跳過下面這段。

對於求解（近似）線性可分問題：

由最大間隔法，得到凸二次規劃問題，這類問題是有最優解的（理論上可以直接調用二次規劃計算包，得出最優解）

我們得到以上凸優化問題的對偶問題，一是因為對偶問題更容易求解，二是引入核函數，推廣到非線性問題。

求解對偶問題得到原始問題的解，進而確定分離超平面和分類決策函數。由於對偶問題里目標函數和分類決策函數只涉及實例與實例之間的內積，即xi,xj。我們引入核函數的概念。

拓展到求解線性不可分問題：

如之前的例子，對於線性不可分的數據集的任意兩個實例：xi,xj。當我們取某個特定映射f之後，f(xi)與f(xj)在高維空間中線性可分，運用上述的求解（近似）線性可分問題的方法，我們看到目標函數和分類決策函數只涉及內積f(xi),f(xj)。由於高維空間中的內積計算非常複雜，我們可以引入核函數K(xi,xj)=f(xi),f(xj)，因此內積問題變成了求函數值問題。最有趣的是，我們根本不需要知道映射f。精彩！

我不準備在這裡放推導過程，因為已經有很多非常好的學習資料，如果有興趣，可以看：CS229 Lecture notes

最後就是SMO算法求解SVM問題，有興趣的話直接看作者論文：Sequential Minimal Optimization:A Fast Algorithm for Training Support Vector Machines

我直接給出代碼：SMO+SVM

在線性可分數據集上運行結果：

圖中標出了支持向量這個非常完美，支持向量都在超平面附近。

在線性不可分數據集上運行結果（200個樣本）：

核函數用了高斯核，取了不同的sigma

sigma=1，有189個支持向量，相當於用整個數據集進行分類。

sigma=10，有20個支持向量，邊界曲線能較好的擬合數據集特點。

我們可以看到，當支持向量太少，可能會得到很差的決策邊界。如果支持向量太多，就相當於每次都利用整個數據集進行分類，類似KNN。

如何用Python實現支持向量機

終於到SVM的實現部分了。那麼神奇和有效的東西還得回歸到實現才可以展示其強大的功力。SVM有效而且存在很高效的訓練算法，這也是工業界非常青睞SVM的原因。

前面講到，SVM的學習問題可以轉化為下面的對偶問題：

需要滿足的KKT條件：

也就是說找到一組αi可以滿足上面的這些條件的就是該目標的一個最優解。所以我們的優化目標是找到一組最優的αi*。一旦求出這些αi*，就很容易計算出權重向量w*和b，並得到分隔超平面了。

這是個凸二次規劃問題，它具有全局最優解，一般可以通過現有的工具來優化。但當訓練樣本非常多的時候，這些優化算法往往非常耗時低效，以致無法使用。從SVM提出到現在，也出現了很多優化訓練的方法。其中，非常出名的一個是1982年由Microsoft Research的John C. Platt在論文《Sequential Minimal Optimization: A Fast Algorithm for TrainingSupport Vector Machines》中提出的Sequential Minimal Optimization序列最小化優化算法，簡稱SMO算法。SMO算法的思想很簡單，它將大優化的問題分解成多個小優化的問題。這些小問題往往比較容易求解，並且對他們進行順序求解的結果與將他們作為整體來求解的結果完全一致。在結果完全一致的同時，SMO的求解時間短很多。在深入SMO算法之前，我們先來了解下坐標下降這個算法，SMO其實基於這種簡單的思想的。

8.1、坐標下降（上升）法

假設要求解下面的優化問題：

在這裡，我們需要求解m個變量αi，一般來說是通過梯度下降（這裡是求最大值，所以應該叫上升）等算法每一次迭代對所有m個變量αi也就是α向量進行一次性優化。通過誤差每次迭代調整α向量中每個元素的值。而坐標上升法（坐標上升與坐標下降可以看做是一對，坐標上升是用來求解max最優化問題，坐標下降用於求min最優化問題）的思想是每次迭代只調整一個變量αi的值，其他變量的值在這次迭代中固定不變。

最裏面語句的意思是固定除αi之外的所有αj(i不等於j)，這時W可看作只是關於αi的函數，那麼直接對αi求導優化即可。這裡我們進行最大化求導的順序i是從1到m，可以通過更改優化順序來使W能夠更快地增加並收斂。如果W在內循環中能夠很快地達到最優，那麼坐標上升法會是一個很高效的求極值方法。

用個二維的例子來說明下坐標下降法：我們需要尋找f(x,y)=x2+xy+y2的最小值處的(x*, y*)，也就是下圖的F*點的地方。

假設我們初始的點是A（圖是函數投影到xoy平面的等高線圖，顏色越深值越小），我們需要達到F*的地方。那最快的方法就是圖中黃色線的路徑，一次性就到達了，其實這個是牛頓優化法，但如果是高維的話，這個方法就不太高效了（因為需要求解矩陣的逆，這個不在這裡討論）。我們也可以按照紅色所指示的路徑來走。從A開始，先固定x，沿着y軸往讓f(x, y)值減小的方向走到B點，然後固定y，沿着x軸往讓f(x, y)值減小的方向走到C點，不斷循環，直到到達F*。反正每次只要我們都往讓f(x, y)值小的地方走就行了，這樣腳踏實地，一步步走，每一步都使f(x, y)慢慢變小，總有一天，皇天不負有心人的。到達F*也是時間問題。到這裡你可能會說，這紅色線比黃色線貧富差距也太嚴重了吧。因為這裡是二維的簡單的情況嘛。如果是高維的情況，而且目標函數很複雜的話，再加上樣本集很多，那麼在梯度下降中，目標函數對所有αi求梯度或者在牛頓法中對矩陣求逆，都是很耗時的。這時候，如果W只對單個αi優化很快的時候，坐標下降法可能會更加高效。

8.2、SMO算法

SMO算法的思想和坐標下降法的思想差不多。唯一不同的是，SMO是一次迭代優化兩個α而不是一個。為什麼要優化兩個呢？

我們回到這個優化問題。我們可以看到這個優化問題存在着一個約束，也就是

假設我們首先固定除α1以外的所有參數，然後在α1上求極值。但需要注意的是，因為如果固定α1以外的所有參數，由上面這個約束條件可以知道，α1將不再是變量（可以由其他值推出），因為問題中規定了：

因此，我們需要一次選取兩個參數做優化，比如αi和αj，此時αi可以由αj和其他參數表示出來。這樣回代入W中，W就只是關於αj的函數了，這時候就可以只對αj進行優化了。在這裡就是對αj進行求導，令導數為0就可以解出這個時候最優的αj了。然後也可以得到αi。這就是一次的迭代過程，一次迭代只調整兩個拉格朗日乘子αi和αj。SMO之所以高效就是因為在固定其他參數後，對一個參數優化過程很高效（對一個參數的優化可以通過解析求解，而不是迭代。雖然對一個參數的一次最小優化不可能保證其結果就是所優化的拉格朗日乘子的最終結果，但會使目標函數向極小值邁進一步，這樣對所有的乘子做最小優化，直到所有滿足KKT條件時，目標函數達到最小）。

總結下來是：

重複下面過程直到收斂{

（1）選擇兩個拉格朗日乘子αi和αj；

（2）固定其他拉格朗日乘子αk(k不等於i和j)，只對αi和αj優化w(α);

（3）根據優化後的αi和αj，更新截距b的值；

}

支持向量機—從推導到python手寫

筆者比較懶能截圖的地方都截圖了。

支持向量機分為三類：

（1）線性可分支持向量機，樣本線性可分，可通過硬間隔最大化訓練一個分類器。

（2）線性支持向量機，樣本基本線性可分，可通過軟間隔最大化訓練一個分類器。

（3）非線性支持向量機，樣本線性不可分，可通過核函數和軟間隔最大化訓練一個分類器。

上面最不好理解的恐怕就是硬間隔和軟間隔了，

說白了硬間隔就是說存在這麼一個平面，可以把樣本完全正確無誤的分開，當然這是一種極理想的情況，現實中不存在，所以就有了軟間隔。

軟間隔說的是，不存在一個平面可以把樣本完全正確無誤的分開，因此呢允許一些樣本被分錯，怎麼做呢就是加入鬆弛變量，因為希望分錯的樣本越小越好，因此鬆弛變量也有約束條件。加入鬆弛變量後，問題就變為線性可分了，因為是每一個樣本都線性可分，因此鬆弛變量是針對樣本的，每一個樣本都對應一個不同的鬆弛變量。

其實感知機說白了就是找到一條直線把樣本點分開，就是上方都是一類，下方是另一類。當然完全分開是好事，往往是不能完全分開的，因此就存在一個損失函數，就是誤分類點到這個平面的距離最短：

這裡啰嗦一句，誤分類點y*(wx+b)0，所以加個負號在前邊。

一般情況下||w||都是可以縮放，那麼我們把它縮放到1，最後的目標函數就變成了

間隔就是距離，我們假設分離超平面為 ，那麼樣本點到這個平面的距離可以記為 。我們都知道通過感知機劃分的點，超平面上方的點 ，下方的點 ，然後通過判斷 的值與y的符號是否一致來判斷分類是否正確。根據這個思路函數間隔定義為：

支持向量的定義來源於幾何間隔，幾何間隔最直接的解釋是離分隔超平面最近點的距離，其他任何點到平面的距離都大於這個值，所以幾何間隔就是支持向量。然後呢同樣道理，w和b是可以縮放的，所以定義支持向量滿足如下條件：

再通俗一點說，支持向量是一些點，這些點到分隔平面的距離最近，為了便於表示，把他們進行一下縮放計算，讓他們滿足了wx+b=+-1.

核函數是支持向量機的核心概念之一，它存在的目的就是將維度轉換之後的計算簡化，達到減少計算量的目的。我們都知道支持向量機求的是間距最大化，通常情況下我們求得的alpha都等於0，因此支持向量決定了間距最大化程度。

核函數的形式是這樣的

其中x(i)和x(j)都是向量，他們兩個相乘就是向量內積，相乘得到一個數。剛才說了目標函數一般只和支持向量有關，因此在做核函數計算之前，實際就是選擇的支持向量進行計算。

這個寫完下面得再補充

我們知道了支持向量的概念，那麼支持向量機的目標函數是要使這兩個支持向量之間的距離儘可能的遠，因為這樣才能更好地把樣本點分開，當然支持向量也要滿足最基本的約束條件，那就是分類正確，還有就是其他點到分隔平面的距離要大於等於支持向量到分隔平面的距離。

這種凸優化問題都可以通過拉格朗日算子進行優化，就是把約束條件通過拉格朗日係數放到目標函數上。這部分基礎知識，就是拉格朗日算法可以將等式約束和不等式約束都加到目標函數上，完成求解問題的轉換，但是要滿足一些約束條件，也就是我們後邊要說的kkt條件。

這裡有個細節就是轉換時候的加減號問題，這個和目標函數還有約束的正負號有關。一般這麼理解，就是求最小化問題時候，如果約束是大於0的，那麼拉個朗日算子可以減到這一部分，這樣一來目標函數只能越來越小，最優解就是約束為0的時候，這個時候和沒有約束的等價，再求最小就是原問題了。

這裡是最小化問題，直接減掉這部分約束，然後後半部分永遠大於等於0所以這個式子的值是要小於原來目標函數值的。我們知道當x滿足原問題的約束條件的時候，最大化L就等於那個原目標函數。所以我們可以把這個問題轉化為：

把它帶回去原來的目標函數中，整理一下。

這個時候只要求最優的α，就可以求出w和b了。我們上邊做了那麼一堆轉換，這個過程要滿足一個叫做kkt條件的東西，其實這個東西就是把一堆約束條件整理到一起。

（1）原有問題的可行性，即h(x )=0,g(x )0

放到這裡就是：

SMO算法的核心思想是求出最優化的α，然後根據之前推導得到的w,b,α之間的關係計算得到w和b，最後的計算公式是：

現在的問題就是怎麼求α了。

SMO算法總共分兩部分，一部分是求解兩個α的二次規划算法，另一部分是選擇兩個α的啟發式算法。

先說這個選擇α的啟發式算法部分：大神可以證明優先優化違反kkt條件的α可以最快獲得最優解，至於咋證明的，就先不看了。

在講支持向量機的求解算法時候，直接給出了核函數K，那麼怎麼去理解核函數呢。核函數的作用是解決樣本點在高維空間的內積運算問題，怎麼理解呢，通常的分類問題都是有很多個特徵的，然後為了達到現線性可分，又會從低維映射到高維，樣本量再一多計算量非常大，因此先通過函數進行一個轉換，減少乘法的計算量。

要理解核函數，先理解內積運算，內積運算實際是兩個向量，對應位置相乘加和，比如我有x1 = [v1,v2], x2=[w1,w2]，那麼x1和x2的內積計算方法就是：v1w1+v2w2。

如果上面那種情況線性不可分，需要到高維進行映射，讓數據變得線性可分，然後數據變為五維的，即v1 2+v2 2+v1+v2+v1v2，然後再進行一次內積計算，數據變為 。

稍作變換，可以變為 ，形式展開和上邊那個長式子差不多，然後其實可以映射內積相乘的情況，所以可以進行核函數的變化。

問題在於，當你需要顯式的寫出來映射形式的時候，在維度很高的時候，需要計算的量太大，比如x1有三個維度，再進行映射就有19維度了，計算很複雜。如果用核函數，還是在原來低維度進行運算，既有相似的效果（映射到高維），又低運算量，這就是核函數的作用了。

核函數的種類：

這部分的核心在於SMO算法的編寫。有待補充。