前言

支援向量機（Support Vector Machine，SVM）在70年代由蘇聯人 Vladimir Vapnik 提出，主要用於處理二分類問題，也就是研究如何區分兩類事物。

本文主要介紹支援向量機如何解決線性可分和非線性可分問題，最後還會對 SMO 演演算法進行推導以及對 SMO 演演算法的收斂性進行簡要分析，但受限於篇幅，本文不會對最佳化問題、核函數、原問題和對偶問題等前置知識做過於深入的介紹，需要了解相關知識的讀者朋友請移步其它文章、資料。

SVM 推導過程主要參考自胡浩基教授的機器學習公開課程；SMO 演演算法相關則主要來自於 Platt 的論文以及網上公開資料，相關連結見文章末尾。

 

快速理解

舉一個粗糙的例子。

科學家收集到一批天體的觀測資料，現在需要按行星和恆星兩種型別對這些未知天體進行分類。顯然這是一項費時費力的工作，我們希望通過機器學習演演算法，讓計算機自動幫我們做區分。

我們拿到了往年一批已經分類好的天體資料樣本，將這些樣本繪製到一個二維座標系上，如下：

這是一個簡單的二維特徵空間，通過肉眼觀察這些資料我們發現，恆星和行星這兩種天體，根據他們的輻射強度和質量的不同，分別聚集在座標系的左下角和右上角兩個區域。

於是我們根據自己的判斷作了這樣一條直線：

 

這時，我們就擁有了一條可以區分恆星和行星的直線，當點落在直線左側的可判斷為行星，如果落在右側則為恆星。

但是上面這條直線是我們憑藉經驗所作，顯然在座標系中能夠劃分這兩類天體的直線有無數條，如下圖：

這種情況下，如何定義一個效能指標去找到一條最合適的直線就是支援向量機要解決的首要問題。

Vapnik 提出了使用如下一對平行線的 間隔（Margin）來作為這個效能指標，間隔越大，意味著最終獲得的直線更具普適性，如下圖：

上面座標系中，首先是在兩種樣本中間找一對平行線，我們從 0 開始擴大平行線的間隔 d，直到兩條線分別經過兩種樣本的一個或多個點為止，這些點被稱為 支援向量（Support Vector），當間隔 d 最大時，兩條平行線的正中間我們可以取到第三條平行線，如下圖紅色虛線所示：

在眾多的分界線當中，這條紅色直線被認為是一個最優解，稱為 決策邊界（Decision Boundary）。

上面的例子中，兩種樣本各自會有一片聚集密度較高的區域，而遠離這片區域，樣本逐漸變得稀疏，樣本越稀疏意味著落到該區域的概率越低。決策邊界直線在兼顧劃分不同樣本的同時，還需要放置在兩種樣本之間最不可能出現的區域，那麼，當間隔 d 取最大時即為最理想的狀態。

目前為止我們可以得到一些初期結論：

實際應用場景中，我們經常會遇到比上面例子複雜得多的問題。例如通過影象區分月季和玫瑰，我們需要從顏色、花瓣形狀、葉子形狀等等多個特徵進行綜合判斷，訓練樣本最終會落到一個多維特徵空間中，此時劃分兩種訓練樣本的邊界將會是一個超平面，稱為 分離超平面（Separating Hyperplane）。

支援向量機本質是用線性方程去解決二分類問題，而在實際問題中，不同的樣本在特徵空間中往往「犬牙交錯」，SVM 這種「一刀切」的方式似乎將變得不再奏效。別擔心，後面筆者將會花大篇幅著墨如何處理這種線性不可分的樣本。

 

支援向量機的兩種模型

支援向量機有兩種模型：線性模型、非線性模型

為了方便推導，接下來對樣本做一些定義。

 

訓練樣本的定義

比如現在有 class1 和 class2 兩種訓練樣本，分佈在這樣一個二維特徵空間中：

那麼，對於第 $i$ 個訓練樣本可以用 向量 和 標籤 去定義它：

$\left( 向量,標籤\right)\Leftrightarrow\left( X_{i},y_{i}\right)$

 

$X_{i}=\begin{bmatrix} x_{i1} \\ x_{i2} \end{bmatrix}$，$y_{i} \in \left\{ 1,-1 \right\}$

標籤 $y_{i}$ 可以理解為第 $i$ 個樣本所屬的類別，SVM 用於處理二分類問題，那麼我們可以使用 $+1$、$-1$ 分別表示 class1 和 class2 兩種訓練樣本。

從上面二維特徵空間的例子，進一步推廣到 $m$ 維特徵空間中的 $N$ 個訓練樣本：

$\left( X_{1},y_{1}\right), \left( X_{2},y_{2}\right), \cdots ,\left( X_{N},y_{N}\right)$

可以記作：

$\left\{ \left( X_{i},y_{i}\right)\right\} _{i=1}^{N}$

 

$X_{i}=\begin{bmatrix} x_{i1} \\ x_{i2} \\ \vdots \\ x_{im} \end{bmatrix}$，$y_{i} \in \left\{ 1,-1 \right\}$

現在我們已經知道了訓練樣本的定義，那麼接下來將對 SVM 線性、非線性兩種模型分別進行討論。

 

線性模型

如果訓練樣本 線性可分（Linear Separable），可以用這樣一個方程來表示分離超平面：

$\omega^{T}X+b=0$

這裡的 $X$ 即上一小節提到的樣本的向量，$\omega$ 和 $X$ 是維度相同的向量，$\omega^{T}$ 是向量 $\omega$ 的轉置，$b$ 是某個實數：

$\omega=\begin{bmatrix} \omega_{1} \\ \omega_{2} \\ \vdots \\ \omega_{m} \end{bmatrix},X=\begin{bmatrix} x_{1} \\ x_{2} \\ \vdots \\ x_{m} \end{bmatrix},b\in R$

$X$ 是已知的向量，最終我們是要求出 $\omega$ 和 $b$，使得分離超平面正確分割開兩種樣本。

總結一下，一個正確分類所有樣本的 SVM 線性模型可以記作：

對於 $\left\{ \left( X_{i},y_{i}\right) \right\} _{i=1}^{N}$，

$\exists \left( \omega,b\right)$，使：

$\forall i = 1,2,\cdots, N$，有：

a) 若 $y_{i}=+1$，則  $\omega^{T}X_{i}+b \geq 0$

b) 若 $y_{i}=-1$，則  $\omega^{T}X_{i}+b < 0$

上面 a、b 是為了方便推導而人為做出的定義，針對不同的場景我們會逐步修改這些定義，希望讀者朋友們在後續的推導中能夠靈活變通，舉一反三。

聯立 a、b 可以進一步簡化得到：

$\begin{align}y_{i}\left( \omega^{T}X_{i}+b\right) \geq 0 \tag{公式1}\end{align}$

換句話說，滿足公式1就代表著樣本能夠被正確分類。

一個可用的 SVM 模型，除了能夠正確分類所有訓練樣本之外，還需要讓間隔 $d$ 最大化，如何用代數式表達最大化 $d$ 是接下來要討論的話題。

回顧高中知識，點 $\left( x_{0},y_{0}\right)$ 到直線 $\omega_{1}x+\omega_{2}y+b=0$ 的距離為：

$d=\dfrac{\left| \omega_{1} x_{0}+\omega_{2}y_{0}+b\right| }{\sqrt{\omega _{1}^{2}+\omega_{2}^{2}}}$

由此可以推匯出，向量 $X_{i}$ 到超平面 $\omega^{T}X+b=0$ 的距離：

$\begin{align*} d &=\dfrac{\left| \omega^{T}X_{i}+b\right| }{\left\| \omega\right\| } \\ &=\frac{\left| \omega^{T}X_{i}+b\right| }{\scriptsize{\sqrt{\sum \limits^{m}_{i=1}\omega_{i}^{2}}}} \end{align*}$

這裡我們需要再明確一個事實，無論我們如何對分離超平面的方程進行縮放，方程表示的都是同一個超平面，即：

那麼，我們總是可以找到一個縮放倍數 $a \in R^{+}$，使得分離超平面對於支援向量 $X_{s}$，有：

$\left| a\omega^{T}X_{s}+ab\right|=1$

因為每個支援向量到超平面的距離都是相等的，任何一個支援向量 $X_{s}$ 到分離超平面的距離將會是：

$d=\dfrac{\left| a\omega^{T}X_{s}+ab\right| }{\left\| a\omega\right\| }=\dfrac{1}{\left\| a\omega\right\| }$ 

上一節我們就知道，支援向量是到分離超平面最近的點，結合上面支援向量到超平面的距離 $d$，我們可以對任何一個向量 $X_{i}$ 做進一步的定義：

前面提到，支援向量機的任務是去找到一個最大的間隔 $d$，於是我們最終得到了一個優化問題，它的 目標函數（Objective Function）和限制條件如下（為了簡化書寫，$a\omega$、$ab$ 重新定義為 $\omega$、$b$，同時為了求導方便，目標函數也做了改造）：

最小化：$\dfrac{1}{2} \left\| \omega\right\|^{2}$

限制條件：$y_{i}\left( \omega^{T}X_{i}+b \right) \geq 1\ ,\ i=1,2,\cdots,N$

這個最佳化問題是一個二次規劃問題，二次規劃（Quadratic Programming）是凸優化問題中的一種，它要求滿足以下條件：

a）目標函數為二次函數

b）限制條件為一次函數

一個二次規劃問題，要麼無解，要麼只有一個極值（這裡不展開證明，我們直接使用這個結論）。

最後，回顧一下整個推導過程：

 

非線性模型

在實際應用中，我們得到的訓練樣本在特徵空間裡大概率是 非線性可分（Non-linear Separable）的。

一些非線性可分的情況

如果樣本是線性不可分的，那麼上一小節得到的最佳化問題將會無解，接下來介紹如何把非線性可分轉換為線性可分問題。

 

引入鬆弛變數

在圖（2）中，因為兩種訓練樣本存在小部分交疊的區域導致樣本線性不可分，屬於可容忍的範圍，這時應該放寬限制條件，給每個訓練樣本引入一個鬆弛變數（Slack Variable）$\xi _{i}$，使一些離群的樣本也能被分類，限制條件改造為（$i=1,2,\cdots,N$）：

最小化：$\dfrac{1}{2} \left\| \omega\right\|^{2}+C\sum \limits^{N}_{i=1}\xi _{i}$

這裡的 $C\sum \limits^{N}_{i=1}\xi _{i}$ 被稱為 正則項（Regulation Trem），$C$ 值越大，對目標函數的懲罰力度就越大，此時目標函數就需要相應地縮小 $\xi_{i}$ 的值，直觀的表現是被錯誤分類的點會變少或到決策邊界的距離會變短。

加入鬆弛變數後，取得最優解時可能得到類似下圖的 SVM 模型：

無法解決問題，於是與問題和解了

在引入了鬆弛變數後，圖（2）的問題得到了較好的解決，但如果直接套用到圖（1）這種情況中，最終得到模型將會非常糟糕，因為決策邊界在圖（1）中可能會變為這樣：

非常糟糕，但至少讓你的生日蛋糕得到了很好的切分

顯然，我們需要另闢蹊徑處理這種情況。

 

低維對映到高維

對於上面這種情況，一般我們的想法是去構造一條曲線來區分兩種樣本，而 Vapnik 則提出了另一個極具創造性的思路，他的想法是對樣本向量進行升維，因為在越高維的空間中，我們越是有概率用分離超平面區分兩種樣本；好比我們在網購時，商家給出商品的引數越多，我們越是能夠判斷商品質量的優劣。

接下來的一個例子，將演示如何通過對線性不可分的樣本進行升維，使得樣本線性可分。

一個二維特徵空間中線性不可分的例子

上面的二維特徵空間中存線上性不可分的四個向量，這四個向量分別屬於 $C_{1}$、$C_{2}$ 兩種標籤：

$X_{1}=\begin{bmatrix} 0 \\ 0 \end{bmatrix} , X_{2}=\begin{bmatrix} 1 \\ 1 \end{bmatrix} \in C_{1}$

$X_{3}=\begin{bmatrix} 1 \\ 0 \end{bmatrix} , X_{4}=\begin{bmatrix} 0 \\ 1 \end{bmatrix} \in C_{2}$

為了使這些樣本變得線性可分，需要人為地制定一個規則 $\varphi$ ，比如仿射函數，將向量對映到高維空間：

$X_{i}=\begin{bmatrix} a \\ b \end{bmatrix}$

$\Downarrow$

$\varphi \left( X_{i}\right)=\begin{bmatrix} a^{2} \\ b^{2} \\ a \\ b \\ ab \end{bmatrix}$

四個向量經過升維將變為：

不要忘了我們的目標是要求出 $\omega$ 和 $b$，回顧一下 SVM 最佳化問題的限制條件（公式1）：

$y_{i}\left( \omega^{T}X_{i}+b\right) \geq 0$

在通過 $\varphi$ 對向量 $X_{i}$ 進行升維後，限制條件公式變為：

$y_{i}\left[ \omega^{T}\varphi \left( X_{i}\right)+b\right] \geq 0$

（注意：$\omega$ 的維度也將得到提升，與 $\varphi \left( X_{i}\right)$ 保持一致）

不考慮優化目標，僅滿足限制條件的情況下，下面是眾多答案的其中一個：

$\omega=\begin{bmatrix} -1 \\ -1 \\ -1 \\ -1 \\ 6 \end{bmatrix}$，$b=1$

驗證一下答案，將 $\omega$ 和 $b$ 代回限制條件公式，可以得到：

$\omega^{T}\varphi \left( X_{1}\right)+b=1 \Rightarrow y_{1}=1$

$\omega^{T}\varphi \left( X_{2}\right)+b=3 \Rightarrow y_{2}=1$

$\omega^{T}\varphi \left( X_{3}\right)+b=-1 \Rightarrow y_{3}=-1$

$\omega^{T}\varphi \left( X_{4}\right)+b=-1 \Rightarrow y_{4}=-1$

通過 $y_{i}$ 的值可以看到，我們已經成功將樣本分成了兩類。

當然，這是燃盡腦細胞後得出的一個結果，而這還是在不考慮優化目標且只有5維的情況下，可想而知，在更高維的情況下，運算將會變得多麼艱難。

前面我們提到 $\omega$ 和 $X_{i}$ 的維度始終保持一致，當 $X_{i}$ 對映成一個無限維向量時，$\omega$ 也將變為一個無限維的向量，此時的方程變得難以求解。不僅是高維情況下的運算難題，如何找到一個合適的 $\varphi$ 使樣本變得線性可分也不是一件容易的事。

為了解決這些問題，SVM 藉助了 核函數（Kernel Function），通過一系列轉換，核函數可以替換分離超平面方程中無限維的 $\omega$ 和 $\varphi\left(X_{i}\right)$，使得方程可解。

 

核函數

感謝核函數，我們不再需要關心 $\varphi \left( X\right)$ 的顯式表達，也就是不需要知道 $\varphi$ 是如何對向量進行升維的，只通過核函數就可以計算兩個升維後的向量 $\varphi \left( X_{1}\right)$、$\varphi \left( X_{2}\right)$ 的內積，它們的關係如下：

$K\left( X_{1},X_{2}\right) =\varphi \left( X_{1}\right) ^{T}\varphi \left( X_{2}\right)$

核函數 $K$ 有明確的代數式，高斯核、多項式核是兩種常用的核函數：

 高斯核：$K\left( X_{1},X_{2}\right) ={\Large e}^{\scriptsize -\dfrac{\left\| X_{1}-X_{2}\right\| ^{2}}{2\sigma^{2} }}$

多項式核：$K\left( X_{1},X_{2}\right) =\left( X_{1}^{T}X_{2}+1\right) ^{d}$

多項式核中的階數 $d$ 是有限的，那麼 $\varphi \left( X_{i}\right)$ 也將是有限維度的向量；但是高斯核對應的 $\varphi \left( X_{i}\right)$ 則是一個無限維的向量，相關證明本文不做展開。

事實上，要使 $K\left( X_{1},X_{2}\right) =\varphi \left( X_{1}\right) ^{T}\varphi \left( X_{2}\right)$ 成立也是有條件的，等式成立的充要條件如下（Mercer 定理）：

充要條件 $2$ 中的 $C_{i}$ 是常數，$X_{i}$ 是向量，關於半正定性見文末推薦閱讀。

現在，我們已經知道了核函數的作用，接下來將討論如何使用原問題以及原問題的對偶問題等理論，讓無限維的超平面方程變得可解。

 

原問題

先來看一下最佳化問題的 原問題（Prime Problem）如何定義：

$\begin{align*}最小化：&f \left( \omega \right)\\ 限制條件：&g_{i} \left( \omega \right) \leq 0 \quad \left( i=1,2,\cdots,K \right) \\ &h_{i} \left( \omega \right) = 0 \quad \left( i=1,2,\cdots,M \right)\end{align*}$

這個定義具有非常高的普適性，目標函數是求最小化 $f \left( \omega \right)$，加入一個負號之後就變成了求最大化 $-f \left( \omega \right)$；$g_{i}$ 同理，加入負號就變成 $-g_{i} \left( \omega \right) \geq 0$，我們可以使用 $g_{i} \left( \omega \right) \leq 0$ 來表示任何不等式；同樣的，$h_{i} \left( \omega \right) = 0$ 可以表示任何等式。

顧名思義，我們可以將任意最佳化問題轉化為上面原問題的格式。當然，限制條件是可選的，可以有一個或多個等式、不等式約束，我們上面展示的是最佳化問題其中一種混合約束的情況，在做轉換的時候需根據實際做增減。

 

對偶問題

接下來介紹原問題的 對偶問題（Dual Problem）。

通過原問題可以得到拉格朗日函數 $L$，關於拉格朗日函數的介紹見文章末尾的推薦閱讀，這裡不做展開，只需知道拉格朗日函數可用來求對偶問題的極值點，後面我們會對這個函數求偏導：

上面公式 (1) 可以用向量形式寫成公式 (2) ，這兩種書寫方式都是可行的。

結合拉格朗日函數，可以得到對偶問題如下：

$最大化：\theta \left( \alpha, \beta \right)=\inf \limits_{\omega} \{ L \left( \omega, \alpha, \beta \right) \} \\ 限制條件：\alpha_{i} \geq 0 \quad \left( i=1,2,\cdots,K \right)$

解釋一下這個目標函數。$\inf$ 表示集合的下确界，可以認為是取集合中的最小值，$\theta \left( \alpha, \beta \right)=\inf \limits_{\omega} \{ L \left( \omega, \alpha, \beta \right) \}$ 的意思是函數 $\theta$ 接收兩個入參 $\alpha$ 和 $\beta$，這時 $\alpha$ 和 $\beta$ 就是已知的，然後通過改變 $\omega$ 找到最小的 $L \left( \omega, \alpha, \beta \right)$ 作為 $\theta \left( \alpha, \beta \right)$ 的輸出結果；而優化目標是找到能使 $\theta \left( \alpha, \beta \right)$ 值最大的 $\alpha$、$\beta$。從程式設計角度理解，可以想象成是一個巢狀迴圈，內層迴圈找最小值，外層迴圈找最大值。

可以發現，原問題的優化目標是求最小值，而它的對偶問題中則變為求最大值。原問題及其對偶問題的特點是，兩者的優化目標是相反的，而在特定條件下他們將擁有相同的最值點，這就引出下一節要介紹的強對偶定理。關於原問題及對偶問題更詳細的內容見文末推薦閱讀。

 

強對偶定理以及 KKT 條件

前面定義的原問題和對偶問題之間存在這樣一個關係（弱對偶定理）：

可以證明一下上面的定理：

$f \left( \omega^{*} \right)$ 與 $\theta \left( \alpha^{*}, \beta^{*} \right)$ 的差稱為原問題與對偶問題的 間距（Duality Gap），記作：

$G=f \left( \omega^{*} \right) - \theta \left( \alpha^{*}, \beta^{*} \right) \geq 0$

推導到這裡，已經可以隱約看到原問題和對偶問題之間的聯絡了，但這還不足以幫助我們解決最佳化問題。這兩者之間存在更緊密的關係，被稱作 強對偶定理（Strong Duality Theorem），這是在特定條件下，使得 $G=0$ 的一種情況：

這裡提到了凸函數，順便簡要介紹一下凸函數的定義：

凸函數在不同專業領域有不同的稱呼，你可以稱它為凸函數或凹函數。它的特點是隻有一個極值點，在本文中暫且認為凸函數的最值為最小值；它的另一個特點是在函數上任取兩個不同的點連一條線段，兩點之間凸函數總是線上段的下方。寫成代數形式如下，當然，下面的式子同樣適用於多維向量：

回到強對偶定理，在證明原問題和對偶問題的關係時，我們知道：

而在強對偶定理成立的條件下，因為 $f \left( \omega^{*} \right) = \theta \left( \alpha^{*}, \beta^{*} \right)$，即：

又因為 $h_{i}\left(\omega^{*} \right)=0$，不難推匯出此時滿足（被稱為 KKT 條件，為了簡潔，省略了一些前置條件）：

$\forall i=1,2,\cdots,K，\alpha^{*}_{i}=0 \enspace或\enspace g_{i} \left(\omega^{*} \right)=0$

簡而言之，在強對偶定理成立的條件下，原問題及其對偶問題的最優解滿足 KKT 條件的約束。

事實上，KKT 條件同時也是取得最優解的充要條件，因為在強對偶定理成立的條件下，變數滿足 KKT 條件也就意味著 $f \left( \omega \right) = \theta \left( \alpha, \beta \right)$，而 $f \left( \omega \right)$ 和 $\theta \left( \alpha, \beta \right)$ 做為凸函數只會有一個最優解。

萬事具備，接下來開始將 SVM 的原問題轉換為對偶問題。

 

SVM 的原問題轉換為對偶問題

前面我們已經知道了原問題及其對偶問題的定義，本節將介紹如何獲得 SVM 最佳化問題的原問題及其對偶問題。

我們在加入鬆弛變數之後得到這樣一個 SVM 的最佳化問題（使用 $\varphi$ 是為了更明顯地看出核函數如何發揮作用）：

$\begin{align*}最小化：&\dfrac{1}{2} \left\| \omega\right\|^{2}+C\sum \limits^{N}_{i=1}\xi _{i}\\ 限制條件：&y_{i}\left[ \omega^{T}\varphi \left(X_{i} \right)+b \right] \geq 1-\xi _{i} \quad \left(i=1,2,\cdots,N \right) \\ &\xi _{i} \geq 0 \quad \left(i=1,2,\cdots,N \right) \end{align*}$

經過證明，SVM 最佳化問題的目標函數是一個凸函數，那麼它肯定有一個最小值。雖然還沒開始推導，但我們已經可以看出它具有強對偶性。

先回顧一下原問題的定義：

$\begin{align*}最小化：&f \left( \omega \right)\\ 限制條件：&g_{i} \left( \omega \right) \leq 0 \quad \left( i=1,2,\cdots,K \right) \\ &h_{i} \left( \omega \right) = 0 \quad \left( i=1,2,\cdots,M \right)\end{align*}$

對比發現，原問題的限制條件和 SVM 最佳化問題的限制條件有一定差距，但是原問題的定義具有很高的普適性，可以對 SVM 最佳化問題做一些改造，讓它和原問題保持一致。只需讓鬆弛變數小於等於 $0$ 即可改造得到 SVM 最佳化問題的原問題：

 $\begin{align*}最小化：&\dfrac{1}{2} \left\| \omega\right\|^{2}-C\sum \limits^{N}_{i=1}\xi _{i}\\ 限制條件：&1+\xi _{i}-y_{i} \omega^{T}\varphi\left(X_{i} \right)-y_{i}b \leq 0 \quad \left(i=1,2,\cdots,N \right) \\ &\xi _{i} \leq 0 \quad \left(i=1,2,\cdots,N \right) \end{align*}$

此時得到改造完成的限制條件存在兩個不等式約束 $g_{i}\left(\omega \right)$，根據拉格朗日函數的構造方法，我們需要分別定義兩個拉格朗日乘子 $\alpha_{i}$、$\beta_{i}$ 對 $g_{i}\left(\omega \right)$ 進行處理（關於拉格朗日函數見文末推薦閱讀），此時可以得到 SVM 的對偶問題如下：

下圖更直觀地展示了整個推導過程：

為了方便後面的推導，需要進一步化簡目標函數。前面說到 $\inf$ 是求最小值，那麼先求偏導：

$\dfrac{\partial L}{\partial \omega}=0 \Rightarrow \omega=\sum \limits^{N}_{i=1} \alpha_{i} y_{i} \varphi \left(X_{i}\right) \\ \dfrac{\partial L}{\partial \xi_{i}}=0 \Rightarrow \beta_{i}+\alpha_{i}=C \quad \left(i=1,2,\cdots,N \right) \\ \dfrac{\partial L}{\partial b}=0 \Rightarrow \sum \limits^{N}_{i=1} \alpha_{i}y_{i}=0$

將結果代回目標函數，得：

最終，使用核函數替換 $\varphi\left(X_{i} \right)^{T}\varphi\left(X_{j} \right)$，並化簡，得到 SVM 對偶問題的目標函數：

將限制條件聯立求導結果，又可以得到 SVM 對偶問題的限制條件：

$\begin{align*}限制條件：&0\leq \alpha_{i} \leq C \quad \left(i=1,2,\cdots,N \right) \\ &\sum \limits^{N}_{i=1}\alpha_{i}y_{i}=0 \end{align*}$

可以看出最佳化問題具有強對偶性，此時對偶問題的解即為 SVM 最佳化問題的解。

到此，無限維向量 $\varphi \left(X_{i}\right)$ 和 $\omega$ 的內積已經被我們成功轉化為核函數 $K$，我們只需求出有限維度的 $\alpha$。

 

SVM 的 KKT 條件

在介紹強對偶定理那一節裡提及了 KKT 條件，而在接下來的章節中仍然會用到這個理論。趁熱打鐵， 我們已經通過對偶問題的定義得到了 SVM 原問題的對偶問題，那也就可以進一步得到 SVM 的 KKT 條件。

SVM 原問題中，存在一組不等式約束：

回顧上一節裡提到的，根據拉格朗日函數的定義，我們需要分別給這兩個限制條件引入拉格朗日乘子，兩個乘子我們還是記作 $\alpha$ 和 $\beta$，此時 SVM 對偶問題的拉格朗日函數為：

根據前文 KKT 條件的推導過程，當取得最優解 $\omega^{*}$、$\xi^{*}$、$b^{*}$、$\alpha^{*}$、$\beta^{*}$ 時，有：

最終得到 SVM 的 KKT 條件為（省略了一些前置條件）：

也就是說，當滿足上面的 KKT 條件時，SVM 取得最優解。

 

訓練

上一節我們得到了 SVM 的對偶問題：

可以看到上面的最佳化問題中，除了向量 $\alpha$，其他引數都是已知的，訓練的目的是為了求出合適的 $\alpha$ 使得 SVM 能對樣本正確地分類。接下來要介紹的 SMO 演演算法是一種常用的求解 $\alpha$ 的演演算法，其表現出的突出效能，值得筆者花費筆墨介紹它的原理。

 

SMO 演演算法

為了提高 SVM 的訓練效率，John Platt 在 1998 年發表的論文《Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines》中提出了 SMO 演演算法。其基本思路是在 $\alpha$ 中選出兩個分量作為變數，比如 $\alpha_{1}$、$\alpha_{2}$，而其餘的分量 $\alpha_{3},\alpha_{4},\dots,\alpha_{N}$ 則作為固定的常數，這些常數都會被賦予初始值，接著通過求導等過程求出 $\alpha_{1}$、$\alpha_{2}$ 後，又會重新選出兩個分量重複此過程，期間 $\alpha$ 的值將不斷收斂，直到滿足 KKT 條件時退出迴圈。

 

改造最佳化問題

為了方便理解，我們設 $\alpha$ 中選出兩個分量 $\alpha_{1}$、$\alpha_{2}$ 作為變數，其他分量看作常數，那麼目標函數將變為（為了方便讀者閱讀時與 Platt 的論文進行對比，這裡把優化目標轉換為求最小值）：

為了書寫方便，令 $K_{ij}=K\left(X_{i},X_{j}\right)=\varphi\left(X_{i}\right)^{T}\varphi\left(X_{j}\right)$，又因為 $y^{2}_{i}=1$，將目標函數繼續拆分化簡得：

紅框內是常數項，在接下來的求導中就會被捨棄，為了簡化公式，在當前階段我們就可以忽略這兩項。忽略常數項後，重新整理一下當前得到的最佳化問題：

 

目標函數求導

在求導前，利用限制條件中 $\alpha_{1}$ 和 $\alpha_{2}$ 關係，將目標函數轉換為只有變數 $\alpha_{2}$ 的一元函數。

令限制條件 $\alpha_{1}y_{1} + \alpha_{2}y_{i} = -\sum \limits_{i=3}^{N}\alpha_{i}y_{i}=\zeta$，等號兩邊乘上 $y_{1}$，可得 $\alpha_{1}$：

$\alpha_{1} = \left(\zeta - \alpha_{2}y_{2}\right)y_{1}$

如果我們最開始只選擇一個分量作為變數，那麼該變數會永遠等於一個常數，演演算法將無法收斂，這也是 SMO 演演算法必須選擇兩個變數的原因。

重新將上面的等式代入目標函數，得到只有變數 $\alpha_{2}$ 的優化目標：

我們可以用符號來替代一些項，便於後面的求導：

別忘了前面章節我們提到核函數的交換性，即 $K_{ij}=K_{ji}$，寫作 $K_{ij}$ 或 $K_{ji}$ 表達的含義都相同。

接下來對目標函數進行求導，得： 

 

求變數 $\alpha_{2}$

當導數為 0 時，得到一個新的 $\alpha_{2}$，我們記作 $\alpha_{2}^{new}$，而舊的值記作 $\alpha_{2}^{old}$。

令 $\frac{\partial \theta\left(\alpha_{2}\right)}{\partial \alpha_{2}}=0$，得：

重新展開 $\zeta$ 和 $v_{i}$，得到 $\alpha^{new}$ 和 $\alpha^{old}$ 之間的關係：

可以重新記作：

可以發現，$\eta$ 其實就是 $\theta \left(\alpha_{2} \right)$ 的二階導，目標函數 $\theta \left(\alpha_{2} \right)$ 是一個凸函數，正常情況下它的二階導 $\eta$ 將會大於 $0$。

 

裁剪 $\alpha_{2}^{new}$ 以及求解 $\alpha_{1}$

回顧一下目前最佳化問題的限制條件：

上一小節我們使用 $\alpha_{1}y_{1} + \alpha_{2}y_{2} = \zeta$ 將目標函數轉換為只有自變數 $\alpha_{2}$ 的一元函數，之後求導得到了 $\alpha_{2}^{new}$，本節將介紹如何使用 $0 \le \alpha_{1},\alpha_{2} \le C$ 對 $\alpha_{2}^{new}$ 進行「裁剪」。

為了始終滿足 $\sum \limits^{N}_{i=1}\alpha_{i}y_{i}=0$ 的約束，訓練開始時一般是把 $\alpha$ 所有的分量都初始化為 $0$，之後每次迭代中對 $\alpha_{1}$、$\alpha_{2}$ 的調整都是基於舊值，新舊值之間的關係如下：

將這兩個限制條件繪製到座標系中，可以更直觀地看出 $\alpha_{2}^{new}$ 的上下限，分別用 $H$ 和 $L$ 表示。

當 $y_{i}\ne y_{j}$ 時：

當 $y_{i} = y_{j}$ 時：

根據得到的上下限 $H$ 和 $L$ 對 $\alpha_{2}^{new}$ 進行「裁剪」，得到 $\alpha_{2}^{new,clipped}$：

如上圖所示，落在紅色線段上的點 $\left(\alpha_{1}^{new},\alpha_{2}^{new,clipped} \right)$ 將滿足限制條件的約束，我們可以通過 $\alpha_{2}^{new,clipped}$ 求得 $\alpha_{1}^{new}$：

$ \alpha_{1}^{new} = \alpha_{1}^{old} + y_{1}y_{2}\left(\alpha_{2}^{old} - \alpha_{2}^{new,clipped} \right)$

 

$\alpha_{i}$ 與 $u_{i}$ 的關係

推導進行到這裡，你會發現函數 $u_{i}$ 中還有一個未知的常數項 $b$，SMO 每輪迭代都需要計算出 $b$，因為這關係到演演算法中的一個優化點，但是求解 $b$ 的前提是知道 $u_{i}$ 的輸出值，為了解決這一問題，本節將介紹 $u_{i}$ 的取值範圍與 $\alpha_{i}$ 之間的關係，為下一節求解 $b$ 做準備。

上文中，對於所有 $X_{i}$，我們設 SVM 的輸出值：

$u_{i}=\omega^{T}\varphi\left(X_{i} \right)+b$

在原問題轉對偶問題的那一節中，通過求偏導得到了 $\omega=\sum \limits^{N}_{j=1} \alpha_{j} y_{j} \varphi \left(X_{j}\right)$，這說明 $\alpha$ 影響著分離超平面多項式中的係數，它和常數項 $b$ 一樣，對 SVM 模型能否正確工作起著決定性作用。

過分關注於公式推導，很容易讓我們迷失其中，在開始本節的推導之前，有必要重申一下 $u_{i}$ 的含義。$u_{i}$ 這個輸出值代表著 SVM 對訓練樣本 $X_{i}$ 的歸類結果，而當我們改變 $\alpha_{i}$ 時，$u_{i}$ 也隨之改變，這說明 $\alpha_{i}$ 的取值影響著 SVM 對樣本 $X_{i}$ 的分類。

下面先羅列推導過程中需要用到的條件。

首先是 KKT 條件，這個理論是整個推導過程的關鍵。前文我們已經得到了 SVM 的 KKT 條件：

其次是 SVM 原問題的對偶問題中的限制條件：

最後是我們在對 SVM 對偶問題目標函數求偏導時，令 $\dfrac{\partial L}{\partial \xi_{i}}=0$ 得到的：

$\beta_{i}+\alpha_{i}=C \ ,\ i=1,2,\cdots,N$

結合上面的條件，從 $\alpha_{i}$ 可能出現的三種取值情況入手進行推導：

下面是推導過程：

最終得到 $\alpha_{i}$ 和 $u_{i}$ 之間的關係：

前面我們討論過，支援向量是離分離超平面最近的點，且所有支援向量到分離超平面的距離都相等，對於任意支援向量 $X_{s}$，滿足下面的關係式：

$\left| \omega^{T}\varphi\left(X_{s} \right)+b\right|=1$

$\Downarrow$

$y_{s}u_{s}=1$

顯然，當 $0 < \alpha_{i} < C$ 時，樣本向量 $X_{i}$ 在 SVM 模型中將作為支援向量。而除此之外的向量可能落在間隔內，也可能落在間隔外；可能被分離超平面正確分類，也可能被錯誤地分類。下面是一個簡單的 SVM 模型例子，通過這個圖可以更直觀地看到樣本和決策邊界之間的關係：

 

更新偏置 $b$

偏置 $b$ 是 $u_{i}$ 中的常數項，但是它並不會影響 $\alpha_{2}^{new}$ 的求解結果，因為這一項在 $u_{1}-u_{2}$ 時就已經被消除了，它間接影響的是一個提高演演算法收斂效率的優化點，這在下一節中再做介紹，在此之前先來看一下如何計算 $b$。

上一小節我們確定了 $u_{i}$ 的取值和 $a_{i}$ 之間的關係，這為求解 $b$ 創造了條件。如果 $0<\alpha_{i}<C$，說明 $X_{i}$ 為支援向量，直接將 $\alpha_{i}$ 代入 $y_{i}u_{i}=1$ 即可求得 $b$；如果 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 的值都不在 $\left(0,C \right)$ 區間內，則分別代入 $y_{i}u_{i}=1$ 求得 $b_{1}$、$b_{2}$，再取他們的平均值作為 $b$。

下面是求解步驟。

將 $y_{1}u_{1}=1$ 等號兩側分別乘以 $y_{1}$，進而求得 $b_{1}$：

為了減少計算量，我們還使用了前面得到的 $E$ 參與運算。

同理，求出 $b_{2}$：

前面說到，本次迭代中的 $X_{1}$、$X_{2}$ 如果都不屬於支援向量，偏置 $b$ 取 $b_{1}^{new}$、$b_{2}^{new}$ 的平均值：

Platt 在他1998年的論文中，2.3 小節末尾這樣寫道：

大概意思是說，如果 $H$ 不等於 $L$，$\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 兩個拉格朗日乘子都在邊界上（等於 $C$ 或 $0$）的時候，從 $b_{1}^{new}$ 到 $b_{2}^{new}$ 區間內的取值都是符合 KKT 條件約束的，這也是為什麼取 $b_{1}^{new}$、$b_{2}^{new}$ 的平均值做為結果的原因。這裡需要注意 $H$ 不等於 $L$ 這一前提，回看裁剪 $\alpha_{2}^{new}$ 那一節，你會發現只要 $C$ 大於 $0$，我們就能大概率保證 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 其中至少有一個在 $\left(0,C \right)$ 區間內。

那麼在 $H\ne L$ 的前提下， $y_{1}=y_{2}$ 時，是否會出現 $\alpha_{1}^{new}$、$\alpha_{2}^{new,clipped}$ 同時等於 $0$ 或同時等於 $C$ 的情況？在這種特殊情況下，如果取平均值做為 $b$，就會導致其中一個 $\alpha$ 違背 KKT 條件，我們又該如何處理？

還是回到裁剪 $\alpha_{2}^{new}$ 那一節中尋找答案，從 $y_{1}=y_{2}$ 的圖裡可以看出這種情況是有可能發生的，發生條件比較苛刻，分別是：

可以看到此時 $\alpha_{2}^{old}=\alpha_{2}^{new,clipped}$，在新舊值相等或變化極小的情況下，重新計算一遍 $b$ 是低效且無意義的。程式碼實現時，建議是在迴圈中直接跳過出現這種情況的迭代，那麼也就不會出現 $b$ 無法滿足 KKT 條件約束的問題。

 

用啟發式方法選擇兩個變數

如何選擇合適的 $\alpha_{1}$、$\alpha_{2}$ 以提高 SMO 演演算法的收斂速度是接下來要探討的內容，前文鋪墊許久的 $b$ 也將在本節發揮它的作用，事實上，如果不打算實現這一優化，我們完全可以在訓練結束後再通過支援向量計算得到 $b$，但是大部分應用場景的訓練集都非常龐大，我們必須見縫插針地對演演算法進行優化。

我們可以這樣理解 SMO 的工作原理，SMO 每次從向量 $\alpha$ 中選擇兩個分量進行優化，$\alpha$ 可以想象成一條直線的斜率，我們通過修改 $\alpha$ 來轉動這條直線，使直線不斷逼近某個角度，直到正確地分隔開所有訓練樣本，即最終目的是要使所有樣本都符合 KKT 條件的約束。

顯然，在某一次迭代中，僅通過優化兩個樣本系數得到的分離超平面不一定能夠正確地分類所有樣本，那麼，我們可以選擇當前被錯誤分類（違背 KKT 條件）的樣本系數作為下一輪迭代待優化的變數，以此提高演演算法的收斂速度，這也是 Platt 的論文 2.2 節中提到的啟發式選擇乘子的基本思想。

這時前面求出的 $b$ 就派上用場了。在某一輪迭代結束時，明確了 $b$ 和 $\alpha$，意味著可以通過函數 $u_{i}$ 計算出當前違背了 KKT 條件的訓練樣本。

先介紹如何選擇 $\alpha_{1}$。注意這裡 $\alpha_{1}$ 的含義不是指第一個樣本系數，它代表的是第一個待求的變數，$\alpha_{2}$ 同理。

啟發式演演算法會迴圈處理所有違背 KKT 條件的點，直到所有樣本都滿足 KKT 條件為止。迴圈內有兩種子迴圈用於選擇並處理變數，第一種是選所有違背 KKT 條件的樣本系數做為 $\alpha_{1}$ 進行遍歷，第二種是選擇違背了 KKT 條件且不在邊界上的樣本系數（$y_{i}u_{i}\ne1$ 且 $0 < \alpha_{i} < C$）做為 $\alpha_{1}$ 進行遍歷，且外層迴圈每次迭代只會執行其中一種子迴圈。整體流程是先執行一次第一種子迴圈，接著會一直呼叫第二種，直到 $0 < \alpha_{i} < C$ 的樣本都被正確分類，然後又會從頭開始，不斷重複此過程。需要注意的是，子迴圈的每次有效迭代都會導致分離超平面方程的係數 $\alpha$ 發生改變，有些待處理的點可能因此變得符合 KKT 條件，所以子迴圈在執行時，還需要跳過那些已經符合條件約束的點。

在子迴圈的每次迭代中，選出 $\alpha_{1}$ 後，再從 $0 < \alpha_{i} < C$ 的樣本系數中選出 $\alpha_{2}$，選擇標準是使得 $\left| E_{1}-E_{2}\right|$ 的值達到最大。從 $\alpha_{2}^{new}$ 的求值公式可以看出 $\left| E_{1}-E_{2}\right|$ 一定程度上反映了每次迭代的步長，增大步長有助於演演算法更快收斂。

可以發現啟發式演演算法在選擇 $\alpha_{1}$ 時，優先選擇不在邊界上的樣本，Platt 在他的論文中稱之為 非邊界樣本（non-bound example）。非邊界樣本做為支援向量，只是佔訓練樣本中的少數，Platt 認為優先處理非邊界樣本有助於減少迭代次數，秉承這一原則，$\alpha_{2}$ 也是從非邊界樣本中選出，只不過 $\alpha_{2}$ 不要求必須違背 KKT 條件，只要能使 $\left| E_{1}-E_{2}\right|$ 的值最大即可。

 

優化項，更新 $\omega$

線上性 SVM 中，可選用線性核 $K \left(X_{1},X_{2}\right)=X_{1}^{T}X_{2}$ 進行運算，其實相當於不使用核函數，那麼在程式實現 $u_{i}$ 函數的時候，我們應該使用 $\omega$ 參與運算而不是使用 $\alpha$：

$u_{i}=\omega^{T}X_{i}+b$

$\alpha$ 直接參與運算會浪費大量算力，正確的做法是使用 $\alpha$ 計算 $\omega$，並對 $\omega$ 做好快取：

 

關於 SMO 演演算法收斂性的討論

關於 SMO 演演算法的收斂性證明可以看 Osuna 等人所著的論文《An Improved Training Algorithm for Support Vector Machines》，SMO 演演算法每次選擇兩個乘子進行優化的思想就是來源於 Osuna 等人的理論。

論文中，$\alpha$ 中的變數被拆分為兩個集合 $B$ 和 $N$，$B$ 被稱為 工作集（Working Set），工作集中是待求的變數，SMO 中選出的兩個乘子就是工作集；$N$ 則代表固定的變數集合。

Osuna 他們先是證明了，將 $B$ 中的變數移動到 $N$ 後，目標函數的輸出仍然保持不變（見 3.2 節 Proposition 3.1）。也就是說，$B$ 中變數的值取得最優解後，將其中一些變數移動到 $N$，此時 $B$ 中剩下的變數值仍然是當前目標函數的最優解。

但如果把 $N$ 中的變數移動到 $B$，即目標函數待求的變數變多了，那麼此時 $B$ 中變數的值還是不是最優解就不得而知了。幸運的是，我們已經知道了 KKT 條件是目標函數取得最優解的充要條件，那麼在每次迭代只取 $N$ 中違背 KKT 條件的變數移動到 $B$ ，就能保證移動後 $B$ 中的值不會是目標函數的解，也就不會導致優化過程做了無用功，這也是 SMO 演演算法在選擇變數時，要求其中至少有一個變數違背 KKT 條件的原因。

總結一下上面的內容。$B$ 取得最優解後，將其中一些變數移入 $N$ ，$B$ 中剩下的變數仍然是目標函數的解；但是從 $N$ 中取出違背 KKT 條件的變數移動到 $B$，則會導致目標函數重新擁有待優化的空間。這說明 SMO 的每一次迭代都會讓 $\alpha$ 往最優解靠近，又因為目標函數是凸函數，演演算法將會在有限次迭代後收斂到全域性最優解。

 

測試

在訓練開始前需要保留一部分訓練樣本，這些樣本不能參與訓練，而是用於訓練結束後檢驗模型的可用性。這一步非常重要，通過分析測試中無法正確分類的樣本，將幫助我們更好地完善演演算法，例如用來判斷模型是否過擬合或欠擬合、$C$ 的值是否需要調整、核函數如何選型等等。

在介紹 SMO 的那一節中就已經提到了 $b$ 的計算方法，根據 SVM 的 KKT 條件，選一個支援向量 $X_{s}$ 即可通過下面公式計算得到：

$b=y_{s}- \sum \limits^{N}_{i=1} \alpha_{i} y_{i} K\left(X_{i},X_{s}\right)$

然後再通過 $y_{i}u_{i}$ 判斷樣本是否能夠被正確分類。如果選用了線性核，同樣可以學習 SMO 演演算法對 $\omega$ 進行快取。

其實關於測試還有很多學問，但是受限於篇幅以及本文重點是 SVM 演演算法，後續有機會在新文章中再做詳細介紹。

 

參考資料

浙江大學胡浩基機器學習公開課程

SMO演演算法原理

支援向量機（五）SMO演演算法

機器學習演演算法實踐-SVM中的SMO演演算法

Sequential Minimal Optimization: A Fast Algorithm for Training Support Vector Machines

An Improved Training Algorithm for Support Vector Machines

程式碼實現

 

推薦閱讀

學習筆記-拉格朗日函數

知識點 | 全面理解支援向量機

正定(positive definite)與半正定(semi-positive definite)

線性規劃的對偶問題

原始問題與對偶問題