姓名：崔升? ? 學(xué)號(hào)：14020120005

轉(zhuǎn)載自：http://www.cnblogs.com/en-heng/p/5965438.html

【嵌牛導(dǎo)讀】：SVM（Support Vector Machines）是分類算法中應(yīng)用廣泛豌研、效果不錯(cuò)的一類妹田。《統(tǒng)計(jì)學(xué)習(xí)方法》對(duì)SVM的數(shù)學(xué)原理做了詳細(xì)推導(dǎo)與論述聂沙，本文僅做整理秆麸。由簡(jiǎn)至繁SVM可分類為三類：線性可分（linear SVM in linearly separable case）的線性SVM、線性不可分的線性SVM及汉、非線性（nonlinear）SVM。

【嵌牛鼻子】：經(jīng)典大數(shù)據(jù)算法之SVM簡(jiǎn)單介紹

【嵌牛提問(wèn)】：SVM是一種怎么的算法屯烦，三種SVM分別是什么坷随？

【嵌牛正文】：

1. 線性可分

對(duì)于二類分類問(wèn)題，訓(xùn)練集T={(x1,y1),(x2,y2),?,(xN,yN)}T={(x1,y1),(x2,y2),?,(xN,yN)}驻龟，其類別yi∈{0,1}yi∈{0,1}温眉，線性SVM通過(guò)學(xué)習(xí)得到分離超平面（hyperplane）:

w?x+b=0w?x+b=0

以及相應(yīng)的分類決策函數(shù)：

f(x)=sign(w?x+b)f(x)=sign(w?x+b)

有如下圖所示的分離超平面，哪一個(gè)超平面的分類效果更好呢翁狐？

直觀上类溢，超平面B1B1的分類效果更好一些。將距離分離超平面最近的兩個(gè)不同類別的樣本點(diǎn)稱為支持向量（support vector）的露懒，構(gòu)成了兩條平行于分離超平面的長(zhǎng)帶闯冷，二者之間的距離稱之為margin。顯然懈词，margin更大蛇耀，則分類正確的確信度更高（與超平面的距離表示分類的確信度，距離越遠(yuǎn)則分類正確的確信度越高）坎弯。通過(guò)計(jì)算容易得到：

margin=2∥w∥margin=2‖w‖

從上圖中可觀察到：margin以外的樣本點(diǎn)對(duì)于確定分離超平面沒(méi)有貢獻(xiàn)纺涤，換句話說(shuō)译暂，SVM是有很重要的訓(xùn)練樣本（支持向量）所確定的。至此撩炊，SVM分類問(wèn)題可描述為在全部分類正確的情況下外永，最大化2∥w∥2‖w‖（等價(jià)于最小化12∥w∥212‖w‖2）；線性分類的約束最優(yōu)化問(wèn)題：

minw,b12|w|2s.t.yi(w?xi+b)?1≥0(1)(2)(1)minw,b12|w|2(2)s.t.yi(w?xi+b)?1≥0

對(duì)每一個(gè)不等式約束引進(jìn)拉格朗日乘子（Lagrange multiplier）αi≥0,i=1,2,?,Nαi≥0,i=1,2,?,N拧咳；構(gòu)造拉格朗日函數(shù)（Lagrange function）：

L(w,b,α)=12|w|2?∑i=1Nαi[yi(w?xi+b)?1](3)(3)L(w,b,α)=12|w|2?∑i=1Nαi[yi(w?xi+b)?1]

根據(jù)拉格朗日對(duì)偶性象迎，原始的約束最優(yōu)化問(wèn)題可等價(jià)于極大極小的對(duì)偶問(wèn)題：

maxαminw,bL(w,b,α)maxαminw,bL(w,b,α)

將L(w,b,α)L(w,b,α)對(duì)w,bw,b求偏導(dǎo)并令其等于0，則

?L?w=w?∑i=1Nαiyixi=0?w=∑i=1Nαiyixi?L?b=∑i=1Nαiyi=0?∑i=1Nαiyi=0?L?w=w?∑i=1Nαiyixi=0?w=∑i=1Nαiyixi?L?b=∑i=1Nαiyi=0?∑i=1Nαiyi=0

將上述式子代入拉格朗日函數(shù)(3)(3)中呛踊，對(duì)偶問(wèn)題轉(zhuǎn)為

maxα?12∑i=1N∑j=1Nαiαjyiyj(xi?xj)+∑i=1Nαimaxα?12∑i=1N∑j=1Nαiαjyiyj(xi?xj)+∑i=1Nαi

等價(jià)于最優(yōu)化問(wèn)題：

minαs.t.12∑i=1N∑j=1Nαiαjyiyj(xi?xj)?∑i=1Nαi∑i=1Nαiyi=0αi≥0,i=1,2,?,N(4)(5)(6)(4)minα12∑i=1N∑j=1Nαiαjyiyj(xi?xj)?∑i=1Nαi(5)s.t.∑i=1Nαiyi=0(6)αi≥0,i=1,2,?,N

線性可分是理想情形砾淌，大多數(shù)情況下，由于噪聲或特異點(diǎn)等各種原因谭网，訓(xùn)練樣本是線性不可分的汪厨。因此，需要更一般化的學(xué)習(xí)算法愉择。

2. 線性不可分

線性不可分意味著有樣本點(diǎn)不滿足約束條件(2)(2)劫乱，為了解決這個(gè)問(wèn)題，對(duì)每個(gè)樣本引入一個(gè)松弛變量ξi≥0ξi≥0锥涕，這樣約束條件變?yōu)椋?/p>

yi(w?xi+b)≥1?ξiyi(w?xi+b)≥1?ξi

目標(biāo)函數(shù)則變?yōu)?/p>

minw,b,ξ12∥w∥2+C∑i=1Nξiminw,b,ξ12‖w‖2+C∑i=1Nξi

其中衷戈，CC為懲罰函數(shù)，目標(biāo)函數(shù)有兩層含義：

margin盡量大层坠，

誤分類的樣本點(diǎn)計(jì)量少

CC為調(diào)節(jié)二者的參數(shù)殖妇。通過(guò)構(gòu)造拉格朗日函數(shù)并求解偏導(dǎo)（具體推導(dǎo)略去），可得到等價(jià)的對(duì)偶問(wèn)題：

minα12∑i=1N∑j=1Nαiαjyiyj(xi?xj)?∑i=1Nαi(7)(7)minα12∑i=1N∑j=1Nαiαjyiyj(xi?xj)?∑i=1Nαi

s.t.∑i=1Nαiyi=00≤αi≤C,i=1,2,?,N(8)(9)(8)s.t.∑i=1Nαiyi=0(9)0≤αi≤C,i=1,2,?,N

與上一節(jié)中線性可分的對(duì)偶問(wèn)題相比破花，只是約束條件αiαi發(fā)生變化谦趣，問(wèn)題求解思路與之類似。

3. 非線性

對(duì)于非線性問(wèn)題座每，線性SVM不再適用了前鹅，需要非線性SVM來(lái)解決了。解決非線性分類問(wèn)題的思路峭梳，通過(guò)空間變換??（一般是低維空間映射到高維空間x→?(x)x→?(x)）后實(shí)現(xiàn)線性可分舰绘，在下圖所示的例子中，通過(guò)空間變換葱椭，將左圖中的橢圓分離面變換成了右圖中直線捂寿。

在SVM的等價(jià)對(duì)偶問(wèn)題中的目標(biāo)函數(shù)中有樣本點(diǎn)的內(nèi)積xi?xjxi?xj，在空間變換后則是?(xi)??(xj)?(xi)??(xj)挫以，由于維數(shù)增加導(dǎo)致內(nèi)積計(jì)算成本增加者蠕，這時(shí)核函數(shù)（kernel function）便派上用場(chǎng)了，將映射后的高維空間內(nèi)積轉(zhuǎn)換成低維空間的函數(shù)：

K(x,z)=?(x)??(z)K(x,z)=?(x)??(z)

將其代入一般化的SVM學(xué)習(xí)算法的目標(biāo)函數(shù)(7)(7)中掐松，可得非線性SVM的最優(yōu)化問(wèn)題：

minαs.t.12∑i=1N∑j=1NαiαjyiyjK(xi,xj)?∑i=1Nαi∑i=1Nαiyi=00≤αi≤C,i=1,2,?,N(10)(11)(12)(10)minα12∑i=1N∑j=1NαiαjyiyjK(xi,xj)?∑i=1Nαi(11)s.t.∑i=1Nαiyi=0(12)0≤αi≤C,i=1,2,?,N

4. 參考資料

[1] 李航踱侣，《統(tǒng)計(jì)學(xué)習(xí)方法》.

[2] Pang-Ning Tan, Michael Steinbach, Vipin Kumar,Introduction to Data Mining.