一小時(shí)領(lǐng)會SVM支持向量機(jī)

在機(jī)器學(xué)習(xí)領(lǐng)域，SVM支持向量機(jī)作為殺手級武器，對于分類問題是一招鮮——吃遍天！它強(qiáng)大的通用技能對于很多偷懶的工程師都是一大福音，所謂是兵來將擋，更有甚者，來了問題用SVM上，沒有問題也要創(chuàng)造問題讓SVM上，開玩笑啦。所以，童鞋們都知道了SVM的重要性，紛紛投向其大本營，于是看到了一大堆公式的推導(dǎo)，懵X……

寫這篇文章的目的就是為了幫助找不到簡單易理解的學(xué)習(xí)資料的童鞋，請你一致向這看齊。

等等，想要熟讀本文，你們還得需要基礎(chǔ)的高數(shù)、線性代數(shù)、統(tǒng)計(jì)學(xué)習(xí)知識，什么？都沒有？學(xué)了都忘了？基本沒關(guān)系，因?yàn)榈綍r(shí)候遇到關(guān)鍵詞的時(shí)候，我會具體指出哪些需要你們花三分鐘百度一下的，好了，又說了這么多，這一次，我們真的要開始了！

先簡單解釋一下支持向量機(jī)的作用。這是一個(gè)二分類分類器，所謂分類分類，就是把你輸入的樣本扔到該待的陣營里。好，舉個(gè)例子，最簡單是二維的，我們現(xiàn)在假設(shè)有n個(gè)(X1，X2)樣本，對應(yīng)的陣營有兩個(gè)類別，分別是1和-1。那么我現(xiàn)在給你一個(gè)(X1，X2)樣本，你告訴我它是屬于1的還是屬于-1的。說得有點(diǎn)抽象，來畫個(gè)圖，假如我給你一個(gè)方塊，你是覺得它是屬于1還是-1，由圖可見，它是屬于1了。

作用我們說完了，接下來我們開始聊原理。上面的圖片告訴我們什么了？我們看到，有兩個(gè)一模一樣的坐標(biāo)圖，方塊和圓圈的分界很明顯，所以你要是給我一個(gè)方塊我毫不猶豫就把它扔進(jìn)-1的區(qū)域。那么問題來了，我大概知道1區(qū)域在哪里，但是具體的邊界位置在哪里？我們看到第一個(gè)坐標(biāo)軸和第二個(gè)坐標(biāo)軸劃分的區(qū)域是不一樣的，第一個(gè)區(qū)域劃分得比較勻稱，而第二個(gè)區(qū)域劃分得有點(diǎn)勉強(qiáng)，為什么會有這種感覺？第一個(gè)劃分線距離每一個(gè)點(diǎn)都是有些距離的，而第二個(gè)劃分線距離其中有些點(diǎn)過于近了，這是我們直觀的判斷感覺。

對于支持向量機(jī)，它是怎么判斷這個(gè)線劃分得好不好？接下來這句話非常重要：我們找的這條線，能夠讓所有點(diǎn)中離它最近的點(diǎn)，具有最大間距。  我們分析一下這句話，我們找的這條線，判斷它好不好，不靠所有的點(diǎn)，而是靠離它最近的一個(gè)點(diǎn)，僅靠這一個(gè)點(diǎn)到直線的距離，來直接判斷這條線好不好。

那我們就開始找這條線，根據(jù)眾多的樣本(X1,X2)，我們設(shè)這個(gè)直線為wTx+b=0 ( wTx=w1x1+w2x2+w3x3+……+wnxn，這里只有二元，所以這里的wTx=w1x1+w2x2)。

wTx看不懂？這里就要開始用到線性代數(shù)知識了，熟悉的直接掠過這段話，這里可以百度矩陣的知識。簡單解釋下，假設(shè)有一條直線y=kx+b，這是一元的。如果是多元的，比如三元一次函數(shù)y=k1x1+k2x2+k3x3+b，這個(gè)時(shí)候我們就可以用矩陣K=[k1,k2,k3]來代表，那么這個(gè)函數(shù)就變成了y=KTx，上標(biāo)T代表矩陣的轉(zhuǎn)置，這里你們需要百度矩陣的乘法。

我們看到了圖中的這條直線wTx+b=0，其實(shí)對于數(shù)學(xué)稍微敏感點(diǎn)的童鞋已經(jīng)知道怎么利用公式判斷點(diǎn)屬于哪個(gè)陣營的了，看圖中方塊都在wTx+b=1直線以上，說明如果wTx+b>=1的一定是方塊，同理，如果wTx+b<=-1的一定是圓圈，重點(diǎn)來了，在這里我介紹一個(gè)函數(shù)，它就是SVM最基礎(chǔ)的決策函數(shù)：f(x)=sgn(wTx+b)，sgn()是一個(gè)函數(shù)，遇到小于等于-1的值會返回-1，遇到大于等于1的值返回1，所以最終f(x)的值是1或者-1，所以我們要把wTx+b=0解出來，再次明確一下我們現(xiàn)在的目標(biāo)，求w和b的值。

wTx+b=0的前后還有兩條平行線，仔細(xì)觀察，這兩條線都與各自區(qū)域內(nèi)最外邊的點(diǎn)是重合關(guān)系，這里說得直白一點(diǎn)，其實(shí)wTx+b=0是由它前后兩條線推出來的，因?yàn)樗幱谇昂髢蓷l線的正中間。要打戰(zhàn)了，我們把那兩條線都當(dāng)作是雙方的戰(zhàn)壕，把每個(gè)點(diǎn)都當(dāng)作要打戰(zhàn)的士兵，士兵打完戰(zhàn)回戰(zhàn)壕休整，這個(gè)時(shí)候當(dāng)然我方戰(zhàn)壕離敵方戰(zhàn)壕越遠(yuǎn)越好，士兵有安全感嘛，而士兵太累活動不了，他們的位置就是不變的，在這種情況下怎么才能把雙方的戰(zhàn)壕隔得最遠(yuǎn)？這里先求兩個(gè)直線的距離，這里假設(shè)第一條直線是w1x1+w2x2=1，第二條直線是w1x1+w2x2=-1，根據(jù)高中的數(shù)學(xué)知識，我們求得它們的距離d=2/ sqrt(W12+w22)，用矩陣表示就是2/||w||,問題轉(zhuǎn)化為求2/||w||的最大值。這兩條線向后退，退到什么時(shí)候距離才是最大的？那就是剛好貼在最前面的士兵，不能再后退了，不然前面的士兵就沒東西擋著了，這個(gè)時(shí)候，我們想起前面一句話，我們找的這條線，能夠讓所有點(diǎn)中離它最近的點(diǎn)，具有最大間距 ，這個(gè)最前面的士兵就是離中線最近的點(diǎn)，所以這個(gè)時(shí)候這兩條直線的距離間接幫助我們解決了找中間這條線的問題。

開始簡化問題，目前我們手中有一個(gè)目標(biāo)函數(shù)，2/||w||，求它的最小值，把它轉(zhuǎn)化一下，就是求1/2*||w||2的最大值，這個(gè)可以理解。直接求肯定是求不出來的，看看有沒有其他條件，我們知道方塊的屬性是y=1，而它的wTx+b>=1，圓圈的屬性是y=-1，而它的wTx+b<=1。所以yi(wTx+b)>=1，我們稱它為約束條件。

這個(gè)時(shí)候我們引入拉格朗日乘子法，其簡單解釋如下圖，即把目標(biāo)函數(shù)和約束條件以一定形式結(jié)合到一個(gè)函數(shù)中，再求解，具體解釋百度拉格朗日乘子法。

由拉格朗日乘子法轉(zhuǎn)換得到

現(xiàn)在把原函數(shù)轉(zhuǎn)化成了現(xiàn)在這個(gè)L函數(shù)，由于轉(zhuǎn)化為對偶問題（這里不懂直接百度拉格朗日對偶問題），原來求的最小值，變成了求L的最大值，不過L也是有約束條件的，不然它就變成無窮大了，這個(gè)約束條件還是那個(gè)yi(wTx+b)>=1。梳理一下思路，現(xiàn)在有三個(gè)變量，分別是w，b，a，那么L函數(shù)最大是什么時(shí)候，就是減號后面為0(因?yàn)樗荒転樨?fù)數(shù)，不然不滿足導(dǎo)入拉格朗日乘子法這個(gè)目的)，所以L函數(shù)最大的時(shí)候還是1/2*||w||2，問題又來了，我們本來不就是要求1/2*||w||2的最小值嗎？所以現(xiàn)在的情況變成了這樣

把它轉(zhuǎn)化一下

有時(shí)候數(shù)學(xué)就是這么奇妙，我們的腦筋還沒轉(zhuǎn)過彎，它就幫我們不知不覺解決了問題，想起一位老師的話：微妙的數(shù)學(xué)思維蘊(yùn)含著宇宙的真理，我們不知道為什么這樣能解出來，可它就是解出來了，就像宇宙中的種種巧合，突然就蹦了出來，當(dāng)然這是眾多資深的數(shù)學(xué)家前輩們窮其一生的精華，值得我們?nèi)プ鹧觥Ｓ植恢勒f到哪里去了，現(xiàn)在我們目標(biāo)就明確了一點(diǎn)，求解L函數(shù)關(guān)于w和b的最小值，你想到什么？沒錯，簡單的一階偏微分就夠了，這個(gè)時(shí)候w，b的梯度都為0，它們在這里都達(dá)到極值。

將第一個(gè)函數(shù)代入L函數(shù)，得到

現(xiàn)在得到了一個(gè)新函數(shù)，是不是有些陌生，其實(shí)這些都是w和b的化身而已，α現(xiàn)在取代了w和b的位置，這樣看起來求解確實(shí)是方便了許多。你們有沒有發(fā)現(xiàn)之前的約束條件已經(jīng)用掉了，現(xiàn)在需要去尋找新的約束條件去求解，眼皮底下只有一個(gè)條件可以用，那就是L函數(shù)關(guān)于b的偏微分所得到的結(jié)果。約束條件找到了，現(xiàn)在把目標(biāo)函數(shù)轉(zhuǎn)化一下，求L函數(shù)的最大值，就是求-L的最小值，重新梳理一下，再次明確我們的目標(biāo)，通過求α的值來求w和b的值。

這里我們先打住，因?yàn)橛斜惹蠼猞粮鼮橹匾氖虑椤，F(xiàn)在既然能用α來表示w和b了，自然也可以用α來表示分類決策函數(shù)。

圖中的b是由y=wTx+b得到的，就這樣我們得到了關(guān)于α的分類決策函數(shù)，其中x是輸入測試的樣本。

接下來我們來考慮另一個(gè)非常重要的問題，如果樣本分布邊界并不是很明顯怎么辦? 打戰(zhàn)的時(shí)候，有些士兵還沒來得及返回自己的戰(zhàn)壕，雙方就歇下了，那他只能就近找個(gè)地方隱蔽自己，可能這個(gè)地方還在敵人的腹地中，那修戰(zhàn)壕肯定不可能把這個(gè)戰(zhàn)友考慮進(jìn)去，不然就修到敵人的地盤去了。所以第一種劃分的方法是不理智的，這個(gè)時(shí)候劃分邊界就要選擇性忽視偏差較大的樣本點(diǎn)，可能那個(gè)樣本是收集數(shù)據(jù)的噪點(diǎn)，也可以從統(tǒng)計(jì)學(xué)來說，它距離均值太遠(yuǎn)，沒啥參考意義。問題又來了，怎么忽略？在機(jī)器學(xué)習(xí)中，我們稱其軟間隔最大化，說得俗點(diǎn)，我們允許這樣偏離較大的樣本出現(xiàn)，并且在目標(biāo)函數(shù)中增加一個(gè)懲罰項(xiàng)降低這些樣本的權(quán)重(這是土理解，反正差不多這個(gè)意思)。

于是我們的目標(biāo)函數(shù)和約束條件變成了這樣

有人說了，這個(gè)公式看不懂，C和x是什么？這里的C稱為懲罰系數(shù)，一般由具體的問題所決定，C大的話對目標(biāo)函數(shù)影響越大，懲罰效果就越強(qiáng)，雙方的戰(zhàn)壕就越近，x是什么？看圖

對于點(diǎn)A和點(diǎn)B來說，假如點(diǎn)B代入公式y(tǒng)=wTx+b，則是wTx+b=1。而點(diǎn)A代入公式則是wTx+b+xi=1，即wTx+b=1-xi，所以約束條件變成了yi(wxi+b)>=1-x。其實(shí)引入這個(gè)懲罰項(xiàng)主要有兩個(gè)目的，第一使1/2*||w||2盡量小，第二使偏離點(diǎn)(誤分類點(diǎn))的個(gè)數(shù)盡量小(這個(gè)就是拉近雙方戰(zhàn)壕的距離，讓那些偏離點(diǎn)看起來不那么偏離)，而C是調(diào)和二者的關(guān)系的作用。

現(xiàn)在有了新的目標(biāo)函數(shù)，那就從新開始求解。這里省略了與上面類似的求解過程，直接看最后的目標(biāo)函數(shù)和約束條件。

我們發(fā)現(xiàn)與上面的約束條件很相似，但是多了一個(gè)條件：0<=ai<=C。

最重要的時(shí)候來了，要開始求解α，真相的大門馬上就要打開了。這里我們用的是序列最小最優(yōu)化算法，簡稱SMO。

先看上圖中的約束條件，發(fā)現(xiàn)每一個(gè)aiyi都是互相關(guān)聯(lián)的，它們所有的和等于0。這里作一個(gè)假設(shè)，假設(shè)這里的α是類似于w的系數(shù)(事實(shí)上α是與w有直接關(guān)系的，這個(gè)假設(shè)還是靠譜的)，那好，我們就當(dāng)它是系數(shù)好了。眼前有無數(shù)個(gè)α等著我們?nèi)ソ獬鰜恚趺唇?？這么多的α，那就一個(gè)一個(gè)解，直到滿足KKT條件為止(KKT條件后面會說明)。由于這些系數(shù)都是互相關(guān)聯(lián)的，不是相對獨(dú)立的，于是有了這么一個(gè)關(guān)系。

用其它的α可以表示出α1，如果想凍住其他α而只對α1進(jìn)行求導(dǎo)取極值是不現(xiàn)實(shí)的，這就變成了牽一發(fā)而動全身了，而我們并不想動全身，只想一個(gè)一個(gè)去求解，有沒有辦法？肯定有，再看一眼上圖的公式，再給它變化一下

這時(shí)可以直接凍住其他α了，由α1和α2保持平衡，可是這時(shí)候有兩個(gè)變量，求解又不那么樂觀了，聰明的你已經(jīng)有新想法了，用α2和其他α表示α1直接代入目標(biāo)方程，再求導(dǎo)求解，α2的值就這么的出來了，是不是很簡單，再把α2的值代入上面的公式，α1的值也出來，這一對的值就求解完畢了，這就是大名鼎鼎的SMO算法，由偉大的platt于1988年提出。

現(xiàn)在我們來解決一下KKT的問題，KKT是拉格朗日乘子法衍生的條件，簡單說一般情況下涉及到對偶問題，或者相關(guān)的轉(zhuǎn)化問題，會有一個(gè)KKT條件作為支撐約束，具體的推導(dǎo)過程可以參考鏈接1。KKT條件如下

解釋一下上圖的條件，當(dāng)α=0時(shí)，可見這個(gè)xi對邊界時(shí)沒有意義的，它一直處于遠(yuǎn)離邊界的自己的地盤中。當(dāng)0<α<C的時(shí)候，則ξi=0，這個(gè)時(shí)候xi作為支持向量(剛好在戰(zhàn)壕線上的點(diǎn))在邊界(戰(zhàn)壕)上。當(dāng)α=C時(shí)，0<ξ<1，xi在邊界(戰(zhàn)壕)和分隔平面(分割線)的中間，ξ=1時(shí)，xi在分隔平面上，ξ>1時(shí)，xi在分隔平面外(過了分割線，已經(jīng)是對方的地盤了)，

解題思路有了，接下來，就要開始動手了。因?yàn)棣?和α2并行作戰(zhàn)，所以它們的取值范圍不僅僅是[0,C]這么簡單了。這里可以寫個(gè)目標(biāo)函數(shù)明確下求值目的。

圖中的Kij看作是(xi,xj)?，F(xiàn)在看約束條件，α1和α2有著很明顯的比例關(guān)系，當(dāng)y1不等于y2的時(shí)候，α1和α2成正比。當(dāng)y1等于y2的時(shí)候，α1和α2成反比。α1和α2各自的取值范圍都是[0,C]，加上這個(gè)條件后，取值范圍就開始變化了。是怎么變化呢？

首先，要明白一件事，α2必然要滿足[L,H]的約束條件，L和H的具體值是什么？

看上左圖，當(dāng)y1不等于y2的時(shí)候，這條直線的左交縱坐標(biāo)是α2-α1，右交縱坐標(biāo)是α2-α1+C，而α的最大值是C，所以這里的α2取值應(yīng)該是[α2-α1，C],我們找一個(gè)規(guī)律滿足圖中直線的取值，它就是這樣

同理，當(dāng)y1等于y2的時(shí)候，L和H的取值規(guī)律是這樣的

取值范圍出來了，輔助條件一個(gè)一個(gè)清晰明了，接下來最重要的一步大棋馬上就要開盤。找α1和α2開戰(zhàn)，準(zhǔn)確地說，是找αi和αj，因?yàn)槭峭ㄟ^無數(shù)對的

αi和αj迭代計(jì)算才能最終出來我們想要的結(jié)果。

αi怎么找？在這里我們用愚笨一點(diǎn)的方法，因?yàn)閮?yōu)化重點(diǎn)在αj上。首先全局遍歷αi，在αi的基礎(chǔ)上用最長步長法找αj，什么是最長步長法？舉個(gè)栗子，我們從大城市出發(fā)，到達(dá)一個(gè)小鄉(xiāng)村，沒有直達(dá)的方法，怎么選擇交通工具？你可以做大客車轉(zhuǎn)大客車轉(zhuǎn)中巴車轉(zhuǎn)小巴車轉(zhuǎn)牛車，你也可以坐火車轉(zhuǎn) 中巴車轉(zhuǎn)牛車，你也可以做飛機(jī)轉(zhuǎn)中巴車轉(zhuǎn)牛車，在不在乎錢的情況下，哪個(gè)最快？毫無疑問啊，坐飛機(jī)效果太明顯，加上轉(zhuǎn)車，可能全部加起來也就幾個(gè)小時(shí)，而國內(nèi)長途火車和大客車都是起步價(jià)十幾個(gè)小時(shí)的，這差了一個(gè)數(shù)量級，結(jié)論是坐飛機(jī)最快。找αj也一樣，我們要找最明顯的那個(gè)αj，一旦 修正了αj，就會讓結(jié)果看上去改變非常大，這個(gè)落實(shí)到具體問題上，就是錯誤率和αi差的最遠(yuǎn)的那個(gè)。這里要說明下一個(gè)小細(xì)節(jié)，顯然找αj的過程涉及到了對比的過程，我們要建立一個(gè)全局變量用于儲存這個(gè)錯誤率的差值，這樣才能找出最大的來尋找αj。

條件全部都找齊了，接下來就是套用公式求值了。

首先要知道錯誤率怎么求，簡單點(diǎn)就是當(dāng)前樣本的決策分類值與它的標(biāo)簽值的差(這里是試驗(yàn)集，所以是有標(biāo)簽的)

接下來求i與j的相似系數(shù)η

括號內(nèi)是矩陣內(nèi)積的運(yùn)算，這里可以百度矩陣內(nèi)積。求這個(gè)相似系數(shù)是為接下來的求αj的公式做鋪墊。

αj由目標(biāo)函數(shù)對αi求導(dǎo)解出，然后用αj求αi。

我們看KKT條件，當(dāng)0<α<C，也就是當(dāng)樣本在邊界上的時(shí)候，yg(x)=1,這個(gè)時(shí)候可以直接求解b的值，也就是b1和b2。假如樣本不再邊界上，就取平均值

整體思路就到這里結(jié)束了，這是一個(gè)超級入門超級入門超級入門的教程，沒有任何正統(tǒng)借鑒意義，給看不懂其他參考文獻(xiàn)的童鞋一個(gè)簡單粗暴的解釋，如果想要深入地研究學(xué)習(xí)SVM，還需要投入更多的時(shí)間去積累和領(lǐng)悟，網(wǎng)上有很多大神的博客都寫得很好這里就不列舉了，相信讀到這里你差不多花了一個(gè)小時(shí)，SVM是一個(gè)很有意思的算法，如果你仍保持很大的學(xué)習(xí)興趣，那就繼續(xù)耕耘吧，到這里才走了僅僅一小步哦！