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

03-06

SVM簡介

支持向量機（support vector machines, SVM）是一種二分類模型，它的基本模型是定義在特徵空間上的間隔最大的線性分類器，間隔最大使它有別於感知機；SVM還包括核技巧，這使它成為實質上的非線性分類器。SVM的的學習策略就是間隔最大化，可形式化為一個求解凸二次規劃的問題，也等價於正則化的合頁損失函數的最小化問題。SVM的的學習演算法就是求解凸二次規劃的最優化演算法。

SVM演算法原理

SVM學習的基本想法是求解能夠正確劃分訓練數據集並且幾何間隔最大的分離超平面。如下圖所示， $oldsymbol{w}cdot x+b=0$ 即為分離超平面，對於線性可分的數據集來說，這樣的超平面有無窮多個（即感知機），但是幾何間隔最大的分離超平面卻是唯一的。

在推導之前，先給出一些定義。假設給定一個特徵空間上的訓練數據集

$T=left{ left( oldsymbol{x}_1,y_1 ight) ,left( oldsymbol{x}_1,y_1 ight) ,...,left( oldsymbol{x}_N,y_N ight) ight}$

其中， $oldsymbol{x}_iin mathbb{R}^n$ ， $y_iin left{ +1,-1 ight} ,i=1,2,...N$ ， $x_i$ 為第 $i$ 個特徵向量， $y_i$ 為類標記，當它等於+1時為正例；為-1時為負例。再假設訓練數據集是線性可分的。

幾何間隔：對於給定的數據集 $T$ 和超平面 $wcdot x+b=0$ ，定義超平面關於樣本點 $left( x_i,y_i ight)$ 的幾何間隔為

$gamma _i=y_ileft( frac{oldsymbol{w}}{lVert oldsymbol{w} Vert}cdot oldsymbol{x}_{oldsymbol{i}}+frac{b}{lVert oldsymbol{w} Vert} ight)$

超平面關於所有樣本點的幾何間隔的最小值為

$gamma =underset{i=1,2...,N}{min}gamma _i$

實際上這個距離就是我們所謂的支持向量到超平面的距離。

根據以上定義，SVM模型的求解最大分割超平面問題可以表示為以下約束最優化問題

$underset{oldsymbol{w,}b}{max} gamma$

$s.t. y_ileft( frac{oldsymbol{w}}{lVert oldsymbol{w} Vert}cdot oldsymbol{x}_{oldsymbol{i}}+frac{b}{lVert oldsymbol{w} Vert} ight) ge gamma ,i=1,2,...,N$

將約束條件兩邊同時除以 $gamma$ ，得到

$y_ileft( frac{oldsymbol{w}}{lVert oldsymbol{w} Vert gamma}cdot oldsymbol{x}_{oldsymbol{i}}+frac{b}{lVert oldsymbol{w} Vert gamma} ight) ge 1$

因為 $lVert oldsymbol{w} Vert ext{，}gamma$ 都是標量，所以為了表達式簡潔起見，令

$oldsymbol{w}=frac{oldsymbol{w}}{lVert oldsymbol{w} Vert gamma}$

$b=frac{b}{lVert oldsymbol{w} Vert gamma}$

得到

$y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) ge 1, i=1,2,...,N$

又因為最大化 $gamma$ ，等價於最大化 $frac{1}{lVert oldsymbol{w} Vert}$ ，也就等價於最小化 $frac{1}{2}lVert oldsymbol{w} Vert ^2$ （ $frac{1}{2}$ 是為了後面求導以後形式簡潔，不影響結果），因此SVM模型的求解最大分割超平面問題又可以表示為以下約束最優化問題

$underset{oldsymbol{w,}b}{min} frac{1}{2}lVert oldsymbol{w} Vert ^2$

$s.t. y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) ge 1, i=1,2,...,N$

這是一個含有不等式約束的凸二次規劃問題，可以對其使用拉格朗日乘子法得到其對偶問題（dual problem）。

首先，我們將有約束的原始目標函數轉換為無約束的新構造的拉格朗日目標函數

$Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight) =frac{1}{2}lVert oldsymbol{w} Vert ^2-sum_{i=1}^N{alpha _ileft( y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) -1 ight)}$

其中 $alpha _i$ 為拉格朗日乘子，且 $alpha _ige 0$ 。現在我們令

$heta left( oldsymbol{w} ight) =underset{alpha _{_i}ge 0}{max} Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight)$

當樣本點不滿足約束條件時，即在可行解區域外：

$y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) <1$

此時，將 $alpha _i$ 設置為無窮大，則 $heta left( oldsymbol{w} ight)$ 也為無窮大。

當滿本點滿足約束條件時，即在可行解區域內：

$y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) ge 1$

此時， $heta left( oldsymbol{w} ight)$ 為原函數本身。於是，將兩種情況合併起來就可以得到我們新的目標函數

$heta left( oldsymbol{w} ight) =egin{cases} frac{1}{2}lVert oldsymbol{w} Vert ^2 ,oldsymbol{x}in ext{可行區域}\ +infty ,oldsymbol{x}in ext{不可行區域}\ end{cases}$

於是原約束問題就等價於

$underset{oldsymbol{w,}b}{min} heta left( oldsymbol{w} ight) =underset{oldsymbol{w,}b}{min}underset{alpha _ige 0}{max} Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight) =p^*$

看一下我們的新目標函數，先求最大值，再求最小值。這樣的話，我們首先就要面對帶有需要求解的參數 $oldsymbol{w}$ 和 $b$ 的方程，而 $alpha _i$ 又是不等式約束，這個求解過程不好做。所以，我們需要使用拉格朗日函數對偶性，將最小和最大的位置交換一下，這樣就變成了：

$underset{alpha _ige 0}{max}underset{oldsymbol{w,}b}{min} Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight) =d^*$

要有 $p^*=d^*$ ，需要滿足兩個條件：

① 優化問題是凸優化問題

② 滿足KKT條件

首先，本優化問題顯然是一個凸優化問題，所以條件一滿足，而要滿足條件二，即要求

$egin{cases} alpha _ige 0\ y_ileft( oldsymbol{w}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) -1ge 0\ alpha _ileft( y_ileft( oldsymbol{w}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) -1 ight) =0\ end{cases}$

為了得到求解對偶問題的具體形式，令 $Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight)$ 對 $oldsymbol{w}$ 和 $b$ 的偏導為0，可得

$oldsymbol{w}=sum_{i=1}^N{alpha _iy_ioldsymbol{x}_{oldsymbol{i}}}$

$sum_{i=1}^N{alpha _iy_i}=0$

將以上兩個等式帶入拉格朗日目標函數，消去 $oldsymbol{w}$ 和 $b$ ，得

$Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight) =frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}-sum_{i=1}^N{alpha _iy_ileft( left( sum_{j=1}^N{alpha _jy_joldsymbol{x}_{oldsymbol{j}}} ight) cdot oldsymbol{x}_{oldsymbol{i}}+b ight) +}sum_{i=1}^N{alpha _i}$

$=-frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}+sum_{i=1}^N{alpha _i}$

即

$underset{oldsymbol{w,}b}{min} Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight) =-frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}+sum_{i=1}^N{alpha _i}$

求 $underset{oldsymbol{w,}b}{min} Lleft( oldsymbol{w,}b,oldsymbol{alpha } ight)$ 對 $oldsymbol{alpha }$ 的極大，即是對偶問題

$underset{oldsymbol{alpha }}{max} -frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}+sum_{i=1}^N{alpha _i}$

$s.t. sum_{i=1}^N{alpha _iy_i}=0$

$alpha _ige 0, i=1,2,...,N$

把目標式子加一個負號，將求解極大轉換為求解極小

$underset{oldsymbol{alpha }}{min} frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}-sum_{i=1}^N{alpha _i}$

$s.t. sum_{i=1}^N{alpha _iy_i}=0$

$alpha _ige 0, i=1,2,...,N$

現在我們的優化問題變成了如上的形式。對於這個問題，我們有更高效的優化演算法，即序列最小優化（SMO）演算法。這裡暫時不展開關於使用SMO演算法求解以上優化問題的細節，下一篇文章再加以詳細推導。

我們通過這個優化演算法能得到 $oldsymbol{alpha }^*$ ，再根據 $oldsymbol{alpha }^*$ ，我們就可以求解出 $oldsymbol{w}$ 和 $b$ ，進而求得我們最初的目的：找到超平面，即」決策平面」。

前面的推導都是假設滿足KKT條件下成立的，KKT條件如下

另外，根據前面的推導，還有下面兩個式子成立

$oldsymbol{w}=sum_{i=1}^N{alpha _iy_ioldsymbol{x}_{oldsymbol{i}}}$

$sum_{i=1}^N{alpha _iy_i}=0$

由此可知在 $oldsymbol{alpha }^*$ 中，至少存在一個 $alpha _{j}^{*}>0$ （反證法可以證明，若全為0，則 $oldsymbol{w}=0$ ，矛盾），對此 $j$ 有

$y_jleft( oldsymbol{w}^*cdot oldsymbol{x}_{oldsymbol{j}}+b^* ight) -1=0$

因此可以得到

$oldsymbol{w}^*=sum_{i=1}^N{alpha _{i}^{*}y_ioldsymbol{x}_i}$

$b^*=y_j-sum_{i=1}^N{alpha _{i}^{*}y_ileft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}$

對於任意訓練樣本 $left( oldsymbol{x}_{oldsymbol{i}},y_i ight)$ ，總有 $alpha _i=0$ 或者。若 $alpha _i=0$ ，則該樣本不會在最後求解模型參數的式子中出現。若 $alpha _i>0$ ，則必有 $y_jleft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{j}}+b ight) =1$ ，所對應的樣本點位於最大間隔邊界上，是一個支持向量。這顯示出支持向量機的一個重要性質：訓練完成後，大部分的訓練樣本都不需要保留，最終模型僅與支持向量有關。

到這裡都是基於訓練集數據線性可分的假設下進行的，但是實際情況下幾乎不存在完全線性可分的數據，為了解決這個問題，引入了「軟間隔」的概念，即允許某些點不滿足約束

$y_jleft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{j}}+b ight) ge 1$

採用hinge損失，將原優化問題改寫為

$underset{oldsymbol{w,}b,xi _i}{min} frac{1}{2}lVert oldsymbol{w} Vert ^2+Csum_{i=1}^m{xi _i}$

$s.t. y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) ge 1-xi _i$

$xi _ige 0 , i=1,2,...,N$

其中 $xi _i$ 為「鬆弛變數」， $xi _i=max left( 0,1-y_ileft( oldsymbol{w}cdot oldsymbol{x}_{oldsymbol{i}}+b ight) ight)$ ，即一個hinge損失函數。每一個樣本都有一個對應的鬆弛變數，表徵該樣本不滿足約束的程度。 $C>0$ 稱為懲罰參數， $C$ 值越大，對分類的懲罰越大。跟線性可分求解的思路一致，同樣這裡先用拉格朗日乘子法得到拉格朗日函數，再求其對偶問題。

綜合以上討論，我們可以得到線性支持向量機學習演算法如下：

輸入：訓練數據集 $T=left{ left( oldsymbol{x}_1,y_1 ight) ,left( oldsymbol{x}_1,y_1 ight) ,...,left( oldsymbol{x}_N,y_N ight) ight}$ 其中， $oldsymbol{x}_iin mathbb{R}^n$ ， $y_iin left{ +1,-1 ight} ,i=1,2,...N$ ；

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

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

$underset{oldsymbol{alpha }}{min} frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jleft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}}-sum_{i=1}^N{alpha _i}$

$s.t. sum_{i=1}^N{alpha _iy_i}=0$

$0le alpha _ile C, i=1,2,...,N$

得到最優解 $oldsymbol{alpha }^*=left( alpha _{1}^{*},alpha _{2}^{*},...,alpha _{N}^{*} ight) ^T$

（2）計算

$oldsymbol{w}^*=sum_{i=1}^N{alpha _{i}^{*}y_ioldsymbol{x}_i}$

選擇 $oldsymbol{alpha }^*$ 的一個分量 $alpha _{j}^{*}$ 滿足條件 $0<alpha _{j}^{*}<C$ ，計算

$b^*=y_j-sum_{i=1}^N{alpha _{i}^{*}y_ileft( oldsymbol{x}_{oldsymbol{i}}cdot oldsymbol{x}_{oldsymbol{j}} ight)}$

（3）求分離超平面

$oldsymbol{w}^*cdot oldsymbol{x}+b^*=0$

分類決策函數：

$fleft( oldsymbol{x} ight) =signleft( oldsymbol{w}^*cdot oldsymbol{x}+b^* ight)$

非線性SVM演算法原理

對於輸入空間中的非線性分類問題，可以通過非線性變換將它轉化為某個維特徵空間中的線性分類問題，在高維特徵空間中學習線性支持向量機。由於在線性支持向量機學習的對偶問題里，目標函數和分類決策函數都只涉及實例和實例之間的內積，所以不需要顯式地指定非線性變換，而是用核函數替換當中的內積。核函數表示，通過一個非線性轉換後的兩個實例間的內積。具體地， $Kleft( x,z ight)$ 是一個函數，或正定核，意味著存在一個從輸入空間到特徵空間的映射 $phi left( x ight)$ ，對任意輸入空間中的 $x,z$ ，有

$Kleft( x,z ight) =phi left( x ight) cdot phi left( z ight)$

在線性支持向量機學習的對偶問題中，用核函數 $Kleft( x,z ight)$ 替代內積，求解得到的就是非線性支持向量機

$fleft( x ight) =signleft( sum_{i=1}^N{alpha _{i}^{*}y_iKleft( x,x_i ight) +b^*} ight)$

綜合以上討論，我們可以得到非線性支持向量機學習演算法如下：

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

（1）選取適當的核函數 $Kleft( x,z ight)$ 和懲罰參數 $C>0$ ，構造並求解凸二次規劃問題

$underset{oldsymbol{alpha }}{min} frac{1}{2}sum_{i=1}^N{sum_{j=1}^N{alpha _ialpha _jy_iy_jKleft( oldsymbol{x}_{oldsymbol{i}},oldsymbol{x}_{oldsymbol{j}} ight)}}-sum_{i=1}^N{alpha _i}$

$s.t. sum_{i=1}^N{alpha _iy_i}=0$

$0le alpha _ile C, i=1,2,...,N$

得到最優解 $oldsymbol{alpha }^*=left( alpha _{1}^{*},alpha _{2}^{*},...,alpha _{N}^{*} ight) ^T$

（2）計算

選擇 $oldsymbol{alpha }^*$ 的一個分量 $alpha _{j}^{*}$ 滿足條件 $0<alpha _{j}^{*}<C$ ，計算

$b^*=y_j-sum_{i=1}^N{alpha _{i}^{*}y_iKleft( oldsymbol{x}_{oldsymbol{i}},oldsymbol{x}_{oldsymbol{j}} ight)}$

（3）分類決策函數：

$fleft( x ight) =signleft( sum_{i=1}^N{alpha _{i}^{*}y_iKleft( x,x_i ight) +b^*} ight)$

介紹一個常用的核函數——高斯核函數

$Kleft( x,z ight) =exp left( -frac{lVert x-z Vert ^2}{2sigma ^2} ight)$

對應的SVM是高斯徑向基函數分類器，在此情況下，分類決策函數為

$fleft( x ight) =signleft( sum_{i=1}^N{alpha _{i}^{*}y_iexp left( -frac{lVert x-z Vert ^2}{2sigma ^2} ight) +b^*} ight)$

參考

[1]《統計學習方法》李航

[2]《機器學習》周志華

[3]Python3《機器學習實戰》學習筆記（八）：支持向量機原理篇之手撕線性SVM Jack-Cui

[4]深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT條件

[5]支持向量機通俗導論（理解SVM的三層境界）

[6]Support Vector Machines for Classification

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

目錄

SVM簡介

SVM演算法原理

非線性SVM演算法原理

參考