開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

本文作者： AI研習(xí)社

2017-05-27 10:27

導(dǎo)語(yǔ)：支持向量機(jī)之我見(jiàn)。

雷鋒網(wǎng)按：本文作者煎魚(yú)，原文載于作者個(gè)人博客，雷鋒網(wǎng)已獲授權(quán)。

寫(xiě)在前面：囫圇吞棗看完SVM，個(gè)人感覺(jué)如果不好好理解一些概念，或說(shuō)如果知其然而不知其所以然的話，不如不看。因此我想隨便寫(xiě)一寫(xiě)，把整個(gè)思路簡(jiǎn)單地整理一遍。: )

SVM與神經(jīng)網(wǎng)絡(luò)

支持向量機(jī)并不是神經(jīng)網(wǎng)絡(luò)，這兩個(gè)完全是兩條不一樣的路吧。不過(guò)詳細(xì)來(lái)說(shuō)，線性SVM的計(jì)算部分就像一個(gè)單層的神經(jīng)網(wǎng)絡(luò)一樣，而非線性SVM就完全和神經(jīng)網(wǎng)絡(luò)不一樣了（是的沒(méi)錯(cuò)，現(xiàn)實(shí)生活中大多問(wèn)題是非線性的），詳情可以參考知乎答案。

這兩個(gè)冤家一直不爭(zhēng)上下，最近基于神經(jīng)網(wǎng)絡(luò)的深度學(xué)習(xí)因?yàn)锳lphaGo等熱門(mén)時(shí)事，促使神經(jīng)網(wǎng)絡(luò)的熱度達(dá)到了空前最高。畢竟，深度學(xué)習(xí)那樣的多層隱含層的結(jié)構(gòu)，猶如一個(gè)黑盒子，一個(gè)學(xué)習(xí)能力極強(qiáng)的潘多拉盒子。有人或許就覺(jué)得這就是我們真正的神經(jīng)網(wǎng)絡(luò)，我們不知道它那數(shù)以百千計(jì)的神經(jīng)元干了什么，也不理解為何如此的結(jié)構(gòu)能誕生如此美好的數(shù)據(jù) —— 猶如復(fù)雜性科學(xué)般，處于高層的我們并不能知道底層的”愚群“為何能涌現(xiàn)。兩者一比起來(lái)，SVM似乎也沒(méi)有深度學(xué)習(xí)等那么令人狂熱，連Hinton都開(kāi)玩笑說(shuō)SVM不過(guò)是淺度學(xué)習(xí)（來(lái)自深度學(xué)習(xí)的調(diào)侃）。

不然，個(gè)人覺(jué)得相對(duì)于熱衷于隱含層的神經(jīng)網(wǎng)絡(luò)，具有深厚的數(shù)學(xué)理論的SVM更值得讓我們研究。SVM背后偉大的數(shù)學(xué)理論基礎(chǔ)可以說(shuō)是現(xiàn)今人類的偉大數(shù)學(xué)成就，因此SVM的解釋性也非神經(jīng)網(wǎng)絡(luò)可比，可以說(shuō)，它的數(shù)學(xué)理論讓它充滿了理性，這樣的理性是一個(gè)理工科生向往的。就如，你渴望知道食物的來(lái)源以確定食物是否有毒，如果有毒是什么毒，這樣的毒會(huì)在人體內(nèi)發(fā)生了什么反應(yīng)以致于讓你不適 —— 我的理性驅(qū)使我這么想，一個(gè)來(lái)路不明的食物是不能讓我輕易接受的。

SVM是什么

簡(jiǎn)單點(diǎn)講，SVM 就是個(gè)分類器，它用于回歸的時(shí)候稱為SVR（Support Vector Regression），SVM和SVR本質(zhì)上都一樣。下圖就是SVM分類：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

（邊界上的點(diǎn)就是支持向量，這些點(diǎn)很關(guān)鍵，這也是”支持向量機(jī)“命名的由來(lái)）

SVM的目的：尋找到一個(gè)超平面使樣本分成兩類，并且間隔最大。而我們求得的w就代表著我們需要尋找的超平面的系數(shù)。

用數(shù)學(xué)語(yǔ)言描述：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

這就是SVM的基本型。

SVM的基本型在運(yùn)籌學(xué)里面屬于二次規(guī)劃問(wèn)題，而且是凸二次規(guī)劃問(wèn)題（convex quadratic programming）。

二次規(guī)劃

二次規(guī)劃的問(wèn)題主要用于求最優(yōu)化的問(wèn)題，從SVM的求解公式也很容易看出來(lái)，我們的確要求最優(yōu)解。

簡(jiǎn)介：
在限制條件為

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

的條件下，找一個(gè)n 維的向量 x ，使得

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

為最小。

其中，c為n 維的向量，Q為n × n 維的對(duì)稱矩陣，A為m × n 維的矩陣，b為m 維的向量。

其中，根據(jù)優(yōu)化理論，如果要到達(dá)最優(yōu)的話，就要符合KKT條件（Karush-Kuhn-Tucker）。

KKT

KKT是在滿足一些有規(guī)則的條件下，一個(gè)非線性規(guī)則問(wèn)題能有最優(yōu)解的一個(gè)充分必要條件。也就是說(shuō)，只要約束條件按照這個(gè)KKT給出的規(guī)則列出，然后符合KKT條件的，就可以有最優(yōu)解。這是一個(gè)廣義化拉格朗日乘數(shù)的成果。

把所有的不等式約束、等式約束和目標(biāo)函數(shù)全部寫(xiě)為一個(gè)式子：

L(a, b, x)= f(x) + a*g(x)+b*h(x)

KKT條件是說(shuō)最優(yōu)值必須滿足以下條件：

● L(a, b, x)對(duì)x求導(dǎo)為零
● h(x) = 0
● a*g(x) = 0

對(duì)偶問(wèn)題

將一個(gè)原始問(wèn)題轉(zhuǎn)換為一個(gè)對(duì)偶問(wèn)題，懂的人知道對(duì)偶問(wèn)題不過(guò)是把原始問(wèn)題換了一種問(wèn)法，從另一角度來(lái)求問(wèn)題的解，其本質(zhì)上是一樣的。就好像我不能證明我比百分之五的人丑，但是我能證明我比百分之九十五的人帥，那樣就夠了。那么，為啥要用對(duì)偶問(wèn)題，直接求原始問(wèn)題不好嗎？參考一下為什么我們要考慮線性規(guī)劃的對(duì)偶問(wèn)題？

而二次規(guī)劃的對(duì)偶問(wèn)題也是二次規(guī)劃，性質(zhì)、解法和原來(lái)一樣，所以請(qǐng)放心。（只做簡(jiǎn)要介紹）

最后訓(xùn)練完成時(shí)，大部分的訓(xùn)練樣本都不需要保留，最終只會(huì)保留支持向量。這一點(diǎn)我們從圖上也能看得出來(lái)，我們要確定的超平面只和支持向量有關(guān)不是嗎？

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

（你看，只和支持向量有關(guān)）

然而，問(wèn)題又出現(xiàn)了（新解法的出現(xiàn)總是因?yàn)樾聠?wèn)題的出現(xiàn)），對(duì)于SVM的對(duì)偶問(wèn)題，通過(guò)二次規(guī)劃算法來(lái)求解的計(jì)算規(guī)模和訓(xùn)練樣本成正比，開(kāi)銷太大。換句話來(lái)說(shuō)，輸入數(shù)據(jù)小的時(shí)候還好，不過(guò)小數(shù)據(jù)幾乎沒(méi)啥用，但是數(shù)據(jù)量大起來(lái)又計(jì)算量太大，所以就得尋找一種適合數(shù)據(jù)量大而且計(jì)算量小的解法，這個(gè)就是SMO。

SMO

SMO，Sequential Minimal Optimization，針對(duì)SVM對(duì)偶問(wèn)題本身的特性研究出的算法，能有效地提高計(jì)算的效率。SMO的思想也很簡(jiǎn)單：固定欲求的參數(shù)之外的所有參數(shù)，然后求出欲求的參數(shù)。

例如，以下是最終求得的分類函數(shù)，也就是我們SVM的目標(biāo)：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

SMO 算法每次迭代只選出兩個(gè)分量 ai 和 aj 進(jìn)行調(diào)整，其它分量則保持固定不變，在得到解 ai 和 aj 之后，再用 ai 和 aj 改進(jìn)其它分量。

如何高效也能通過(guò) SMO 算法的思想看得出來(lái) —— 固定其他參數(shù)后，僅優(yōu)化兩個(gè)參數(shù)，比起之前優(yōu)化多個(gè)參數(shù)的情況，確實(shí)高效了。然而，與通常的分解算法比較，它可能需要更多的迭代次數(shù)。不過(guò)每次迭代的計(jì)算量比較小，所以該算法表現(xiàn)出較好的快速收斂性，且不需要存儲(chǔ)核矩陣，也沒(méi)有矩陣運(yùn)算。說(shuō)白了，這樣的問(wèn)題用 SMO 算法更好。

核函數(shù)

我們的SVM目的其實(shí)也簡(jiǎn)單，就是找一個(gè)超平面，引用一張圖即可表述這個(gè)目的：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

然而現(xiàn)實(shí)任務(wù)中，原始樣本空間也許并不能存在一個(gè)能正確劃分出兩類樣本的超平面，而且這是很經(jīng)常的事。你說(shuō)說(shuō)要是遇到這樣的數(shù)據(jù)，怎么劃分好呢：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

告訴我你的曲線方程吧，傻了吧~

于是引入了一個(gè)新的概念：核函數(shù)。它可以將樣本從原始空間映射到一個(gè)更高維的特質(zhì)空間中，使得樣本在這個(gè)新的高維空間中可以被線性劃分為兩類，即在空間內(nèi)線性劃分。這個(gè)過(guò)程可以觀看視頻感受感受，由于是 youtube 所以我截一下圖：

這是原始數(shù)據(jù)和原始空間，明顯有紅藍(lán)兩類：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

通過(guò)核函數(shù)，將樣本數(shù)據(jù)映射到更高維的空間（在這里，是二維映射到三維）：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

而后進(jìn)行切割：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

再將分割的超平面映射回去：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

大功告成，這些就是核函數(shù)的目的。

再進(jìn)一步，核函數(shù)的選擇變成了支持向量機(jī)的最大變數(shù)（如果必須得用上核函數(shù)，即核化），因此選用什么樣的核函數(shù)會(huì)影響最后的結(jié)果。而最常用的核函數(shù)有：線性核、多項(xiàng)式核、高斯核、拉普拉斯核、sigmoid核、通過(guò)核函數(shù)之間的線性組合或直積等運(yùn)算得出的新核函數(shù)。（這里只涉及概念，不涉及數(shù)學(xué)原理）

軟間隔

知道了上面的知識(shí)后，你不是就覺(jué)得SVM分類就應(yīng)該是這樣的：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

然而這也不一定是這樣的，上圖給出的是一種完美的情況，多么恰巧地兩類分地很開(kāi)，多么幸運(yùn)地能有一個(gè)超平面能將兩個(gè)類區(qū)分開(kāi)來(lái)！要是這兩個(gè)類有一部分摻在一起了，那又該怎么分?。?/p>

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的

有時(shí)候如果你非要很明確地分類，那么結(jié)果就會(huì)像右邊的一樣 —— 過(guò)擬合。明顯左邊的兩個(gè)都比過(guò)擬合好多了，可是這樣就要求允許一些樣本不在正確的類上，而且這樣的樣本越少越好，”站錯(cuò)隊(duì)“的樣本數(shù)量要通過(guò)實(shí)際來(lái)權(quán)衡。這就得用上”軟間隔“，有軟間隔必然有硬間隔，應(yīng)間隔就是最開(kāi)始的支持向量機(jī)，硬間隔支持向量機(jī)只能如此”明確“地分類。特意找來(lái)了這個(gè)數(shù)學(xué)解釋：

開(kāi)發(fā)者自述：我是怎樣理解支持向量機(jī)（SVM）與神經(jīng)網(wǎng)絡(luò)的