機器學習筆記-支持向量機(SVM)（一）

03-02

支持向量機（SVM）是一種有監督的分類模型，基本思想是在特徵空間中找到一個超平面將不同類的樣本點分隔開，學習策略是間隔最大化，最後可轉換為求解一個凸二次規劃問題。

一、線性可分支持向量機

1.1 線性可分假設

首先，我們先做一個假設：

假設我們的訓練集樣本是線性可分的。

線性可分的意思：對一個數據集： $T=left{(x_{1},y_{1}),(x_{},y_{2}),…,(x_{m},y_{m}) ight}$

其中 $x_{i}inchi=R^{n}$ ， $y_{i}in Y=left{ +1,-1 ight}$ ， $i=1,2,3,4,…m$ ，可以找到一個超平面 $S$ :

$qquadqquadqquadqquadqquadqquad w·x+b=0$

使得數據集中的正反樣本完全正確地分割在超平面的兩側，用式子表達起來是：

$qquadqquadqquadqquadqquad w·x_{i}+b=left{ egin{aligned} >0 & & y_{i}=+1\ <0 & & y_{i}=-1 \ end{aligned} ight.$

則稱這個數據集 $T$ 是線性可分的，否則是線性不可分的。

線性可分集例子：

在這裡定義一個函數： $g(x)=w·x+b$ ，這個函數在後面會多次出現

1.2 學習策略

上面提到，對於一個線性可分數據集，存在超平面將兩類樣本點分割開，但一般這樣的超平面會有無窮個：

既然我們有這麼多個超平面，該選擇哪一個呢，直觀上我們選擇這樣的一個超平面：既可以完全分割開數據集，並且讓樣本點和這個超平面的「距離」儘可能遠。恰好這樣的超平面魯棒性也是最好的，即泛化能力最強，而且最重要的是這樣的超平面是唯一的。

那麼接下來的問題就是如何定義樣本點到超平面的距離呢？

1.3 函數間隔和幾何間隔

一般來說，一個點距離超平面的遠近可以代表分類預測的置信度，即樣本點距離超平面越遠，就越能肯定該樣本點是分類正確的。

在超平面 $S$ : $w·x+b$ =0確定的情況下，我們可以用 $left| w·x_{i}+b ight|$ 表示 $x_{i}$ 距離超平面的遠近，又 $y_{i}$ 與 $w·x_{i}+b$ 的符號是否相同又代表分類是否正確，所以綜合這兩個我們用 $y_{i}(w·x_{i}+b)$ 表示分類的正確度。

定義1.1 （函數間隔）

對超平面 $w·x+b=0$ 和樣本點 $left( x_{i},y_{i} ight)$ ，樣本點的函數間隔定義為：

$qquadqquadqquadqquadqquadqquad ilde{gamma_{i}}=y_{i}(w·x_{i}+b)$

整個數據集的函數間隔為取所有樣本點函數間隔的最小值，即

$qquadqquadqquadqquadqquadqquad ilde{gamma}= min_{i=1,2,..m} ilde{gamma}_{i}$

下面解釋為什麼這樣說

如上圖，若要計算點A到超平面的距離 $gamma_{i}$ ，設A為 $x_{1}$ ，其類標記為 $y=+1$ ，B為A關於超平面的投影點，設為 $x_{0}$ ，則有

$qquadqquadqquadqquadqquadqquadleft{ egin{aligned} x_{0}+gamma_{i}*frac{w}{left| left| w ight| ight|}=x_{1}\ w·x_{0}+b=0\ end{aligned} ight.$

解得 $gamma_{i}=frac{w}{left| left| w ight| ight|}·x+frac{b}{left| left| w ight| ight|}$

這是樣本是正類的情況。

而當 $y=-1$ 時的情況是

$qquadqquadqquadqquadqquadgamma_{i}=-left( frac{w}{left| left| w ight| ight|}·x+frac{b}{left| left| w ight| ight|} ight)$

綜合這兩種情況，我們得到一個既包括樣本類信息和距離信息的度量，就是

$qquadqquadqquadqquadqquadgamma_{i}=y_{i}left( frac{w}{left| left| w ight| ight|}·x_{i}+frac{b}{left| left| w ight| ight|} ight)$

這就是接下來一直使用的概念：幾何間隔

定義1.2 （幾何間隔）

對超平面 $w·x+b=0$ 和樣本點 $left( x_{i},y_{i} ight)$ ，樣本點的幾何間隔定義為：

$qquadqquadqquadqquadqquadgamma_{i}=y_{i}left( frac{w}{left| left| w ight| ight|}·x_{i}+frac{b}{left| left| w ight| ight|} ight)$

整個數據集的函數間隔為取所有樣本點函數間隔的最小值，即

$qquadqquadqquadqquadqquadqquadgamma= min_{i=1,2,..m}gamma_{i}$

從定義看出，函數間隔和幾何間隔之間只是一個 $left| left| w ight| ight|$ 倍關係，即

$qquadqquadqquadqquadqquadqquadgamma_{i}=frac{ ilde{gamma_{i}}}{left| left| w ight| ight|}$

$qquadqquadqquadqquadqquadqquad gamma=frac{ ilde{gamma}}{left| left| w ight| ight|}$

若 $left| left| w ight| ight|$ =1，那麼此時函數間隔和幾何間隔相等，而且當超平面 $w,b$ 成比例地改變，此時表平面沒有改變，幾何間隔也不改變。

1.4 間隔最大化和最大間隔分離超平面

上面得到了一個關於樣本點到超平面度量的好指標，就是幾何間隔。那麼我們使間隔最大化，就是讓數據集的幾何間隔最大化。

1.4.1 最大間隔分離超平面

上面的分析已經明確了需要得到的是一個幾何間隔最大的超平面，這個問題我們可以用以下最優化約束問題來表示：

$qquadqquadqquadqquadqquadqquad max_{w,b} gamma$

$qquadqquadqquadqquadqquad s.t quad y_{i}left( frac{w}{left| left| w ight| ight|}*x_{i}+frac{b}{left| left| w ight| ight|} ight)geqgammaquad i=1,2,3,....m$

式子的意思是我們讓數據集的幾何間隔 $gamma$ 最大化，約束條件表示所有點的幾何間隔都必須大於等於 $gamma$ ，對應上面對數據集幾何間隔的定義。

考慮到幾何間隔和函數間隔的關係，上面的最優化問題等價於下面這個問題：

$qquadqquadqquadqquadqquadqquadmax_{w,b} frac{ ilde{gamma}}{left| left| w ight| ight|}$

$qquadqquadqquadqquadqquad s.t quad y_{i}left( w*x_{i}+b ight)geq ilde{gamma} quad i=1,2,3,....m$

觀察上面這個優化問題，我們可以發現無論函數間隔 $ilde{gamma}$ 取什麼值，問題的解都不會改變。事實上，我們把 $w,b$ 按比例進行縮放變為 $lambda w,lambda b$ ，此時函數間隔就變為 $lambda ilde{gamma}$ 。而這一改變並沒有影響到目標和約束條件（約掉了）。這一事實和上面提到的不能以函數間隔為間隔度量是一致的。既然這樣，我們索性就讓函數間隔為常數1，方面我們處理，問題變為：

$qquadqquadqquadqquadqquadqquadmax_{w,b} frac{1}{left| left| w ight| ight|}$

$qquadqquadqquadqquadqquad s.t quad y_{i}left( w*x_{i}+b ight)geq1 quad i=1,2,3,....m$

但是上面目標函數是非凸函數，不方便我們求解問題，因為最大化 $frac{1}{left| left| w ight| ight|}$ 和最小化 $frac{1}{2} left| left| w ight| ight|^{2}$ 是等價的，而 $frac{1}{2} left| left| w ight| ight|^{2}$ 是凸函數，所以我們得到線性可分支持向量機的最優化問題

$qquadqquadqquadqquadqquadqquad min_{w,b}frac{1}{2} left| left| w ight| ight|^{2}$

$qquadqquadqquadqquadqquad s.t quad y_{i}left( w*x_{i}+b ight)geq1 quad i=1,2,3,....m$

這是一個凸二次規劃問題。而且在線性可分數據集上一定是存在最優解的。（證明可見李航老師的《統計學習方法》）

ps：凸優化問題定義是指以下形式最優化問題:

$qquadqquadqquadqquadqquadqquad min_{w} fleft( w ight)$

$qquadqquadqquadqquad s.t qquad g_{i}left( w ight)leq0 ，i=1,2,3...k$

$h_{i}left( w ight)=0 ，i=1,2,3...l$

其中，目標函數 $fleft( w ight)$ 和約束函數 $g_{i}left( w ight)$ 是 $R^{n}$ 上連續可微的凸函數，約束函數 $h_{i}left( w ight)$ 是 $R^{n}$ 上的仿射函數。『

仿射函數定義：若 $f(x)=w·x+b$ ， $win R^{n},bin R,xin R^{n}$ ,這稱 $f(x)$ 為仿射函數。

而當目標函數 $fleft( w ight)$ 是二次函數並且約束函數 $g_{i}left( w ight)$ 都為仿射函數時，上面的凸最優化就是一個凸二次規劃問題。

我們已經得到了最優化問題，那麼我們要是能得到最優解 $w^{*},b^{*}$ ，那麼我們就得到我們的分類模型 $fleft( x ight)=sign(w^{*}·x+b^{*})$ ，因為問題是凸二次規劃問題，現在有很多優化軟體都可以幫我們解決這個問題，但是數據集龐大，軟體就不能很好地勝任這個工作，下面一篇筆記將會利用數學方法將優化問題再次轉換為更容易求解的對偶問題。

參考：

《機器學習》周志華

《統計學習方法》李航