[機器學習] 支援向量機(SVM)

支援向量機（SVM）

支援向量機（support vector machines, SVM）是一種二分類模型，它的基本模型是定義在特征空間上的間隔最大的線性分類器

SVM的的學習政策就是間隔最大化，可形式化為一個求解凸二次規劃的問題

• 優點:泛化錯誤率低，計算開銷不大，結果易解釋
• 缺點:對參數調節和核函數的選擇敏感，原始分類器不加修改僅适用于處理二類問題

分隔超平面

上面将資料集分隔開來的直線稱為分隔超平面 ( separating hyperplane)

在上面給出的例子中，由于資料點都在二維平面上，所 以此時分隔超平面就隻是一條直線。但是，如果所給的資料集是三的，那麼此時用來分隔資料的就是一個平面

顯而易見，更高維的情況可以依此類推。如果資料集是1024維的，那麼就需要一個1023維的對象來對資料進行分隔，該對象被稱之為超平面(hyperplane)，也就是分類的決策邊界

分布在超平面一側的所有資料都屬于某個類别，而分布在另一側的所有資料則屬于另一個類别

線性可劃分

存在一個劃分超平面能将訓練樣本正确分類

而現實人物中，原始樣本空間内也許并不在一個能正确劃分兩類樣本的超平面，如下圖

對這樣的問題, 可将樣本從原始空間映射到一個更高維的特征空間, 使得樣本在這個特征空間内線性可分

例如在上圖中， 若将原始的二維空間映射到一個合适的三維空間, 就能找到一個合适的劃分超平面

比如想要将下圖的紅點和藍點變成線性可分的，那麼就将映射 y = x y = x y=x變成映射 y = x 2 y=x^2 y=x2，這樣就線性可分了

間隔(margin)

對于任意一個超平面，其兩側資料點都距離它有一個最小距離（垂直距離），這兩個最小距離的和就是間隔margin

Hard Margin SVM

當訓練資料線性可分時，通過硬間隔最大化，學習一個線性的分類器，即線性可分支援向量機

svm嘗試尋找一個最優決策邊界，距離兩個類别最近的樣本距離最遠

在樣本空間中，劃分超平面可用如下線性方程來描述：

w T x + b = 0 w^Tx+b=0 wTx+b=0

其中 w = ( w 1 ; w 2 ; … ; w d ) \boldsymbol{w}=\left(w_{1} ; w_{2} ; \ldots ; w_{d}\right) w=(w1​;w2​;…;wd​) 為法向量, 決定了超平面的方向; b b b 為位移項, 決定了超平面與原點之間的距離

樣本空間中任意點 x \boldsymbol{x} x 到超平面 ( w , b ) (\boldsymbol{w}, b) (w,b) 的距離可寫為

r = ∣ w T x + b ∣ ∥ w ∥ r=\frac{\left|\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}+b\right|}{\|\boldsymbol{w}\|} r=∥w∥∣∣​wTx+b∣∣​​

假設超平面 ( w , b ) (\boldsymbol{w}, b) (w,b) 能将訓練樣本正确分類, 即對于 ( x i , y i ) ∈ D , \left(\boldsymbol{x}_{i}, y_{i}\right) \in D, (xi​,yi​)∈D, 若 y i = y_{i}= yi​= + 1 , +1, +1, 則有 w T x i + b > 0 ; \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b>0 ; wTxi​+b>0; 若 y i = − 1 , y_{i}=-1, yi​=−1, 則有 w T x i + b < 0. \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b<0 . wTxi​+b<0. 令

{ w T x i + b ⩾ + 1 , y i = + 1 w T x i + b ⩽ − 1 , y i = − 1 \left\{\begin{array}{ll} \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \geqslant+1, & y_{i}=+1 \\ \boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b \leqslant-1, & y_{i}=-1 \end{array}\right. {wTxi​+b⩾+1,wTxi​+b⩽−1,​yi​=+1yi​=−1​

如上圖所示, 距離超平面最近的這幾個訓練樣本點使上式的等号成立, 它們被稱為**“支援向量”(support vector)**, 兩個異類支援向量到超平面的距離之和為

γ = 2 ∥ w ∥ \gamma=\frac{2}{\|\boldsymbol{w}\|} γ=∥w∥2​

顯然, 為了最大化間隔, 僅需最大化 ∥ w ∥ − 1 , \|\boldsymbol{w}\|^{-1}, ∥w∥−1, 這等價于最小化 ∥ w ∥ 2 \|\boldsymbol{w}\|^{2} ∥w∥2

min ⁡ w , b 1 2 ∥ w ∥ 2  s.t.  y i ( w T x i + b ) ⩾ 1 , i = 1 , 2 , … , m \begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array} minw,b​21​∥w∥2 s.t. yi​(wTxi​+b)⩾1,i=1,2,…,m​

這就是支援向量機(Support Vector Machine, 簡稱 SVM)的基本型

Soft Margin SVM

當訓練資料近似線性可分時，通過軟間隔最大化，學習一個線性支援向量機，又稱為軟間隔支援向量機

前面我們是假定所有的訓練樣本在樣本空間或特征空間中是嚴格線性可分的，即存在一個超平面能把不同類的樣本完全分開，然而現實任務中很難确定這樣的超平面（不管是線性超平面還是經過核變換到高維空間的超平面），是以引入松弛變量，允許一些樣本出錯，但我們希望出錯的樣本越少越好，是以松弛變量也有限制

具體來說，前面介紹的支援向量機的形式要求所有樣本滿足限制，即所有的樣本必須劃分正确，這稱為硬間隔，而軟間隔則是允許某些樣本不滿足限制

y i ( w T x i + b ) ⩾ 1 y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right) \geqslant 1 yi​(wTxi​+b)⩾1

如下圖紅色圈出了不滿足限制的樣本

當然, 在最大化間隔的同時, 不滿足限制的樣本應盡可能少. 于是, 優化目标可寫為

min ⁡ w , b 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ℓ 0 / 1 ( y i ( w T x i + b ) − 1 ) \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{0 / 1}\left(y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)-1\right) w,bmin​21​∥w∥2+Ci=1∑m​ℓ0/1​(yi​(wTxi​+b)−1)

其中 C > 0 C>0 C>0 是一個常數, ℓ 0 / 1 \ell_{0 / 1} ℓ0/1​ 是“0/1損失函數”

ℓ 0 / 1 ( z ) = { 1 ,  if  z < 0 0 ,  otherwise  \ell_{0 / 1}(z)=\left\{\begin{array}{ll} 1, & \text { if } z<0 \\ 0, & \text { otherwise } \end{array}\right. ℓ0/1​(z)={1,0,​ if z<0 otherwise ​

引入“松他變量" (slack variables) ξ i ⩾ 0 , \xi_{i} \geqslant 0, ξi​⩾0, 可将上式重寫為

min ⁡ w , b , ξ i 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ξ i \min _{\boldsymbol{w}, b, \xi_{i}} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \xi_{i} w,b,ξi​min​21​∥w∥2+Ci=1∑m​ξi​

對偶問題

現在的目标函數是二次的，限制條件是線性的，是以它是一個凸二次規劃問題

這個問題可以用現成的QP (Quadratic Programming) 優化包進行求解

此外，由于這個問題的特殊結構，還可以通過拉格朗日對偶性（Lagrange Duality）變換到對偶變量 (dual variable) 的優化問題，即通過求解與原問題等價的對偶問題（dual problem）得到原始問題的最優解，這就是線性可分條件下支援向量機的對偶算法

這樣做的優點在于：

• 一者對偶問題往往更容易求解
• 二者可以自然的引入核函數，進而推廣到非線性分類問題

具體來說, 對每條限制添加拉格朗日乘子 α i ⩾ 0 , \alpha_{i} \geqslant 0, αi​⩾0, 則該問題的拉格朗日函數可寫為

L ( w , b , α ) = 1 2 ∥ w ∥ 2 + ∑ i = 1 m α i ( 1 − y i ( w T x i + b ) ) L(\boldsymbol{w}, b, \boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^{2}+\sum_{i=1}^{m} \alpha_{i}\left(1-y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \boldsymbol{x}_{i}+b\right)\right) L(w,b,α)=21​∥w∥2+i=1∑m​αi​(1−yi​(wTxi​+b))

其中 α = ( α 1 ; α 2 ; … ; α m ) . \alpha=\left(\alpha_{1} ; \alpha_{2} ; \ldots ; \alpha_{m}\right) . α=(α1​;α2​;…;αm​). 令 L ( w , b , α ) L(\boldsymbol{w}, b, \boldsymbol{\alpha}) L(w,b,α) 對 w \boldsymbol{w} w 和 b b b 的偏導為零可得

w = ∑ i = 1 m α i y i x i 0 = ∑ i = 1 m α i y i \begin{aligned} \boldsymbol{w} &=\sum_{i=1}^{m} \alpha_{i} y_{i} \boldsymbol{x}_{i} \\ 0 &=\sum_{i=1}^{m} \alpha_{i} y_{i} \end{aligned} w0​=i=1∑m​αi​yi​xi​=i=1∑m​αi​yi​​

即可将 L ( w , b , α ) L(\boldsymbol{w}, b, \boldsymbol{\alpha}) L(w,b,α) 中的 w \boldsymbol{w} w 和 b b b 消去, 就得到的目标函數對偶問題

max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j x i T x j \max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j} αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​xiT​xj​

非線形SVM

當訓練資料線性不可分時，通過使用核技巧(kernel trick)及軟間隔最大化，學習非線形支援向量機

非線性SVM算法原理

對于輸入空間中的非線性分類問題，可以通過非線性變換将它轉化為某個維特征空間中的線性分類問題，在高維特征空間中學習線性支援向量機

令 ϕ ( x ) \phi(x) ϕ(x) 表示将 x x x 映射後的特征向量, 于是, 在特征空間中劃分超平面所對

應的模型可表示為

f ( x ) = w T ϕ ( x ) + b f(\boldsymbol{x})=\boldsymbol{w}^{\mathrm{T}} \phi(\boldsymbol{x})+b f(x)=wTϕ(x)+b

其中 w \boldsymbol{w} w 和 b b b 是模型參數，有

min ⁡ w , b 1 2 ∥ w ∥ 2  s.t.  y i ( w T ϕ ( x i ) + b ) ⩾ 1 , i = 1 , 2 , … , m \begin{array}{l} \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2} \\ \text { s.t. } y_{i}\left(\boldsymbol{w}^{\mathrm{T}} \phi\left(\boldsymbol{x}_{i}\right)+b\right) \geqslant 1, \quad i=1,2, \ldots, m \end{array} minw,b​21​∥w∥2 s.t. yi​(wTϕ(xi​)+b)⩾1,i=1,2,…,m​

其對偶問題是

max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j ϕ ( x i ) T ϕ ( x j ) \max _{\boldsymbol{\alpha}} \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \phi\left(\boldsymbol{x}_{i}\right)^{\mathrm{T}} \phi\left(\boldsymbol{x}_{j}\right) αmax​i=1∑m​αi​−21​i=1∑m​j=1∑m​αi​αj​yi​yj​ϕ(xi​)Tϕ(xj​)

 s.t.  ∑ i = 1 m α i y i = 0 α i ⩾ 0 , i = 1 , 2 , … , m \begin{array}{ll} \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array}  s.t. ​∑i=1m​αi​yi​=0αi​⩾0,i=1,2,…,m​

由于線上性支援向量機學習的對偶問題裡，目标函數和分類決策函數都隻涉及執行個體和執行個體之間的内積，是以不需要顯式地指定非線性變換，而是用核函數替換當中的内積

有了這樣的函數，我們就不必直接去計算高維甚至無窮維特征空間中的内積，于是上式可重寫為

max ⁡ α ∑ i = 1 m α i − 1 2 ∑ i = 1 m ∑ j = 1 m α i α j y i y j κ ( x i , x j )  s.t.  ∑ i = 1 m α i y i = 0 α i ⩾ 0 , i = 1 , 2 , … , m \begin{array}{ll} \max _{\boldsymbol{\alpha}} & \sum_{i=1}^{m} \alpha_{i}-\frac{1}{2} \sum_{i=1}^{m} \sum_{j=1}^{m} \alpha_{i} \alpha_{j} y_{i} y_{j} \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \sum_{i=1}^{m} \alpha_{i} y_{i}=0 \\ & \alpha_{i} \geqslant 0, \quad i=1,2, \ldots, m \end{array} maxα​ s.t. ​∑i=1m​αi​−21​∑i=1m​∑j=1m​αi​αj​yi​yj​κ(xi​,xj​)∑i=1m​αi​yi​=0αi​⩾0,i=1,2,…,m​

常見的核函數

 線性核  κ ( x i , x j ) = x i T x j  多項式核  κ ( x i , x j ) = ( x i T x j ) d d ⩾ 1  為多項式的次數   高斯核  κ ( x i , x j ) = exp ⁡ ( − ∥ x i − x j ∥ 2 2 σ 2 ) σ > 0  為高斯核的帶寬(width)   拉普拉斯核  κ ( x i , x j ) = exp ⁡ ( − ∥ x i − x j ∥ σ ) σ > 0  Sigmoid 核  κ ( x i , x j ) = tanh ⁡ ( β x i T x j + θ )  tanh 為雙曲正切函數,  β > 0 , θ < 0 \begin{aligned} &\text { 線性核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\\ &\text { 多項式核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\left(\boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}\right)^{d} \quad d \geqslant 1 \text { 為多項式的次數 }\\ &\text { 高斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|^{2}}{2 \sigma^{2}}\right) \quad \sigma>0 \text { 為高斯核的帶寬(width) }\\ &\text { 拉普拉斯核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\exp \left(-\frac{\left\|\boldsymbol{x}_{i}-\boldsymbol{x}_{j}\right\|}{\sigma}\right) \quad \sigma>0\\ &\text { Sigmoid 核 } \quad \kappa\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right)=\tanh \left(\beta \boldsymbol{x}_{i}^{\mathrm{T}} \boldsymbol{x}_{j}+\theta\right) \quad \text { tanh 為雙曲正切函數, } \beta>0, \theta<0 \end{aligned} ​ 線性核 κ(xi​,xj​)=xiT​xj​ 多項式核 κ(xi​,xj​)=(xiT​xj​)dd⩾1 為多項式的次數  高斯核 κ(xi​,xj​)=exp(−2σ2∥xi​−xj​∥2​)σ>0 為高斯核的帶寬(width)  拉普拉斯核 κ(xi​,xj​)=exp(−σ∥xi​−xj​∥​)σ>0 Sigmoid 核 κ(xi​,xj​)=tanh(βxiT​xj​+θ) tanh 為雙曲正切函數, β>0,θ<0​

二分類擴充到多分類問題

SVM 擴充可解決多個類别分類問題

one-vs-rest

對于每個類，有一個目前類和其他類的二類分類器（one-vs-rest）

将多分類問題轉化為 n 個二分類問題

svm解決回歸問題

現在我們來考慮回歸問題，傳統回歸模型通常直接基于模型輸出 f ( x ) f(x) f(x) 與真實輸出 y y y 之 間的差别來計算損失, 當且僅當 f ( x ) f(\boldsymbol{x}) f(x) 與 y y y 完全相同時, 損失才為零

與此不同 , , , **支援向量回歸(Support Vector Regression, 簡稱 SVR)**假設我們能容忍 f ( x ) f(x) f(x) 與 y y y 之間最多有 ϵ \epsilon ϵ 的偏差, 即僅當 f ( x ) f(\boldsymbol{x}) f(x) 與 y y y 之間的差别絕對值大于 ϵ \epsilon ϵ 時才計算損失

如圖所示, 這相當于以 f ( x ) f(x) f(x) 為中心, 建構了一個寬度為 2 ϵ 2 \epsilon 2ϵ 的間隔帶, 若訓練樣本落入此間隔帶, 則認為是被預測正确的

于是, SVR 問題可形式化為

min ⁡ w , b 1 2 ∥ w ∥ 2 + C ∑ i = 1 m ℓ c ( f ( x i ) − y i ) \min _{\boldsymbol{w}, b} \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum_{i=1}^{m} \ell_{c}\left(f\left(\boldsymbol{x}_{i}\right)-y_{i}\right) w,bmin​21​∥w∥2+Ci=1∑m​ℓc​(f(xi​)−yi​)

其中 C C C 為正則化常數, ℓ ϵ \ell_{\epsilon} ℓϵ​ 是圖 6.7 所示的 ϵ \epsilon ϵ -不敏感損失 ( ϵ (\epsilon (ϵ -insensitive loss ) ) ) 函數

ℓ ϵ ( z ) = { 0 ,  if  ∣ z ∣ ⩽ ϵ ∣ z ∣ − ϵ ,  otherwise  \ell_{\epsilon}(z)=\left\{\begin{array}{ll} 0, & \text { if }|z| \leqslant \epsilon \\ |z|-\epsilon, & \text { otherwise } \end{array}\right. ℓϵ​(z)={0,∣z∣−ϵ,​ if ∣z∣⩽ϵ otherwise ​

參考

機器學習算法（一）SVM

機器學習-周志華

支援向量機（SVM）——原理篇

Machine Learning in Action by Peter Harrington