开心六月综合激情婷婷|欧美精品成人动漫二区|国产中文字幕综合色|亚洲人在线成视频

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

圖1.1

對(duì)于支持向量機(jī)來(lái)說(shuō)，數(shù)據(jù)點(diǎn)若是

維向量，我們用

維的超平面來(lái)分開(kāi)這些點(diǎn)。但是可能有許多超平面可以把數(shù)據(jù)分類。最佳超平面的一個(gè)合理選擇就是以最大間隔把兩個(gè)類分開(kāi)的超平面。因此，SVM選擇能夠使離超平面最近的數(shù)據(jù)點(diǎn)的到超平面距離最大的超平面。

• 線性可分SVM

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

• 線性SVM

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

• 非線性SVM

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

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

其中

是一個(gè)含有

個(gè)元素的列向量, 即

;

是標(biāo)量,

,

時(shí)表示

屬于正類別,

時(shí)表示

屬于負(fù)類別。

注: 本文中,

、

、

等都是(列)向量，有的文章一般用

表示一個(gè)向量而用

表示所有

組成的一個(gè)矩陣，注意區(qū)分。

一個(gè)超平面由法向量

和截距

決定,其方程為

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

注意: 如果

和

都是列向量,即

會(huì)得到

和

的點(diǎn)積(dot product, 是一個(gè)標(biāo)量),等價(jià)于

和

。

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

:

我們的目標(biāo)是使

最大, 等價(jià)于使

最大:

通過(guò)求解上式即可得到最優(yōu)超平面

和

。具體如何求解見(jiàn)2.4和2.5節(jié)。

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

中的約束條件取等的點(diǎn)，即滿足

的點(diǎn)。也即所有在直線

或直線

的點(diǎn)。如下圖所示:

如何求解式

呢？

我們稱式

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

• 對(duì)偶問(wèn)題更易求解，由下文知對(duì)偶問(wèn)題只需優(yōu)化一個(gè)變量

  

  且約束條件更簡(jiǎn)單；
• 能更加自然地引入核函數(shù)，進(jìn)而推廣到非線性問(wèn)題。

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

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

因此，給定一個(gè)

和

, 若不滿足式

的約束條件，那么有

否則，若滿足式

的約束條件，有

結(jié)合式

和

知，優(yōu)化問(wèn)題

與式

所述問(wèn)題是完全等價(jià)的。

根據(jù)拉格朗日對(duì)偶性，式

所述問(wèn)題即原始問(wèn)題的對(duì)偶問(wèn)題是:

為了求得對(duì)偶問(wèn)題的解，需要先求得

對(duì)

和

的極小再求對(duì)

的極大。

(1) 求

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

將上面兩式代入

：

(2) 求

對(duì)

的極大:

等價(jià)于式

對(duì)

求極大，也等價(jià)于式

取負(fù)數(shù)后對(duì)

求極小，即

至此，我們得到了原始最優(yōu)化問(wèn)題

和對(duì)偶最優(yōu)化問(wèn)題

、

。

由slater條件知，因?yàn)樵純?yōu)化問(wèn)題的目標(biāo)函數(shù)和不等式約束條件都是凸函數(shù)，并且該不等式約束是嚴(yán)格可行的(因?yàn)閿?shù)據(jù)是線性可分的), 所以存在

,

,

，使得

,

是原始問(wèn)題的解，

是對(duì)偶問(wèn)題的解。這意味著求解原始最優(yōu)化問(wèn)題

可以轉(zhuǎn)換為求解對(duì)偶最優(yōu)化問(wèn)題

、

。

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

假設(shè)原始問(wèn)題目標(biāo)函數(shù)

和不等式約束條件

都是凸函數(shù)，原始問(wèn)題等式約束

都是仿射函數(shù)，且不等式約束

是嚴(yán)格可行的，即存在

，對(duì)所有

都有

，則存在

,

,

，使

是原始問(wèn)題的解，

,

是對(duì)偶問(wèn)題的解。

那么如何求解優(yōu)化問(wèn)題

、

的最優(yōu)解

呢？不難發(fā)現(xiàn)這是一個(gè)二次規(guī)劃問(wèn)題，有現(xiàn)成的通用的算法來(lái)求解。

假設(shè)我們現(xiàn)在求得了

、

的最優(yōu)解

，則根據(jù)式

可求得最優(yōu)

：

因?yàn)橹辽俅嬖谝粋€(gè)

(若不存在，即

全為0，則

, 即

,顯然不行), 再根據(jù)KKT條件，即

所以至少存在一個(gè)

, 使

, 即可求得最優(yōu)

:

再來(lái)分析KKT條件里的互補(bǔ)條件，對(duì)于任意樣本

，總會(huì)有

或者

。則有若

，此樣本點(diǎn)不是支持向量，對(duì)模型沒(méi)有任何作用；若

，此樣本點(diǎn)位于最大間隔邊界上，是一個(gè)支持向量，如下圖所示。

此外，當(dāng)樣本點(diǎn)是非支持向量時(shí)，因?yàn)?/span>

, 所以SVM的解中的求和項(xiàng)中第

項(xiàng)就為0，所以SVM的解

、

可簡(jiǎn)化為如下形式:

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

為了使不滿足上述條件的樣本點(diǎn)盡可能少，我們需要在優(yōu)化的目標(biāo)函數(shù)

里面新增一個(gè)對(duì)這些點(diǎn)的懲罰項(xiàng)。最常用的是hinge損失:

即若樣本點(diǎn)滿足約束條件損失就是0, 否則損失就是

,則優(yōu)化目標(biāo)

變成

其中

稱為懲罰參數(shù)，

越小時(shí)對(duì)誤分類懲罰越小，越大時(shí)對(duì)誤分類懲罰越大，當(dāng)

取正無(wú)窮時(shí)就變成了硬間隔優(yōu)化。實(shí)際應(yīng)用時(shí)我們要合理選取

，

越小越容易欠擬合，

越大越容易過(guò)擬合。

如果我們引入“松弛變量”

, 那么式

可重寫(xiě)成

式

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

對(duì)應(yīng)的拉格朗日函數(shù)為

類似2.4節(jié)，為了求得對(duì)偶問(wèn)題的解，我們需要先求得

對(duì)

、

和

的極小再求對(duì)

和

的極大。

以下兩步和2.4節(jié)幾乎完全一樣，除了最后對(duì)

的約束條件略有不同。

(1) 求

: 將

分別對(duì)

、

和

求偏導(dǎo)并令為0可得

將上面三個(gè)式子代入式

并進(jìn)行類似式

的推導(dǎo)即得

注意其中的

被消去了。

(2) 求

對(duì)

的極大：

式

對(duì)

求極大，也等價(jià)于式

取負(fù)數(shù)后對(duì)

求極小，即

至此，我們得到了原始最優(yōu)化問(wèn)題

和對(duì)偶最優(yōu)化問(wèn)題

、

。

類似2.4節(jié)地，假設(shè)我們現(xiàn)在通過(guò)通用的二次規(guī)劃求解方法或者SMO算法求得了

、

的最優(yōu)解

，則根據(jù)式

可求得最優(yōu)

：

其中

需滿足

。

對(duì)于任意樣本

，若

，此樣本點(diǎn)不是支持向量，該樣本對(duì)模型沒(méi)有任何的作用；若

，此樣本是一個(gè)支持向量。

若滿足

，進(jìn)一步地，若

, 由式

得

，即剛好

，樣本恰好在最大間隔邊界上；若

，有

，此時(shí)若

則該樣本落在最大間隔內(nèi)部，若

則該樣本落在最大間隔內(nèi)部即被錯(cuò)誤分類。

對(duì)于不同懲罰參數(shù)

，SVM結(jié)果如下圖所示

前一項(xiàng)可以理解為“結(jié)構(gòu)風(fēng)險(xiǎn)(structural risk)”，用來(lái)描述所求模型的某些性質(zhì)(SVM就是要求間隔最大)；第二項(xiàng)稱為“經(jīng)驗(yàn)風(fēng)險(xiǎn)(empirical risk)”，用來(lái)描述模型與訓(xùn)練數(shù)據(jù)的契合程度(即誤差)。而參數(shù)

就是用于對(duì)二者的折中,即我們一方面要求模型要滿足某種性質(zhì)另一方面又想使模型與訓(xùn)練數(shù)據(jù)很契合。

從正則化角度來(lái)講，

稱為正則化項(xiàng)，

稱為懲罰參數(shù)，

越大即對(duì)誤分類的懲罰越大(要求模型對(duì)訓(xùn)練模型更契合)，這可能會(huì)存在過(guò)擬合；

越小即相對(duì)更加看重正則化項(xiàng)，此時(shí)可能存在欠擬合。

設(shè)

是輸入空間(歐式空間

的子集或離散集合)，又設(shè)

是特征空間(希爾伯特空間)，如果存在一個(gè)

到

的映射

使得對(duì)所有

，函數(shù)

滿足條件

則稱

為核函數(shù)，

為映射函數(shù)，式中

為

和

的內(nèi)積。

通常，直接計(jì)算

比較容易而通過(guò)

和

計(jì)算

并不容易。而幸運(yùn)的是，在線性支持向量機(jī)的對(duì)偶問(wèn)題中，無(wú)論是目標(biāo)函數(shù)還是決策函數(shù)都只涉及到輸入樣本與樣本之間的內(nèi)積，因此我們不需要顯式地定義映射

是什么而只需事先定義核函數(shù)

即可。也就是說(shuō)，在核函數(shù)

給定的情況下，可以利用解線性問(wèn)題的方法求解非線性問(wèn)題的支持向量機(jī)，此過(guò)程是隱式地在特征空間中進(jìn)行的。

由上面的介紹可知，我們只需要定義核函數(shù)就可以了。但是如何不通過(guò)映射

判斷給定的一個(gè)函數(shù)

是不是核函數(shù)呢？或者說(shuō)，

需要滿足什么條件才是一個(gè)核函數(shù)。

設(shè)

,

是定義在

上的對(duì)稱函數(shù)，如果對(duì)任意的

，

對(duì)應(yīng)的Gram矩陣

是半正定矩陣，則

是正定核。

雖然有了上述定義，但是實(shí)際應(yīng)用時(shí)驗(yàn)證

是否是正定核依然不容易，因此在實(shí)際問(wèn)題中一般使用已有的核函數(shù)，下面給出一些常用的核函數(shù)。

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

• 首先選取適當(dāng)?shù)暮撕瘮?shù)

  

  和適當(dāng)?shù)膮?shù)

  

  ，構(gòu)造最優(yōu)化問(wèn)題
  
• 再利用現(xiàn)成的二次規(guī)劃問(wèn)題求解算法或者SMO算法求得最優(yōu)解

  

  。
• 選擇

  

  的一個(gè)滿足

  

  的分量

  

  ，計(jì)算
  
• 構(gòu)造決策函數(shù)：
  

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

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