本文是“支持向量機(jī)系列”的第一篇，參見(jiàn)本系列的其他文章。

支持向量機(jī)即 Support Vector Machine，簡(jiǎn)稱(chēng) SVM 。我最開(kāi)始聽(tīng)說(shuō)這頭機(jī)器的名號(hào)的時(shí)候，一種神秘感就油然而生，似乎把 Support 這么一個(gè)具體的動(dòng)作和 Vector 這么一個(gè)抽象的概念拼到一起，然后再做成一個(gè) Machine ，一聽(tīng)就很玄了！

不過(guò)后來(lái)我才知道，原來(lái) SVM 它并不是一頭機(jī)器，而是一種算法，或者，確切地說(shuō)，是一類(lèi)算法，當(dāng)然，這樣摳字眼的話(huà)就沒(méi)完沒(méi)了了，比如，我說(shuō) SVM 實(shí)際上是一個(gè)分類(lèi)器 (Classifier) ，但是其實(shí)也是有用 SVM 來(lái)做回歸 (Regression) 的。所以，這種字眼就先不管了，還是從分類(lèi)器說(shuō)起吧。

SVM 一直被認(rèn)為是效果最好的現(xiàn)成可用的分類(lèi)算法之一（其實(shí)有很多人都相信，“之一”是可以去掉的）。這里“現(xiàn)成可用”其實(shí)是很重要的，因?yàn)橐恢币詠?lái)學(xué)術(shù)界和工業(yè)界甚至只是學(xué)術(shù)界里做理論的和做應(yīng)用的之間，都有一種“鴻溝”，有些很 fancy 或者很復(fù)雜的算法，在抽象出來(lái)的模型里很完美，然而在實(shí)際問(wèn)題上卻顯得很脆弱，效果很差甚至完全 fail 。而 SVM 則正好是一個(gè)特例——在兩邊都混得開(kāi)。

好了，由于 SVM 的故事本身就很長(zhǎng)，所以廢話(huà)就先只說(shuō)這么多了，直接入題吧。當(dāng)然，說(shuō)是入貼，但是也不能一上來(lái)就是 SVM ，而是必須要從線(xiàn)性分類(lèi)器開(kāi)始講。這里我們考慮的是一個(gè)兩類(lèi)的分類(lèi)問(wèn)題，數(shù)據(jù)點(diǎn)用 x 來(lái)表示，這是一個(gè) n 維向量，而類(lèi)別用 y 來(lái)表示，可以取 1 或者 -1 ，分別代表兩個(gè)不同的類(lèi)（有些地方會(huì)選 0 和 1 ，當(dāng)然其實(shí)分類(lèi)問(wèn)題選什么都無(wú)所謂，只要是兩個(gè)不同的數(shù)字即可，不過(guò)這里選擇 +1 和 -1 是為了方便 SVM 的推導(dǎo)，后面就會(huì)明了了）。一個(gè)線(xiàn)性分類(lèi)器就是要在 n 維的數(shù)據(jù)空間中找到一個(gè)超平面，其方程可以表示為

wTx+b=0

一個(gè)超平面，在二維空間中的例子就是一條直線(xiàn)。我們希望的是，通過(guò)這個(gè)超平面可以把兩類(lèi)數(shù)據(jù)分隔開(kāi)來(lái)，比如，在超平面一邊的數(shù)據(jù)點(diǎn)所對(duì)應(yīng)的 y 全是 -1 ，而在另一邊全是 1 。具體來(lái)說(shuō)，我們令 f(x)=wTx+b ，顯然，如果 f(x)=0 ，那么 x 是位于超平面上的點(diǎn)。我們不妨要求對(duì)于所有滿(mǎn)足 f(x)<0 的點(diǎn)，其對(duì)應(yīng)的 y 等于 -1 ，而 f(x)>0 則對(duì)應(yīng) y=1 的數(shù)據(jù)點(diǎn)。當(dāng)然，有些時(shí)候（或者說(shuō)大部分時(shí)候）數(shù)據(jù)并不是線(xiàn)性可分的，這個(gè)時(shí)候滿(mǎn)足這樣條件的超平面就根本不存在，不過(guò)關(guān)于如何處理這樣的問(wèn)題我們后面會(huì)講，這里先從最簡(jiǎn)單的情形開(kāi)始推導(dǎo)，就假設(shè)數(shù)據(jù)都是線(xiàn)性可分的，亦即這樣的超平面是存在的。

如圖所示，兩種顏色的點(diǎn)分別代表兩個(gè)類(lèi)別，紅顏色的線(xiàn)表示一個(gè)可行的超平面。在進(jìn)行分類(lèi)的時(shí)候，我們將數(shù)據(jù)點(diǎn) x 代入 f(x) 中，如果得到的結(jié)果小于 0 ，則賦予其類(lèi)別 -1 ，如果大于 0 則賦予類(lèi)別 1 。如果 f(x)=0 ，則很難辦了，分到哪一類(lèi)都不是。事實(shí)上，對(duì)于 f(x) 的絕對(duì)值很小的情況，我們都很難處理，因?yàn)榧?xì)微的變動(dòng)（比如超平面稍微轉(zhuǎn)一個(gè)小角度）就有可能導(dǎo)致結(jié)果類(lèi)別的改變。理想情況下，我們希望 f(x) 的值都是很大的正數(shù)或者很小的負(fù)數(shù)，這樣我們就能更加確信它是屬于其中某一類(lèi)別的。

從幾何直觀上來(lái)說(shuō)，由于超平面是用于分隔兩類(lèi)數(shù)據(jù)的，越接近超平面的點(diǎn)越“難”分隔，因?yàn)槿绻矫嫔晕⑥D(zhuǎn)動(dòng)一下，它們就有可能跑到另一邊去。反之，如果是距離超平面很遠(yuǎn)的點(diǎn)，例如圖中的右上角或者左下角的點(diǎn)，則很容易分辯出其類(lèi)別。

實(shí)際上這兩個(gè) Criteria 是互通的，我們定義 functional margin 為 γ?=y(wTx+b)=yf(x) ，注意前面乘上類(lèi)別 y 之后可以保證這個(gè) margin 的非負(fù)性（因?yàn)?f(x)<0 對(duì)應(yīng)于 y=?1 的那些點(diǎn)），而點(diǎn)到超平面的距離定義為 geometrical margin 。不妨來(lái)看看二者之間的關(guān)系。如圖所示，對(duì)于一個(gè)點(diǎn) x ，令其垂直投影到超平面上的對(duì)應(yīng)的為 x0 ，由于 w 是垂直于超平面的一個(gè)向量（請(qǐng)自行驗(yàn)證），我們有

x=x0+γww

又由于 x0 是超平面上的點(diǎn)，滿(mǎn)足 f(x0)=0 ，代入超平面的方程即可算出

γ=wTx+bw=f(x)w

不過(guò)，這里的 γ 是帶符號(hào)的，我們需要的只是它的絕對(duì)值，因此類(lèi)似地，也乘上對(duì)應(yīng)的類(lèi)別 y 即可，因此實(shí)際上我們定義 geometrical margin 為：

γ?=yγ=γ?w

顯然，functional margin 和 geometrical margin 相差一個(gè) w 的縮放因子。按照我們前面的分析，對(duì)一個(gè)數(shù)據(jù)點(diǎn)進(jìn)行分類(lèi)，當(dāng)它的 margin 越大的時(shí)候，分類(lèi)的 confidence 越大。對(duì)于一個(gè)包含 n 個(gè)點(diǎn)的數(shù)據(jù)集，我們可以很自然地定義它的 margin 為所有這 n 個(gè)點(diǎn)的 margin 值中最小的那個(gè)。于是，為了使得分類(lèi)的 confidence 高，我們希望所選擇的 hyper plane 能夠最大化這個(gè) margin 值。

不過(guò)這里我們有兩個(gè) margin 可以選，不過(guò) functional margin 明顯是不太適合用來(lái)最大化的一個(gè)量，因?yàn)樵?hyper plane 固定以后，我們可以等比例地縮放 w 的長(zhǎng)度和 b 的值，這樣可以使得 f(x)=wTx+b 的值任意大，亦即 functional margin γ? 可以在 hyper plane 保持不變的情況下被取得任意大，而 geometrical margin 則沒(méi)有這個(gè)問(wèn)題，因?yàn)槌狭?w 這個(gè)分母，所以縮放 w 和 b 的時(shí)候 γ? 的值是不會(huì)改變的，它只隨著 hyper plane 的變動(dòng)而變動(dòng)，因此，這是更加合適的一個(gè) margin 。這樣一來(lái)，我們的 maximum margin classifier 的目標(biāo)函數(shù)即定義為

maxγ?

當(dāng)然，還需要滿(mǎn)足一些條件，根據(jù) margin 的定義，我們有

yi(wTxi+b)=γ?iγ?,i=1,…,n

其中 γ?=γ?w ，根據(jù)我們剛才的討論，即使在超平面固定的情況下，γ? 的值也可以隨著 w 的變化而變化。由于我們的目標(biāo)就是要確定超平面，因此可以把這個(gè)無(wú)關(guān)的變量固定下來(lái)，固定的方式有兩種：一是固定 w ，當(dāng)我們找到最優(yōu)的 γ? 時(shí) γ? 也就可以隨之而固定；二是反過(guò)來(lái)固定 γ? ，此時(shí) w 也可以根據(jù)最優(yōu)的 γ? 得到。處于方便推導(dǎo)和優(yōu)化的目的，我們選擇第二種，令 γ?=1 ，則我們的目標(biāo)函數(shù)化為：

max1w,s.t.,yi(wTxi+b)1,i=1,…,n

通過(guò)求解這個(gè)問(wèn)題，我們就可以找到一個(gè) margin 最大的 classifier ，如下圖所示，中間的紅色線(xiàn)條是 Optimal Hyper Plane ，另外兩條線(xiàn)到紅線(xiàn)的距離都是等于 γ? 的：

到此為止，算是完成了 Maximum Margin Classifier 的介紹，通過(guò)最大化 margin ，我們使得該分類(lèi)器對(duì)數(shù)據(jù)進(jìn)行分類(lèi)時(shí)具有了最大的 confidence （實(shí)際上，根據(jù)我們說(shuō)給的一個(gè)數(shù)據(jù)集的 margin 的定義，準(zhǔn)確的說(shuō)，應(yīng)該是“對(duì)最不 confidence 的數(shù)據(jù)具有了最大的 confidence”——雖然有點(diǎn)拗口）。不過(guò)，到現(xiàn)在似乎還沒(méi)有一點(diǎn)點(diǎn) Support Vector Machine 的影子。很遺憾的是，這個(gè)要等到下一次再說(shuō)了，不過(guò)可以先小小地劇透一下，如上圖所示，我們可以看到 hyper plane 兩邊的那個(gè) gap 分別對(duì)應(yīng)的兩條平行的線(xiàn)（在高維空間中也應(yīng)該是兩個(gè) hyper plane）上有一些點(diǎn)，顯然兩個(gè) hyper plane 上都會(huì)有點(diǎn)存在，否則我們就可以進(jìn)一步擴(kuò)大 gap ，也就是增大 γ? 的值了。這些點(diǎn)呢，就叫做 support vector ，嗯，先說(shuō)這么多了。

ps: 本文開(kāi)頭那張照片來(lái)源于這里。Allaboutinquiry 同學(xué)留言揭露典故真相啦：

關(guān)于這個(gè)同學(xué)舉牌子的典故我知道，我也是CMU的。這是在2009年在Pittsburgh舉行的G20峰會(huì)現(xiàn)場(chǎng)外面。很多反對(duì)G20的，支持G20的都來(lái)湊熱鬧。我們這位同學(xué)也來(lái)了，魚(yú)目混珠的高舉Support Vector Machine的牌子。很多老美就暈了，你說(shuō)你支持加強(qiáng)控制二氧化碳排放我懂，你支持的的這個(gè)Vector Machine是個(gè)什么東西??？然后這個(gè)同學(xué)搞笑的目的就達(dá)到了。