【干貨】支持向量機SVM算法推演

來源：海闊心

盡管早就聽說SVM比較復雜，當真正下筆推導時其復雜程度還是出乎意料瘤缩，上周花了整整兩天的時間把支持向量機分類算法的每一個細節(jié)推導了一遍喇完，但很遺憾智力及時間有限，最核心的SMO算法仍然有幾個公式?jīng)]能推導出為什么剥啤，因此本文將只推導出一個完整的SVM算法锦溪，SMO部分留待日后再續(xù)不脯。

本文旨在進一步理順SVM的算法思路，加深理解刻诊，關于SMO算法防楷、KKT法則以及核函數(shù)的介紹并不細致（以后有機會逐個拿出來介紹），算是一個粗略的學習筆記则涯，歡迎各位大神指正复局、拍磚、給出好的建議粟判，無論是關于SVM的還是其他算法抑或機器學習的任何方面亿昏。

當然，關于SVM的內(nèi)容已經(jīng)有很多經(jīng)典的論文档礁、書籍包括博文問世角钩，最基本的原理部分免不了會有重復，文末會給出本文的參考文獻及其版本呻澜。好了递礼，步入正題。

一羹幸、邏輯回歸

支持向量機（support?vector?machine）脊髓，簡稱SVM，是一種二類分類模型睹欲。理解SVM需要先理解邏輯回歸供炼，我們先簡單回顧邏輯回歸的知識，再引出SVM窘疮。

給出一堆n維樣本數(shù)據(jù)（x,y）其中x是表示樣本的特征數(shù)據(jù)，y表示樣本的類別標簽（-1,1）冀墨，此處-1和1并無特別含義闸衫，僅僅是代表兩個不同的類別，SVM分類器的學習目標便是在這堆樣本數(shù)據(jù)中找到一個超平面可以將這些樣本分成兩類诽嘉，這個超平面的方程可以表示為:

邏輯回歸的目的是通過訓練從樣本數(shù)據(jù)中學習特征蔚出，訓練出一個0/1分類器，通常以樣本所有特征列（不包括標簽列虫腋，假設標簽為0,1）為自變量骄酗，表前列為作為因變量，模型對因變量的預測結果是從負無窮到正無窮悦冀。成熟做法是用logistic函數(shù)將預測結果映射到（0,1）上趋翻，映射后的值被認為是y=1的概率。

假設函數(shù)

其中x是n維自變量盒蟆，函數(shù)g即為logistic函數(shù)踏烙，而

的圖像如下：

可以看到师骗，logistic 函數(shù)將因變量映射到（0,1）范圍內(nèi)，上述假設函數(shù)即為y=1的概率

那么當新的樣本點到來時讨惩，我們只需要算

即可辟癌，若大于0.5,就認為是屬于y=1的類，反之屬于y=0的類荐捻。

下面我們對邏輯回歸做一個變形黍少，首先將標簽由（0,1）變?yōu)椋?1,1），然后將

（

）中的替換為b处面，最后將后面的

替換為

仍侥，則有了

，由此看來鸳君，除了將因變量標簽由（0,1）變?yōu)椋?1,1）外农渊，邏輯回歸函數(shù)與SVM分類器函數(shù)

并沒有什么區(qū)別。我們通過以下映射函數(shù)將y映射到（-1,1）

二或颊、函數(shù)間隔（function margin）和幾何間隔（geometrical margin）

對于一個樣本點砸紊，在超平面（w,b）確定的情況下，|w*x+b|可以表示該樣本點到超平面的遠近（注意不是距離）囱挑，而通過觀察w*x+b與標簽y的符號是否一致可以判斷分類器分類的正確性醉顽，于是，引出函數(shù)間隔的概念：

而超平面（w,b）關于所有樣本點的函數(shù)間隔最小值便為超平面（w,b）關于訓練數(shù)據(jù)集（xi,yi）的函數(shù)間隔(其中x表示特征平挑，y表示類別標簽游添，i表示第i個樣本)：

=min

i ?(i=1，...n)

此時若成比例的改變w和b（比如2w,2b）通熄，那么函數(shù)間隔也會同比例改變唆涝，而此時超平面并未發(fā)生改變，間隔卻是不確定的唇辨！因此需要引出幾何間隔廊酣，才能更精準的描述樣本點到超平面度的距離。

假定對于一個點x赏枚，其垂直投影到超平面上的對應點是x0, w是垂直于超平面的一個向量亡驰，

為樣本x到超平面的距離，如下圖：

由平面幾何知識知道有：

其中||w||是w的二階范數(shù)饿幅，

為單位向量凡辱，又有x0位于超平面上，滿足f(x0)=0, 帶入

有

即

栗恩。

兩邊同時乘以

透乾， 再有

和

可以算出：

令

乘上對應的類別y，即得出幾何間隔的定義：

由函數(shù)間隔和幾何間隔的定義知道，幾何間隔就是函數(shù)間隔除以||w||,而函數(shù)間隔y*(w*x+b)其實就是|f(x)|, 只是認為定義的一個度量续徽，而幾何間隔才是直觀上點到超平面的距離蚓曼。

三、最優(yōu)間隔分類器

對數(shù)據(jù)點進行分類時钦扭，數(shù)據(jù)點距離超平面的間隔越大則超平面分類的確信度就越高纫版，因此我們需要讓找到的超平面使得數(shù)據(jù)點距離超平面的間隔最大化，如下圖間隔：

因為函數(shù)間隔

會因為w和b的縮放而等比例縮放客情，因此認為幾何間隔比較適合用來最大化“間隔”其弊，則最大間隔分類器的目標函數(shù)可以為：

根據(jù)函數(shù)間隔的定義有：

又有幾何間隔的定義有：

若令函數(shù)間隔

為1，則易知

=1/||w||膀斋，且

梭伐，那么目標函數(shù)轉化為：

如下圖中間的實線就是所找的超平面，兩條虛線間隔邊界上的點就是支持向量仰担，這些支持向量在虛線間隔邊界上糊识，那么滿足：

，而所有不在虛線上的點有：

摔蓝。

四赂苗、原始問題轉化為對偶問題

前文已得到最優(yōu)化函數(shù)：

等價于：

顯然目標函數(shù)是二次的，又有線性約束條件贮尉，它是一個凸二次規(guī)劃問題拌滋，我們可以使用現(xiàn)有的優(yōu)化包求解，也可以通過拉格朗日對偶性變換到對偶變量的優(yōu)化問題猜谚，即通過求解與原問題等價的的對偶問題來求解超平面败砂。

定義拉格朗日函數(shù)（不知道的請自行查閱高等數(shù)學或百度百科）：

令：

在滿足約束條件的情況下最小化1/2||w||^2,目標函數(shù)變?yōu)椋?/p>

表示此問題的最優(yōu)值，同原始問題等價魏铅。為易于求解昌犹，我們調換最大和最小的位置：

下面可以先求L對w,b的極小值，再求L對

的極大沦零。

五祭隔、對偶問題的求解

（1）、先固定

路操，讓L對w,b求偏導：

將偏導結果帶入L函數(shù)有：

化簡可得（此化簡過程用到了線性代數(shù)的轉置和乘積運算，感興趣可以自己推導千贯，并不難）：

此時拉格朗日函數(shù)只包含一個變量

（求出了

就能求出w,b）屯仗。

（2）、求拉格朗日函數(shù)對

的極大

由（1）得知：

這樣求出

搔谴，又有可以求出w：

那么只剩下b可以這樣表示

這樣就得出了分離超平面和分類函數(shù)魁袜。

在L對w,b最小化以及對

最大化時，最后一步可以用SMO算法求解拉個讓日乘子

，本文并不推導SMO算（以后會單獨拿出一篇的章節(jié)來介紹和推導SMO）峰弹，下面介紹非線性求解情況店量，并以此引入核函數(shù)。

六鞠呈、線性不可分情況

通過以上推導我們知道所謂超平面其實就是把自變量x帶入：

得到結果后以正負號劃分分類融师。并有w:

分類函數(shù)為：

仔細觀察分類函數(shù)，對于一個新的需要預測的點來說蚁吝，只需要計算它與訓練數(shù)據(jù)點的內(nèi)積即可旱爆。另外回憶一下我們之前得到的一個目標函數(shù)：

注意到若數(shù)據(jù)點xi是支持向量的話，上式中紅色部分為0（支持向量的函數(shù)間隔為1）窘茁，而所有非支持向量的函數(shù)和間隔均大于1怀伦，紅色部分大于0，

是非負的山林，為滿足最大化房待，非支持向量的

均必須為0，因此針對新點的預測只需要針對少量支持向量進行計算即可驼抹。

目前我們的支持向量機分類器還只能處理線性分類桑孩，為推廣到非線性形式，下面稍稍介紹下核函數(shù)砂蔽。

七洼怔、核函數(shù)

對于非線性數(shù)據(jù)分類的問題，SVM的通常做法是用一個和函數(shù)將數(shù)據(jù)由低維空間映射到高維空間左驾，在高維空間中解決原始空間中線性不可分問題镣隶。

如下圖一堆數(shù)據(jù)點在二維空間中不可分，映射帶到三維空間中劃分：

由于對偶形式是線性學習器的一個重要性質诡右，這意味著假設集可以表示為訓練點的線性組合安岂，因此決策規(guī)則可以用測試點和訓練點的內(nèi)積來表示：

若可以在特征空間中直接計算內(nèi)積〈φ(xi?·?φ(x)〉，就像在原始輸入點的函數(shù)中一樣帆吻，將兩個步驟融合到一起建立一個非線性的學習器域那，這樣直接計算法的方法稱為核函數(shù)方法。

八猜煮、引入松弛變量處理 outliers

現(xiàn)實世界中的數(shù)據(jù)集常常是伴隨著大量的噪音次员，他們偏離正常的位置很遠，我們成為outliers王带，這些outliers對超平面的劃分會有很大的干擾淑蔚，因為超平面本身就是由幾個支持向量決定的，如圖：

用黑圈圈起來的那個藍點是一個 outlier 愕撰，它偏離了自己本應所在的那個半空間刹衫，若直接忽略掉它醋寝，超平面還是挺好的，但是由于 outlier 的出現(xiàn)带迟，分隔超平面被擠歪音羞，變成途中黑色虛線，同時間隔也相應變小了仓犬。若這個 outlier 再往右上移動一點嗅绰，也許我們將無法建立成超平面。

在原本我們的約束條件上考慮到outliers的因素：

為松弛變量婶肩，表示我們能夠容忍對應的數(shù)據(jù)點偏離函數(shù)間隔的程度办陷，松弛變量不能無限大，在目標函數(shù)加上一項約束他：

其中C是一個常數(shù)律歼，用來平衡“尋找最優(yōu)超平面”和“保證數(shù)據(jù)點偏差總量最小”這兩個約束的權重民镜。將新的約束條件加入到目標函數(shù)又有新的拉格朗日函數(shù)：

同樣轉為對偶問題，讓L先對w,b和

極小化险毁，

將以上結果帶入L函數(shù)然后化簡制圈，你會驚奇的發(fā)現(xiàn)松弛變量竟然消失了！得到了和之前一樣的目標函數(shù)：

上面化簡得到

畔况，又有

鲸鹦，因此有

，那么整個目標函數(shù)和約束條件可以寫做：

把目標函數(shù)和約束條件同之前對比發(fā)現(xiàn)只是對

的約束多了一個C，Kernel 化的非線性形式只需要把（xi,xj）換成K（xi,xj）。這樣一個完整的病蛉，可以處理線性和非線性并能容忍噪音和 outliers 的支持向量機就終于介紹完畢了弧蝇。

SVM本質上是一個分類方法闰歪，用w^T+b定義分類函數(shù)，于是求w、b，為尋最大間隔眯停，引出1/2||w||^2，繼而引入拉格朗日因子卿泽，化為對拉格朗日乘子

的求解（求解過程中會涉及到一系列最優(yōu)化或凸二次規(guī)劃等問題）莺债，如此，求w.b與求

等價签夭，而

的求解可以用一種快速學習算法SMO齐邦，至于核函數(shù)，是為處理非線性情況第租，若直接映射到高維計算恐維度爆炸侄旬，故在低維計算，等效高維表現(xiàn)煌妈。

關于SVM的深層理論我也不是理解的很透徹，本文僅作學習筆記之用，還有很多細節(jié)需要來回追究璧诵，還是那句話汰蜘，歡迎各位大神指正、拍磚之宿、給出好的建議族操，無論是關于SVM的還是其他算法抑或機器學習的任何方面。

參考文獻：

《深度學習》周志華版本

《統(tǒng)計學習方法》李航

《數(shù)據(jù)挖掘導論》Pang-Ning Tan, Michacl Sterinbach, Vipin Kumar

《支持向量機導論》Nello Cristianini, John Shawe-Taylor

了解更多：

http://blog.pluskid.org/?page_id=683

http://www.cnblogs.com/jerrylead/

http://blog.csdn.net/johnnyconstantine/article/details/46335763