前言
支援向量機(Support Vecor Machine,以下簡稱SVM)雖然誕生隻有短短的二十多年，但是自一誕生便由于它良好的分類性能席卷了機器學習領域，并牢牢壓制了神經網絡領域好多年。如果不考慮內建學習的算法，不考慮特定的訓練資料集，在分類算法中的表現SVM說是排第一估計是沒有什麼異議的。
SVM是一個二進制分類算法，線性分類和非線性分類都支援。經過演進，現在也可以支援多元分類，同時經過擴充，也能應用于回歸問題。本篇的重點是SVM用于線性分類時模型和損失函數優化的一個總結。
回顧感覺機模型
在（
機器學習(7)之感覺機python實作）中，講到了感覺機的分類原理，感覺機的模型就是嘗試找到一條直線，能夠把二進制資料隔離開。放到三維空間或者更高維的空間，感覺機的模型就是嘗試找到一個超平面，能夠把所有的二進制類别隔離開。對于這個分離的超平面，我們定義為 wTx+b=0，如下圖。在超平面 wTx+b=0 上方的我們定義為y=1,在超平面 wTx+b=0下方的我們定義為y=−1。可以看出滿足這個條件的超平面并不止一個。那麼我們可能會嘗試思考，這麼多的可以分類的超平面，哪個是最好的呢？或者說哪個是泛化能力最強的呢?
感覺機模型的損失函數優化，它的思想是讓所有誤分類的點(定義為M)到超平面的距離和最小，即最小化下式：
當和w和b成比例的增加，比如,當分子的和w和b擴大N倍時，分母的L2範數也會擴大N倍。也就是說，分子和分母有固定的倍數關系。那麼我們可以固定分子或者分母為1，然後求另一個即分子自己或者分母的倒數的最小化作為損失函數，這樣可以簡化我們的損失函數。在感覺機模型中，我們采用的是保留分子，固定分母||w||2=1,即最終感覺機模型的損失函數為：
如果我們不是固定分母，改為固定分子，作為分類模型有沒有改進呢？
函數間隔與幾何間隔
在正式介紹SVM的模型和損失函數之前，還需要先了解下函數間隔和幾何間隔的知識。
在分離超平面固定為wTx+b=0的時候，|wTx+b|表示點x到超平面的距離。通過觀察wTx+b和y是否同号，我們判斷分類是否正确，這些知識我們在感覺機模型裡都有講到。這裡我們引入函數間隔的概念，定義函數間隔γ′為：
它就是感覺機模型裡面的誤分類點到超平面距離的分子。對于訓練集中m個樣本點對應的m個函數間隔的最小值，就是整個訓練集的函數間隔。
函數間隔并不能正常反應點到超平面的距離，在感覺機模型裡我們也提到，當分子成比例的增長時，分母也是成倍增長。為了統一度量，我們需要對法向量w加上限制條件，這樣我們就得到了幾何間隔γ,定義為：
支援向量
在感覺機模型中，我們可以找到多個可以分類的超平面将資料分開，并且優化時希望所有的點都離超平面遠。但是實際上離超平面很遠的點已經被正确分類，我們讓它離超平面更遠并沒有意義。反而我們最關心是那些離超平面很近的點，這些點很容易被誤分類。如果我們可以讓離超平面比較近的點盡可能的遠離超平面，那麼我們的分類效果會好有一些。SVM的思想起源正起于此。
如下圖所示，分離超平面為wTx+b=0，如果所有的樣本不光可以被超平面分開，還和超平面保持一定的函數距離，那麼這樣的分類超平面是比感覺機的分類超平面優的。可以證明，這樣的超平面隻有一個。和超平面平行的保持一定的函數距離的這兩個超平面對應的向量，我們定義為支援向量，如下圖虛線所示。
SVM模型目标函數與優化
SVM的模型是讓所有點到超平面的距離大于一定的距離，也就是所有的分類點要在各自類别的支援向量兩邊。用數學式子表示為：
一般我們都取函數間隔γ′為1，這樣我們的優化函數定義為：
也就是說，我們要在限制條件yi(wTxi+b)≥1(i=1,2,...m)下，最大化1)||w||2。可以看出，這個感覺機的優化方式不同，感覺機是固定分母優化分子，而SVM是固定分子優化分母，同時加上了支援向量的限制。由于1||w||2的最大化等同于12||w||22的最小化。這樣SVM的優化函數等價于：
由于目标函數12||w||22是凸函數，同時限制條件不等式是仿射的，根據凸優化理論，我們可以通過拉格朗日函數将我們的優化目标轉化為無限制的優化函數，這和（
機器學習（13）之最大熵模型詳解）中講到了目标函數的優化方法一樣。具體的，優化函數轉化為：
這個優化函數滿足KKT條件，也就是說，我們可以通過拉格朗日對偶将我們的優化問題轉化為等價的對偶問題來求解。我們可以先求優化函數對于和w和b的極小值。接着再求拉格朗日乘子α的極大值。
首先我們來求和w和b的極小值，即minL(w,b,α)。這個極值我們可以通過對和w和b分别求偏導數得到：
從上兩式子可以看出，我們已經求得了和w和α的關系，隻要我們後面接着能夠求出優化函數極大化對應的α，就可以求出我們的w了，至于b，由于上兩式已經沒有b，是以最後的b可以有多個。既然我們已經求出和w和α的關系，就可以帶入優化函數L(w,b,α)消去w了。我們定義:
現在我們來看将w替換為α的表達式以後的優化函數ψ(α)的表達式：
對ψ(α)求極大化的數學表達式如下:
可以去掉負号，即為等價的極小化問題如下：
隻要我們可以求出上式極小化時對應的α向量就可以求出和w和b了。在這裡，我們假設通過SMO算法，我們得到了對應的α的值α∗。可以求出對應的w的值：
求b則稍微麻煩一點。注意到，對于任意支援向量(xx,ys)，都有
小結
線性可分SVM的學習方法對于非線性的資料集是沒有辦法使用的， 有時候不能線性可分的原因是線性資料集裡面多了少量的異常點，由于這些異常點導緻了資料集不能線性可分， 那麼怎麼可以處理這些異常點使資料集依然可以用線性可分的思想呢？ 我們在下一節的線性SVM的軟間隔最大化裡繼續講。
原文釋出時間為：2017-09-01
本文來自雲栖社群合作夥伴“
機器學習算法與Python學習”，了解相關資訊可以關注“
”。