支持向量機是機器學習中最不易理解的算法之一，它對數學有較高的要求。之前SIGAI微信公眾號已經發過「用一張圖理解SVM脈絡」，「理解SVM的核函數和參數」這兩篇文章，今天重啟此話題，對SVM的推導做一個清晰而透徹的介紹，幫助大家真正理解SVM，掌握其精髓。市面上有不少講解支持向量機的文章和書籍，但真正結構清晰、觸達精髓的講解非常少見。
在2012年深度學習火了之後，SVM用得越來越少了，目前在機器視覺領域CNN是標配，NLP中通常也使用RNN/LSTM和CNN，語音識別中大量使用RNN/LSTM。為什麼還要學SVM？原因有3：
1.保證機器學習知識的系統性、完整性。SVM作為歷史上出現的最重要的有監督學習算法之一，其思想、原理（包括核技巧）是機器學習的重要組成部分。如果不學它，你對機器學習的理解是不完整的。對於做學術，很多東西是一脈相承的，新的方法和理論有不少是借鑑於或擴展於已有的方法和思想。
2.面試時經常會問到，尤其是應屆生校招面試。SVM、logistic回歸、決策樹、EM算法之類的知識點，很多時候在面試官眼裡是檢驗應聘者機器學習水平的試金石，如果你不想因為它而導致面試掛掉，那就一定要啃下這個硬骨頭。
3.在某些問題上，可能還會使用此算法。在某些結構化數據預測（分類與回歸問題）上，SVM有很好的效果，核函數是很強悍的，可以解決非線性問題；在小樣本的情況下，SVM也可以訓練出高精度、泛化性能好的模型，而且核函數可以規避維數災難問題。
要理解支持向量機，下面的數學知識是必不可少的：
1.解析幾何中點到平面距離的計算公式
2.拉格朗日對偶，包括強對偶條件、Slater條件
3.KKT條件
4.凸優化，Hessian矩陣
在推導和證明中將會大量使用這些知識，如果對它們還不清楚，一定要沉下心來仔細學習理解。本文不對這些數學知識做專門的介紹。
在之前的公眾號文章「用一句話總結常用的機器學習算法」中對SVM的一句話解釋是：最大化分類間隔的線性分類器（不考慮核函數）。這一總結可謂精準 ，指出了SVM的本質。SVM的推導過程冗長而複雜，為了讓大家不至於迷路，只知細節而無法把握整體，我們總結了整個推導過程中的關鍵步驟和要點，畫出了下面的圖：
這是之前的公眾號文章「用一張圖理解SVM脈絡」的升級版。下面我們以此圖為主線，介紹SVM的推導過程和核心的點。
SVM起源於線性分類器，如果不使用費線性核函數，它就是線性分類器。因此要理解SVM首先要真正理解線性分類器的原理。
線性分類器是n維空間中的分類超平面，它將空間切分成兩部分，對應於正樣本和負樣本所在的區域。對於二維空間，線性分類器是一條直線；對於三維空間，它是一個平面；超平面是在更高維空間的推廣。
線性分類器所依賴的超平面方程為
其中x為輸入向量（樣本特徵向量）；w是權重向量，b是偏置項（標量），這兩組參數通過訓練得到。一個樣本如果滿足
則被判定為正樣本，否則被判定為負樣本。下圖是線性分類器對空間進行分割的示意圖，在這裡是二維平面
令很多初學者困惑的是，到底在直線哪一邊的樣本是正樣本，哪一邊的樣本是負樣本？其實無論哪一邊，都是可以做到的。因為只要將超平面方程乘以一個負數，即可實現上面不等式的反號。下面用一個例子說明，如下圖
在上圖中，正樣本有一個樣本點(5, 5)，以紅色表示。負樣本有一個樣本點(1, 1)，用藍色表示。分類超平面即圖中的直線的方程為
將正樣本的點代入上面的方程，計算出的值為正。將負樣本的點代入，計算出來的結果為負。但如果我們將方程兩邊同乘以-1，得到如下的方程
此方程所表示的還是同一條直線，但將正樣本代入方程之後，計算出的結果為負，負樣本則為正。因此我們可以控制權重向量w和偏置項b的值使得正樣本的預測值一定為正。
一般情況下，給定一組訓練樣本可以得到不止一個可行的線性分類器將兩類樣本正確分類，如下圖的例子
問題來了：在所有可行的線性分類器中，什麼樣的分類器是好的？為了得到好的泛化性能，分類平面應該不偏向於任何一類，並且離兩個類的樣本都儘可能的遠。這樣，落在直線兩邊這個間隔內的樣本都能被正確分類。這種最大化分類間隔的目標就是SVM的基本思想。
SVM的目標是尋找一個分類超平面，不僅能正確的分類每一個樣本，且要使得每一類樣本中距離超平面最近的樣本到超平面的距離儘可能遠。假設訓練樣本集有l個樣本，特徵向量是n維向量，類別標籤取值為+1或者-1，分別對應正樣本和負樣本。SVM為這些樣本尋找一個最優分類超平面
由於正樣本的的類別標籤為+1，負樣本的類別標籤為-1，可統一寫成如下不等式約束
第二個要求是超平面離兩類樣本的距離要儘可能大。根據解析幾何中點到平面的距離公式，每個樣本離分類超平面的距離為
其中是向量的L2範數。顯然上面的超平面方程有冗餘，將方程兩邊都乘以不等於0的常數，還是同一個超平面，利用這個特點可以簡化求解的問題。可以對w和b加上如下約束
消掉此冗餘，同時簡化點到超平面距離計算公式。對分類超平面的約束變成
這是上面那個不等式約束的加強版。分類超平面與兩類樣本之間的間隔為
目標是使得這個間隔最大化，等價於最小化下面的目標函數
加上前面定義的約束條件之後，求解的優化問題可以寫成：
可以證明這個問題是凸優化問題，且滿足Slater條件。一個被證明為凸優化問題，意義是重大的，它意味著我們可以用通行的數值優化算法得到全局最優解。而滿足Slater條件則意味著我們可以用拉格朗日對偶將其轉化為對偶問題求解，對偶問題的求解難度遠小於求解原問題。具體的證明與推導可以閱讀參考文獻[1]。
上面的優化問題帶有大量不等式約束，因此不容易求解，可以用拉格朗日對偶將其轉化成對偶問題。經過推導，得到對偶問題為
這裡的α是拉格朗日乘子變量，在對偶問題中，它們是優化變量。具體的推導過程可以閱讀文獻[1]。需要強調的是，不是什麼問題都可以用拉格朗日對偶轉化為對偶問題求解，它需要滿足強對偶條件，此時原問題與對偶問題有相同的最優解。強對偶成立的一種判據是Slater條件。
在推導過程中可以解出w的值，由此得到SVM的預測函數為
不為0的α對應的訓練樣本稱為支持向量，這就是支持向量機這一名字的來歷。下圖是支持向量的示意圖
另外可以證明對偶問題同樣為凸優化問題，在文獻[1]中有詳細的證明過程。限於篇幅，本文不對推導和證明和推導的細節進行過多的介紹。
線性可分的支持向量機不具有太多的實用價值，因為在現實應用中樣本一般都不是線性可分的，接下來對它進行擴展，得到能夠處理線性不可分問題的支持向量機。通過使用鬆弛變量和懲罰因子對違反不等式約束的樣本進行懲罰，可以得到如下最優化問題
其中是鬆弛變量，如果它不為0，表示樣本違反了不等式約束條件。C為懲罰因子，是人工設定的大於0的參數，用來對違反不等式約束條件的樣本進行懲罰。
同樣可以證明此問題是凸優化問題，且滿足Slater條件，因此可以用拉格朗日對偶轉化為對偶問題求解。
上面的原問題中還是帶有大量的不等式約束，不易求解，通過拉格朗日對偶，將其轉化為如下的對偶問題
和線性可分的對偶問題相比，唯一的區別是多了不等式約束，這是乘子變量的上界。將w的值代入超平面方程，得到分類決策函數為：
這和線性可分時是一樣的。這個預測函數是線性函數，因此這種SVM還是一個線性分類器。同樣可以證明，此時的對偶問題是凸優化問題。
在最優點處必須滿足KKT條件，將其應用於原問題，可以得到，在最優點處所有的樣本都必須要滿足下面的條件
上面第一種情況對應的是自由變量即非支持向量，第二種情況對應的是支持向量，第三種情況對應的是違反不等式約束的樣本。在後面的SMO算法中，會應用此條件來選擇優化變量，以及判定算法是否收斂。
雖然加入鬆弛變量和懲罰因子之後可以處理線性不可分問題，但支持向量機還是一個線性分類器，只是允許錯分樣本的存在，這從前面給出的預測函數可以看出。本節要介紹的核映射使得支持向量機成為非線性分類器，決策邊界不再是線性的超平面，而可以是形狀非常複雜的曲面。
如果樣本線性不可分，可以對特徵向量進行映射將它轉化到更高維的空間，使得在該空間中線性可分，這種方法在機器學習中被稱為核技巧。核映射將特徵向量變換到更高維的空間
在對偶問題中計算的是兩個樣本向量之間的內積，映射後的向量在對偶問題中為
直接計算這個映射效率太低，而且不容易構造映射函數。如果映射函數選取得當，存在函數K，使得下面等式成立
這樣只需先對向量做內積然後用函數進行變換，這等價於先對向量做核映射然後再做內積，這將能有效的簡化問題的求解。在這裡我們看到了求解對偶問題的另外一個好處，對偶問題中出現的是樣本特徵向量之間的內積，而核函數剛好作用於這種內積，替代對特徵向量的核映射。滿足上麵條件的函數稱為核函數，常用的核函數有以下幾種
核函數的精妙之處在於不用真的對特徵向量做核映射，而是直接對特徵向量的內積進行變換，而這種變換卻等價於先對特徵向量做核映射然後做內積。
需要注意的是，並不是任何函數都可以用來做核函數，必須滿足一定的條件-即Mercer條件。
為向量加上核映射後，要求解的對偶問題變為
如果核函數K是非線性函數，此時的預測函數是非線性的，因此SVM是非線性的。與不用核映射相比，只是求解的目標函數、最後的判定函數對特徵向量的內積做了核函數變換。預測時的時間複雜度為，當訓練樣本很多、支持向量的個數很大的時候，速度是一個問題。
其中e是分量全為1的向量，y是樣本的類別標籤向量。
前面給出了支持向量機的對偶問題，但並沒有說明怎麼求解此問題。由於矩陣的規模和樣本數相等，當訓練樣本數很大的時候，這個矩陣的規模很大，求解二次規劃問題的經典算法將會面臨性能問題。本節將介紹高效的求解算法-經典的SMO算法。
前面已經推導出加上鬆弛變量和核函數後的對偶問題：
Q矩陣半正定由核函數的性質保證。
為了表述方便，定義下面的核矩陣：
在極小值點處必須滿足該條件，由於對偶問題是凸優化問題，KKT條件是取得極值的充分條件。在後面的求解過程中將使用這一結論。
SMO算法由Platt等人提出，是求解支持向量機對偶問題的高效算法。算法的核心思想是每次在優化變量中挑出兩個分量進行優化，讓其他分量固定，這樣能保證滿足等式約束條件，這是一種分治法的思想。
下面先給出這兩個變量的優化問題（稱為子問題）的求解方法。假設選取的兩個分量為和，其他分量都固定即當成常數。由於
現在的核心問題是求解兩個變量的二次函數的極值。約束條件為線性約束與常數不等式約束。這個問題可以得到公式解。利用等式約束可以消掉一個變量，轉化為一元函數函數在區間上的極值問題，只要學過初中數學，都可以推導，無非是過程較為繁瑣而已。詳細的推導可以閱讀文獻[1]。
上面已經解決了兩個變量問題的求解，接下來說明怎麼選擇這兩個變量，在這裡使用了啟發式規則。第一個變量的選擇方法是在訓練樣本中選取違反KKT條件最嚴重的那個樣本。在最優點處訓練樣本是否滿足KKT條件的判據是
其中
前面講述的支持向量機只能解決二分類問題。對於多分類問題，可以用這種二分類器的組合來解決，常用的是如下兩種方案：
1對剩餘方案。對於有K個類的分類問題，訓練k個二分類器。訓練時第i個分類器的正樣本是第i類樣本，負樣本是除第i類之外其他類型的樣本，這個分類器的作用是判斷樣本是否屬於第i類。在進行分類時，對於待預測樣本，用每個分類器計算輸出值，取輸出值最大那個作為預測結果。
1對1方案。如果有k個類，訓練個二分類器，即這些類兩兩組合。訓練時將第類作為正樣本，其他各個類依次作為負樣本，總共有k(k-1)/2種組合。每個分類器的作用是判斷樣本是屬於第i類還是第j類。對樣本進行分類時採用投票的方法，依次用每個二分類器進行預測，如果判定為第m類，則m類的投票數加1，得票最多的那個類作為最終的判定結果。
下面用一個簡單的例子來進行說明，我們要對3個類進行分類。如果採用1對剩餘方案，則訓練3個分類器：
第1個分類器在訓練時以第1類樣本作為正樣本，另外兩類作為負樣本；第2個分類器在訓練時以第2類樣本作為正樣本，另外兩類作為負樣本；第3個分類器在訓練時以第3類樣本作為正樣本，另外兩類作為負樣本。在預測時，輸入樣本特徵向量，計算每個模型的預測函數值，將樣本判別為預測值最大的那個類。這種方案如下圖所示，黑色的樣本為待預測樣本。
在訓練第1個分類器時，以第1類樣本作為正樣本，第2類樣本作為負樣本；其他的模型以此類推。在預測時，用3個模型對輸入向量進行預測。然後統計投票，對於模型，如果預測值為+1，則第類的投票加1,；否則第類的投票加1。最後將樣本判定為得票最多的那個類。這種方案如下圖所示，同樣的，黑色樣本為待預測樣本。
這兩種情況下，黑色的樣本點應該被判定為哪一類，留給讀者自己思考。
前面最大化分類間隔的目標推導出了支持向量機的原問題，通過拉格朗日對偶得到了對偶問題，下面將從另一個角度來定義支持向量機的優化問題。SVM求解如下最優化問題
其中C為懲罰因子。目標函數的第一部分為正則化項，第二部分為真正的損失項，是一次函數。上述形式的損失函數稱為hinge loss，即合頁損失函數。其意義為當
。間隔越小，損失越大。這個問題和線性不可分時的支持向量機原問題是等價的。如果令
根據合頁損失函數可以定義出其他版本的支持向量機。L2正則化L1損失函數線性支持向量機求解如下最優化問題
其中C為懲罰因子。目標函數的第一部分為正則化項，第二部分為真正的損失項，是一次函數。
L2正則化L2損失函數線性支持向量機求解如下最優化問題
目標函數的第一部分為正則化項，目標函數的第二部分為真正的損失項，這是一個二次函數，其意義和L1損失函數相同。
L1正則化L2損失函數線性支持向量機求解如下最優化問題：
目標函數的前半部分其中為L1範數的正則化項。
在之前的介紹中，解決多分類問題是通過多個二分類器實現的，在這裡直接構造多類問題的損失函數。假設訓練樣本為
，其中為n維特徵向量，類別標籤
，其中k為類型數。多類分類問題的線性支持向量機求解如下最優化問題
這可以看成是二分類問題的推廣，目標函數的左邊部分是k個二次函數的和，每一個代表一個分界面；右邊是對錯分類的懲罰項。分類決策函數為
本文所講的內容，在參考文獻[1]即《機器學習-原理、算法與應用》一書的第10章-支持向量機，第11章-線性模型中有詳細而清晰的講述，所有核心的點均有詳細的證明與推導。讀完本文，你對SVM將有不一樣的理解。
參考文獻
[1] 機器學習-原理、算法與應用，雷明著，清華大學出版社