支持向量機(Support Vecor Machine,以下簡稱SVM)雖然誕生只有短短的二十多年，但是自一誕生便由於它良好的分類性能席捲了機器學習領域，並牢牢壓制了神經網絡領域好多年。如果不考慮集成學習的算法，不考慮特定的訓練數據集，在分類算法中的表現SVM說是排第一估計是沒有什麼異議的。
SVM是一個二元分類算法，線性分類和非線性分類都支持。經過演進，現在也可以支持多元分類，同時經過擴展，也能應用於迴歸問題。本系列文章就對SVM的原理做一個總結。本篇的重點是SVM用於線性分類時模型和損失函數優化的一個總結。
1. 回顧感知機模型
在感知機原理小結中，我們講到了感知機的分類原理，感知機的模型就是嘗試找到一條直線，能夠把二元數據隔離開。放到三維空間或者更高維的空間，感知機的模型就是嘗試找到一個超平面，能夠把所有的二元類別隔離開。對於這個分離的超平面，我們定義為wTx+b=0，如下圖。在超平面wTx+b=0上方的我們定義為y=1，在超平面wTx+b=0下方的我們定義為y=−1。可以看出滿足這個條件的超平面並不止一個。那麼我們可能會嘗試思考，這麼多的可以分類的超平面，哪個是最好的呢？或者說哪個是泛化能力最強的呢?
接著我們看感知機模型的損失函數優化，它的思想是讓所有誤分類的點(定義為M)到超平面的距離和最小，即最小化下式：
當w和b和b成比例的增加，比如,當分子的w和b擴大N倍時。也就是說，分子和分母有固定的倍數關係。那麼我們可以固定分子或者分母為1，然後求另一個即分子自己或者分母的倒數的最小化作為損失函數，這樣可以簡化我們的損失函數。在感知機模型中，我們採用的是保留分子，固定分母||w||2=1|，即最終感知機模型的損失函數為：
如果我們不是固定分母，改為固定分子，作為分類模型有沒有改進呢？
這些問題在我們引入SVM後會詳細解釋。
2. 函數間隔與幾何間隔
在正式介紹SVM的模型和損失函數之前，我們還需要先了解下函數間隔和幾何間隔的知識。
在分離超平面固定為wTx+b=0的時候，|wTx+b|表示點x到超平面的相對距離。通過觀察wTx+b和y是否同號，我們判斷分類是否正確，這些知識我們在感知機模型裡都有講到。這裡我們引入函數間隔的概念，定義函數間隔γ′為：
可以看到，它就是感知機模型裡面的誤分類點到超平面距離的分子。對於訓練集中m個樣本點對應的m個函數間隔的最小值，就是整個訓練集的函數間隔。
函數間隔並不能正常反應點到超平面的距離，在感知機模型裡我們也提到，當分子成比例的增長時，分母也是成倍增長。為了統一度量，我們需要對法向量w加上約束條件，這樣我們就得到了幾何間隔γ,定義為：
幾何間隔才是點到超平面的真正距離，感知機模型裡用到的距離就是幾何距離。
3. 支持向量
在感知機模型中，我們可以找到多個可以分類的超平面將數據分開，並且優化時希望所有的點都被準確分類。但是實際上離超平面很遠的點已經被正確分類，它對超平面的位置沒有影響。我們最關心是那些離超平面很近的點，這些點很容易被誤分類。如果我們可以讓離超平面比較近的點儘可能的遠離超平面，最大化幾何間隔，那麼我們的分類效果會更好一些。SVM的思想起源正起於此。
如下圖所示，分離超平面為wTx+b=0，如果所有的樣本不光可以被超平面分開，還和超平面保持一定的函數距離（下圖函數距離為1），那麼這樣的分類超平面是比感知機的分類超平面優的。可以證明，這樣的超平面只有一個。和超平面平行的保持一定的函數距離的這兩個超平面對應的向量，我們定義為支持向量，如下圖虛線所示。
支持向量到超平面的距離為1/||w||2,兩個支持向量之間的距離為2/||w||2。
4. SVM模型目標函數與優化
SVM的模型是讓所有點到超平面的距離大於一定的距離，也就是所有的分類點要在各自類別的支持向量兩邊。用數學式子表示為：
一般我們都取函數間隔γ′為1，這樣我們的優化函數定義為：
也就是說，我們要在約束條件下，最大化1/||w||2。可以看出，這個感知機的優化方式不同，感知機是固定分母優化分子，而SVM是固定分子優化分母，同時加上了支持向量的限制。
由於1||w||2的最大化等同於1/||w||2的最小化。這樣SVM的優化函數等價於：
由於目標函數12||w||22是凸函數，同時約束條件不等式是仿射的，根據凸優化理論，我們可以通過拉格朗日函數將我們的優化目標轉化為無約束的優化函數，這和最大熵模型原理小結中講到了目標函數的優化方法一樣。具體的，優化函數轉化為：
由於引入了朗格朗日乘子，我們的優化目標變成：
和最大熵模型一樣的，我們的這個優化函數滿足KKT條件，也就是說，我們可以通過拉格朗日對偶將我們的優化問題轉化為等價的對偶問題來求解。如果對凸優化和拉格朗日對偶不熟悉，建議閱讀鮑德的《凸優化》。
也就是說，現在我們要求的是：
從上式中，我們可以先求優化函數對於w和bw和b的極小值。接著再求拉格朗日乘子αα的極大值。
首先我們來求L(w,b,α)L(w,b,α)基於w和bw和b的極小值，即min(w)L(w,b,α)。這個極值我們可以通過對w和b分別求偏導數得到：
從上兩式子可以看出，我們已經求得了w和α的關係，只要我們後面接著能夠求出優化函數極大化對應的α，就可以求出我們的w了，至於b，由於上兩式已經沒有b，所以最後的b可以有多個。
好了，既然我們已經求出w和α的關係，就可以帶入優化函數L(w,b,α)消去w了。我們定義:
現在我們來看將w替換為α的表達式以後的優化函數ψ(α)的表達式：
其中，(1)式到(2)式用到了範數的定義||w||22=wTw, (2)式到(3)式用到了上面的w=∑i=1mαiyixi， (3)式到(4)式把和樣本無關的wT提前，(4)式到(5)式合併了同類項，(5)式到(6)式把和樣本無關的bb提前，(6)式到(7)式繼續用到w=∑i=1mαiyixi，（7）式到(8)式用到了向量的轉置。由於常量的轉置是其本身，所有隻有向量xixi被轉置，（8）式到(9)式用到了上面的∑i=1mαiyi=0，（9）式到(10)式使用了(a+b+c+…)(a+b+c+…)=aa+ab+ac+ba+bb+bc+…的乘法運算法則，（10）式到(11)式僅僅是位置的調整。
從上面可以看出，通過對w,b極小化以後，我們的優化函數ψ(α)僅僅只有α向量做參數。只要我們能夠極大化ψ(α)，就可以求出此時對應的α，進而求出w,b.
對ψ(α)求極大化的數學表達式如下:
可以去掉負號，即為等價的極小化問題如下：
只要我們可以求出上式極小化時對應的α向量就可以求出w和b了。具體怎麼極小化上式得到對應的α，一般需要用到SMO算法，這個算法比較複雜，我們後面會專門來講。在這裡，我們假設通過SMO算法，我們得到了對應的α的值α∗。
那麼我們根據w=∑i=1mαiyixi，可以求出對應的w的值
求b則稍微麻煩一點。注意到，對於任意支持向量(xx,ys)，都有
假設我們有S個支持向量，則對應我們求出S個b∗,理論上這些b∗都可以作為最終的結果， 但是我們一般採用一種更健壯的辦法，即求出所有支持向量所對應的b∗s，然後將其平均值作為最後的結果。注意到對於嚴格線性可分的SVM，b的值是有唯一解的，也就是這裡求出的所有b∗都是一樣的，這裡我們仍然這麼寫是為了和後面加入軟間隔後的SVM的算法描述一致。
怎麼得到支持向量呢？根據KKT條件中的對偶互補條件α∗i(yi(wTxi+b)−1)=0，如果αi>0則有
yi(wTxi+b)=1 即點在支持向量上，否則如果αi=0則有yi(wTxi+b)≥1，即樣本在支持向量上或者已經被正確分類。
5. 線性可分SVM的算法過程
這裡我們對線性可分SVM的算法過程做一個總結。
輸入是線性可分的m個樣本(x1,y1),(x2,y2),...,(xm,ym),其中x為n維特徵向量。y為二元輸出，值為1，或者-1.
輸出是分離超平面的參數w∗和b∗和分類決策函數。
算法過程如下：
1）構造約束優化問題
2）用SMO算法求出上式最小時對應的α向量的值α∗向量.
3) 計算w∗=∑i=1mα∗iyixi
線性可分SVM的學習方法對於非線性的數據集是沒有辦法使用的， 有時候不能線性可分的原因是線性數據集裡面多了少量的異常點，由於這些異常點導致了數據集不能線性可分， 那麼怎麼可以處理這些異常點使數據集依然可以用線性可分的思想呢？我們在下一節的線性SVM的軟間隔最大化裡繼續講。
閱讀更多 洛鴻0920 的文章
