機器學習 | 深入SVM原理及模型推導（一）
本文始發於個人公眾號：TechFlow，原創不易，求個關注
今天是機器學習專題的第32篇文章，我們來聊聊SVM。
SVM模型大家可能非常熟悉，可能都知道它是面試的常客，經常被問到。它最早誕生於上世紀六十年代。那時候雖然沒有機器學習的概念，也沒有這麼強的計算能力，但是相關的模型和理論已經提出了不少，SVM就是其中之一。
SVM完全可以說是通過數學推導出來的模型，由於當時還沒有電腦，所以模型當中的參數都是數學家們用手來算的。它有一個巨大的應用就是前蘇聯的計劃經濟體系，我們知道在計劃經濟當中，國家有多少社會資源，每樣商品需要生產多少都是國家統籌規劃的。
但是國家和社會不是一成不變的，去年消耗了多少糧食不意味著今年也會消耗這麼多，很多因素會影響。所以當時前蘇聯的科學家們用當時最先進的方法來計算參數預測各項商品的消耗來完成社會資源的調度，這個最先進的方法就是SVM。
廢話說了這麼多，下面我們就來看看這個模型實際的原理吧。
演算法描述
SVM的英文全稱是Support Vector Machine，翻譯過來的意思是支援向量機。無論是英文還是中文，我們直觀上有些難以理解。
難以理解沒有關係，我們先把支援向量這個概念放一放，先來介紹一下它整體的原理。
SVM最基本的原理就是尋找一個分隔「平面」將樣本空間一分為二，完成二分類。進一步我們可以知道，對於二維的平面，我們要分隔數據需要一條線。對於三維的空間我們要分開需要一個面，發散開去對於一個n維的空間，我們要將它分開需要一個n-1的超平面。
SVM尋找的就是這樣的超平面，為了方便理解，我們以最簡單的二維場景為例。
我們觀察一下上圖，很明顯圖中的數據可以分成兩個部分。對於上圖的數據而言理論上來說我們有無數種劃分的方法，我們既可以像左邊這樣隨意的劃分，也可以像右邊這樣看起來嚴謹許多的劃分，在這麼多劃分方法當中究竟哪一種是最好的呢？我們怎麼來定義劃分方法的好和壞呢？
SVM對這個問題的回答很乾脆，右圖的劃分是最好的，原因是它的間隔最大。
從圖中我們可以看到，間隔也就是被劃分成兩個部分之間最接近的距離，間隔正中的這條紅線就是SVM找到的用來劃分的超平面。
我們進一步觀察可以發現，對於間隔這個事情來說，絕大多數樣本都不起作用，能夠起作用的只有在落在虛線上也就是間隔邊緣的樣本。是這些樣本確定了間隔，從而間接確定了分隔平面，支撐起了模型。
所以SVM當中把這些落在邊緣上的樣本成為支援向量，這也是SVM得名的由來。
模型推導
我們首先來考慮最簡單的情況，即線性可分，也就是說所有樣本都可以被正確的劃分。這樣劃分出來得到的間隔是實實在在的，所以我們把線性可分的情況下的間隔稱為硬間隔。
首先我們先寫出這個分隔平面的公式：
\]
其中x表示一條n維的樣本特徵組成的向量，\(\omega\)是平面的n維法向量，決定平面的方向。雖然從公式上來看和線性回歸很像，但是它們之間的本質區別是線性回歸是用來擬合label的，而SVM的平面方程是用來確定平面方向的。這裡的b就是簡單的偏移量，表示平面距離原點的距離。
表示出來分隔平面之後，我們就可以表示出每一個樣本距離平面的距離：
\]
這個公式看起來好像不太明白，其實它是由二維的點到平面的距離公式演化得到的：\(d = \frac{|Ax + By + c|}{A^2 + B^2}\)
這裡的\(||\omega||\)是一個L2範數，我們把它也展開可以寫成：\(||\omega|| = \sqrt{\sum_{i=1}^k \omega_i^2}\)
模型假設
這裡我們做一點假設，對於樣本當中的點，在分隔平面上方的類別為1，在分隔平面下方的類別為-1。那麼我們可以進一步得到\(\omega x_i +b\)應該和\(y_i\)同號。所以我們可以寫成：\(y(\omega^T x + b) > 0\)。
我們來觀察支援向量，也就是剛好在間隔邊緣的點，它們到分割平面的距離剛好是間隔的一半。我們假設這個點的函數值是\(\gamma\)，我們把它表示出來可以得到：
y_i(\omega^T x_i + b)&=\gamma\\
y_i(\frac{\omega}{\gamma}x_i + \frac{b}{\gamma}) &= 1
\end{aligned}
\]
我們令新的\(\hat{\omega} = \frac{\omega}{\gamma}\)，新的\(\hat{b}= \frac{b}{\gamma}\)。也就是說我們通過變形可以將函數值縮放到1，為了方便計算，我們選取恰當的參數，使得間隔剛好為1。既然如此，對於所有的樣本點，我們都可以得到\(y_i(\omega^Tx_i + b) \ge 1\)，對於支援向量來說\(y_i(\omega^Tx_i + b)\)=1。
利用這點，我們可以表示出間隔：
\]
\(\frac{2}{||\omega||}\)是一個分數，我們要求它的最大值，也就是求\(||\omega||^2\)的最小值。我們想要在線性可分的基礎上讓這個間隔盡量大，所以這是一個帶約束的線性規劃問題，我們把整個式子寫出來：
接下來我們要做的就是在滿足約束的前提下找到使得\(\frac{1}{2}||\omega||^2\)最小的\(\omega\)，這個式子看起來非常麻煩，又有不等式摻和在裡面，那麼我們應該怎麼辦呢？
這部分內容我們將會在下一篇文章分享，敬請期待。
今天的文章到這裡就結束了，如果喜歡本文的話，請來一波素質三連，給我一點支援吧（關注、轉發、點贊）。
