很多人第一次聽說 SVM 時都覺得它是個非常厲害的東西，但其實 SVM 本身“只是”一個線性模型。
只有在應用了核方法後，SVM 才會“升級”成為一個非線性模型
不過由於普遍說起 SVM 時我們都默認它帶核方法，所以我們還是隨大流、稱 SVM 的原始版本為 LinearSVM。
不過即使“只是”線性模型，這個“只是”也是要打雙引號的——它依舊強大，且在許許多多的問題上甚至要比帶核方法的 SVM 要好（比如文本分類）
由於支持向量機內容很多也很重要，所以分為四篇文章來講，今天首先講一講其中的奧秘
在支持向量機原理(一) 線性支持向量機中，我們對線性可分SVM的模型和損失函數優化做了總結。最後我們提到了有時候不能線性可分的原因是線性數據集裡面多了少量的異常點，由於這些異常點導致了數據集不能線性可分，本篇就對線性支持向量機如何處理這些異常點的原理方法做一個總結。
1. 線性分類SVM面臨的問題
有時候本來數據的確是可分的，也就是說可以用 線性分類SVM的學習方法來求解，但是卻因為混入了異常點，導致不能線性可分，比如下圖，本來數據是可以按下面的實線來做超平面分離的，可以由於一個橙色和一個藍色的異常點導致我們沒法按照上一篇線性支持向量機中的方法來分類。
另外一種情況沒有這麼糟糕到不可分，但是會嚴重影響我們模型的泛化預測效果，比如下圖，本來如果我們不考慮異常點，SVM的超平面應該是下圖中的紅色線所示，但是由於有一個藍色的異常點，導致我們學習到的超平面是下圖中的粗虛線所示，這樣會嚴重影響我們的分類模型預測效果。
如何解決這些問題呢？SVM引入了軟間隔最大化的方法來解決。
2. 線性分類SVM的軟間隔最大化
所謂的軟間隔，是相對於硬間隔說的，我們可以認為上一篇線性分類SVM的學習方法屬於硬間隔最大化。
回顧下硬間隔最大化的條件：
接著我們再看如何可以軟間隔最大化呢？
SVM對訓練集裡面的每個樣本引入了一個鬆弛變量,使函數間隔加上鬆弛變量大於等於1，也就是說：
對比硬間隔最大化，可以看到我們對樣本到超平面的函數距離的要求放鬆了，之前是一定要大於等於1，現在只需要加上一個大於等於0的鬆弛變量能大於等於1就可以了。當然，鬆弛變量不能白加，這是有成本的，每一個鬆弛變量, 對應了一個代價，這個就得到了我們的軟間隔最大化的SVM學習條件如下：
這裡,為懲罰參數，可以理解為我們一般迴歸和分類問題正則化時候的參數。越大，對誤分類的懲罰越大，越小，對誤分類的懲罰越小。
也就是說，我們希望儘量小，誤分類的點儘可能的少。C是協調兩者關係的正則化懲罰係數。在實際應用中，需要調參來選擇。
這個目標函數的優化和上一篇的線性可分SVM的優化方式類似，我們下面就來看看怎麼對線性分類SVM的軟間隔最大化來進行學習優化。
3. 線性分類SVM的軟間隔最大化目標函數的優化
和線性可分SVM的優化方式類似，我們首先將軟間隔最大化的約束問題用拉格朗日函數轉化為無約束問題如下：
其中 ,均為拉格朗日系數。
也就是說，我們現在要優化的目標函數是：
這個優化目標也滿足KKT條件，也就是說，我們可以通過拉格朗日對偶將我們的優化問題轉化為等價的對偶問題來求解如下：
我們可以先求優化函數對於的極小值, 接著再求拉格朗日乘子和 的極大值。
首先我們來求優化函數對於的極小值，這個可以通過求偏導數求得：
好了，我們可以利用上面的三個式子去消除和了。
其中，(1)式到(2)式用到了, (2)式到(3)式合併了同類項，(3)式到(4)式用到了範數的定義, (4)式到(5)式用到了上面的， (5)式到(6)式把和樣本無關的提前，(6)式到(7)式合併了同類項，(7)式到(8)式把和樣本無關的提前，(8)式到(9)式繼續用到，（9）式到(10)式用到了向量的轉置。由於常量的轉置是其本身，所有隻有向量被轉置，（10）式到(11)式用到了上面的，（11）式到(12)式使用了的乘法運算法則，（12）式到(13)式僅僅是位置的調整。
仔細觀察可以發現，這個式子和我們上一篇線性可分SVM的一樣。唯一不一樣的是約束條件。現在我們看看我們的優化目標的數學形式：s.t.
對於，，這3個式子，我們可以消去，只留下，也就是說。同時將優化目標函數變號，求極小值，如下：
這就是軟間隔最大化時的線性可分SVM的優化目標形式，和上一篇的硬間隔最大化的線性可分SVM相比，我們僅僅是多了一個約束條件。我們依然可以通過SMO算法來求上式極小化時對應的向量就可以求出和了。
4. 軟間隔最大化時的支持向量
在硬間隔最大化時，支持向量比較簡單，就是滿足就可以了。根據KKT條件中的對偶互補條件，如果則有即點在支持向量上，否則如果則有，即樣本在支持向量上或者已經被正確分類。
在軟間隔最大化時，則稍微複雜一些，因為我們對每個樣本引入了鬆弛變量。我們從下圖來研究軟間隔最大化時支持向量的情況，第i個點到對應類別支持向量的距離為。根據軟間隔最大化時KKT條件中的對偶互補條件我們有：
a) 如果,那麼,即樣本在間隔邊界上或者已經被正確分類。如圖中所有遠離間隔邊界的點。
b) 如果,那麼,即點在間隔邊界上。
c) 如果，說明這是一個可能比較異常的點，需要檢查此時
i)如果,那麼點被正確分類，但是卻在超平面和自己類別的間隔邊界之間。如圖中的樣本2和4.
ii)如果,那麼點在分離超平面上，無法被正確分類。
iii)如果,那麼點在超平面的另一側，也就是說，這個點不能被正常分類。如圖中的樣本1和3.
5. 軟間隔最大化的線性可分SVM的算法過程
這裡我們對軟間隔最大化時的線性可分SVM的算法過程做一個總結。
輸入是線性可分的m個樣本,其中x為n維特徵向量。y為二元輸出，值為1，或者-1.
輸出是分離超平面的參數和和分類決策函數。
算法過程如下：
1）選擇一個懲罰係數, 構造約束優化問題 s.t.
2）用SMO算法求出上式最小時對應的向量的值向量.
3) 計算
4) 找出所有的S個支持向量對應的樣本，通過 ，計算出每個支持向量對應的,計算出這些. 所有的對應的平均值即為最終的
這樣最終的分類超平面為：，最終的分類決策函數為：
6. 合頁損失函數
線性支持向量機還有另外一種解釋如下：
其中稱為合頁損失函數(hinge loss function)，下標+表示為：
也就是說，如果點被正確分類，且函數間隔大於1，損失是0，否則損失是,如下圖中的綠線。我們在下圖還可以看出其他各種模型損失和函數間隔的關係：對於0-1損失函數，如果正確分類，損失是0，誤分類損失1， 如下圖黑線，可見0-1損失函數是不可導的。對於感知機模型，感知機的損失函數是，這樣當樣本被正確分類時，損失是0，誤分類時，損失是，如下圖紫線。對於邏輯迴歸之類和最大熵模型對應的對數損失，損失函數是, 如下圖紅線所示。
線性可分SVM通過軟間隔最大化，可以解決線性數據集帶有異常點時的分類處理，但是現實生活中的確有很多數據不是線性可分的，這些線性不可分的數據也不是去掉異常點就能處理這麼簡單。那麼SVM怎麼能處理中這樣的情況呢？我們在下一篇就來討論線性不可分SVM和核函數的原理。
至此今天的新內容變講結束啦！如果有遺忘的知識可以看下昨天的內容，如下：
前情回顧
支持向量機(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 的文章
