SVM是數(shù)據(jù)挖掘算法中比較復雜難懂的，反復觀看斯坦福機器學習的視頻， 以及網(wǎng)上零散學習各種數(shù)學和SVM相關資料， 對SVM還只能算有個粗淺的理解，寫篇文章梳理下SVM的基本脈絡，和大家分享下，有不正確之處請指正。

SVM介紹

SVM支持向量機（英文全稱：support vector machine）是一個分類算法， 通過找到一個分類平面， 將數(shù)據(jù)分隔在平面兩側， 從而達到分類的目的。
如下圖所示， 直線表示的是訓練出的一個分類平面， 將數(shù)據(jù)有效的分隔開。

SVM分類示意圖

SVM實現(xiàn)原理

SVM的分類基本思路是找到一個分類平面， 下面重點探討下如何找到這個平面。 先梳理下SVM求解的基本思路;

Paste_Image.png

如圖SVM的推導分為5個步驟：

1. 用數(shù)學來定義要求解的問題
   SVM是求解一個平面S：y = wx + b， 其實就是求解參數(shù)w, b。如何來求解w, b呢？ 怎么判斷訓練的w, b構成的平面已經(jīng)足夠好呢？ 這就需要把問題建模成一個數(shù)學問題（稱為原始問題），從而明確求解的目標以及約束條件。

2. 求解原始問題轉換為二次凸函數(shù)+約束條件的優(yōu)化問題
   原始問題很難求解出參數(shù)， 轉換為二次凸函數(shù)+約束條件的優(yōu)化問題， 這種轉換保證兩個函數(shù)取最優(yōu)解時，參數(shù)是相同的。做這種轉換的主要原因是二次凸函數(shù)和約束條件有成熟的計算方法和理論支撐(拉格朗日優(yōu)化理論)。

3. 拉格朗日優(yōu)化+對偶特性構建方程
   將w, b參數(shù)優(yōu)化轉換為對參數(shù)alpha的優(yōu)化（alpah為拉格朗日約束函數(shù)的參數(shù)）

4. SMO求解alpha最優(yōu)值
   通過上步構建的方程， w, b可以通過alpha來表示。 SMO可以求解出alpha， 再通過alpha求出w,b。 到此平面的方程就可推導出來。

SVM的數(shù)學定義

SVM是要找到最合適的分類平面， 那么怎么才算最合適的? 最直接的評估標準：被分隔的兩邊數(shù)據(jù)距離平面間隔最大， 換句話，SVM就是獲取最大間隔的超平面。下面介紹兩個衡量樣本到超平面間隔的定義。

1. 函數(shù)間隔
   在超平面w * x + b = 0確定的情況下，|wx+b|表示點距離超平面的距離，而超平面作為二分類器，如果wx+b>0， 判斷類別y為1, 否則判定為-1。從而引出函數(shù)間隔的定義：

單樣本函數(shù)間隔

其中y是訓練數(shù)據(jù)的類標記值， 如果y(w^T * x + b) >0說明，預測的值和標記的值相同， 分類正確，而且值越大，說明點離平面越遠，分類的可靠程度更高。這是對單個樣本的函數(shù)定義， 對整個樣本集來說，要找到所有樣本中間隔值最小的作為整個集合的函數(shù)間隔：

整個數(shù)據(jù)集的函數(shù)間隔

即w和b同時縮小或放大M倍后，超平面并沒有變化，但是函數(shù)間隔跟著w和b變化。所以，需要加入約束條件使得函數(shù)間隔固定, 也就是下面介紹的幾何間隔。

2.幾何間隔
根據(jù)點到平面的距離公式和w*x+b=0平面公式， 推導得到幾何間隔定義：

Paste_Image.png

和函數(shù)間隔類似， 為得到r的絕對值， 我們定義幾何間隔:在上述公式中乘以y值， 同時也得到與函數(shù)間隔的關系：幾何間隔就是函數(shù)間隔除以w的范式。

Paste_Image.png

為方便推導和優(yōu)化， 令函數(shù)間隔等于1得到最大間隔分類器的原始定義：

Paste_Image.png

最大間隔分類器就是我們求取的分類超平面， 等于max(幾何間隔)， 而函數(shù)間隔假設為1，就可得到最大間隔超平面: max(1/||w||), 而約束條件是因為函數(shù)間隔是所有樣本點的間隔函數(shù)中最小值。

SVM的二次凸函數(shù)和約束條件

最大間隔分類器的求解， 可以轉換為上面的一個最優(yōu)化問題， 即在滿足約束條件：

Paste_Image.png

求出就最大的1/||w||。
為更好的利用現(xiàn)有的理論和計算方法， 可以將求解1/||w||最大值， 轉換為一個二次凸函數(shù)優(yōu)化問題：求解 Min(1/2 * (||w||)^2 )， 兩者問題是等價的。原來的問題轉換為二次凸函數(shù)優(yōu)化問題：

Paste_Image.png

拉格朗日構建方程

在對二次凸函數(shù)進行優(yōu)化前，先討論下對偶性問題。 如下圖所示, 假設一個函數(shù)F(x,y) = f(x, y) + a * (g(x, y) - c)， 橢圓線是f(x, y)在平面上的等高線， 綠色是g(x, y)=c的軌跡。

拉格朗日

從圖上可以看出， F(x, y)的極值點肯定是f(x,y)和g(x,y)-c相切的點， 這點上兩個曲線的法向量平行。從而可以得到如下結論：

Paste_Image.png

類似的，可以將1/2 * ||w|| ^2優(yōu)化函數(shù)和約束條件結合起來， 構建一個函數(shù)：

Paste_Image.png

其中ai是拉格朗日乘子。

利用對偶性的結論， 對L(w，b，a)關于w和b求偏導數(shù)：

Paste_Image.png

將上面兩個等式，代入L(w, b, a)函數(shù)，最終最大間隔分類器優(yōu)化文件， 就轉換成如下定義（過程太過復雜，直接看下結論就可以）， 注意這個公式中只涉及求解ai的極大值， 不涉及w, b參數(shù)的求解， 因為w, b都可以用ai來表示， 求出ai后， 自然就求出了w,b的值。

Paste_Image.png

SMO算法求解alpha

上面推導的公式， 是通過SMO算法來求解的。最常見的是Platt SMO算法 ， 這個算法是在1996年John Platt 發(fā)布的。SMO算法（Sequential Minimal Optimization）全稱是最小序列優(yōu)化。SMO的基本思路類似動態(tài)規(guī)劃， 也是一種啟發(fā)式算法，它將原優(yōu)化問題分解為多個小優(yōu)化問題來求解，并且對這些小優(yōu)化問題進行順序求解得到的結果作為作為整體的結果。本文不詳細介紹， 后續(xù)文章更新。

后記：

1. 本文大體梳理下SVM的推導求解過程， 但這個推導只針對線性的分類超平面，非線性分類超平面需要用到核函數(shù)， 將低維線性不可分通過空間映射到高維， 從而變得線性可分。
2. SMO的具體用法和實現(xiàn)代碼先記下， 有時間再更新。

介紹一篇比較總結比較好的文章：
http://mp.weixin.qq.com/s/Uha_MJQtJiWRhBuVW32y9g