推導 | SVM詳解（1）SVM基本型

05-04

P.S. 鑒於個人水平有限，若有表述錯誤之處敬請指出，願我們共同進步~
原文放在我的博客上的~傳送門：

推導 | SVM詳解（1）SVM基本型?

www.zuozuovera.com

1-基本型推導

SVM一直是我非常喜歡的一個演算法，所以沒事喜歡推一推。

這裡嘗試用簡單直白的語言來對它的推導過程進行介紹~如果你覺得你已經把高數和高中數學忘得差不多了，我想這或許就是你一直在找的簡明SVM推導過程介紹~??

給定 $D={(x1,y1),(x2,y2),...,(xm,ym)},y_i in {-1,+1}$ ，SVM考慮基於訓練集 $D$ 在樣本空間中找到一個劃分超平面(hiperplane)，將不同類別的樣本分開。

劃分超平面公式：

${f omega}^Tx+b=0 ag{1.1}$ （別慌，它其實就是一條直線公式而已）

其中 $omega=(omega_1;omega_2;...;omega_d;)$ 為法向量，決定了超平面的方向； $b$ 為位移項，決定了超平面與原點之間的距離。通常劃分超平面用 $(omega,b)$ 來表示，因為其可被法向量 $omega$ 和位移 $b$ 確定。

樣本空間中任意點 $x$ 到超平面 $(omega,b)$ 的距離可寫為 $r=frac{|omega^Tx+b|}{||omega||} ag{1.2}$
（再次別慌，讓我們轉動我們掌握了初中數學知識的小腦瓜來想一下，其實這就是點到直線的距離公式對吧）
假設超平面 $(omega,b)$ 能將訓練樣本正確分類，對於 $(x_i,y_i)in D$ ,有以下式子：

$egin{cases}omega^Tx_i+b > 0, & y_i = +1\omega^Tx_i+b < 0, & y_i = -1end{cases} ag{1.3}$

這其實便是 邏輯回歸 的思路，非黑即白，但是這明顯對自己的演算法太自信了對吧。我們可愛的支持向量機對此表示懷疑，並且多留了一個心眼，於是它令： $egin{cases}omega^Tx_i+b geq +1, & y_i = +1\omega^Tx_i+b leq -1, & y_i = -1end{cases} ag{1.4}$

如圖所示：

其中距離超平面最近的幾個訓練樣本點使上式的等號成立，這幾個訓練樣本就被稱作支持向量（support vector），兩個異類支持向量到超平面的距離之和，也稱為間隔（margin），為

$gamma = frac{2}{||omega||} ag{1.5}$ (其實就是 $omega^Tx_i+b = +1$ 和 $omega^Tx_i+b = -1$ 兩條直線之間的距離公式)

那麼按我們的設想，我們做分類學習，實際上就是為了找到一個劃分超平面將這些樣本給隔開，那麼什麼樣子的劃分超平面是最有效的呢？

從直觀上來看，位於正負樣本「正中間」的劃分超平面，也就是上上圖紅色的那一個劃分超平面，應該是最好的，因為它的魯棒性最好，對未知樣本的泛化性最好。

那麼如何去得到這個剛好位於正負樣本「正中間」的劃分超平面呢？

思考一下，是不是只要我們讓間隔最大，這樣只要我們取間隔中間的那條直線，我們就可以找到這個最棒的劃分超平面了？

換句話說，對於基於SVM的分類學習而言，問題已經從找到一個最好的劃分超平面轉換為了找到樣本空間里的最大化間隔。

我們用數學語言來描述一下這個更新後的問題，就變成了找到能滿足 $式(1.4)$ 的約束條件的參數 $omega$ 和 $b$ ，並且要使得 $gamma = frac{2}{||omega||}$ 中的 $gamma$ 最大。

用數學公式來表示是這個樣子。

$max_{omega,b} frac{2}{||omega||},s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.6}$

OK，你可能會喊：

等等等等， $max_{omega,b} frac{2}{||omega||}$ 是表示 $max gamma$ 我懂，但是你這個條件 $y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m$ 是什麼鬼你要不要解釋一下？

嗯咳，讓我們暫停一下，回看一下約束條件：

$egin{cases}omega^Tx_i+b geq +1, & y_i = +1\omega^Tx_i+b leq -1, & y_i = -1end{cases} ag{1.4}$

注意，是不是上下兩個約束條件的左右式子相乘（ $omega^Tx_i+b geq +1 * y_i = +1$ or $omega^Tx_i+b leq -1 * y_i = -1$ ）就等於 $y_i(omega^Tx_i+b) geq 1$ 了？

OK，讓我們繼續往下。對於式子

$max_{omega,b} frac{2}{||omega||},s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.6}$ 顯然，為了最大化間隔，僅需最大化 $frac{1}{||omega||}$ ，這等價於最小化 $||omega||^2$ 。於是上式我們可以重寫為 $min_{omega,b}frac{1}{2}||omega||^2,s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.7}$

這就是SVM的基本型。

2-凸二次規劃問題

$min_{omega,b}frac{1}{2}||omega||^2,s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.7}$

在我們開始對這個式子進行求解之前，首先我們需要注意到，它其實是一個凸二次規劃問題（convex quadratic programming）。

等等，你可能會問，什麼叫做凸二次規劃問題？

（下方涉及較為複雜的數學表達，非戰鬥人員請迅速撤離現場。如果你已經做好了心理準備，請扛上草稿本和我一起來~）

2.1 凸集

在講凸二次規劃問題之前，我們需要介紹一些更細緻的定義。

首先是凸集，這個的幾何意義如圖所示，指集合中任意兩點間的線段永遠在集合中的集合。

你可以看到，左圖中任意兩點，它們的線段一定會在 $C$ 這個集合中，所以它就是一個凸集，但是對於右圖而言，其線段就可能會有部分不在集合中，因此它不是凸集。

如果我們用數學定義來描述凸集的話，它是指這樣的一個集合 $C$ ：對任意 $x,y in C, Theta in R, 0 leq Theta leq 1$ ，都有

$Theta x + (1-Theta)y in C ag{2.1}$

常見的凸集有，n維實數空間；一些範數約束形式的集合；仿射子空間；凸集的交集；n維半正定矩陣集。

2.2 凸函數

那麼知道凸集是什麼意思後，讓我們看看凸函數。

凸函數的幾何意義是，函數任意兩點(x, y)連線上的值一定大於對應自變數區(x, y)間內的函數值(f(x),f(y))，示例圖如下：

你可以看到，將xy連接起來的直線上的值，一定大於xy兩點範圍內的函數值$f(x)$

如果我們用數學定義來描述凸函數的話，凸函數 $f(x)$ 是這樣的一個函數：定義域為凸集 $D(f)$ ，且對於任意 $x,y in D(f),Theta in R, 0 leq Theta leq 1$ ，有

$f(Theta x + (1-Theta)y) leq Theta f(x) + (1-Theta)f(y) ag{2.2}$

常見的凸函數有，指數函數族；非負對數函數；仿射函數；二次函數；常見的範數函數；凸函數非負加權的和等。

2.3 凸優化問題

講解完凸集和凸函數的定義，終於到凸優化問題了。 凸優化問題，實際上就是研究定義於凸集中的凸函數最小化問題。

正式的說，凸優化問題在優化問題中的形式是這樣的

$min f(x), s.t. x in C ag{2.3}$

其中 $f$ 是一個凸函數， $C$ 為凸集， $x$ 是優化變數。

因為上面這個表達還是有些含糊，所以凸優化問題我們更常用這個形式來表示它

$min f(x), s.t. g_i(x) leq 0, i = 1,...,m, h_i(x) = 0, i = 1,...,m ag{2.4}$

其中 $f$ 是一個凸函數， $g_i$ 是一個凸函數, $h_i$ 為仿射函數， $x$ 是優化變數。

常見的凸優化問題有，線性規劃、二次規劃、二次約束的二次規劃、半正定規劃。

2.4 二次規劃

二次規劃（Quadratic Programming，簡稱QP）是一類典型的優化問題，包括凸二次規劃和非凸二次優化。在此類問題中，目標函數是變數的二次函數，而約束條件是變數的線性不等式。

假定變數個數為 $d$ ，約束條件的個數是 $m$ ，則標準的二次規劃問題形如

$min_x frac{1}{2} x^TQx + c^Tx, s.t. Ax leq b ag{2.5}$

其中 $x$ 為 $d$ 維向量， $Qin R^{d imes d}$ 為實對稱矩陣， $A in R^{m imes d}$ 為實矩陣， $b in R^m$ 和 $c in R^d$ 為實向量， $Ax leq b$ 的每一行對應一個約束。

通常一個優化問題可以從兩個角度來考慮，即主問題(primal problem)和對偶問題(dual problem)。在約束最優化問題中，常常利用拉格朗日對偶性將原始問題（主問題）轉換成對偶問題，通過解對偶問題來得到原始問題的解。這樣做是因為對偶問題的複雜度往往低於主問題。

$min_{omega,b}frac{1}{2}||omega||^2, s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.7}$

在求解SVM的時候，我們也會通過其拉格朗日對偶性，將該主問題式(1.7)轉換成對偶問題，然後進行求解。

需要說明的是，因為主問題本身是一個凸二次規劃問題，因此它是能直接用現成的優化計算包求解的，使用拉格朗日乘子法得到其對偶問題是為了優化運算效率。

2.5 拉格朗日乘子法

拉格朗日乘子法（Largrange multipliers）是一種尋找多元函數在一組約束下的極值的方法。通過引入拉格朗日乘子，可將有 $d$ 個變數與 $k$ 個約束條件的最優化問題轉化為具有 $d+k$ 個變數的無約束優化問題求解。

這樣說你可能會覺得很抽象，那麼讓我們先舉一個稍微簡單一點的例子。

2.5.1 等式約束的優化問題

先考慮一個等式約束的優化問題，假定 $x$ 為 $d$ 維向量，我們想要尋找 $x$ 的某個取值 $x^*$ ，使得目標函數 $f(x)$ 最小且同時滿足 $g(x)=0$ 的約束。從幾何角度看，這個問題的目標是在方程 $g(x)=0$ 確定的 $d-1$ 維曲面上尋找能使目標函數最小化的點。如圖所示

通過上面的描述，我們不難得到如下結論：

對於約束曲面上的任意點 $x$ ，該點的梯度 $abla g(x)$ 正交於約束曲面；
在最優點 $x^*$ ，目標函數在該點的梯度 $abla f(x^*)$ 正交於約束曲面；

由此可知，在最優點 $x^*$ ，如上圖所示，梯度 $abla g(x)$ 和 $abla f(x)$ 的方向必相同或相反，即存在 $lambda eq 0$ ( $lambda$ 稱為拉格朗日乘子)使得 $abla f(x^*) + lambda abla g(x^*) = 0 ag{2.6}$

基於上面這個式子，我們可以定義拉格朗日函數

$L(x,lambda) = f(x) + lambda g(x) ag{2.7}$

你可能會疑惑，為什麼拉格朗日函數會是這個樣子。那麼讓我們對這個函數進行求導看看：

當 $L(x,lambda)$ 對 $x$ 求導時：(因為要求最優解，所以我們需要置 $abla_x L(x, lambda)$ 為0) $abla_x L(x, lambda) = abla f(x) + lambda abla g(x) = 0 ag{2.8}$
當 $L(x,lambda)$ 對 $lambda$ 求導時：（我們同樣置 $abla_{lambda} L(x, lambda)$ 為0） $abla_{lambda} L(x, lambda) = 0 + g(x) = 0 ag{2.9}$

注意，在一開始，我們的目標是尋找 $x$ 的某個取值 $x^*$ ，使得目標函數 $f(x)$ 最小且同時滿足 $g(x)=0$ 的約束。

那麼通過拉格朗日函數的兩次對不同變數的求導，你可以發現

式(2.8) = 式(2.6)，這是為了使得目標函數 $f(x)$ 最小
式(2.9) = 約束條件 $g(x)=0$ ，這是為了滿足約束條件

因此，原約束優化問題就轉化為了對拉格朗日函數$L(x, lambda)$的無約束優化問題。

2.5.2 不等式約束的優化問題

現在考慮不等式約束 $g(x) leq 0$ ，如圖B.1(b)所示，此時最優點 $x^*$ 要麼在 $g(x) < 0$ 的區域里，要麼在邊界 $g(x) = 0$ 上。

對於 $g(x)<0$ 的情形，約束 $g(x) leq 0$ 不起作用，可直接通過條件 $abla f(x)=0$ 來獲得最優點，這等價於將 $lambda$ 置0，然後對 $abla_x L(x, lambda)$ 置0得到最優點
對於 $g(x)=0$ 的情形，類似於上面我們對等式約束的分析，但需注意的是，此時 $abla f(x^*)$ 的方向必與 $abla g(x^*)$ 相反，即存在常數 $lambda > 0$ 使得 $abla f(x^*) + lambda abla g(x^*) = 0$

對上面描述的兩種情況進行整合，在約束 $g(x) leq 0$ 下最小化 $f(x)$ 的任務，可以轉化為在如下約束下最小化 $L(x,lambda) = f(x) + lambda g(x)$ 的任務：

$egin{cases}g(x) leq 0\ lambda geq 0\ lambda_j g_j(x) = 0end{cases} ag{2.10}$

式(2.10)就是大名鼎鼎的Karush-Kuhn-Tucker（簡稱KKT）條件。

2.5.3 多個約束條件的優化問題

在對等式約束優化問題和不等式約束優化問題進行講解後，我們可以將其推廣到多個約束。

考慮具有 $m$ 個等式約束和 $n$ 個不等式約束，且可行域 $D subset R^d$ 非空的優化問題

$min_x f(x), s.t. h_i(x)=0 (i = 1,...,m), g_j(x) leq 0 (j = 1,...,m) ag{2.11}$ 引入拉格朗日乘子$ $lambda = (lambda_1, lambda_2, ..., lambda_m)^T$ 和 $mu = (mu_1,mu_2,...,mu_n)^T$ ，相應的拉格朗日函數為 $L(x,lambda, mu) = f(x) + sum_{i=1}^m lambda_i h_i(x) +sum_{j=1}^n mu_j g_j(x) ag{2.12}$ 由不等式約束引入的KKT條件(j=1,2,...,n)為

$egin{cases}g_j(x) leq 0\ mu_j geq 0\ mu_j g_j(x) = 0end{cases} ag{2.13}$

2.5.4 SVM的拉格朗日函數

好了好了，我想看了前面那麼多推導，你可能已經想捶我了。（逃

其實前面說那麼多，都是為了這部分做鋪墊，那麼讓我們來看看如何得出SVM的拉格朗日函數吧！

首先回顧一下SVM基本式的公式——

$min_{omega,b}frac{1}{2}||omega||^2,s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.7}$ 我希望現在你能一眼發現，它和前面式(2.11)的相似之處。

你可以看到，對於SVM基本式而言，其——

$f(omega, b) = frac{1}{2}||omega||^2$
$g(omega, b) = 1-y_i(omega^Tx_i+b) leq 0,i=1,2,...,m.$
$h(omega, b) = 0$

因此，我們將SVM的 $f(omega, b)、g(omega, b)、h(omega, b)$ 代入式(2.12)中後，就可以得到該問題的拉格朗日函數了，即

$L(omega,b, alpha) = frac{1}{2}||omega||^2 + sum_{i=1}^m alpha_i (1-y_i(omega^Tx_i + b)) ag{2.14}$

其中 $alpha = (alpha_1; alpha_2;...;alpha_m)$ ,拉格朗日乘子 $alpha_i geq 0$ 。

3-對偶問題

前面我們說過，一個優化問題可以從兩個角度來考慮，即主問題(primal problem)和對偶問題(dual problem)。在約束最優化問題中，常常利用拉格朗日對偶性將原始問題（主問題）轉換成對偶問題，通過解對偶問題來得到原始問題的解。這樣做是因為對偶問題的複雜度往往低於主問題。

3.1 多約束對偶問題

在講解SVM的對偶問題之前，我們先來看一下多約束對偶問題的通用解。

多約束對偶問題的主問題:
$min_x f(x), s.t. h_i(x)=0 (i = 1,...,m), g_j(x) leq 0 (j = 1,...,m) ag{2.11}$
其相應的拉格朗日函數為 $L(x,lambda, mu) = f(x) + sum_{i=1}^m lambda_i h_i(x) +sum_{j=1}^n mu_j g_j(x) ag{2.12}$

基於(2.12)，對主問題(2.11)的拉格朗日對偶函數 $Gamma: R^m cdot R^n ightarrow R$ 定義為

$Gamma(lambda,mu) = inf_{x in D} L(x,lambda,mu) = inf_{x in D} (f(x) + sum_{i=1}^m lambda_i h_i(x) +sum_{j=1}^n mu_j g_j(x)) ag{3.1}$

若 $ilde{x} in D$ 為主問題(2.11)可行域中的點，則對任意 $mu geq 0$ 和 $lambda$ 都有

$sum_{i=1}^m lambda_i h_i(x) + sum_{j=1}^n mu_j g_j(x) leq 0 ag{3.2}$

進而有

$Gamma(lambda,mu) = inf_{x in D} L(x,lambda,mu) leq L( ilde{x},lambda,mu) leq f( ilde{x}) ag{3.3}$

若主問題(2.11)的最優值為 $p^*$ ，則對任意 $mu geq 0$ 和 $lambda$ 都有

$Gamma(lambda,mu) leq p^* ag{3.4}$

即對偶函數給出了主問題最優值的下界。顯然，這個下界取決於 $mu$ 和 $lambda$ 的值。於是一個很自然的問題就是：基於對偶函數能獲得的最好下界是什麼？這就引出了優化問題 $max_{lambda, mu} Gamma(lambda, mu) s.t. mu geq 0 ag{3.5}$

式(3.5)就是主問題（2.11）的對偶問題，其中 $mu$ 和 $lambda$ 稱為對偶變數（dual variable）。無論主問題（2.11）的凸性如何，對偶問題（3.5）始終是凸優化問題。

考慮式(3.5)的最優值 $d^*$ ，顯然有

$d^* leq p^*$ ，這稱為「弱對偶性(weak duality)」成立；
若 $d^* = p^*$ ，則稱為「強對偶性（strong duality）」成立，此時由對偶問題能獲得主問題的最優下界；

對於一般的優化問題，強對偶性通常不成立，但是若主問題是凸優化問題，如式(2.11)中 $f(x)$ 和 $g_j(x)$ 均為凸函數， $h_i(x)$ 為仿射函數，且其可行域中至少有一點使不等式約束嚴格成立，則此時強對偶性成立。

P.S. 在強對偶性成立時，將拉格朗日函數分別對元變數和對偶變數求導，再同時令導數等於0，即可得到原變數與對偶變數的數值關係。
於是對偶問題解決了，主問題也就解決了。

3.2 SVM的對偶問題

那麼讓我們回顧一下

SVM的主問題
$min_{omega,b}frac{1}{2}||omega||^2,s.t. y_i(omega^Tx_i+b) geq 1, i = 1,2,...,m ag{1.7}$
SVM的拉格朗日函數
$L(omega,b, alpha) = frac{1}{2}||omega||^2 + sum_{i=1}^m alpha_i (1-y_i(omega^Tx_i + b)) ag{2.14}$ 其中 $alpha = (alpha_1; alpha_2;...;alpha_m)$ ,拉格朗日乘子 $alpha_i geq 0$ 。

你可以發現，SVM恰恰滿足了前面我們所說的強對偶性。

因此，考慮令 $L(omega,b, alpha)$ 對 $omega$ 和 $b$ 的偏導為0可得

$omega = sum_{i=1}^m alpha_i y_i x_i ag{3.6}$ $0 = sum_{i=1}^m alpha_i y_i ag{3.7}$ 將式(3.6)代入(2.14)，就可以將 $L(omega,b, alpha)$ 中的 $omega$ 和 $b$ 消去，再考慮式(3.7)的約束，就得到式（2.14）的對偶問題。 $max_{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 x_i^T x_j ag{3.8}$

$s.t. sum_{i=1}^m alpha_i y_i = 0, alpha_i geq 0, i=1,2,...,m$

4-求解模型

解出 $alpha$ 後，求出 $omega$ 和 $b$ 即可得到模型

$f(x) = omega^T x + b = sum_{i=1}^m alpha_i y_i x_i^Tx + b ag{4.1}$

從對偶問題（3.8）解出的 $alpha_i$ 是式(2.14)中的拉格朗日乘子，它恰好對應著訓練樣本 $(x_i,y_i)$ 。因為式(1.7)中有不等式約束，因此上述過程還需滿足KKT條件，即 $egin{cases}alpha_i geq 0\ y_i f(x_i)-1 geq 0\ alpha_i(y_i f(x_i)-1) = 0end{cases} ag{4.2}$

於是，對任意訓練樣本 $(x_i,y_i)$ ，總有 $alpha_i=0$ 或 $y_i f(x_i)=1$ 。

若 $alpha_i = 0$ ，則該樣本將不會在式（4.1）的求和中出現，也就不會對 $f(x)$ 產生任何影響；
若 $alpha_i > 0$ ，則必有 $y_i f(x_i)=1$ ，所對應的樣本點位於最大間隔邊界上，是一個支持向量。

這顯示出支持向量機的一個重要性質：

訓練完成後，大部分的訓練樣本都不需保留，最終模型僅與支持向量有關。

那麼如何求解式（3.8）呢？

不難發現，這是一個二次規劃問題，可使用通用的二次規劃演算法來求解，這一部分可以參考剛才對【二次規劃】的講解，除此之外，還可以使用SMO等演算法對其進行求解。

關於SMO演算法，我們就下次再說啦~

5-References

[1] 周志華. 機器學習[M]. 清華大學出版社, 2016.

[2] 凸優化|技藝

[3] Stanford CS229 Machine Learning的教學資料