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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

把它轉(zhuǎn)化一下

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

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

現(xiàn)在得到了一個(gè)新函數(shù)，是不是有些陌生，其實(shí)這些都是w和b的化身而已，α現(xiàn)在取代了w和b的位置，這樣看起來(lái)求解確實(shí)是方便了許多。你們有沒(méi)有發(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)，通過(guò)求α的值來(lái)求w和b的值。

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

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

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

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

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

對(duì)于點(diǎn)A和點(diǎn)B來(lái)說(shuō)，假如點(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)(誤分類(lèi)點(diǎn))的個(gè)數(shù)盡量小(這個(gè)就是拉近雙方戰(zhàn)壕的距離，讓那些偏離點(diǎn)看起來(lái)不那么偏離)，而C是調(diào)和二者的關(guān)系的作用。

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

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

最重要的時(shí)候來(lái)了，要開(kāi)始求解α，真相的大門(mén)馬上就要打開(kāi)了。這里我們用的是序列最小最優(yōu)化算法，簡(jiǎn)稱(chēng)SMO。

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

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

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

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

解釋一下上圖的條件，當(dāng)α=0時(shí)，可見(jiàn)這個(gè)xi對(duì)邊界時(shí)沒(méi)有意義的，它一直處于遠(yuǎn)離邊界的自己的地盤(pá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在分隔平面外(過(guò)了分割線，已經(jīng)是對(duì)方的地盤(pán)了)，

解題思路有了，接下來(lái)，就要開(kāi)始動(dòng)手了。因?yàn)棣?和α2并行作戰(zhàn)，所以它們的取值范圍不僅僅是[0,C]這么簡(jiǎn)單了。這里可以寫(xiě)個(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è)條件后，取值范圍就開(kāi)始變化了。是怎么變化呢？

首先，要明白一件事，α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ī)律是這樣的

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

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

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

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

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

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

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

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

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

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