SVM是數(shù)據(jù)挖掘算法中比較復(fù)雜難懂的副渴，反復(fù)觀看斯坦福機(jī)器學(xué)習(xí)的視頻， 以及網(wǎng)上零散學(xué)習(xí)各種數(shù)學(xué)和SVM相關(guān)資料， 對(duì)SVM還只能算有個(gè)粗淺的理解慕匠，寫篇文章梳理下SVM的基本脈絡(luò)，和大家分享下域醇，有不正確之處請(qǐng)指正絮重。

SVM介紹

SVM支持向量機(jī)（英文全稱：support vector machine）是一個(gè)分類算法， 通過找到一個(gè)分類平面歹苦， 將數(shù)據(jù)分隔在平面兩側(cè)青伤， 從而達(dá)到分類的目的。
如下圖所示殴瘦， 直線表示的是訓(xùn)練出的一個(gè)分類平面狠角， 將數(shù)據(jù)有效的分隔開。

SVM分類示意圖

SVM實(shí)現(xiàn)原理

SVM的分類基本思路是找到一個(gè)分類平面蚪腋， 下面重點(diǎn)探討下如何找到這個(gè)平面丰歌。 先梳理下SVM求解的基本思路;

Paste_Image.png

如圖SVM的推導(dǎo)分為5個(gè)步驟：

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

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

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

4. SMO求解alpha最優(yōu)值
   通過上步構(gòu)建的方程描融， w, b可以通過alpha來表示铝噩。 SMO可以求解出alpha， 再通過alpha求出w,b窿克。 到此平面的方程就可推導(dǎo)出來骏庸。

SVM的數(shù)學(xué)定義

SVM是要找到最合適的分類平面， 那么怎么才算最合適的? 最直接的評(píng)估標(biāo)準(zhǔn)：被分隔的兩邊數(shù)據(jù)距離平面間隔最大年叮， 換句話具被，SVM就是獲取最大間隔的超平面。下面介紹兩個(gè)衡量樣本到超平面間隔的定義谋右。

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

單樣本函數(shù)間隔

其中y是訓(xùn)練數(shù)據(jù)的類標(biāo)記值辈挂， 如果y(w^T * x + b) >0說明衬横，預(yù)測的值和標(biāo)記的值相同， 分類正確终蒂，而且值越大蜂林，說明點(diǎn)離平面越遠(yuǎn)，分類的可靠程度更高拇泣。這是對(duì)單個(gè)樣本的函數(shù)定義噪叙， 對(duì)整個(gè)樣本集來說，要找到所有樣本中間隔值最小的作為整個(gè)集合的函數(shù)間隔：

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

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

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

Paste_Image.png

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

Paste_Image.png

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

Paste_Image.png

最大間隔分類器就是我們求取的分類超平面寥枝， 等于max(幾何間隔)， 而函數(shù)間隔假設(shè)為1将塑，就可得到最大間隔超平面: max(1/||w||), 而約束條件是因?yàn)楹瘮?shù)間隔是所有樣本點(diǎn)的間隔函數(shù)中最小值脉顿。

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

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

Paste_Image.png

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

Paste_Image.png

拉格朗日構(gòu)建方程

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

拉格朗日

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

Paste_Image.png

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

Paste_Image.png

其中ai是拉格朗日乘子。

利用對(duì)偶性的結(jié)論玻粪， 對(duì)L(w隅津，b，a)關(guān)于w和b求偏導(dǎo)數(shù)：

Paste_Image.png

將上面兩個(gè)等式劲室，代入L(w, b, a)函數(shù)伦仍，最終最大間隔分類器優(yōu)化文件， 就轉(zhuǎn)換成如下定義（過程太過復(fù)雜很洋，直接看下結(jié)論就可以）充蓝， 注意這個(gè)公式中只涉及求解ai的極大值， 不涉及w, b參數(shù)的求解蹲缠， 因?yàn)閣, b都可以用ai來表示棺克， 求出ai后悠垛， 自然就求出了w,b的值。

Paste_Image.png

SMO算法求解alpha

上面推導(dǎo)的公式娜谊， 是通過SMO算法來求解的确买。最常見的是Platt SMO算法 ， 這個(gè)算法是在1996年John Platt 發(fā)布的纱皆。SMO算法（Sequential Minimal Optimization）全稱是最小序列優(yōu)化湾趾。SMO的基本思路類似動(dòng)態(tài)規(guī)劃， 也是一種啟發(fā)式算法派草，它將原優(yōu)化問題分解為多個(gè)小優(yōu)化問題來求解搀缠，并且對(duì)這些小優(yōu)化問題進(jìn)行順序求解得到的結(jié)果作為作為整體的結(jié)果。本文不詳細(xì)介紹近迁， 后續(xù)文章更新艺普。

后記：

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

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