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

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

2017-05-27 10:27

導(dǎo)語：支持向量機(jī)之我見。

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

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

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

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

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

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

SVM是什么

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

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

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

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

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

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

這就是SVM的基本型。

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

二次規(guī)劃

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

簡介：
在限制條件為

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

的條件下，找一個n 維的向量 x ，使得

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

為最小。

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

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

KKT

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

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

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

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

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

對偶問題

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

而二次規(guī)劃的對偶問題也是二次規(guī)劃，性質(zhì)、解法和原來一樣，所以請放心。（只做簡要介紹）

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

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

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

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

SMO

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

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

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

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

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

核函數(shù)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

軟間隔

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

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

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

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

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

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