機器學習演算法 II : support vector machine (SVM)

05-04

第一節：導論

Support vector machine 最早是用來處理線性可分問題的。假設我們有一組數據 $(oldsymbol{x}_{i}, y_{i}), i = 1, 2, ..., N$ . 其中，矢量 $oldsymbol{x}_{i}$ 是一組feature，標量 $y_{i}$ 為該矢量所對應的label. 規定label的取值只能是 -1 或者 1. 對於線性可分問題，我們可以在由矢量 $oldsymbol{x}_{i}$ 張成的空間中畫出所有的數據點，並且可以找到一個超平面，使得該超平面將這組數據點分為兩類。超平面一側的所有點的label都是 -1，另外一側所有點的label都是1. 如下圖所示。

圖片中是二維情形下的support vector machine的示意圖。這裡每一個數據點都有一個label。這些數據點可以用一條直線分離為兩類。一類點label 都是1，另外一類點label都是 -1. 很明顯，不止一條線可以將這組數據點分為兩類。Support vector machine演算法的目的是找出一條最優的分離線。最優分離線(或者對應高維情況下的最優分離面)的定義在下一節。

第二節：最優分離面的定義

把數據點記作 $(oldsymbol{x}_{i}, y_{i}), i = 1, 2, ..., N$ . 假設分離平面為 $eta^{T}x + eta_0 = 0$ . 位於平面一側的點滿足關係 $eta^{T}x + eta_0 > 0$ ，另一側的點滿足關係 $eta^{T}x + eta_0 < 0$ . 通過合適的scaling，我們總是可以令所有 label 為 1 的點滿足關係 $eta^{T}x + eta_0 ge 1$ ，所有 label 為 -1 的點滿足關係 $eta^{T}x + eta_0 le -1$ . 總是存在一組參數 $eta, eta_0$ ，使得平面 $P_1: eta^{T}x + eta_0 = 1$ 與 $P_2: eta^{T}x + eta_0 = -1$ 之間的距離最大。定義此時的分離平面 $eta^{T}x + eta_0 = 0$ 為最優分離面。接下來我們要計算平面 $P_1$ 與 $P_2$ 之間的距離。

已知一點 $x_0$ 到線性集合 $Ax = b$ 的距離的平方為 $d^2 = (b - Ax_0)^T (AA^{T})^{-1} (b - Ax_0)$ . 如果已知點 $x_0$ 位於平面 $P_2$ 上，也就是該點滿足 $eta^{T}x_0 + eta_0 = -1$ . 那麼該點距離平面 $P_1$ 的距離為

$d = frac{2}{||eta||_2}$ . 所以最優分離面的計算可以歸結為下面的優化問題：

$min_{eta} frac{1}{2}||eta||^2 \ ext{s.t. } -y_{i}(eta^{T}x_{i} + eta_0) le -1, i = 1, 2, ..., N$

這個問題並不容易求解。為了求解這個問題，我們需要引入拉格朗日對偶關係。

第三節：拉格朗日對偶

上一節已經證明了，最優分離面的求解可以歸結為計算一個受限約束條件下的極小值問題。這類問題可以通過拉格朗日乘子法來解決。定義拉格朗日函數為

$L(eta, eta_0; alpha) = frac{1}{2}eta^T eta + sum_{i = 1}^{N}alpha_i Big( -y_i(eta^T x_i + eta_0) + 1 Big)$

為了計算拉格朗日函數的極小值，根據 KKT 條件（關於KKT條件，這裡有一篇文章，給出了非常好的推導: 淺談最優化問題的KKT條件），求該函數對變數 $eta, eta_0$ 的梯度，令梯度為零，得到

$abla_{eta}L(eta, eta_0; alpha) = eta - sum_{i = 1}^{N}alpha_i y_i x_{i} = 0$

$frac{partial L}{partial eta_0} = -sum_{i = 1}^{N}alpha_i y_{i} = 0$

此外，根據 KKT 條件，我們有

$alpha_i ge 0, forall i$

$alpha_{i}Big( -y_{i}(eta^T x_i + eta_0) + 1Big) ge 0, forall i$

由此，我們可以得到拉格朗日對偶函數為

$g(alpha) = inf_{eta, eta_0} L(eta, eta_0; alpha) = sum_{i =1}^{N}alpha_i - frac{1}{2} sum_{i= 1}^{N} sum_{j = 1}^{N} alpha_{i}alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j}$

利用拉格朗日對偶關係，原來的極小化問題可以轉化為一個極大化問題：

$max_{alpha} g(alpha)\ ext{s.t. } alpha_{i } ge 0, i = 1, 2, ..., N \ sum_{i = 1}^{N}alpha_{i}y_i = 0$

相比原問題，這個問題更容易求解。下一節將會給出求解該類問題的一個演算法。

第四節：內點法求解拉格朗日對偶問題

上一節已經將計算最優分離面問題轉化為它的拉格朗日對偶問題，該問題可以重新寫作一種等價形式為:

$min_{alpha} -g(alpha)\ ext{s.t. } -alpha_{i } le 0, i = 1, 2, ..., N \ sum_{i = 1}^{N}alpha_{i}y_i = 0$

為了求解這個問題，我們可以用內點法(interior point method)。在這裡我已經描述過內點法在線性規劃問題中的應用：凸優化演算法 I: 內點法(interior point method)求解線性規劃問題

同樣可以使用內點法求解現在的拉格朗日對偶問題。為此，定義函數:

$h(alpha, lambda; t) = -sum_{i = 1}^{N}alpha_i + frac{1}{2}sum_{i = 1}^{N}sum_{j = 1}^{N}alpha_{i}alpha_{j}y_{i}y_{j}x_{i}^{T}x_{j} + sum_{i = 1}^{N} -frac{1}{t}log alpha_{i} + lambdasum_{i = 1}^{N}alpha_{i}y_{i}$

定義對稱矩陣 $A_{ij} = y_{i}y_{j}x_{i}^{T}x_{j}$ . 這個矩陣可以進一步寫作 $A = xi^{T}xi$ , 其中 $xi = (y_1x_1, y_2x_2, ..., y_Nx_N)$ . 因為通常情況下點的個數遠大於矢量 $x_{i}$ 的維數，所以矩陣 $A$ 為不可逆矩陣。利用這個記號，函數 $h(alpha, lambda; t)$ 可以寫作

$h(alpha, lambda; t) = -sum_{i = 1}^{N}alpha_i + frac{1}{2}alpha^{T}Aalpha + sum_{i = 1}^{N} -frac{1}{t}log alpha_{i} + lambda alpha^{T}y$

對於固定的參數 $t$ ，我要計算使得該函數取得極值時變數 $alpha, lambda$ 的值. 一旦知道了 $alpha$ 的值，我們就可以通過 $eta = sum_{i = 1}^{N}alpha_i y_i x_{i}$ 求出最優分離面的法向量 $eta$ 的值，並且進一步求出截距 $eta_0$ . 注意， $alpha$ 為長度為 $N$ 的矢量， $lambda$ 為一個標量。

對變數 $alpha, lambda$ 求微分，得到

$frac{partial h}{partial alpha_{k}} = -1 + A_{kj}alpha_{j} - frac{1}{t}frac{1}{alpha_{k}} + lambda y_{k}$

$frac{partial h}{partial lambda} = alpha^{T} y$

令微分等零，得到一個方程組

$egin{pmatrix} frac{partial h}{partial alpha} \ frac{partial h}{partial lambda} end{pmatrix} = egin{pmatrix} 0\ 0 end{pmatrix}$

可以用牛頓迭代法求解該方程，牛頓迭代公式為

$egin{pmatrix} alpha^{(n+1)} \ lambda^{(n+1)} end{pmatrix} = egin{pmatrix} alpha^{(n)} \ lambda^{(n)} end{pmatrix} - H^{-1}egin{pmatrix} frac{partial h}{partial alpha} \ frac{partial h}{partial lambda} end{pmatrix}$

這裡，Hessian矩陣 $H$ 為

$H = egin{pmatrix} A_{ij} + frac{1}{t}frac{delta_{ij}}{alpha_{i}^2} & y \ y^T & 0 end{pmatrix}$

其中，矩陣 $A_{ij} = y_{i}y_{j}x_{i}^{T}x_{j}$ .

通過牛頓迭代，可以求出對應固定參數 $t$ 時方程的解 $(alpha_{t}^{star}, lambda_{t}^{star})$ .根據內點法的定義，我們有 $lim_{t ightarrow infty} (alpha_{t}^{star}, lambda_{t}^{star}) = (alpha^{star}, lambda^{star})$ . 通過淬火演算法，我們可以得到符合精度的解。

第五節：程序

我已經寫了一個Python程序來實現這個演算法。程序地址為:

https://github.com/PrimerLi/svm?

github.com

第六節：結果

對於一組可以線性分離的點，通過上一節的程序可以解得最優分離面。如下圖所示：

第七節：附錄I

在這裡，我將要推導如何計算空間中一點到一個線性集合的距離。這個公式在推導兩個平面之間的距離時起了關鍵性作用。

定義一個線性集合為 $Sigma: Ax = b$ . 其中 $A$ 為一個矩陣， $b$ 為一個矢量。超平面可以理解為一個特殊的線性集合。空間中一點 $x_0$ 到集合 $Sigma$ 的距離定義為:

$d = min_{x} || x- x_0 ||, x in Sigma$ .

為了求解距離的表達式，我們可以藉助凸優化演算法。首先，將問題重新表述為

$min_{x} frac{1}{2} || x - x_0 ||^2 \ ext{s.t. } A x = b$

定義拉格朗日函數為

$L(x; lambda) = frac{1}{2} (x - x_0)^T (x - x_0) + lambda^{T} (Ax - b)$

求梯度:

$abla_{x}L = x - x_0 + A^{T}lambda$

令梯度為零，得到 $x = x_0 - A^{T}lambda$ . 拉格朗日對偶函數為

$g(lambda) = inf_{x}L(x; lambda) = frac{1}{2} lambda^{T} A A^{T} lambda + lambda^T(Ax_0 - AA^{T}lambda - b) = -frac{1}{2}lambda^{T} A A^{T} lambda + lambda^{T}(Ax_0 - b)$

$abla_{lambda}g(lambda) = -AA^{T}lambda + Ax_0 - b$

令梯度為零，求得 $lambda^{star} = (AA^{T})^{-1}(Ax_0 - b)$ . 這裡，因為線性集合的定義中，約束條件的個數小於變數的個數，所以矩陣 $AA^{T}$ 可逆，並且該矩陣為正定矩陣。將 $lambda^{star}$ 代入 $g(lambda)$ ，得到

$g(lambda^{star}) = max_{lambda} g(lambda)= frac{1}{2}(Ax_0 - b)^T(AA^{T})^{-1}(Ax_0 - b) = frac{1}{2}d^2$

所以，空間中一點到線性集合的距離為

$d = sqrt{(Ax_0 - b)^T(AA^{T})^{-1}(Ax_0 - b)}$

對於一張平面 $P: eta^{T}x + eta_0 = 0$ ，空間中一點 $x_0$ 到該平面的距離為

$d = frac{||eta^T x_{0} + eta_0 || }{||eta||}$

很容易看出來，兩張平面 $P_1: eta^{T}x + eta_0 = 1; P_2: eta^T x + eta_0 = -1$ 之間的距離為

$d = frac{2}{||eta||}$

第八節：附錄II

上面的全都是hard margin SVM的演算法。所謂hard margin，指的是該分類方法不允許出現任何不可分的點。實際情況下，兩類點未必是嚴格可分的，而且就算兩類點是嚴格可分的，我們有時也希望對margin做一些鬆動，以錯分一些點為代價換取一個更寬的margin. 這時就需要用到soft margin SVM. 該演算法與hard margin SVM 演算法唯一的區別是拉格朗日對偶問題中限制條件變成了 $0 le alpha_i le C, i = 1, 2, ..., N$ , 也就是我們的目標函數變為

$max_{alpha} g(alpha)\ ext{s.t. } 0 le alpha_{i } le C, i = 1, 2, ..., N \ sum_{i = 1}^{N}alpha_{i}y_i = 0$

當 $alpha_i = 0$ 時， $y_{i}(eta^Tx_{i} + eta_0) > 1$ ，此時點落在上下兩個邊界之外; $alpha_{i} = C$ 時， $y_{i}(eta^Tx_{i} + eta_0) < 1$ ，此時點落在上下兩個邊界之間 ; $0 < alpha_i < C$ 時， $y_{i}(eta^T x_{i} + eta_0 ) = 1$ ，此時點在落在上下兩條邊界上。

這個受限優化問題仍然可以使用內點法求解. 構造輔助函數:

$f(alpha, lambda; t_1, t_2) = -sum_{i} alpha_i + frac{1}{2}alpha^T A alpha + lambdasum_{i}alpha_i y_i - frac{1}{t_1}sum_{i}logalpha_i - frac{1}{t_2}sum_{i}log(C - alpha_i)$

為了簡化，可以令 $t_1 = t_2$ , 於是輔助函數簡化為

$f(alpha, lambda; t) = -sum_{i} alpha_i + frac{1}{2}alpha^T A alpha + lambdasum_{i}alpha_i y_i - frac{1}{t}sum_{i}logalpha_i(C - alpha_i)$

該函數的梯度為

$frac{partial f}{partial alpha_k } = -1 + A_{kj}alpha_j + lambda y_{k} - frac{1}{t} Big(frac{1}{alpha_k} - frac{1}{C - alpha_k}Big)$

$frac{partial f}{partial lambda} = alpha^{T}y$

Hessian矩陣元素為

$frac{partial^2 f}{partialalpha_{k}partialalpha_{l}} = A_{kl} + frac{1}{t} delta_{kl} Big(frac{1}{alpha_{k}^2} + frac{1}{(C - alpha_{k})^2} Big)$

$frac{partial^2 f}{partial alpha_{k}partial lambda} = frac{partial^2f}{partiallambdapartialalpha_{k}} = y_{k}$

$frac{partial^2f}{partial lambda^2} = 0$

矩陣形式為

$H = egin{pmatrix} A_{kl} + frac{1}{t} delta_{kl} Big(frac{1}{alpha_{k}^2} + frac{1}{(C - alpha_{k})^2} Big) & y \ y^T & 0 end{pmatrix}$

當 $C ightarrowinfty$ 時，Hessian矩陣退化為hard margin SVM的形式。

只需對原來的 SVM 程序稍作修改就可以實現soft margin SVM. 程序地址為:

https://github.com/PrimerLi/svm/blob/master/soft_margin_svm.py?

github.com

結果如圖所示：

如果點嚴格可分，那麼我們仍然可以得到與SVM 相同的結果；如果有不可分的點，那麼 soft margin SVM 仍然可以給出一個比較好的結果，而hard margin SVM在這時就得不到任何結果了。