1. 前言
支援向量機是機器學習算法中一個非常優秀且經典的特征分類器。在神經網絡及深度學習非常火熱的當下，支援向量機的熱度仍然居高不下。
支援向量機的數學原理非常優美，它将對特征空間的劃分轉化為一個凸優化問題，求解目标函數的全局極小值。在人臉識别等機器學習應用中，将支援向量機作為深度神經網絡的輸出特征的分類器，往往能夠取得不錯的效果。
支援向量機可以說是我進入機器學習領域接觸的第一個算法。從此，我被其優雅的數學、奇妙的“戲法”深深的吸引。從監督學習到強化學習、從算法原理到項目實戰、從堅定從事人工智能行業到成為AI算法工程師，我走過的每一步，都離不開那一場美麗的邂逅。
我和機器學習的故事（機器學習算法原理詳解系列文章），就從那場美麗的邂逅開始講起吧！
2. 基本定義
2.1 線性可分與非線性可分
對于一個訓練樣本集{(X1,y1), (X2,y2), … , (Xn,yn)}，若存在(W,b)，使得對i=1~n有：
（1）若yi=+1，則WTXi+b>0;
（2）若yi=-1，則WTXi+b<0。
則該訓練樣本集在i=1~n線性可分，否則該訓練樣本集在i=1~n非線性可分。
其中Xi和W均為列向量，yi為樣本i的标簽。
假設空心點表示一類，實心點表示另一類。如圖1所示，存在一條直線将兩類分開，則圖1中的樣本是線性可分的；如圖2所示，不存在一條直線将兩類分開，則圖2中的樣本是非線性可分的。
2.2 凸優化問題
凸優化問題指的是在定義域内具有全局最優解的問題，其數理化定義為：
最 小 化 ( m i n i m i z e ) : f ( x ) ( 1 ) 最小化(minimize):~~~~f(x)~~~~~~~~~~~~~~~~(1) 最小化(minimize): f(x) (1)
限 制 條 件 ( s u b j e c t t o ) : h i ( x ) = 0 , i = 1 , 2 , . . . , m ( 2 ) 限制條件(subject~to):~~~~h_i(x)=0,\ i=1,2,...,m~~~~~~~~~~~~~~~~(2) 限制條件(subject to): hi(x)=0, i=1,2,...,m (2)
g j ( x ) < = 0 , j = 1 , 2 , . . . , n ( 3 ) g_j(x)<=0,~j=1,2,...,n~~~~~~~~~~~~~~~~(3) gj(x)<=0, j=1,2,...,n (3)
如果目标函數 f ( x ) f(x) f(x)、不等式限制 g j ( x ) g_j(x) gj(x)全為凸函數，以及等式限制 h i ( x ) h_i(x) hi(x)是仿射的（即為線性函數），那麼這個優化問題就是凸優化問題。
若一個問題是凸優化問題，則該問題要麼無解，有麼有且僅有唯一解。
2.2.1 二次規劃問題
若一個凸優化問題的目标函數是二次的，限制條件是一次的，則該凸優化問題為二次規劃問題。
3. 支援向量機——線性可分情況
對于線性可分情況，即存在一條直線分開兩類，顯然則存在無數條直線分開兩類，如圖3所示。
支援向量機考慮的第一個問題是，在無數條分開兩類的直線中，那一條最好？或者說最優的分開兩類的直線應該滿足什麼性質？
支援向量機的創始人Vapnik等人指出，将任意一條分開兩類的直線c分别向上向下平移，直至剛好使兩類中的某一些樣本點落在直線上，得到直線a、直線b。将直線a、直線b之間的距離稱為間隔(Margin)，位于直線a或直線b上的樣本點稱為支援向量(Support Vector)，如圖4所示，則最優分類直線應該滿足如下3個性質：
（1）該直線分開了2類；
（2）該直線最大化間隔；
（3）該直線位于間隔的中間，到所有支援向量的距離相等。
線上性可分情況下，顯然有且隻有唯一一條直線滿足上述三個條件。
設直線c的方程為 W T X + b = 0 W^TX+b=0 WTX+b=0，對于某個支援向量 X s X_s Xs，易知其與直線c的距離 d = ∣ W T X s + b ∣ ∣ ∣ W ∣ ∣ d=\frac{|W^TX_s+b|}{||W||} d=∣∣W∣∣∣WTXs+b∣。支援向量機尋找的是最大化間隔的直線，是以支援向量機的優化問題可以寫成如下形式：
最 大 化 ( m a x i m i z e ) : ∣ W T X s + b ∣ ∣ ∣ W ∣ ∣ ( 4 ) 最大化(maximize):~~\frac{|W^TX_s+b|}{||W||}~~~~~~~~~~~~~~~~~~~~~(4) 最大化(maximize): ∣∣W∣∣∣WTXs+b∣ (4)
限 制 條 件 ： ∣ W T X i + b ∣ ∣ ∣ W ∣ ∣ > = ∣ W T X s + b ∣ ∣ ∣ W ∣ ∣ , i = 1 ~ n ( 5 ) 限制條件：~~\frac{|W^TX_i+b|}{||W||}>=\frac{|W^TX_s+b|}{||W||},~~i=1\text{\textasciitilde}n~~~~~~~~~~~~~~~~~(5) 限制條件： ∣∣W∣∣∣WTXi+b∣>=∣∣W∣∣∣WTXs+b∣, i=1~n (5)
其中 X i X_i Xi表示樣本集中的任意樣本點， ∣ ∣ W ∣ ∣ ||W|| ∣∣W∣∣表示向量 W W W的模。由于支援向量到直線c的距離最短，是以任意樣本點 X i X_i Xi到直線c的距離大于或等于支援向量 X s X_s Xs到直線c的距離。
将式(5)兩邊同時乘以 ∣ ∣ W ∣ ∣ ||W|| ∣∣W∣∣，可得式(6)如下：
∣ W T X i + b ∣ > = ∣ W T X s + b ∣ , i = 1 ~ n ( 6 ) |W^TX_i+b|>=|W^TX_s+b|,~~i=1\text{\textasciitilde}n~~~~~~~~~~~~~~~~~(6) ∣WTXi+b∣>=∣WTXs+b∣, i=1~n (6)
聯立式(4)和式(6)，可将支援向量機的優化問題寫成如下形式：
最 大 化 : ∣ W T X s + b ∣ ∣ ∣ W ∣ ∣ ( 7 ) 最大化:~~\frac{|W^TX_s+b|}{||W||}~~~~~~~~~~~~~~~~~~~~~(7) 最大化: ∣∣W∣∣∣WTXs+b∣ (7)
限 制 條 件 ： ∣ W T X i + b ∣ > = ∣ W T X s + b ∣ , i = 1 ~ n ( 8 ) 限制條件：~~|W^TX_i+b|>=|W^TX_s+b|,~~i=1\text{\textasciitilde}n~~~~~~~~~~~~~~~~~(8) 限制條件： ∣WTXi+b∣>=∣WTXs+b∣, i=1~n (8)
進一步，可将支援向量機的優化問題轉化為如下形式，将該轉化稱為【轉化一】：
最 大 化 : 1 ∣ ∣ W ∣ ∣ ( 9 ) 最大化:~~\frac{1}{||W||}~~~~~~~~~~~~~~~~~~~~~(9) 最大化: ∣∣W∣∣1 (9)
限 制 條 件 ： ∣ W T X i + b ∣ > = 1 , i = 1 ~ n ( 10 ) 限制條件：~~|W^TX_i+b|>=1,~~i=1\text{\textasciitilde}n~~~~~~~~~~~~~~~~~(10) 限制條件： ∣WTXi+b∣>=1, i=1~n (10)
事實上，可以用嚴格的數學證明【轉化一】前後的優化問題是同解的。在這裡，我不用嚴格的數學證明一步步推導二者同解，而是采用如下方法直覺了解兩個優化問題同解：
易知方程 W T X + b = 0 W^TX+b=0 WTX+b=0和 a W T X + a b = 0 ( a > 0 ) aW^TX+ab=0~~(a>0) aWTX+ab=0 (a>0)表示的是同一條直線。是以，不論支援向量機優化問題求出來的直線所對應的 W 和 b W和b W和b為何值，均可使用一個a同時乘以 W 和 b W和b W和b，并令 a W 和 a b aW和ab aW和ab的值指派給 W 和 b W和b W和b，使得 ∣ W T X s + b ∣ = 1 |W^TX_s+b|=1 ∣WTXs+b∣=1。此時，經過被指派後的 W 和 b W和b W和b所對應的直線與原直線保持不變。
再反過來了解，令 ∣ W T X s + b ∣ = 1 |W^TX_s+b|=1 ∣WTXs+b∣=1，求解上述優化問題，會得到一個 W 和 b W和b W和b，令 ∣ W T X s + b ∣ = 2 |W^TX_s+b|=2 ∣WTXs+b∣=2，會得到另一個 W 和 b W和b W和b，令 ∣ W T X s + b ∣ = k ( 某 個 不 為 0 的 實 數 ) |W^TX_s+b|=k(某個不為0的實數) ∣WTXs+b∣=k(某個不為0的實數)，又會得到一個 W 和 b W和b W和b。但是不論令 ∣ W T X s + b ∣ 等 于 幾 |W^TX_s+b|等于幾 ∣WTXs+b∣等于幾，求解出來的 W 和 b W和b W和b所對應的直線均為同一條直線，隻是這些 W 和 b W和b W和b等比例地擴大了a倍而已。
是以，可以令 ∣ W T X s + b ∣ = 1 |W^TX_s+b|=1 ∣WTXs+b∣=1。
綜上所述，線上性可分情況下，支援向量機尋找最優直線的優化問題可描述如下：
最 小 化 : 1 2 ∣ ∣ W ∣ ∣ 2 ( 11 ) 最小化:~~\frac{1}{2}||W||^2~~~~~~~~~~~~~~~~~~~~~(11) 最小化: 21∣∣W∣∣2 (11)
限 制 條 件 ： y i ( W T X i + b ) > = 1 , i = 1 ~ n ( 12 ) 限制條件：~~y_i(W^TX_i+b)>=1,~~i=1\text{\textasciitilde}n~~~~~~~~~~~~~~~~~(12) 限制條件： yi(WTXi+b)>=1, i=1~n (12)
說明：最大化 1 ∣ ∣ W ∣ ∣ \frac{1}{||W||} ∣∣W∣∣1與最小化 1 2 ∣ ∣ W ∣ ∣ 2 \frac{1}{2}||W||^2 21∣∣W∣∣2是等同的。乘以 1 2 \frac{1}{2} 21是為了後續求導簡便。 y i y_i yi是人為規定的訓練樣本的标簽，當令 y i ∈ { + 1 , − 1 } y_i\in\{+1,-1\} yi∈{+1,−1}時， y i ( W T X i + b ) 和 ∣ W T X i + b ∣ y_i(W^TX_i+b)和|W^TX_i+b| yi(WTXi+b)和∣WTXi+b∣是等同的。
上述優化問題中， ( X i , y i ) , i = 1 ~ n (X_i,y_i),~~i=1\text{\textasciitilde}n (Xi,yi), i=1~n是已知的， ( W , b ) (W,b) (W,b)是待求的。
該優化問題是典型的凸優化問題中的二次規劃問題。在機器學習領域，如果一個問題是凸優化問題，那麼該問題即可視為一個已解決的問題。可使用序列最小優化算法（Sequential minimal optimization, SMO）求解上述優化問題，得到 ( W , b ) (W,b) (W,b),進而得到線性可分情況下支援向量機優化問題的解。
為了便于了解，前文基于2維特征空間（即分開兩類的線性函數平面上的直線）對線性可分情況支援向量機優化問題進行了推導，易知在特征空間次元大于2（即向量 X X X的分量數大于2，分開兩類的線性函數是高維特征空間中的線性超平面）時，上述推導過程仍然成立。
4. 後記
本文詳細推導了線上性可分情況下，支援向量機求解最優分類直線或線性超平面的過程。清晰地展現了支援向量機如何将尋找最優分類直線或線性超平面問題轉化為一個凸優化問題。
後續我們将看到支援向量機如何在非線性可分情況下求解最優分類直線或線性超平面。屆時我們将可以看到支援向量機創始人Vapnik等人極具創造性的做法，以及一個非常奇妙的“戲法”——核函數戲法。
後文：
支援向量機（SVM）詳解（二）
支援向量機（SVM）詳解（三）