機器學習——SVM

目錄

• SVM 基本概念
• 構造超平面
• 拉格朗日乘子法
• • 等式限制
  • 不等式限制——KKT條件
• SVM目标函數求解
• 線性不可分的情況
• SMO算法
• 核函數

支援向量機（SVM）最早是由 Vladimir N. Vapnik 和 Alexey Ya. Chervonenkis 在1963年提出，目前的版本(soft margin)是由 Corinna Cortes 和 Vapnik 在1993年提出。在深度學習（2012）出現之前，SVM 被認為機器學習中近十幾年來最成功，表現最好的算法。

SVM 基本概念

将執行個體的特征向量（以二維為例）映射為空間中的一些點，它們屬于不同的兩類。給定訓練樣本集 D = ( ( x 1 , y 1 ) , ( x 2 , y 2 ) , . . . , ( x m , y m ) ) , y i ∈ { − 1 , 1 } D=((x_1,y_1),(x_2,y_2),...,(x_m,y_m)),yi∈\{−1,1\} D=((x1​,y1​),(x2​,y2​),...,(xm​,ym​)),yi∈{−1,1}, （假設樣本線性可分），線性分類器基于訓練樣本D在二維空間中找到一個超平面來分開二類樣本。

但是符合條件的線是有無數條可以畫的，差別就在于效果好不好。SVM 的目的就是想要畫出一條線，以“最好地”區分這兩類點，以至如果以後有了新的點，這條線也能做出很好的分類。

挑選的标準：

SVM 将會尋找可以區分兩個類别并且能使邊際（margin）最大的超平面，這個超平面離直線兩邊的資料的間隔最大，對訓練集的資料的局限性或噪聲有最大的“容忍”能力。

邊際（margin）就是某一條線距離它兩側最近的點的距離之和，下圖中兩條虛線構成的帶狀區域就是 margin，虛線是由距離中央實線最近的兩個點所确定出來的。第一種劃分方式 margin 比較小，如果用第二種方式畫，margin 明顯變大也更接近我們的目标。

構造超平面

超平面可以用函數 f ( X ) = W T X + b f(X)=W^TX+b f(X)=WTX+b 表示。 當 f ( X ) f(X) f(X)等于0的時候， X X X便是位于超平面上的點，而 f ( X ) f(X) f(X)大于0的點對應 y = 1 y=1 y=1的資料點， f ( X ) f(X) f(X)小于0的點對應 y = − 1 y=-1 y=−1的點。

y y y隻是一個label ，标注為 { − 1 ， + 1 } \{-1，+1\} {−1，+1}不過為了描述友善，使得分類正确的情況下 y i ( W T x i + b ) > = 1 y_i(W^Tx_i+b)>=1 yi​(WTxi​+b)>=1 。

• W：權重向量， w = { w 1 , w 2 , . . . , w n } ， n w=\{w_1,w_2,...,w_n\}，n w={w1​,w2​,...,wn​}，n是特征值的個數
• X：訓練執行個體
• b：bias 偏向

假定我們找到了這個超平面，以二維特征向量舉例，即 X = ( x 1 , x 2 ) X=(x_1,x_2) X=(x1​,x2​)，然後定義一下離這個線最近的點到這個分界面（線）的距離分别為d1,d2。

我們認為最佳分界面不偏向與任何一方，分界面到兩邊的舉例相等，即d1=d2。

再假設我們有這兩個平行于分界面的虛線，分别過離分界面最近的樣本點。

假設分界面離上下虛線是k個距離，即虛線方程為 ∣ W T X + b ∣ = k |W^TX+b|=k ∣WTX+b∣=k，兩邊同除k并不會改變這條線，是以可以通過調整權值使上下虛線的方程變為 ∣ W T X + b ∣ = 1 |W^TX+b|=1 ∣WTX+b∣=1。

我們的目的是使虛線之間的距離D最大，首先計算上虛線與分界面的距離：

下虛線與分界面的距離也為d，是以：

要想尋找距離D的最大值，則等價于求 ∣ ∣ W ∣ ∣ ||W|| ∣∣W∣∣的最小值，也等同于求 ∣ ∣ W ∣ ∣ 2 ||W||^2 ∣∣W∣∣2即 W T W W^TW WTW的最小值，為了後續計算友善，我們再加一個系數1/2。是以可以建構一個目标函數：

但這個結論是有前提的，即所有的樣本點在虛線上或虛線外，即 y i ( W T x i + b ) > = 1 y_i(W^Tx_i+b)>=1 yi​(WTxi​+b)>=1 。

是以，完整的目标函數為：

s . t . s.t. s.t.表示受限制于，此時每個樣本點都受此限制，假設有N個樣本，代表該目标函數的限制條件有N個。

接下來隻要找到在限制條件下使目标函數最小的 W W W，帶入方程求出 b b b，便找到了最佳分界面。

拉格朗日乘子法

我們已經構造出了目标函數，但在衆多限制條件下求解有些困難，這裡我們需要引入拉格朗日乘子法。

等式限制

解決一個組合優化問題，一般需要拉格朗日乘子法，這裡舉個例子：

如果沒有限制條件，我們可以對 f f f求導，最值一定位于極值點處。但有限制條件的情況下，極值點可能不滿足限制條件。

既然有了限制不能直接求導，那麼可以思考如何把限制去掉。既然是等式限制，那麼我們把這個限制乘一個系數加到目标函數中去，這樣就相當于既考慮了原目标函數，也考慮了限制條件，比如上面那個函數，加進去就變為：

這裡 g 1 ( x ) , g 2 ( x ) g1(x),g2(x) g1(x),g2(x)為限制函數， α 1 , α 2 \alpha_1,\alpha_2 α1​,α2​為系數。

分别求 L L L對 x , α x,\alpha x,α的偏導，令其為0，求 L L L的極值，因為 α \alpha α的偏導就是限制函數，令其為零就代表此時的 L L L等于 f f f，且滿足限制條件。

上例中：

兩個變量（ α 1 , α 2 \alpha_1,\alpha_2 α1​,α2​）兩個等式（限制條件），可以求解，最終可以得到系數 α 1 , α 2 \alpha_1,\alpha_2 α1​,α2​，再帶回去求x就可以了。

不等式限制——KKT條件

帶有不等式的限制問題怎麼辦？那麼就需要用更一般化的拉格朗日乘子法，即KKT條件，來解決這種問題了。

任何原始問題限制條件無非最多3種，等式限制，大于号限制，小于号限制，而這三種最終通過将限制方程化簡化為兩類：限制方程等于0和限制方程小于0。再舉個簡單的方程為例，假設原始限制條件為下列所示：

那麼把限制條件變個樣子：

把限制條件變成小于是為了後續計算友善。

将限制拿到目标函數中去就變成：

KKT條件的定理：

如果一個優化問題在轉變完後變成

其中g是不等式限制，h是等式限制。那麼KKT條件就是函數的最優值，它必定滿足下面條件

此時分别對x1、x2求導數：

（1）α1=α2=0，那麼看上面的關系可以得到x1=1,x2=−1,再把兩個x帶到不等式限制，發現第一個就是需要滿足（10-1+20=29<0)顯然不行，29>0的，舍棄。

（2）g1(x)=g2(x)=0，帶進去解得，x1=110/101;x2=90/101,再帶回去求解α1，α2α1，α2，發現α1=58/101，α2=4/101，它們滿足大于0的條件，那麼顯然這組解是可以的。

SVM目标函數求解

我們剛才構造了SVM的目标函數：

把限制條件換成小于号的形式：

引入拉格朗日乘子法了，優化的目标變為：

注意， W T W W^TW WTW為凸函數，是以才能使用KKT。由于 α i > = 0 \alpha_i>=0 αi​>=0， h i ( x ) < = 0 h_i(x)<=0 hi​(x)<=0，是以 L ( w , b , α ) L(w,b,\alpha) L(w,b,α)一定小于等于原目标函數，則求原目标函數最小值的問題便成了求在KKT條件下 L ( w , b , α ) L(w,b,\alpha) L(w,b,α)的最大值。

求導：

帶入原式：

最終的問題為：

至此，可以用SMO法解出最優解 α i ∗ \alpha_i^* αi∗​，進而求出 W ∗ W^* W∗與 b ∗ b^* b∗。

SMO法下文詳細介紹，接下來先讨論線性不可分的情況。

線性不可分的情況

上述所有的構造都是在資料完全線性可分的情況下，且分界面完全将兩類分開，若正負兩類的最遠點沒有明顯的分解面，甚至存在一些離群點或者噪聲點而線性不可分，導緻整個系統用不了。

SVM考慮到這種情況，是以在上下分界面上加入松弛變量 ξ i \xi_i ξi​,認為如果正類中有點到上界面的距離小于 ξ i \xi_i ξi​，那麼認為他是正常的點，哪怕它在上界面稍微偏下一點的位置，同理下界面。

這樣，限制條件就變成了：

目标函數：

拉格朗日函數：

最終的問題為：

接下來和線性可分的情況一樣，用SMO法解出最優解 α i ∗ \alpha_i^* αi∗​，進而求出 W ∗ W^* W∗與 b ∗ b^* b∗。

SMO算法

SVM問題最終演化為求下列帶限制條件的問題：

問題的解就是找到一組 α i ∗ \alpha_i^* αi∗​使得 W W W最小。

每次隻選擇其中兩個乘子做優化，其他因子認為是常數。将N個解問題,轉換成兩個變量的求解問題:并且目标函數是凸的。

考察目标函數，假設 α 1 \alpha_1 α1​和 α 2 \alpha_2 α2​是變量，其餘均為定值：

SMO疊代公式：

退出條件：

核函數

可以使用核函數，将原始輸入空間映射到新"的特征空間，進而使得原本線性不可分的羊本可能在核空間可分。

常用的核函數：

使用核函數的意義在于：

1. 将向量的次元從低維映射到高維
2. 降低運算複雜度降低運算複雜度