支持向量機(jī)（英語：support vector machine,，常簡稱為SVM，又名支持向量網(wǎng)絡(luò)）是在分類與回歸分析中分析數(shù)據(jù)的監(jiān)督式學(xué)習(xí)模型與相關(guān)的學(xué)習(xí)算法,。給定一組訓(xùn)練實例,，每個訓(xùn)練實例被標(biāo)記為屬于兩個類別中的一個或另一個，SVM訓(xùn)練算法創(chuàng)建一個將新的實例分配給兩個類別之一的模型,，使其成為非概率二元線性分類器,。SVM模型是將實例表示為空間中的點(diǎn)，這樣映射就使得單獨(dú)類別的實例被盡可能寬的明顯的間隔分開,。然后,，將新的實例映射到同一空間，并基于它們落在間隔的哪一側(cè)來預(yù)測所屬類別,。

圖1.1

對于支持向量機(jī)來說，數(shù)據(jù)點(diǎn)若是維向量,，我們用維的超平面來分開這些點(diǎn),。但是可能有許多超平面可以把數(shù)據(jù)分類。最佳超平面的一個合理選擇就是以最大間隔把兩個類分開的超平面,。因此,，SVM選擇能夠使離超平面最近的數(shù)據(jù)點(diǎn)的到超平面距離最大的超平面。

• 線性可分SVM

當(dāng)訓(xùn)練數(shù)據(jù)線性可分時，通過硬間隔(hard margin,，什么是硬,、軟間隔下面會講)最大化可以學(xué)習(xí)得到一個線性分類器，即硬間隔SVM,，如上圖的的H3,。

• 線性SVM

當(dāng)訓(xùn)練數(shù)據(jù)不能線性可分但是可以近似線性可分時，通過軟間隔(soft margin)最大化也可以學(xué)習(xí)到一個線性分類器,，即軟間隔SVM,。

• 非線性SVM

當(dāng)訓(xùn)練數(shù)據(jù)線性不可分時，通過使用核技巧(kernel trick)和軟間隔最大化,，可以學(xué)習(xí)到一個非線性SVM,。

考慮如下形式的線性可分的訓(xùn)練數(shù)據(jù)集:

其中是一個含有個元素的列向量, 即;是標(biāo)量,,時表示屬于正類別,時表示屬于負(fù)類別。

注: 本文中,,、,、等都是(列)向量,，有的文章一般用表示一個向量而用表示所有組成的一個矩陣，注意區(qū)分,。

一個超平面由法向量和截距決定,其方程為, 可以規(guī)定法向量指向的一側(cè)為正類,另一側(cè)為負(fù)類。下圖畫出了三個平行的超平面,，法方向取左上方向,。

注意: 如果和都是列向量,即會得到和的點(diǎn)積(dot product, 是一個標(biāo)量),等價于和。

將高數(shù)里面求兩條平行直線的距離公式推廣到高維可求得圖2.1中margin的:

我們的目標(biāo)是使最大, 等價于使最大:

通過求解上式即可得到最優(yōu)超平面和,。具體如何求解見2.4和2.5節(jié),。

在線性可分的情況下，訓(xùn)練數(shù)據(jù)集的樣本點(diǎn)中與分離超平面距離最近的數(shù)據(jù)點(diǎn)稱為支持向量(support vector),，支持向量是使中的約束條件取等的點(diǎn),，即滿足

的點(diǎn)。也即所有在直線或直線的點(diǎn),。如下圖所示:

如何求解式呢,？

我們稱式所述問題為原始問題(primal problem), 可以應(yīng)用拉格朗日乘子法構(gòu)造拉格朗日函數(shù)(Lagrange function)再通過求解其對偶問題(dual problem)得到原始問題的最優(yōu)解。轉(zhuǎn)換為對偶問題來求解的原因是:

• 對偶問題更易求解,，由下文知對偶問題只需優(yōu)化一個變量且約束條件更簡單,；
• 能更加自然地引入核函數(shù)，進(jìn)而推廣到非線性問題,。

首先構(gòu)建拉格朗日函數(shù),。為此需要引進(jìn)拉格朗日乘子(Lagrange multiplier)。則拉格朗日函數(shù)為:

因此,，給定一個和, 若不滿足式的約束條件,，那么有

否則，若滿足式的約束條件,，有

結(jié)合式和知,，優(yōu)化問題

與式所述問題是完全等價的。

根據(jù)拉格朗日對偶性,，式所述問題即原始問題的對偶問題是:

為了求得對偶問題的解,，需要先求得對和的極小再求對的極大。

(1) 求: 對拉格朗日函數(shù)求導(dǎo)并令導(dǎo)數(shù)為0,，有:

將上面兩式代入：

(2) 求對的極大:

等價于式對求極大，也等價于式取負(fù)數(shù)后對求極小,，即

至此,，我們得到了原始最優(yōu)化問題和對偶最優(yōu)化問題、,。

由slater條件知,，因為原始優(yōu)化問題的目標(biāo)函數(shù)和不等式約束條件都是凸函數(shù)，并且該不等式約束是嚴(yán)格可行的(因為數(shù)據(jù)是線性可分的), 所以存在,,,，使得,是原始問題的解,，是對偶問題的解。這意味著求解原始最優(yōu)化問題可以轉(zhuǎn)換為求解對偶最優(yōu)化問題,、,。

則其拉格朗日函數(shù)為

假設(shè)原始問題目標(biāo)函數(shù)和不等式約束條件都是凸函數(shù)，原始問題等式約束都是仿射函數(shù),，且不等式約束是嚴(yán)格可行的,，即存在，對所有都有,，則存在,,,，使是原始問題的解，,是對偶問題的解,。

那么如何求解優(yōu)化問題,、的最優(yōu)解呢？不難發(fā)現(xiàn)這是一個二次規(guī)劃問題,，有現(xiàn)成的通用的算法來求解,。

假設(shè)我們現(xiàn)在求得了,、的最優(yōu)解，則根據(jù)式可求得最優(yōu)：

因為至少存在一個(若不存在,，即全為0,，則, 即,顯然不行), 再根據(jù)KKT條件，即

所以至少存在一個, 使, 即可求得最優(yōu):

再來分析KKT條件里的互補(bǔ)條件，對于任意樣本,，總會有或者,。則有若，此樣本點(diǎn)不是支持向量,，對模型沒有任何作用,；若，此樣本點(diǎn)位于最大間隔邊界上,，是一個支持向量,，如下圖所示。

此外,，當(dāng)樣本點(diǎn)是非支持向量時,，因為, 所以SVM的解中的求和項中第項就為0，所以SVM的解,、可簡化為如下形式:

所以，整個SVM的解只與支持向量SV有關(guān),，與非支持向量無關(guān),。這也就解釋了2.3節(jié)的結(jié)論，即在決定最佳超平面時只有支持向量起作用,，而其他數(shù)據(jù)點(diǎn)并不起作用,。

為了使不滿足上述條件的樣本點(diǎn)盡可能少,，我們需要在優(yōu)化的目標(biāo)函數(shù)里面新增一個對這些點(diǎn)的懲罰項。最常用的是hinge損失:

即若樣本點(diǎn)滿足約束條件損失就是0, 否則損失就是,則優(yōu)化目標(biāo)變成

其中稱為懲罰參數(shù)，越小時對誤分類懲罰越小,，越大時對誤分類懲罰越大,，當(dāng)取正無窮時就變成了硬間隔優(yōu)化。實際應(yīng)用時我們要合理選取,，越小越容易欠擬合,，越大越容易過擬合,。

如果我們引入“松弛變量”, 那么式可重寫成

式表示的軟間隔支持向量機(jī)依然是一個凸二次規(guī)劃問題，和硬間隔支持向量機(jī)類似,，我們可以通過拉格朗日乘子法將其轉(zhuǎn)換為對偶問題進(jìn)行求解,。式對應(yīng)的拉格朗日函數(shù)為

類似2.4節(jié)，為了求得對偶問題的解,，我們需要先求得對,、和的極小再求對和的極大。

以下兩步和2.4節(jié)幾乎完全一樣,，除了最后對的約束條件略有不同。

(1) 求: 將分別對、和求偏導(dǎo)并令為0可得

將上面三個式子代入式并進(jìn)行類似式的推導(dǎo)即得

注意其中的被消去了,。

(2) 求對的極大：

式對求極大,，也等價于式取負(fù)數(shù)后對求極小，即

至此,，我們得到了原始最優(yōu)化問題和對偶最優(yōu)化問題,、。

類似2.4節(jié)地,，假設(shè)我們現(xiàn)在通過通用的二次規(guī)劃求解方法或者SMO算法求得了,、的最優(yōu)解，則根據(jù)式可求得最優(yōu)：

其中需滿足。

對于任意樣本,，若,，此樣本點(diǎn)不是支持向量，該樣本對模型沒有任何的作用,；若,，此樣本是一個支持向量。

若滿足,，進(jìn)一步地,，若, 由式得，即剛好，樣本恰好在最大間隔邊界上,；若,，有，此時若則該樣本落在最大間隔內(nèi)部,，若則該樣本落在最大間隔內(nèi)部即被錯誤分類,。

對于不同懲罰參數(shù),，SVM結(jié)果如下圖所示

前一項可以理解為“結(jié)構(gòu)風(fēng)險(structural risk)”，用來描述所求模型的某些性質(zhì)(SVM就是要求間隔最大),；第二項稱為“經(jīng)驗風(fēng)險(empirical risk)”,，用來描述模型與訓(xùn)練數(shù)據(jù)的契合程度(即誤差)。而參數(shù)就是用于對二者的折中,即我們一方面要求模型要滿足某種性質(zhì)另一方面又想使模型與訓(xùn)練數(shù)據(jù)很契合,。

從正則化角度來講,，稱為正則化項，稱為懲罰參數(shù),，越大即對誤分類的懲罰越大(要求模型對訓(xùn)練模型更契合),，這可能會存在過擬合；越小即相對更加看重正則化項,，此時可能存在欠擬合,。

設(shè)是輸入空間(歐式空間的子集或離散集合)，又設(shè)是特征空間(希爾伯特空間),，如果存在一個到的映射使得對所有,，函數(shù)滿足條件則稱為核函數(shù),，為映射函數(shù)，式中為和的內(nèi)積,。

通常,，直接計算比較容易而通過和計算并不容易。而幸運(yùn)的是,，在線性支持向量機(jī)的對偶問題中,，無論是目標(biāo)函數(shù)還是決策函數(shù)都只涉及到輸入樣本與樣本之間的內(nèi)積，因此我們不需要顯式地定義映射是什么而只需事先定義核函數(shù)即可,。也就是說,，在核函數(shù)給定的情況下，可以利用解線性問題的方法求解非線性問題的支持向量機(jī),，此過程是隱式地在特征空間中進(jìn)行的,。

由上面的介紹可知,，我們只需要定義核函數(shù)就可以了,。但是如何不通過映射判斷給定的一個函數(shù)是不是核函數(shù)呢？或者說,，需要滿足什么條件才是一個核函數(shù),。

設(shè),是定義在上的對稱函數(shù),，如果對任意的,，對應(yīng)的Gram矩陣是半正定矩陣，則是正定核,。

雖然有了上述定義,，但是實際應(yīng)用時驗證是否是正定核依然不容易，因此在實際問題中一般使用已有的核函數(shù),，下面給出一些常用的核函數(shù),。

• 多項式核函數(shù)(polynomial kernel function)
  
• 高斯核函數(shù)(Guassian kernel function)
  

• 首先選取適當(dāng)?shù)暮撕瘮?shù)和適當(dāng)?shù)膮?shù),，構(gòu)造最優(yōu)化問題
  
• 再利用現(xiàn)成的二次規(guī)劃問題求解算法或者SMO算法求得最優(yōu)解。
• 選擇的一個滿足的分量,，計算
  
• 構(gòu)造決策函數(shù)：
  

1. 由于SVM是一個凸優(yōu)化問題，所以求得的解一定是全局最優(yōu)而不是局部最優(yōu),。
2. 不僅適用于線性線性問題還適用于非線性問題(用核技巧),。
3. 擁有高維樣本空間的數(shù)據(jù)也能用SVM，這是因為數(shù)據(jù)集的復(fù)雜度只取決于支持向量而不是數(shù)據(jù)集的維度,，這在某種意義上避免了“維數(shù)災(zāi)難”,。
4. 理論基礎(chǔ)比較完善(例如神經(jīng)網(wǎng)絡(luò)就更像一個黑盒子)。

1. 二次規(guī)劃問題求解將涉及m階矩陣的計算(m為樣本的個數(shù)), 因此SVM不適用于超大數(shù)據(jù)集,。(SMO算法可以緩解這個問題)
2. 只適用于二分類問題,。(SVM的推廣SVR也適用于回歸問題；可以通過多個SVM的組合來解決多分類問題)