SVM概述
支援向量機(SVM)是一種有監督的分類算法，并且它絕大部分處理的也是二分類問題，先通過一系列圖檔了解幾個關于SVM的概念。
上圖中有橙色點和藍色點分别代表兩類标簽，如果想要将其分類，需要怎麼做呢？可能有的夥伴會想到上一篇文章講到的邏輯回歸拟合決策邊界，這肯定是一種不錯的方法，本文所講的SVM也是可以解決這種分類問題的；既然都是分類算法，是以通過一個例子可以比對出二者的相同點和不同點。
超平面
可以看到，這裡給出了兩種劃分方式，就圖中實線而言，在邏輯回歸中可以稱作決策邊界，而在SVM中它被稱為超平面(hyperplane)。
上面例子中資料點都分布在二維平面上，是以此時超平面就為一條直線。如果給出的資料集是三、四、... 、N維呢？此時超平面對應的次元就是二、三、...、N-1維的，下圖展示了資料集多元時的超平面。
最大間隔
對于這個例子，可以将其準确分類的超平面可能有多個，其中具有最大間隔(兩條虛線之間的距離)的超平面就是SVM要找的最優解，這個最優解對應兩側虛線所穿過的樣本點，就是“支援向量(support vector)”,支援向量到超平面的距離被稱為間隔(margin)，如下圖繪制辨別。
公式推導
超平面方程
我們利用SVM算法模組化最後想要從衆多超平面中求解具有最大間隔的超平面，是以這也是一個最優化問題。
這裡需要了解一下最優化問題的兩個基本因素：
- 目标函數：你希望什麼東西的什麼名額達到最好。
-
優化對象：你希望改變哪些因素使目标函數達到最優。
線上性SVM算法中，目标函數就是“間隔”，優化對象則是“超平面”。
是以首先需要推導“超平面”的方程，二維空間内“超平面”的公式也就是直線方程，如下：
這裡将x變成x1，y變成x2的操作是為了将其向量化。
最後将其整理成：
一般的向量為列向量，是以這裡對$\omega$進行了轉置，并且$\omega$向量與我們所設直線是互相垂直的，隻需要假定直線斜率a為一個常數，繪圖即可證明，其中$\omega$控制着直線的方向，b則控制着直線的位置，是以直線方程中需要改變$\omega$和b使目标函數達到最優。
間隔公式
“間隔”就是圖中點到“超平面”的距離，公式如下：
其中d代表間隔，$||\omega||$代表的是$\omega$的二範數(模)，即對所有元素的平方和開平方。
模組化的目标就是為了找到最大間隔，其中最大間隔W=2d，隻要W越大，則代表該模型分類的效果越好，最後也就變成了求解d最大化的問題。
限制條件
針對上述我們所建分類器，當我們輸入資料給分類器時，它會傳回一個類别标簽，這裡先規定藍色為負樣本(-1)、紅色為正樣本(+1)，我們可以得到一組公式，如果超平面能夠準确對圖中樣本點分類，則可得到以下公式：
上述公式可歸化成：
s.t.表示?imageView2/2/w/1620"subject to"即服從某種條件
這裡再回顧一下上面的最大間隔方程，求最大間隔的思想可以概括為求最小的點到超平面的幾何距離的最大化。最小是為了分類時不同類别都能夠得到準确分類，距離最大化則是為了擷取”最大間隔“，以達到對分類器調優，公式如下：
如果我們希望最優的超平面的間隔的幾何距離為$\gamma$,即所有樣本點到超平面的幾何距離至少為$\gamma$，是以下面公式一定成立。
這裡$\gamma$将其設定為1。可以這麼想，不論我們$\gamma$設定的是幾，将等式兩邊同時除以$\gamma$，$\omega$和b的系數縮小了$\gamma$倍，但超平面是不動的，系數是可以同比例縮放的，可以類比直線方程。
固定$\gamma$之後，可以得到以下公式。
這裡對$\omega$做了一定處理，最大化$\frac{1}{||\omega||}$和最小化$\frac{1}{2}||\omega||^2$是等價的，這樣做是為了在進行最優化時對目标函數求導友善，對最優解沒有影響。
其中第一個公式為我們的目标函數，第二公式也就是這個最優化問題中的限制條件，由于$min\frac{1}{2}||\omega||^2$是一個凸函數，是以這個問題是凸優化問題。
求解最優化問題
最優化問題分類
最優化問題一般可分為兩大類：無限制優化問題和限制優化問題，而限制優化問題又可分為含等式限制優化問題和含不等式限制優化問題。
- 對于無限制優化問題，可以對函數求導，然後令其為零，從候選值中選取最優值，并加以驗證；若函數為凸函數，則可以保證是最優解。随機梯度下降和批量梯度下降就是無限制優化方法。
- 對于含等式限制優化問題，常用的方法是利用拉格朗日乘子法将其轉化為無限制優化問題求解。具體為将限制條件和函數寫成一個函數，稱為拉格朗日函數，系數為拉格朗日乘子；通過拉格朗日函數對各個變量求導，令其為零，從候選值中選取最優值，并加以驗證。
- 對于含不等式限制優化問題，主要通過KKT條件将其轉化成無限制優化問題求解。具體為通過建構拉格朗日函數，在一些條件下求出最優值的必要條件，這個條件就是KKT條件。
A的必要條件就是A可以推出的結論
對于我們所構造出的最優化問題明顯是屬于含不等式限制優化問題，關于拉格朗日函數的概念不過多介紹，下面介紹拉格朗日乘子法，并通過拉格朗日乘子法引出對偶問題和KKT條件。
拉格朗日乘子法
拉格朗日乘子法的思想就是通過引入拉格朗日乘子，将有d個變量和k個限制條件的最優化問題轉化為d+k個變量的無限制優化問題求解。
這裡感興趣的夥伴可以搜一下大佬的部落格或者西瓜書上都有詳細介紹，真是後悔高數課上沒有仔細聽這部分。
通過引入拉格朗日乘子$\lambda$可以将上述的最優化問題轉化成下面形式：
其中需要注意的是$\lambda>=0$,$1-y_i(\omega^Tx_i+b)<=0$,通過拉格朗日函數我們可以将上述公式轉化為：
有的夥伴這裡可能會不了解，為什麼是拉格朗日函數最大值的最小化，下圖介紹了原因。
很明顯當$1-y_i(\omega^Tx_i+b)>0$時，目标函數取值為正無窮是沒有意義的，而當$1-y_i(\omega^Tx_i+b)<=0$時,兩者則是等價的。
對偶問題
利用對偶性可以将上述原問題轉化成對偶問題，如下：
這個過程的主要操作就是将min和max互掉位置，并且二者之間有一個性質，即前者>=後者，這就好比在高個子人群中挑一個身高較矮的要高于在矮個子人群中挑一個身高較高的。預設情況下二者是呈弱對偶關系的，但在此目标函數和限制條件下是呈強對偶關系(等價關系)的。
在轉化成對偶問題之後，我們可以先求$min_\omega,bL(\omega,b,\lambda)$,分别令函數$L(\omega,b,\lambda)$對$\omega,b$求偏導，并使其等于0。
在将上述兩個式子帶入至建構的拉格朗日函數中，可得：
最後整理一下得出我們推導過後最終的優化問題，如下：
KKT條件
假設有這樣一個含不等式限制的優化問題：
如果想利用KKT條件處理此優化問題，需要利用拉格朗日乘子法将不等式限制、等式限制和目标函數合并寫成一個式子，如下：
KKT條件就是說取到的最優值必須滿足以下條件：
當原問題與對偶問題呈強對稱關系是此問題滿足KKT條件的充分必要條件，是以本文最優化問題滿足的條件如下：
根據這些條件，我們可以得出隻有在樣本點為支援向量(樣本點處于虛線上)時，$\lambda$可以取任意值，而其他位置的樣本點$\lambda$一定為0。這就和邏輯回歸有不同之處了，邏輯回歸在拟合決策邊界時，所有樣本都會有影響，而SVM有作用的主要是邊界線附近的樣本。
因為我們所設超平面方程為$f(x)=\omega^Tx+b$，是以我們求得原始最優化問題的解為$\omega^、b^$，在L對$\omega$求導時得到了$\omega^$的解，而對于$b^$,求解過程如下：
這裡需要注意的點是設定$(x_k,y_k)$是支援向量，是以$y_k=+1或y_k=-1$,$(y_k)^2=1$就可以消去。最終擷取到的最優超平面方程如下：
總結
- 介紹了超平面與最大間隔的概念。
- 在二維空間内推導超平面方程并介紹間隔公式。
- 推導該優化問題的限制條件。
- 介紹了最優化問題的分類及對應解決思想。
- 通過拉格朗日乘子法引出對偶問題。
- 在對偶問題的基礎上講解KKT條件。
-
部落客還是個菜鳥，歡迎指出文中出現的問題。
本文不包含代碼，着重于公式推導，對于手寫代碼比較重要的部分應該在于公式推導，隻有了解每一步驟的思想及由來，才能更好的進行程式設計，下篇文章将會介紹一個簡化版的序列最小化(SMO)算法，歡迎關注、感謝閱讀。
關注公衆号【奶糖貓】擷取更多精彩好文