支援向量機即Support Vector Machine，簡稱SVM。一聽這個名字，就有眩暈的感覺。支援(Support)、向量(Vector)、機器(Machine)，這三個毫無關聯的詞，硬生生地湊在了一起。從修辭的角度，這個合成詞最終落腳到”Machine”上，還以為是一種牛X的機器呢？實際上，它是一種算法，是效果最好的分類算法之一。
SVM是最大間隔分類器，它能很好地處理線性可分的問題，并可推廣到非線性問題。實際使用的時候，還需要考慮噪音的問題。
本文隻是一篇學習筆記，主要參考了July、pluskid等人相關文章。将要點記錄下來，促進自己的進步。
SVM是最大間隔分類器
既然SVM是用來分類的，咱就舉個簡單的例子，看看這個SVM有啥特點。如下圖所示，有一個二維平面，平面上有兩種不同的資料，分别用圈和叉表示。由于這些資料是線性可分的，可以用一條直線将這兩個資料分開，這樣的直線可以有無數條。
綠線、粉紅線、黑線都能将兩類區分開。但是那種更好呢？感覺上黑線似乎更好些。粉紅線和綠線都離樣本太近。要是樣本或分界線稍稍有些擾動，分類就可能出錯。黑線好就好在離兩類都有一個安全間隔（藍線與黑線間的間隔），即使有些擾動，分類還是準确的。這個安全間隔，也就是“Margin”，當然我們覺得間隔越大分類越準确。
這種分類思想該作何了解呢，他和邏輯回歸的分類有何差別呢？
當用邏輯回歸的思想來處理分類問題時(将資料分成正負兩類:正類y=1，負類y=0)。邏輯回歸函數反映的是資料是正類的機率，當這個機率大于0.5時，預測這個資料是正類，反之，小于0.5時，預測這個資料是負類。它優化的目标是預測出錯的機率越小越好。可以參看這裡
SVM則不同，它要找出一條離兩類都有一定安全間隔的分界線（專業點叫超平面）。優化的目标就是安全間隔越大越好。
是以，SVM也被叫做最大間隔分類器。
線性可分的情況
SVM是通過間隔來分類。我們怎麼來定量地表達呢？先來看看線性可分的情況，分類函數
f(x)=wTx+b
x 是特征向量，w是與特征向量維數相同的向量，也叫權重向量， b 是一個實數，也叫偏置。當f(x)=0時，表達的就是SVM的分類邊界，也就是超平面。SVM分成的類y可以為1或-1（注意，與邏輯回歸不同，不是1和0）。 f(x) 大于0的點對應y=1的資料， f(x) 小于0的點對應y=-1的資料。那我們關心的間隔怎麼表達？
先來看看函數間隔，用 γ^ 表示： γ^=y(wTx+b)=yf(x) 。 |f(x)| 值越大，也就是 yf(x) 越大，資料點離超平面越遠，我們越能确信這個資料屬于哪一類别，這是最直覺的認識。
那這個是不是就完美表達了我們想要的間隔呢？看看這種情況，固定超平面，當 w ，b同時乘以2，這個間隔就擴大了兩倍。那怎麼表達不受參數縮放的變化影響的間距呢？老老實實來畫個圖看看咯。
x 是超平面外的一點，它離超平面的距離是γ，顯然 w 是超平面的法向量，x0是 x 在超平面的投影。則x=x0+γw||w||，其中 ||w|| 是範數，用初等數學來了解就是向量的長度，也叫向量的模。因為在超平面上， f(x0)=0 ,等式兩邊乘以 wT ，再加上一個 b ，化簡可得γ=wTx+b||w||=f(x)||w||。注意這個 γ 是可正可負的，為了得到絕對值，乘以一個對應的類别y，即可得出幾何間隔（用 γ~ 表示）的定義：
γ~=yf(x)∥w∥=γ^∥w∥
這個 γ~ 是不受參數縮放影響的。于是，我們的SVM的目标函數就是 maxγ~
，當然它得滿足一些條件，根據margin的含義 yi(wTxi+b)=γ^i≥γ^,i=1,…,n
其中 γ^=γ~∥w∥ .之前說過，即使超平面固定， γ~ 的值也會随着 ||w|| 的變化而變化。由于我們的目标就是要确定超平面，是以可以将無關的變量固定下來，固定的方式有兩種：一是固定 ||w|| ，當我們找到最優的 γ~ 時 γ^ 也就随之而固定；二是反過來固定 γ^ ，此時 ||w|| 也可以根據最優的 γ~ 得到。出于友善推導和優化的目的，我們選第二種，令 γ^=1 ，則我們的目标函數化為：
max1∥w∥,s.t.,yi(wTxi+b)≥1,i=1,…,n
支援向量作何了解
說了這麼多，也沒有說到Support vector(支援向量)，仔細觀看下圖：
有兩個支撐着中間的分界超平面的超平面，稱為gap。它們到分界超平面的距離相等。這兩個gap上必定會有一些資料點。如果沒有，我們就可以進一步擴大margin了，那就不是最大的margin了。這些經過gap的資料點，就是支援向量（Support Vector）（它們支援了中間的超平面）。很顯然，隻有支援向量才決定超平面，其他的資料點不影響超平面的确定。
這是一個十分優良的特性。假設有100萬個資料點，支援向量100個，我們實際上隻需要用這100個支援向量進行計算!！！這将大大提高存儲和計算的性能。
線性SVM的求解
考慮目标函數： max1∥w∥,s.t.,yi(wTxi+b)≥1,i=1,…,n
由于求的 1||w|| 最大值相當于求 12∥w∥2 的最小值，是以上述目标函數等價于：
min12∥w∥2s.t.,yi(wTxi+b)≥1,i=1,…,n
1/2是友善求導時約去。這時目标函數是二次的，限制條件是線性的，是以它是一個凸二次規劃問題。這個問題可以用現成的QP（Quadratic Programming）的優化包進行求解。但是這個問題還有些特殊的結構，可以通過Lagrange Duality變換到對偶變量的優化問題。通常求解對偶變量優化問題的方法比QP優化包高效得多，而且推導過程中，可以很友善地引出核函數。
簡單地說，通過給每個限制條件加上一個拉格朗日乘子，我們可以将它們融和到目标函數裡去，拉格朗日函數如下：
L(w,b,α)=12∥w∥2−∑i=1nαi(yi(wTxi+b)−1)
這裡還需要說明一點。當 xi 不是支援向量時， αi=0 ；當 xi 是支援向量時， yi(wTxi+b)−1=0 。這個其實很好了解，因為超平面由支援向量決定，非支援向量不會影響到參數w。
這裡省略掉推導的過程，這個函數經過變換，并且滿足KKT條件。會得出如下結論：
w=∑i=1nαiyixi
∑i=1nαiy=0
求解的問題可以變換為
maxα∑i=1nαi−12∑i,j=1nαiαjyiyjxTixjs.t.αi≥0,i=1,…,n
上式可以通過SMO算法求出拉格朗日乘子 α ，進而求出 w ，通過
b=−maxyi=−1wTxi+minyj=1wTxj2
，求出b
處理非線性問題
通過上面的讨論，我們表達了SVM的目标函數，并給出了求解的方法。于是SVM就講完了，可以休息了?細心的讀者一定發現，上面是線上性可分的前提下展開讨論的。線性不可分的時候怎麼辦？
那可不可以将非線性問題轉換成線性問題呢？先來看個例子。
二維平面上，這是一個典型的線性不可分的問題。但我們增加一些特征，将資料點映射到高維空間，他就變成了線性可分的點集了。如下圖：
事實上，将任何線性不可分的點集映射到高維空間（甚至可以到無窮維空間），總能變成線性可分的情況。隻不過維數越高，計算量越大。維數大到無窮的時候，就是一場災難了。
現在我們還是從數學上梳理一下這個映射的過程。
根據 w=∑ni=1αiyixi ，分類函數可寫成：
f(x)=(∑i=1nαiyixi)Tx+b=∑i=1nαiyixTix+b=∑i=1nαiyi⟨xi,x⟩+b
⟨⋅⟩ 表示向量内積。這個形式的有趣之處在于，對新點x的預測，隻需要計算它與訓練資料點的内積即可。因為所有非支援向量所對應的系數 α 都是0，是以對于新點的内積計算實際上隻要針對少量的“支援向量”而不是所有的訓練資料。
經過映射，分類函數變成
f(x)=∑i=1nαiyi⟨ϕ(xi),ϕ(x)⟩+b
而 α 可以通過求解如下問題得到：
maxα∑i=1nαi−12∑i,j=1nαiαjyiyj⟨ϕ(xi),ϕ(xj)⟩s.t.αi≥0,i=1,…,n
這樣，似乎是拿到非線性資料，就找一個适當的映射 ϕ ，把原來的資料映射到新空間中，再做線性SVM即可。不過這個适當的映射可不是好惹的。二維空間做映射，需要5個次元，三維空間做映射，需要19個次元，次元數目是爆炸性增長的。到了無窮維，根本無法計算。這個時候就需要核函數出馬了。
觀察上式，映射隻是一個中間過程，我們實際需要的是計算内積。如果有一種方式可以在特征空間中直接計算内積。就能很好地避免維數災難了，這樣直接計算的方法稱為核函數方法。
核是一個函數 κ ,對所有 x1 ， x2 ，滿足 κ(x1,x2)=⟨ϕ(x1),ϕ(x2)⟩
，這裡 ϕ 是從 x 到内積特征空間FF的映射。
幾個常用的核函數
通常人們會從一些常用的核函數中選擇（根據問題和資料的不同，選擇不同的參數，實際上就是得到了不同的核函數），例如：
- 高斯核\kappa(x_1,x_2) = \exp\left(-\frac{|x_1-x_2|^2}{2\sigma^2}\right) κ(x1,x2)=exp(−|x1−x2|22σ2) ，這個空間會将原始空間映射到無窮維空間。不過，如果\sigma σ 選得很大的話，高次特征上的權重實際上衰減得非常快，是以實際上（數值上近似一下）相當于一個低維的空間；反過來，如果\sigma σ 選得很小的話，則可以将任意的資料映射為線性可分。當然，這不一定是好事，因為随之而來的可能是非常嚴重的過拟合問題。不過，總的來說，通過調控參數，高斯核實際上具有相當的靈活性，也是使用最廣泛的核函數之一。下圖所示的例子便是把低維空間不可分資料通過高斯核函數映射到了高維空間：
-
多項式核\kappa(x_1,x_2)=(\langle x_1,x_2\rangle+R)^d κ(x1,x2)=(⟨x1,x2⟩+R)d
，這個核所對應的映射實際上是可以寫出來的，該空間的次元是
\binom{m+d}{d} (m+dd) ，其中m m 是原始空間的次元。
- 線性核\kappa(x_1,x_2) = \langle x_1,x_2\rangleκ(x1,x2)=⟨x1,x2⟩，這實際上就是原始空間中的内積。這個核存在的主要目的是使得“映射後空間中的問題”和“映射前空間中的問題”兩者在形式上統一起來了(意思是說，咱們有的時候，寫代碼，或寫公式的時候，隻要寫個模闆或通用表達式，然後再代入不同的核，便可以了，于此，便在形式上統一了起來，不用再分别寫一個線性的，和一個非線性的)。
核函數的本質
總結一下核函數，實際是三點：
- 實際中，當我們遇到線性不可分的樣例，常用做法是把樣例特征映射到高維空間中
- 但如果凡是遇到線性不可分的樣例，一律映射到高維空間，那麼這個次元大小是會高到可怕的
- 此時，核函數就隆重登場了，核函數的價值在于它雖然也是将特征進行從低維到高維的轉換，但核函數絕就絕在它事先在低維上進行計算，而将實質上的分類效果表現在了高維上，也就如上文所說的避免了直接在高維空間中的複雜計算。
處理噪音
回顧此前的介紹，SVM用來處理線性可分的問題。後來為了處理非線性資料，使用核函數将原始資料映射到高維空間，轉化為線性可分的問題。但是有時候，并不是資料本身是非線性結構的，而隻是因為資料有噪音。對于這種偏離正常位置很遠的資料點，我們稱之為outlier。超平面本身就是隻有少數幾個支援向量組成，如果支援向量裡存在outlier，就會有嚴重影響。如下圖：
用黑圈圈起來的那個藍點就是一個outlier，它偏離了自己原本所應該的那個半空間，如果直接忽略掉，原本的分隔超平面還是挺好的，但是由于這個outlier的出現，導緻分隔超平面不得不被擠歪了，變成黑色虛線所示，同時margin也相應變小了。更嚴重的是，如果outlier再往右上移動一些距離的話，将無法構造出能将資料分開的超平面來。
為了處理這種情況，SVM允許資料點在一定程度上偏離一下超平面。上圖中，黑色實線所對應的距離，就是該outlier偏離的距離，如果把它移動回來，就剛好落在原來的超平面上，而不會使超平面發生變形了。具體來說，原來的限制條件變成：
yi(wTxi+b)≥1−ξi,i=1,…,n
其中 ξi≥0 稱為松弛變量，對應資料點 xi 允許偏離的函數間隔的量。對于一般的資料（非支援向量，也非outlier），這個值就是0。如果 ξi 任意大的話，那任意的超平面都是符合要求的。是以，我們在原來的目标函數後面加上一項，使得這些 ξi 的總和也要最小： min12||w||2+C∑i=1nξi
，其中C是一個參數，用于控制目标函數中兩項（尋找margin最大的超平面和保證資料點偏差最小）之間的權重。注意， ξi 是需要優化的變量，而 C 是一個事先确定好的常量。完整的目标函數是：
min12||w||2+C∑i=1nξis.t.yi(wTxi+b)≥1−ξi,i=1,…,n
通過拉格朗日對偶求解，
w=∑i=1nαiyixi
∑i=1nαiy=0
求解的問題可以變換為
maxα∑i=1nαi−12∑i,j=1nαiαjyiyjxTixjs.t.0≤αi≤C,i=1,…,n
對比之前的結果，隻不過是 α 多了一個上限 C 。
總結
- SVM是一個最大間距分類器。
- 線上性可分的情況下，它的目标函數是min12|w|2s.t.,yi(wTxi+b)≥1,i=1,…,n， 較好的求解方法是轉換為拉格朗日對偶問題，并用SMO算法進行求解。
- 線上性不可分的情況下，其基本思想是，将低維線性不可分的問題映射為高維可分的問題。具體實作辦法是：利用核函數，在低維空間進行運算，而将實質上的分類效果表現在高維上。
- 考慮到資料點中可能存在噪音的幹擾，需要将目标函數中加入松弛變量而求解的思路和方法不變。