學習筆記【機器學習重點與實戰】——6 支援向量機原理

1 支援向量機

支援向量機(support vector machines，SVM)是一種二類分類模型。它的基本模型是定義在特征空間上的間隔最大的線性分類器，間隔最大使它有别于感覺機；支援向量機還包括核技巧，這使它成為實質上的非線性分類器。支援向量機的學習政策就是間隔最大化，可形式化為一個求解凸二次規劃(convex quadratic programming)的問題，也等價于正則化的合頁損失函數的最小化問題。支援向量機的學習算法是求解凸二次規劃的最優化算法。

支援向量機學習方法包含建構由簡至繁的模型：線性可分支援向量機(linear support vector machine in linearly separable case)、線性支援向量機(linear support vector machine)及非線性支援向量機(non-linear vector machine)。簡單模型是複雜模型的基礎，也是複雜模型的特殊情況。當訓練資料線性可分時，通過硬間隔最大化(hard margin maximization)，學習一個線性的分類器，即線性可分支援向量機，又稱為硬間隔支援向量機；當訓練資料近似線性可分時，通過軟間隔最大化(soft margn maximization)，也學習一個線性的分類器，即線性支援向量機，又稱為軟間隔支援向量機；當訓練資料線性不可分時，通過使用核技巧(kernel trick)及軟間隔最大化，學習非線性支援向量機。

——《統計學習方法》 P95 P 95

優點：泛化錯誤率低，計算開銷不大，結果易解釋。

缺點：對參數調節和核函數的選擇敏感，原始分類器不加修改僅适用于處理二分類問題。

适用資料類型：數值型和标稱型資料。

——《機器學習實戰》 P89 P 89

2 線性可分支援向量機

給定線型可分訓練資料集，通過間隔最大化或等價地求解相應的凸二次規劃問題學習得到的分離超平面為：

ωT⋅Φ(x)+b=0 ω T · Φ ( x ) + b = 0

分類決策函數為：

f(x)=sign(ωT⋅Φ(x)+b) f ( x ) = s i g n ( ω T · Φ ( x ) + b )

該決策函數稱為線型可分支援向量機。

Φ(x) Φ ( x ) 是某個确定的特征空間轉換函數，作用是将x映射到（更高的）次元。最簡單的為 Φ(x)=x Φ ( x ) = x 。

2.1 原理及定義

對于上圖所示的二分類問題，線性可分支援向量機學習的目标是在特征空間中找到一個分離超平面，然而存在無窮個分離超平面可将兩類資料正确分開；線性可分支援向量機則是利用間隔最大化求最優分離超平面，解是唯一的，圖中的紅色直線即為求解得到的最優分離超平面，将執行個體分到不同的類。

線性可分支援向量機中的間隔最大化又稱為硬間隔最大化（與下面小節的軟間隔最大化相對應）。

間隔最大化的直覺解釋是：對訓練資料集找到幾何間隔最大的超平面意味着以充分大的确信度對訓練資料進行分類。也就是說，不僅将正負執行個體點分開，而且對最難分的執行個體點（離超平面最近的點）也有足夠大的确信度将它們分開。這樣的超平面應該對未知的新執行個體有很好的分類預測能力。

支援向量（support vector）：訓練資料集的樣本點中與分離超平面距離最近的樣本點的執行個體。上圖中兩條虛線上的三個點即為支援向量。限制條件為：

yi(ωT⋅Φ(x)i+b)−1=0 y i ( ω T · Φ ( x ) i + b ) − 1 = 0

間隔邊界：支援向量所在的兩個超平面。

間隔（margin）：間隔邊界之間的距離。其值為 2||ω|| 2 | | ω | | 。

在決定分離超平面時隻有支援向量起作用，而其他執行個體點并不起作用、如果移動支援向量将改變所求的解；但是如果在間隔邊界以外移動其他執行個體點，甚至去掉這些點，則解是不會改變的。由于支援向量在确定分離超平面中起着決定性作用，是以将這種分類模型稱為支援向量機。支援向量的個數一般很少．是以支援向量機由很少的“重要的”訓練樣本确定。

2.2 算法步驟

輸入：線型可分訓練集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，

其中 xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N; x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N ;

輸出：分離超平面和分類決策樹

（1）構造并求解限制最優化問題

minαs.t.αi≥0,12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi∑i=1Nαiyi=0i=1,2,...,N(3)(4)(5) (3) min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i · x j ) − ∑ i = 1 N α i (4) s . t . ∑ i = 1 N α i y i = 0 (5) α i ≥ 0 , i = 1 , 2 , . . . , N

求得最優解 α∗=(α∗1,α∗2,...,α∗N)T α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T

（2）計算

ω∗=∑i=1Nα∗iyixi ω ∗ = ∑ i = 1 N α i ∗ y i x i

并選擇 α∗ α ∗ 的一個正分量 α∗>0 α ∗ > 0 ，計算

b∗=yi−∑i=1Nα∗iyi(xi⋅xj) b ∗ = y i − ∑ i = 1 N α i ∗ y i ( x i · x j )

（3）求得分離超平面

ω∗⋅x+b∗=0 ω ∗ · x + b ∗ = 0

分類決策函數：

f(x)=sign(ω∗⋅x+b∗) f ( x ) = s i g n ( ω ∗ · x + b ∗ )

線上型可分支援向量機中， ω∗ ω ∗ 和 b∗ b ∗ 隻依賴于訓練資料中對應于 α∗>0 α ∗ > 0 的樣本點 (xi,yi) ( x i , y i ) ，而其它樣本點對 ω∗ ω ∗ 和 b∗ b ∗ 沒有影響。則訓練資料中對應于 α∗>0 α ∗ > 0 的執行個體點 xi∈Rn x i ∈ R n 稱為支援向量。

3 線性支援向量機

3.1 原理及定義

對于線性可分問題，上述線性可分支援向量機的學習（硬間隔最大化）算法是完美的。但是，訓練資料集線性可分是理想的情形。在現實問題中，訓練資料集往往是線性不可分的，即在樣本中出現噪聲或特異點。這就需要将硬間隔最大化，改為軟間隔最大化，允許支援向量機在一些樣本上出錯。

對每個樣本點 (xi,yi) ( x i , y i ) 引進松弛變量 ζi≥0 ζ i ≥ 0 ，使得函數間隔加上松弛變量≥1。限制條件變為：

yi(ω⋅xi+b)≥1−ζi y i ( ω · x i + b ) ≥ 1 − ζ i

同時，對每個松弛變量 ζi ζ i ，支付一個代價 ζi ζ i 。目标函數由原來的 12||ω||2 1 2 | | ω | | 2 變成：

12||ω||2+C∑i=1Nζi 1 2 | | ω | | 2 + C ∑ i = 1 N ζ i

這裡，C>0稱為懲罰參數，一般由應用問題決定。

C越大，訓練精度會變高，有可能過拟合，過渡帶寬度越來越小。

軟間隔的支援向量或者在間隔邊界上，或者在間隔邊界與分離超平面之間，或者在分離超平面誤分一側。若 α∗i<C α i ∗ < C ，則 ζi=0 ζ i = 0 ，支援向量 xi x i 恰好落在間隔邊界上；若 α∗i=C α i ∗ = C ， 0<ζi<1 0 < ζ i < 1 ，則分類正确， xi x i 在間隔邊界與分離超平面之間；若 α∗i=C α i ∗ = C ， ζi=1 ζ i = 1 ，則在分離超平面上；若 α∗i=C α i ∗ = C ， ζi>1 ζ i > 1 ，則 xi x i 位于分離超平面誤分一側。

3.2 損失函數

然而，0/1損失函數非凸、非連續，數學性質不太好，使得 ζi ζ i 不易直接求解。于是，人們通常用其他一些函數來代替 0/1損失函數， 稱為”替代損失” (surrogate loss)。替代損失函數一般具有較好的數學性質，如它們通常是凸的連續函數且是 0/1損失函數的上界。下圖給出了三種常用的替代損失函數：

hinge損失：lhinge(z)=max(0,1−z)指數損失（exponentialloss）：lexp(z)=exp(−z)對率損失（logisticloss）：llog(z)=log(1+exp(−z))(6)(7)(8) (6) h i n g e 損 失 ： l h i n g e ( z ) = m a x ( 0 , 1 − z ) (7) 指 數 損 失 （ e x p o n e n t i a l l o s s ） ： l e x p ( z ) = e x p ( − z ) (8) 對 率 損 失 （ l o g i s t i c l o s s ） ： l l o g ( z ) = l o g ( 1 + e x p ( − z ) )

由圖可知，”替代損失”不僅要分類正确，而且确信度足夠高時損失才是0，也就是說，對學習有更高的要求。

3.3 算法步驟

輸入：線型可分訓練集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，

其中 xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N; x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N ;

輸出：分離超平面和分類決策樹

（1）選擇懲罰參數C>0，構造并求解凸二次規劃問題

minαs.t.12∑i=1N∑j=1Nαiαjyiyj(xi⋅xj)−∑i=1Nαi∑i=1Nαiyi=00≤αi≤C,i=1,2,...,N(9)(10)(11) (9) min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j ( x i · x j ) − ∑ i = 1 N α i (10) s . t . ∑ i = 1 N α i y i = 0 (11) 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N

求得最優解 α∗=(α∗1,α∗2,...,α∗N)T α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T

（2）計算

ω∗=∑i=1Nα∗iyixi ω ∗ = ∑ i = 1 N α i ∗ y i x i

并選擇 α∗ α ∗ 的一個正分量 C>α∗>0 C > α ∗ > 0 ，計算

b∗=yi−∑i=1Nα∗iyi(xi⋅xj) b ∗ = y i − ∑ i = 1 N α i ∗ y i ( x i · x j )

（3）求得分離超平面

ω∗⋅x+b∗=0 ω ∗ · x + b ∗ = 0

分類決策函數：

f(x)=sign(ω∗⋅x+b∗) f ( x ) = s i g n ( ω ∗ · x + b ∗ )

4 非線性支援向量機

4.1 原理及定義

前面兩個算法都是假設訓練樣本是線性可分的，即存在一個分離超平面能将訓練樣本正确分類。然而在現實任務中，原始樣本空間内也許并不存在一個能正确劃分兩類樣本的超平面。例如下圖中的” 異或 ” 問題就不是線性可分的。

對這樣的問題，可将樣本從原始空間映射到一個更高維的特征空間，使得樣本在這個特征空間内線性可分。例如在上圖中，若将原始的二維空間映射到一個合适的三維空間 ，就能找到一個合适的分離超平面。幸運的是，如果原始空間是有限維，即屬性數有限，那麼一定存在一個高維特征空間使樣本可分。

用線性分類方法求解非線性分類問題分為兩步：首先使用一個變換将原空間的資料映射到新空間；然後在新空間裡用線性分類學習方法從訓練資料中學習分類模型。

4.2 核函數

核技巧的做法是，在學習與預測中隻定義核函數 K(x,z) K ( x , z ) ，而不顯式地定義映射函數。

即将上面優化目标函數中的 (xi⋅xj) ( x i · x j ) 替換為 K(xi⋅xj) K ( x i · x j ) 。

核技巧巧妙的利用線性分類學習方法和核函數解決非線性問題。在實際應用中，往往以各領域知識直接選擇核函數，核函數的選擇的有效應需要通過實驗驗證。

常用核函數如下表：

名稱	表達式	參數
線性核	K(xi,xj)=xTixj K ( x i , x j ) = x i T x j
多項式核	K(xi,xj)=(xTixj)d K ( x i , x j ) = ( x i T x j ) d	d≥1 d ≥ 1 為多項式的次數
高斯核	K(xi,xj)=exp(−||xi−xj||22σ2) K ( x i , x j ) = e x p ( − | | x i − x j | | 2 2 σ 2 )	σ>0 σ > 0 為高斯核的帶寬 (width)
拉普拉斯核	K(xi,xj)=exp(−||xi−xj||σ) K ( x i , x j ) = e x p ( − | | x i − x j | | σ )	σ>0 σ > 0
Sigmoid 核	K(xi,xj)=tanh(βxTixj+θ) K ( x i , x j ) = t a n h ( β x i T x j + θ )	tanh 為雙曲正切函數， β>0,θ<0 β > 0 , θ < 0

此外，還可通過函數組合得到，例如：

• 若 K1 K 1 和 K2 K 2 為核函數，則對于任意正數 γ1 γ 1 、 γ2 γ 2 ，其線性組合

γ1K1+γ2K2 γ 1 K 1 + γ 2 K 2

也是核函數；

• 若 K1 K 1 和 K2 K 2 為核函數，則而核函數的直積

K1⊙K2(x,z)=K1(x,z)K2(x,z) K 1 ⊙ K 2 ( x , z ) = K 1 ( x , z ) K 2 ( x , z )

也是核函數；

• 若 K1 K 1 為核函數，則對于任意函數 g(x) g ( x )

K(x,z)=g(x)K1(x,z)g(z) K ( x , z ) = g ( x ) K 1 ( x , z ) g ( z )

也是核函數。

4.3 算法步驟

輸入：訓練集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，其中

xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N; x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N ;

輸出：分類決策樹

（1）選擇适當的核函數 K(x,z) K ( x , z ) 和适當的懲罰參數C>0，構造并求解最優化問題

minαs.t.12∑i=1N∑j=1NαiαjyiyjK(xi⋅xj)−∑i=1Nαi∑i=1Nαiyi=00≤αi≤C,i=1,2,...,N(12)(13)(14) (12) min α 1 2 ∑ i = 1 N ∑ j = 1 N α i α j y i y j K ( x i · x j ) − ∑ i = 1 N α i (13) s . t . ∑ i = 1 N α i y i = 0 (14) 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N

求得最優解 α∗=(α∗1,α∗2,...,α∗N)T α ∗ = ( α 1 ∗ , α 2 ∗ , . . . , α N ∗ ) T

（2）選擇 α∗ α ∗ 的一個正分量 C>α∗>0 C > α ∗ > 0 ，計算

b∗=yi−∑i=1Nα∗iyiK(xi⋅xj) b ∗ = y i − ∑ i = 1 N α i ∗ y i K ( x i · x j )

（3）構造決策函數：

f(x)=sign(∑i=1Nα∗iyiK(x⋅xi)+b∗) f ( x ) = s i g n ( ∑ i = 1 N α i ∗ y i K ( x · x i ) + b ∗ )

5 序列最小優化算法-SMO

5.1 原理及定義

支援向量機的學習問題可以形式化為求解凸二次規劃問題。這樣的凸二次規劃問題具有全局最優解，并且有許多最優化算法可以用于這一問題的求解，但是當訓練樣本容量很大時，這些算法往往變得非常低效，以緻無法使用。是以，如何高效地實作支援向量機學習就成為一個重要的問題。

1998年Platt提出序列最小最優化(sequential minimal optimization，SMO)算法。該算法是支援向量機學習的一種快速算法，其特點是不斷地将原二次規劃問題分解為隻有兩個變量的二次規劃子問題，并對子問題進行解析求解，直到所有變量滿足KKT條件為止。這樣通過啟發式的方法得到原二次規劃問題的最優解。因為子問題有解析解，是以每次計算子問題都很快，雖然計算子問題次數很多，但在總體上還是高效的。

5.2 算法步驟

輸入：訓練集 T={(x1,y1),(x2,y2),...,(xN,yN)} T = { ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x N , y N ) } ，

其中 xi∈X=Rn,yi∈Y={−1,+1},i=1,2,...,N x i ∈ X = R n , y i ∈ Y = { − 1 , + 1 } , i = 1 , 2 , . . . , N ，精度 ε ；

輸出：近似解 α^ α ^

（1）取初值 α(0)=0 α ( 0 ) = 0 ，令 k=0 k = 0 ；

（2）選取優化變量 α(k)1,α(k)2 α 1 ( k ) , α 2 ( k ) ，解析求解兩個變量的最優化問題

minα1,α2W(α1,α2)=s.t.12K11α21+12K22α22+y1y2K12α1α2−(α1+α2)+y1α1∑i=3NyiαiKi1+y2α2∑i=3NyiαiKi2α1y1+α2y2=∑i=3Nαiyi=ζ0≤αi≤C,i=1,2(15)(16)(17)(18) (15) min α 1 , α 2 W ( α 1 , α 2 ) = 1 2 K 11 α 1 2 + 1 2 K 22 α 2 2 + y 1 y 2 K 12 α 1 α 2 (16) − ( α 1 + α 2 ) + y 1 α 1 ∑ i = 3 N y i α i K i 1 + y 2 α 2 ∑ i = 3 N y i α i K i 2 (17) s . t . α 1 y 1 + α 2 y 2 = ∑ i = 3 N α i y i = ζ (18) 0 ≤ α i ≤ C , i = 1 , 2

求得最優解 α(k+1)1,α(k+1)2 α 1 ( k + 1 ) , α 2 ( k + 1 ) ，更新 α α 為 α(k+1) α ( k + 1 ) ；

（3）若在精度 ε 範圍内滿足停機條件

∑i=1Nαiyi=00≤αi≤C,i=1,2,...,Nyi⋅g(xi)=⎧⎩⎨≥1,{xi|αi=0}=1,{xi|0≤αi≤C}≤1,{xi|αi=C}(19)(20)(21) (19) ∑ i = 1 N α i y i = 0 (20) 0 ≤ α i ≤ C , i = 1 , 2 , . . . , N (21) y i · g ( x i ) = { ≥ 1 , { x i | α i = 0 } = 1 , { x i | 0 ≤ α i ≤ C } ≤ 1 , { x i | α i = C }

其中，

g(xi)=∑j=1NαjyjK(xj,xi)+b g ( x i ) = ∑ j = 1 N α j y j K ( x j , x i ) + b

則轉（4）；否則令 k=k+1 k = k + 1 ，轉（2）；

（4）取 α^=α(k+1) α ^ = α ( k + 1 )

6 支援向量回歸

對樣本 (x,y) ，傳統回歸模型通常直接基于模型輸出 f(x) 與真實輸出 y 之間的差别來計算損失，當且僅當 f(x) 與 y 完全相同時，損失才為零。與此不同，支援向量回歸 (Support Vector Regression，簡稱 SVR)假設我們能容忍 f(x) 與 y 之間最多有 ε 的偏差，即僅當 f(x) 與 y 之間的差别絕對值大于 ε 時才計算損失。如下圖所示，這相當于以 f(x) 為中心，建構了一個寬度為 2ε 的間隔帶，若訓練樣本落入此間隔帶，則認為是被預測正确的。

引入松弛變量ζ_i和\hatζ_i，SVR可形式化為最優化問題：

mins.t.12||ω||2+C∑i=1N(ζi+ζ^i)f(xi)−yi≤ε+ζi,yi−f(xi)≤ε+ζ^i,ζi≥0,ζ^i≥0,i=1,2,...,N(22)(23)(24)(25) (22) m i n 1 2 | | ω | | 2 + C ∑ i = 1 N ( ζ i + ζ ^ i ) (23) s . t . f ( x i ) − y i ≤ ε + ζ i , (24) y i − f ( x i ) ≤ ε + ζ ^ i , (25) ζ i ≥ 0 , ζ ^ i ≥ 0 , i = 1 , 2 , . . . , N

7 參考

1. 機器學習更新版視訊 - 鄒博
2. 《統計學習方法》第7章 支援向量機
3. 《機器學習實戰》第6章 支援向量機
4. 《機器學習 - 周志華》第6章 支援向量機

===========文檔資訊============

學習筆記由部落客整理編輯，供非商用學習交流用

如本文涉及侵權，請随時留言部落客，必妥善處置

版權聲明：非商用自由轉載-保持署名-注明出處

署名(BY) ：dkjkls（dkj卡洛斯）

文章出處：http://blog.csdn.net/dkjkls