【重磅】用一張圖理解SVM的脈絡

05-04

CVer推薦
來源: SigAI
作者: AI學習與實踐平台

導言

SVM在之前的很長一段時間內是性能最好的分類器，它有嚴密而優美的數學基礎作為支撐。在各種機器學習演算法中，它是最不易理解的演算法之一，要真正掌握它的原理有一定的難度。在本文中，SIGAI將帶領大家通過一張圖來理清SVM推導過程的核心過程。

簡介

在各種機器學習演算法中，SVM是對數學要求較高的一種，一直以來不易被初學者掌握。如果能把握住推導的整體思路，則能降低理解的難度，在本文中SIGAI將通過一張圖來為大家講述SVM的整個推導過程。

SVM由Vapnik等人在1995年提出，在出現之後的20多年裡它是最具影響力的機器學習演算法之一。在深度學習技術出現之前，使用高斯核的SVM在很多問題上一度取得了最好的效果。SVM不僅可以用於分類問題，還可以用於回歸問題。它具有泛化性能好，適合小樣本等優點，被廣泛應用於各種實際問題。

下面我們開始整個推導過程。先看這張圖：

最簡單的SVM從線性分類器導出，根據最大化分類間隔的目標，我們可以得到線性可分問題的SVM訓練時求解的問題。但現實應用中很多數據是線性不可分的，通過加入鬆弛變數和懲罰因子，可以將SVM推廣到線性不可分的情況，具體做法是對違反約束條件的訓練樣本進行懲罰，得到線性不可分的SVM訓練時優化的問題。這個優化問題是一個凸優化問題，並且滿足Slater條件，因此強對偶成立，通過拉格朗日對偶可以將其轉化成對偶問題求解。

到這裡為止，支持向量機還是一個線性模型，只不過允許有錯分的訓練樣本存在。通過核函數，可以將它轉化成非線性模型，此時的對偶問題也是一個凸優化問題。這個問題的求解普遍使用的是SMO演算法，這是一種分治法，它每次選擇兩個變數進行優化，這兩個變數的優化問題是一個帶等式和不等式約束條件的二次函數極值問題，可以求出公式解，並且這個問題也是凸優化問題。優化變數的選擇通過KKT條件來確定。

下面我們按照這個思路展開，給出SVM完整的推導過程，難點在於拉格朗日對偶和KKT條件。

預備知識

為了大家能夠理解推導過程，我們先介紹KKT條件。在微積分中我們學習過，帶等式約束的最優化問題可以用拉格朗日乘數法求解，對於既有等式約束又有不等式約束的問題，也有類似的條件定義函數的最優解-這就是KKT條件。對於如下優化問題：

首先構造拉格朗日乘子函數：

其中

稱為拉格朗日乘子。最優解

必須滿足如下條件：

除了原本應該滿足的等式約束和不等式約束之外,

和拉格朗日乘數法一樣。唯獨多了

這一條件。

下面介紹拉格朗日對偶。對偶是最求解優化問題的一種手段，它將一個優化問題轉化為另外一個更容易求解的問題，這兩個問題是等價的。常見的對偶有拉格朗日對偶、Fenchel對偶。這裡我們介紹拉格朗日對偶。

對於如下帶等式約束和不等式約束的最優化問題：

仿照拉格朗日乘數法構造如下廣義拉格朗日函數：

同樣的稱

為拉格朗日乘子。變數

必須滿足

的約束。接下來將上面的問題轉化為如下所謂的原問題形式，其最優解為：

等式右邊的含義是先固定住變數x，將其看成常數，讓拉格朗日函數對乘子變數

求最大值。消掉這兩組變數之後，再對變數x求最小值。為了簡化表述，定義如下最大化問題：

這是一個對乘子變數求最大值的問題，將x看成常數。這樣原問題被轉化為先對乘子變數求最大值，再對x求最小值。這個原問題和我們要求解的最小化問題有同樣的解，如果x違反了等式或不等式約束，上面問題的最優解是無窮大，因此不可能是問題的解。如果x滿足等式和不等式約束，上面的問題的最優解就是

, 因此二者等價。通過這樣的構造，將帶約束條件的問題轉化成對x沒有約束的問題。詳細的證明在SIGAI後續的文章中會給出。

接下來定義對偶問題與其最優解：

其中

和上面的做法相反，這裡是先固定拉格朗日乘子，調整x讓拉格朗日函數對x求極小值；然後再調整拉格朗日乘子對函數求極大值。

原問題和對偶問題只是改變了求極大值和極小值的順序，每次操控的變數是一樣的。如果原問題和對偶問題都存在最優解，則對偶問題的最優值不大於原問題的最優值，即：

這稱為弱對偶，後面的文章中我們會給出證明。原問題最優值和對偶問題最優值的差

稱為對偶間隙。如果原問題和對偶問題有相同的最優解，我們就可以把求解原問題轉化為求解對偶問題，這稱為強對偶。強對偶成立的一種前提條件是Slater條件。

Slater條件指出，一個凸優化問題如果存在一個候選x使得所有不等式約束都嚴格滿足，即對於所有的i都有

不等式不取等號。則存在

使得它們分別為原問題和對偶問題的最優解，並且：

Slater條件是強對偶成立的充分條件而不是必要條件。強對偶的意義在於：我們可以將求原問題轉化為求對偶問題，有些時候對偶問題比原問題更容易求解。強對偶只是將原問題轉化成對偶問題，而這個對偶問題怎麼求解則是另外一個問題。

線性可分的情況

首先我們來看最簡單的情況，線性可分的SVM。對於二分類問題，線性分類器用一個超平面將兩類樣本分開，對於二維平面，這個超平面是一條直線。線性分類器的判別函數為：

其中，w為權重向量，b為偏置項，是一個標量。一般情況下，給定一組訓練樣本可以得到不止一個線性分類器，下圖就是一個例子：

兩個不同的線性分類器

上面的兩個線性分類器都可以將兩類樣本分開，既然有不止一個可行的線性分類器，那麼哪個分類器是最好的？SVM的目標是尋找一個分類超平面，它不僅能正確的分類每一個樣本，並且要使得每一類樣本中距離超平面最近的樣本到超平面的距離儘可能遠。

給定一批訓練樣本，假設樣本的特徵向量為x，類別標籤為y，取值為+1或者-1，分別代表正樣本和負樣本。SVM為這些樣本尋找一個最優分類超平面，其方程為：

首先要保證每個樣本都被正確分類。對於正樣本有：

對於負樣本有：

由於正樣本的的類別標籤為+1，負樣本的類別標籤為-1，可以統一寫成如下不等式約束：

第二個要求是超平面離兩類樣本的距離要儘可能大。根據解析幾何中點到平面的距離公式，每個樣本點離分類超平面的距離為：

其中

是向量的L2範數。上面的分類超平面方程有冗餘，如果將方程兩邊都乘以不等於0的常數，還是同一個超平面。利用這個特點可以簡化問題的表述。對w和b加上如下約束：

即離超平面最近的正、負樣本代入超平面方程之後絕對值為1。這樣可以消掉這個冗餘，同時簡化了點到平面距離的計算公式。對分類超平面的約束變成：

這是上面那個不等式約束的加強版。分類超平面與兩類樣本之間的間隔為：

目標是使得這個間隔最大化，這等價於最小化下面的函數：

帶上前面定義約束條件之後優化問題可以寫成：

下圖是線性可分的SVM示意圖：

線性可分的支持向量機示意圖

線性不可分的情況

線性可分的SVM不具有太多的實用價值，因為現實問題中樣本一般都不是線性可分的，接下來我們將它進行擴展，得到能夠解決線性不可分問題的模型。為了處理這個問題，當線性不可分時通過加上鬆弛變數和懲罰因子對錯誤分類的樣本進行懲罰，可以得到如下最優化問題：

其中

是鬆弛變數，如果它不為0，表示樣本突破了不等式約束條件。C為懲罰因子，是人工設定的大於0的參數，用來對突破了不等式約束條件的樣本進行懲罰。可以證明這個問題是凸優化問題，因此可以保證求得全局最優解，在後面的文章中SIGAI會給出證明，請關注我們的微信公眾號。

另外，上述問題是滿足Slater條件的。如果令

則有

不等式條件嚴格滿足，因此強對偶條件成立，原問題和對偶問題有相同的最優解。因此可以轉化成對偶問題求解，這樣做的原因是原問題的不等式約束太多太複雜，不易於求解。

對偶問題

下面介紹如何將原問題轉化成對偶問題。首先將上面最優化問題的等式和不等式約束方程寫成標準形式：

然後構造拉格朗日乘子函數：

其中

是拉格朗日乘子。轉換成對偶問題的具體做法是先固定住這兩組乘子變數，對

求偏導數並令它們為0，得到如下方程組：

將上面的這些結果代入拉格朗日函數中，消掉這些變數，得到關於乘子變數

的函數，然後控制乘子變數，對函數取極大值

由於有等式約束

, 並且有不等式約束

, 因此有

這等價與如下最優化問題

轉化成對偶問題之後，不等式和等式約束都很簡單，求解更為容易。可以證明，上面這個問題是也凸優化問題，可以保證求得全局最優解，在SIGAI後續的文章中我們將給出證明，請大家關注我們的微信公眾號。將w的值代入超平面方程，最後的策函數為：

那些

的樣本即為支持向量，下面是支持向量的示意圖：

支持向量示意圖

核函數

雖然加入了鬆弛變數和懲罰因子，但支持向量機還是一個線性模型，只是允許錯分樣本的存在，這從它的決策函數也可以看出來。接下來要介紹的核映射使得支持向量機成為非線性模型，決策邊界不再是線性的超平面，而可以是形狀非常複雜的曲面。

如果樣本線性不可分，可以對特徵向量進行映射將它轉化到一般來說更高維的空間，使得在該空間中是線性可分的，這種方法在機器學習中被稱為核技巧。核映射將特徵向量變換到另外一個空間：

在對偶問題中計算的是兩個樣本向量之間的內積，因此映射後的向量在對偶問題中為：

直接計算效率太低，而且不容易構造映射函數。如果映射函數選取得當，能夠確保存在函數K，使得下面等式成立：

這樣只需先對向量做內積然後用函數K進行變換，這等價於先對向量做核映射然後再做內積。在這裡我們看到了求解對偶問題的另外一個好處，對偶問題中出現的是樣本特徵向量之間的內積，而核函數剛好作用於這種內積，替代對特徵向量的核映射。滿足上麵條件的函數稱為核函數，常用的核函數有以下幾種：

各種核函數與它們的計算公式

核函數的精妙之處在於不用真的對特徵向量做核映射，而是直接對特徵向量的內積進行變換，而這種變換卻等價於先對特徵向量做核映射然後做內積。

為向量加上核映射後，要求解的最優化問題變為：

根據核函數滿足的等式條件，它等價於下面的問題：

最後得到的分類判別函數為：

和不用核映射相比，只是求解的目標函數、最後的判定函數對特徵向量的內積做了核函數變換。如果K是一個非線性函數，上面的決策函數則是非線性函數，此時SVM是非線性模型。當訓練樣本很多、支持向量的個數很大的時候，預測時的速度是一個問題，因此很多時候我們會使用線性支持向量機。

如果我們定義矩陣Q，其元素為：

同時定義矩陣K，其元素為：

對偶問題可以寫成矩陣和向量形式：

可以證明，這個對偶問題同樣是凸優化問題，這是由核函數的性質保證的，在SIGAI公眾號SVM系列的後續文章中我們會介紹。下圖是使用高斯核的SVM對異或問題的分類結果：

只要參數設置得當，使用高斯核的支持向量機確實能解決非線性分類問題，分類邊界可以是非常複雜的曲線。

KKT條件

對於帶等式和不等式約束的問題，在最優點處必須滿足KKT條件，將KKT條件應用於SVM原問題的拉格朗日乘子函數，得到關於所有變數的方程，對於原問題中的兩組不等式約束，根據KKT條件必須滿足：

對於第一個方程，如果

，則必須有

即

而由於

，因此必定有

。

再來看第二種情況：如果

，則對

的值沒有約束。由於有

的約束，因此

；又因為

的限制，如果

，則必須有

。由於原問題中有約束條件

而由於

，因此有

對於

的情況，我們又可以細分為

和

。如果

，由於有

的約束，因此有

；因為有

的約束，因此

。不等式約束：

變為

由於

時，既要滿足

又要滿足

因此有

將三種情況合併起來，在最優點處，所有的樣本都必須滿足：

上面第一種情況對應的是自由變數即非支持向量，第二種情況對應的是支持向量，第三種情況對應的是違反不等式約束的樣本。在後面的求解演算法中，會應用此條件來選擇優化變數。

SMO演算法

前面我們給出了SVM的對偶問題，但並沒有說明對偶問題怎麼求解。由於矩陣Q的規模和樣本數相等，當訓練樣本數很大的時候，這個矩陣的規模很大，求解二次規劃問題的經典演算法將會遇到性能問題。下面將介紹SVM最優化問題的高效求解演算法-經典的SMO演算法。

SMO演算法由Platt等人在1998年提出，是求解SVM對偶問題的高效演算法。這個演算法的思路是每次在優化變數中挑出兩個分量進行優化，而讓其他分量固定，這樣才能保證滿足等式約束條件，這是一種分治法的思想。

下面先給出對於這兩個變數的優化問題（稱為子問題）的求解方法。假設選取的兩個分量為

，其他分量都固定即當成常數。由於

以及

對這兩個變數的目標函數可以寫成：

其中c是一個常數。前面的二次項很容易計算出來，一次項要複雜一些，其中：

這裡的變數

為變數а在上一輪迭代後的值。上面的目標函數是一個兩變數的二次函數，我們可以直接給出最小值的解析解（公式解），只要你學過初中數學，都能理解這個方法。這個問題的約束條件為：

前面兩個不等式約束構成了一個矩形，最後一個等式約束是一條直線。由於

的取值只能為+1或者-1，如果它們異號，等式約束為

它確定的可行域是一條斜率為1的直線段。因為

，要滿足約束條件

和

，它們的可行域如下圖所示：

可行域示意圖-情況1

上圖中的兩條直線分別對應於

為1和-1的情況。如果是上面那條直線，則

的取值範圍為

。如果是下面的那條直線，則為

。

對於這兩種情況

的下界和上界可以統一寫成如下形式：

下邊界是直線和x軸交點的x坐標以及0的較大值；上邊界是直線和的交點的x坐標和C的較小值。

再來看第二種情況。如果

同號，等式約束為

此時的下界和上界為：

這種情況如下圖所示：

可行域示意圖-情況2

利用這兩個變數的等式約束條件，可以消掉

，只剩下一個變數

，目標函數是它的二次函數。我們可以直接求得這個二次函數的極值，假設不考慮約束條件得到的極值點為，則最終的極值點為：

這三種情況如下圖所示：

3種情況下的二次函數極小值

上圖中第一種情況是拋物線的最小值點在[L,H]中；第二種情況是拋物線的最小值點大於H，被截斷為H；第三種情況是小於L，被截斷為L。

下面我們來計算不考慮截斷時的函數極值。為了避免分-1和+1兩種情況，我們將上面的等式約束兩邊同乘以

有：

變形後得到：

為了表述簡介，令

，將上面方程代入目標函數中消掉

，有：

對自變數求導並令導數為0，得：

而

化簡得：

即：

將w和v帶入，化簡得：

如果令

上式兩邊同時除以

，可以得到

其中

，考慮前面提推導過的約束：

在求得

之後，根據等式約束條件我們就可以求得另外一個變數的值：

目標函數的二階導數為

，前面假設二階導數

，從而保證目標函數是凸函數即開口向上的拋物線，有極小值。如果

或者

，該怎麼處理？對於線性核或正定核函數，可以證明矩陣K的任意一個上述子問題對應的二階子矩陣半正定，因此必定有

，SIGAI公眾號後面的文章中我們會給出證明。無論本次迭代時

的初始值是多少，通過上面的子問題求解演算法得到是在可行域里的最小值，因此每次求解更新這兩個變數的值之後，都能保證目標函數值小於或者等於初始值，即函數值下降。

上面已經解決了兩個變數問題的求解，接下來說明怎麼選擇這兩個變數，最簡單的是使用啟發式規則。第一個變數的選擇方法是在訓練樣本中選取違反KKT條件最嚴重的那個樣本。在前面我們推導過，在最優點處訓練樣本是否滿足KKT條件的判據是：

其中

首先遍歷所有滿足約束條件

的樣本點，即位於間隔邊界上的支持向量點，檢驗它們是否滿足KKT條件。如果這些樣本都滿足KKT條件，則遍歷整個訓練樣本集，判斷它們是否滿足KKT條件，直到找到一個違反KKT條件的變數

，找到了第一個變數之後，接下來尋找

，選擇的標準是使得它有足夠大的變化。根據前面的推導我們知道

依賴於

，因此，我們選擇使得

最大的

。由於

已經選出來了，因此

已經知道了。如果

則選擇最小的

，否則選擇最大的

。

至此，我們給出了支持向量機求解的問題的完整推導過程，通過這張圖，你將能更容易地理解這個演算法，如果在理解的過程中有任何疑問，可以向SIGAI公眾號發消息，我們將為你解答。