1、零基礎(chǔ)學(xué) SVM Support Vector Machine 系列之一本文原作者耳東陳， 本文原載于作者的知乎文章。 AI 研習(xí)社已獲得轉(zhuǎn)載授權(quán)。如果你是一名模式識(shí)別專業(yè)的研究生，又或者你是機(jī)器學(xué)習(xí)愛(ài)好者， SVM 是一個(gè)你避不開(kāi)的問(wèn)題。如果你只是有一堆數(shù)據(jù)需要SVM 幫你處理一下，那么無(wú)論是 Matlab 的 SVM 工具箱， LIBSVM 還是 python 框架下的SciKit Learn 都可以提供方便快捷的解決方案。但如果你要追求的不僅僅是會(huì)用，還希望挑戰(zhàn)一下“理解”這個(gè)層次，那么你就需要面對(duì)一大堆你可能從來(lái)沒(méi)聽(tīng)過(guò)的名詞，比如：非線性約束條件下的最優(yōu)化、 KKT 條件、拉格朗日對(duì)偶

2、、最大間隔、最優(yōu)下界、核函數(shù)等等。這些名詞往往會(huì)跟隨一大堆天書一般的公式。如果你稍微有一點(diǎn)數(shù)學(xué)基礎(chǔ)，那么單個(gè)公式你可能看得明白，但是怎么從一個(gè)公式跳到另一個(gè)公式就讓人十分費(fèi)解了，而最讓人糊涂的其實(shí)并不是公式推導(dǎo)，而是如果把這些公式和你腦子里空間構(gòu)想聯(lián)系起來(lái)。我本人就是上述問(wèn)題的受害者之一。我翻閱了很多關(guān)于 SVM 的書籍和資料，但沒(méi)有找到一份材料能夠在公式推導(dǎo)、理論介紹，系統(tǒng)分析、變量說(shuō)明、代數(shù)和幾何意義的解釋等方面完整地對(duì) SVM 加以分析和說(shuō)明的。換言之，對(duì)于普通的一年級(jí)非數(shù)學(xué)專業(yè)的研究生而言， 要想看懂 SVM 需要搜集很多資料，然后對(duì)照閱讀和深入思考，才可能比較透徹地理解 SVM 算法

3、。由于我本人也在東北大學(xué)教授面向一年級(jí)碩士研究生的模式識(shí)別技術(shù)與應(yīng)用課程，因此希望能總結(jié)出一份相對(duì)完整、簡(jiǎn)單和透徹的關(guān)于 SVM 算法的介紹文字，以便學(xué)生能夠快速準(zhǔn)確地理解 SVM 算法。以下我會(huì)分為四個(gè)步驟對(duì)最基礎(chǔ)的線性SVM 問(wèn)題加以介紹， 分別是 1 ) 問(wèn)題原型， 2 )數(shù)學(xué)模型，3 )最優(yōu)化求解，4 )幾何解釋。我盡可能用最簡(jiǎn)單的語(yǔ)言和最基本的數(shù)學(xué)知識(shí)對(duì)上述問(wèn)題進(jìn)行介紹，希望能對(duì)困惑于 SVM 算法的學(xué)生有所幫助。 SVM 算法要解決什么問(wèn)題 SVM 的全稱是 Support Vector Machine ，即支持向量機(jī)，主要用于解決模式識(shí)別領(lǐng)域中的數(shù)據(jù)分類問(wèn)題，屬于有監(jiān)督學(xué)習(xí)算法的

4、一種。 SVM 要解決的問(wèn)題可以用一個(gè)經(jīng)典的二分類問(wèn)題加以描述。如圖 1 所示，紅色和藍(lán)色的二維數(shù)據(jù)點(diǎn)顯然是可以被一條直線分開(kāi)的，在模式識(shí)別領(lǐng)域稱為線性可分問(wèn)題。然而將兩類數(shù)據(jù)點(diǎn)分開(kāi)的直線顯然不止一條。圖1(b)和(c)分別給由了 A、B兩種不同的分類方案，其中黑色實(shí)線為分界線，術(shù)語(yǔ)稱為“決策面”。每個(gè)決策面對(duì)應(yīng)了一個(gè)線性分類器。雖然在目前的數(shù)據(jù)上看，這兩個(gè)分類器的分類結(jié)果是一樣的，但如果考慮潛在的其他數(shù)據(jù)，則兩者的分類性能是有差別的。圖 1 二分類問(wèn)題描述SVM 算法認(rèn)為圖1 中的分類器A 在性能上優(yōu)于分類器B ，其依據(jù)是A 的分類間隔比 B 要大。 這里涉及到第一個(gè)SVM 獨(dú)有的概念“分類

5、間隔”。 在保證決策面方向不變且不會(huì)出現(xiàn)錯(cuò)分樣本的情況下移動(dòng)決策面，會(huì)在原來(lái)的決策面兩側(cè)找到兩個(gè)極限位置（越過(guò)該位置就會(huì)產(chǎn)生錯(cuò)分現(xiàn)象） ，如虛線所示。虛線的位置由決策面的方向和距離原決策面最近的幾個(gè)樣本的位置決定。而這兩條平行虛線正中間的分界線就是在保持當(dāng)前決策面方向不變的前提下的最優(yōu)決策面。兩條虛線之間的垂直距離就是這個(gè)最優(yōu)決策面對(duì)應(yīng)的分類間隔。顯然每一個(gè)可能把數(shù)據(jù)集正確分開(kāi)的方向都有一個(gè)最優(yōu)決策面（有些方向無(wú)論如何移動(dòng)決策面的位置也不可能將兩類樣本完全分開(kāi)） ，而不同方向的最優(yōu)決策面的分類間隔通常是不同的， 那個(gè)具有“最大間隔”的決策面就是 SVM 要尋找的最優(yōu)解。而這個(gè)真正的最優(yōu)解對(duì)應(yīng)的

6、兩側(cè)虛線所穿過(guò)的樣本點(diǎn)，就是SVM 中的支持樣本點(diǎn)，稱為“支持向量”。對(duì)于圖 1 中的數(shù)據(jù)， A 決策面就是 SVM 尋找的最優(yōu)解，而相應(yīng)的三個(gè)位于虛線上的樣本點(diǎn)在坐標(biāo)系中對(duì)應(yīng)的向量就叫做支持向量。從表面上看，我們優(yōu)化的對(duì)象似乎是這個(gè)決策面的方向和位置。但實(shí)際上最優(yōu)決策面的方向和位置完全取決于選擇哪些樣本作為支持向量。而在經(jīng)過(guò)漫長(zhǎng)的公式推導(dǎo)后，你最終會(huì)發(fā)現(xiàn)，其實(shí)與線性決策面的方向和位置直接相關(guān)的參數(shù)都會(huì)被約減掉，最終結(jié)果只取決于樣本點(diǎn)的選擇結(jié)果。 到這里， 我們明確了 SVM算法要解決的是一個(gè)最優(yōu)分類器的設(shè)計(jì)問(wèn)題。既然叫作最優(yōu)分類器，其本質(zhì)必然是個(gè)最優(yōu)化問(wèn)題。所以，接下來(lái)我們要討論的就是如何把

7、SVM 變成用數(shù)學(xué)語(yǔ)言描述的最優(yōu)化問(wèn)題模型，這就是我們?cè)诘诙糠忠v的“線性 SVM 算法的數(shù)學(xué)建模”。* 關(guān)于“決策面”，為什么叫決策面， 而不是決策線？好吧，在圖 1 里，樣本是二維空間中的點(diǎn)，也就是數(shù)據(jù)的維度是 2 ，因此 1 維的直線可以分開(kāi)它們。但是在更加一般的情況下，樣本點(diǎn)的維度是n ，則將它們分開(kāi)的決策面的維度就是 n-1 維的超平面（可以想象一下 3 維空間中的點(diǎn)集被平面分開(kāi)） ，所以叫“決策面”更加具有普適性，或者你可以認(rèn)為直線是決策面的一個(gè)特例。 線性 SVM 算法的數(shù)學(xué)建模一個(gè)最優(yōu)化問(wèn)題通常有兩個(gè)最基本的因素： 1 ）目標(biāo)函數(shù)，也就是你希望什么東西的什么指標(biāo)達(dá)到最好； 2

8、 ）優(yōu)化對(duì)象，你期望通過(guò)改變哪些因素來(lái)使你的目標(biāo)函數(shù)達(dá)到最優(yōu)。在線性SVM 算法中，目標(biāo)函數(shù)顯然就是那個(gè)“分類間隔”，而優(yōu)化對(duì)象則是決策面。所以要對(duì)SVM 問(wèn)題進(jìn)行數(shù)學(xué)建模，首先要對(duì)上述兩個(gè)對(duì)象 （“分類間隔”和“決策面”） 進(jìn)行數(shù)學(xué)描述。 按照一般的思維習(xí)慣， 我們先描述決策面。 2.1 決策面方程 （請(qǐng)注意，以下的描述對(duì)于線性代數(shù)及格的同學(xué)可能顯得比較啰嗦，但請(qǐng)你們照顧一下用高數(shù)課治療失眠的同學(xué)們。 ）請(qǐng)你暫時(shí)不要糾結(jié)于 n 維空間中的 n-1 維超平面這種超出正常人想象力的情景。我們就老老實(shí)實(shí)地看看二維空間中的一根直線，我們從初中就開(kāi)始學(xué)習(xí)的直線方程形式很簡(jiǎn)單。現(xiàn)在我們做個(gè)小小的改變，讓

9、原來(lái)的x軸變成x?軸，y變成x?軸,于是公式 （2.1） 中的直線方程會(huì)變成下面的樣子公式 （2.3） 的向量形式可以寫成考慮到我們?cè)诘仁絻蛇叧松先魏螌?shí)數(shù)都不會(huì)改變等式的成立，所以我們可以寫出一個(gè)更加一般的向量表達(dá)形式：看到變量3、X略顯粗壯的身體了嗎？他們是黑體，表示變量是個(gè)向量， ， 。一般我們提到向量的時(shí)候，都默認(rèn)他們是個(gè)列向量，所以我在方括號(hào)后面加上了上標(biāo) T ，表示轉(zhuǎn)置(我知道我真的很啰嗦，但是關(guān)于“零基礎(chǔ)”三個(gè)字，我是認(rèn)真的。 ) ，它可以幫忙把行向量豎過(guò)來(lái)變成列向量，所以在公式(2.5)里面3后面的轉(zhuǎn)置符號(hào) T,會(huì)把列向量又轉(zhuǎn)回到行向量。這樣一個(gè)行向量和一個(gè)列向量 X 就可快快樂(lè)

10、樂(lè)的按照矩陣乘法的方式結(jié)合，變成一個(gè)標(biāo)量，然后好跟后面的標(biāo)量y相加后相互抵消變成 0。就著公式(2.5),我們?cè)偕陨試L試深入一點(diǎn)。那就是探尋一下向量點(diǎn)積，和標(biāo)量 y的幾何意義是什么。讓我們回到公式 (2.4) ，對(duì)比公式 (2.5) ，可以發(fā)現(xiàn)此時(shí)的。然后再去看公式 (2.2) ，還記得那條我們熟悉的直線方程中的 a 的幾何意義嗎？對(duì)的，那是直線的斜率。如果我們構(gòu)造一個(gè)向量，它應(yīng)該跟我們的公式 (2.2)描述的直線平行。然后我們求一下兩個(gè)向量的點(diǎn)積，你會(huì)驚喜地發(fā)現(xiàn)結(jié)果是 0 。我們管這種現(xiàn)象叫作“兩個(gè)向量相互正交”。通俗點(diǎn)說(shuō)就是兩個(gè)向量相互垂直。當(dāng)然，你也可以在草稿紙上自己畫出這兩個(gè)向量，比如

11、讓，你會(huì)發(fā)現(xiàn)在第一象限，與橫軸夾角為 60 °，而在第四象限與橫軸夾角為30 °，所以很顯然他們兩者的夾角為 90 °。你現(xiàn)在是不是已經(jīng)忘了我們討論正交或者垂直的目的是什么了？那么請(qǐng)把你的思維從坐標(biāo)系上抽出來(lái)，回到?jīng)Q策面方程上來(lái)。我是想告訴你向量跟直線是相互垂直的，也就是說(shuō)控制了直線的方向。另外，還記得小時(shí)候我們學(xué)過(guò)的那個(gè)叫做截距的名詞嗎？對(duì)了，Y就是截距，它控制了直線的位置。然后，在本小節(jié)的末尾，我冒昧地提示一下，在n 維空間中 n-1 維的超平面的方程形式也是公式(2.5)的樣子，只不過(guò)向量a、x的維度從原來(lái)的2維變成了n 維。如果你還是想不出來(lái)超平面的樣子，

12、也很正常。那么就請(qǐng)你始終記住平面上它們的樣子也足夠了。到這里，我們花了很多篇幅描述一個(gè)很簡(jiǎn)單的超平面方程(其實(shí)只是個(gè)直線方程)，這里真正有價(jià)值的是這個(gè)控制方向的參數(shù)3。接下來(lái)，你會(huì)有很長(zhǎng)一段時(shí)間要思考它到底是個(gè)什么東西，對(duì)于 SVM 產(chǎn)生了怎樣的影響。 2.2 分類“間隔”的計(jì)算模型我們?cè)诘谝徽吕锝榻B過(guò)分類間隔的定義及其直觀的幾何意義。間隔的大小實(shí)際上就是支持向量對(duì)應(yīng)的樣本點(diǎn)到?jīng)Q策面的距離的二倍， 如圖 2 所示。 圖 2 分類間隔計(jì)算所以分類間隔計(jì)算似乎相當(dāng)簡(jiǎn)單，無(wú)非就是點(diǎn)到直線的距離公式。如果你想要回憶高中老師在黑板上推導(dǎo)的過(guò)程，可以隨便在百度文庫(kù)里搜索關(guān)鍵詞“點(diǎn)到直線距離推導(dǎo)公式”，你會(huì)

13、得到至少 6 、 7種推導(dǎo)方法。但這里，請(qǐng)?jiān)徫医o出一個(gè)簡(jiǎn)單的公式如下：這里| 3|是向?qū)У哪＃硎驹诳臻g中向量的長(zhǎng)度，就是支持向量樣本點(diǎn)的坐標(biāo)。3, Y就是決策面方程的參數(shù)。而追求 W 的最大化也就是尋找d 的最大化。看起來(lái)我們已經(jīng)找到了目標(biāo)函數(shù)的數(shù)學(xué)形式。但問(wèn)題當(dāng)然不會(huì)這么簡(jiǎn)單，我們還需要面對(duì)一連串令人頭疼的麻煩。 2.3 約束條件接著2.2節(jié)的結(jié)尾，我們討論一下究竟還有哪些麻煩沒(méi)有解決： 1. 并不是所有的方向都存在能夠?qū)崿F(xiàn)100% 正確分類的決策面，我們?nèi)绾闻袛嘁粭l直線是否能夠?qū)⑺械臉颖军c(diǎn)都正確分類？ 2. 即便找到了正確的決策面方向，還要注意決策面的位置應(yīng)該在間隔區(qū)域的中軸線上，所

14、以用來(lái)確定決策面位置的截距Y也不能自由的優(yōu)化，而是受到?jīng)Q策面方向和樣本點(diǎn)分布的約束。 3.即便取到了合適的方向和截距，公式 (2.6) 里面的 x 不是隨隨便便的一個(gè)樣本點(diǎn)，而是支持向量對(duì)應(yīng)的樣本點(diǎn)。對(duì)于一個(gè)給定的決策面，我們?cè)撊绾握业綄?duì)應(yīng)的支持向量？以上三條麻煩的本質(zhì)是“約束條件”，也就是說(shuō)我們要優(yōu)化的變量的取值范圍受到了限制和約束。事實(shí)上約束條件一直是最優(yōu)化問(wèn)題里最讓人頭疼的東西。但既然我們已經(jīng)論證了這些約束條件確實(shí)存在，就不得不用數(shù)學(xué)語(yǔ)言對(duì)他們進(jìn)行描述。盡管上面看起來(lái)是3 條約束，但SVM 算法通過(guò)一些巧妙的小技巧，將這三條約束條件融合在了一個(gè)不等式里面。我們首先考慮一個(gè)決策面是否能夠?qū)?/p>

15、所有的樣本都正確分類的約束。圖 2 中的樣本點(diǎn)分成兩類(紅色和藍(lán)色) ，我們?yōu)槊總€(gè)樣本點(diǎn)加上一個(gè)類別標(biāo)簽：如果我們的決策面方程能夠完全正確地對(duì)圖 2 中的樣本點(diǎn)進(jìn)行分類，就會(huì)滿足下面的公式如果我們要求再高一點(diǎn)，假設(shè)決策面正好處于間隔區(qū)域的中軸線上，并且相應(yīng)的支持向量對(duì)應(yīng)的樣本點(diǎn)到?jīng)Q策面的 距離為d,那么公式(2.8)就可以進(jìn)一步寫成： 符號(hào)是“對(duì)于所有滿足條件的” 的縮寫。我們對(duì)公式 (2.9) 中的兩個(gè)不等式的左右兩邊除上 d ，就可得到：其中和就當(dāng)成一條直線的方向矢量和截距。你會(huì)發(fā)現(xiàn)事情沒(méi)有發(fā)生任何變化，因?yàn)橹本€和直線其實(shí)是一條直線。現(xiàn)在，現(xiàn)在讓我忘記原來(lái)的直線方程參數(shù)3和Y,我們可以把參

16、數(shù)和重新起個(gè)名字，就叫它們 3和Y。我們可以直接說(shuō)：“對(duì)于存在分類間隔的兩類樣本點(diǎn)，我們一定可以找到一些決策面，使其對(duì)于所有的樣本點(diǎn)均滿足下面的條件：”公式 (2.11) 可以認(rèn)為是 SVM 優(yōu)化問(wèn)題的約束條件的基本描述。 2.4 線性 SVM 優(yōu)化問(wèn)題基本描述公式(2.11) 里面的情況什么時(shí)候會(huì)發(fā)生呢，參考一下公式 (2.9)就會(huì)知道，只有當(dāng)是決策面所對(duì)應(yīng)的支持向量樣本點(diǎn)時(shí)，等于1 或-1 的情況才會(huì)出現(xiàn)。這一點(diǎn)給了我們另一個(gè)簡(jiǎn)化目標(biāo)函數(shù)的啟發(fā)。回頭看看公式 (2.6) ，你會(huì)發(fā)現(xiàn)等式右邊分子部分的絕對(duì)值符號(hào)內(nèi)部的表達(dá)式正好跟公式 (2.11) 中不等式左邊的表達(dá)式完全一致，無(wú)論原來(lái)這些表

17、達(dá)式是 1 或者 -1 ，其絕對(duì)值都是 1 。所以對(duì)于這些支持向量樣本點(diǎn)有：公式 (2.12)的幾何意義就是，支持向量樣本點(diǎn)到?jīng)Q策面方程的距離就是1/| 3 |我們?cè)瓉?lái)的任務(wù)是找到一組參數(shù)3、Y使得分類間隔W=2d最大化，根據(jù)公式(2.12)就可以轉(zhuǎn)變?yōu)閨 3|的最小化問(wèn)題，也等效于1/2| 3 |的最小化問(wèn)題。我們之所以要在| 3 |上加上平方和 1/2 的系數(shù)，是為了以后進(jìn)行最優(yōu)化的過(guò)程中對(duì)目標(biāo)函數(shù)求導(dǎo)時(shí)比較方便，但這絕不影響最優(yōu)化問(wèn)題最后的解。另外我們還可以嘗試將公式 (2.11) 給出的約束條件進(jìn)一步在形式上精練，把類別標(biāo)簽和兩個(gè)不等式左邊相乘，形成統(tǒng)一的表述：好了，到這里我們可以給出

18、線性 SVM 最優(yōu)化問(wèn)題的數(shù)學(xué)描述了：這里m 是樣本點(diǎn)的總個(gè)數(shù)，縮寫 s. t.表示“ Subject to 是“服從某某條件”的意思。”， 公式 (2.14) 描述的是一個(gè)典型的不等式約束條件下的二次型函數(shù)優(yōu)化問(wèn)題，同時(shí)也是支持向量機(jī)的基本數(shù)學(xué)模型。 (此時(shí)此刻，你也許會(huì)回頭看 2.3 節(jié)我們提出的三個(gè)約束問(wèn)題，思考它們?cè)诠?.14 的約束條件中是否已經(jīng)得到了充分的體現(xiàn)。 但我不建議你現(xiàn)在就這么做， 因?yàn)?2.14 采用了一種比較含蓄的方式表示這些約束條件，所以你即便現(xiàn)在不理解也沒(méi)關(guān)系，后面隨著推導(dǎo)的深入，這些問(wèn)題會(huì)一點(diǎn)點(diǎn)露出真容。 )接下來(lái)，我們將在第三章討論大多數(shù)同學(xué)比較陌生的問(wèn)題：如何利用最優(yōu)化技術(shù)求解公式 (2.14)描述的問(wèn)題。哪些令人望而生畏的術(shù)語(yǔ)，凸二次優(yōu)化、拉格朗日對(duì)偶、 KKT 條件、鞍點(diǎn)等等，大多出現(xiàn)在這個(gè)部分。全面理解和熟練掌握這些概念當(dāng)然不容易，但如果你的目的主要是了解這些技術(shù)如何在 SVM 問(wèn)題進(jìn)行應(yīng)用的，那么閱讀過(guò)下面一章后，你有很大的機(jī)會(huì)可