支持向量機

04-30

1. 概述

支持向量機是機器學習中的一種分類方法，屬於判別式模型(Discriminative Model)中的一種。其基本思想是：對於給定的數據集D在樣本空間中找到一個劃分超平面，從而將不同類別的樣本分開。如圖1 所示：

圖 1

圖1中的灰色區域部分的寬度即為「間隔」(margin), 支持向量機的目標在於尋找一個最大間隔的劃分超平面，使得該超平面將不同類別的樣本區分開。最大間隔的劃分超平面對訓練樣本的局部擾動的「容忍」性最好，分類結果最魯棒，對未見示例的泛化能力也最強。

2. Linear SVM

在樣本空間中，劃分超平面可以通過下面的線性方程來描述：

$omega^Tx+b = 0$

其中，w為法向量，決定了超平面的方向；b為位移項，決定了超平面與原點之間的距離。接下來，如何計算樣本空間中任意點x到超平面的距離呢？首先，先回顧一下向量投影的相關知識：

圖2

向量xx沿單位向量 $mu$ 方向的投影距離d可由下列公式推導出：

$d = | overrightarrow{xx}|cos heta = | overrightarrow{xx}| | hat{mu}|cos heta = overrightarrow{xx} cdot hat{mu}$

圖3

對於圖3中超平面外的一點x，其到超平面的距離推導如下：

$egin{align} &ecause x, x ext{ on hyperplane} \ & herefore omega^Tx = -b, omega^Tx = -b \ & ecause omega ot hyperplane \ & herefore omega^T cdot (x -x) = 0 \ & herefore distance = project(x - x) to omega end{align}$

所以，x到超平面的距離dist為：

$egin{align} dist &= |frac{omega^T}{|omega|} (x -x)| \ & = frac{|omega^Tx - omega^Tx|}{|omega|} \ &= frac{|omega^Tx+b|}{|omega|} end{align}$

其中， $frac{omega^T}{left | omega ight | }$ 表示沿超平面法向量 $omega$ 方向的單位向量。

給定訓練集 $D ={(x_1, y_1), (x_2, y_2), ..., (x_n, y_n)}, y_i in {-1, +1}$ ，當 $y_i$ =+1，有 $omega^Tx_i+b>0$ ；當 $y_i$ =-1，有 $omega^Tx_i+b < 0$ 。聯立這兩種情況得： $y_i(omega^Tx_i+b) >0$ 。所以點x到超平面的距離可以轉化為：

$egin{align} dist &= frac{|omega^Tx+b|}{|omega|} \ & = frac{1}{|omega|} y(omega^Tx+b) end{align}$

支持向量機的基本思想是最大化間隔("margin")，也就是最大化「支持向量」(距離超平面最近的樣本點)到超平面的距離，表示成目標函數為：

$egin{align} &max_{omega, b} margin(omega, b) \ &s.t. margin(omega, b)= min_{i = 1, ..., n}frac{1}{|omega|} y_i(omega^Tx_i+b) end{align}$

圖4

如圖4所示，取經過異類支持向量的兩個超平面分別為：　

$omega^Tx+b = +1, omega^Tx+b = -1$

則 $min_{i = 1, 2, ..., n}y_i(omega^Tx_i+b) = 1$ ，所以上述的目標函數可以簡化為：

$egin{align} &max_{omega, b} frac{1}{|omega|} \ &s.t. y(omega^Tx+b) geq 1 end{align}$

顯然，最大化 $left | omega ight |^{-1}$ 等價於最小化 $left | omega ight|^2$ ，於是，目標函數等價於

$egin{align} &min_{omega, b} frac{1}{2}|omega|^2 \ &s.t. y(omega^Tx+b) geq 1 end{align}$

3. Dual Problem

拉格朗日對偶問題：

$egin{align} &min_{omega} f(omega) \ &s.t. g_i(omega) leq 0small{(不等式約束)}, i = 1, 2, ..., k \ & h_j(omega) = 0small{(等式約束)}, j = 1, 2, ..., l end{align}$

為目標函數的每條約束條件引入拉格朗日乘子 $alpha_i geq 0, eta_j e 0$ ，則該問題的拉格朗日函數可以寫為

$egin{align} &L(omega, alpha, eta) = f(omega) + sum_{i=1}^{k} alpha_ig_i(omega) + sum_{j = 1}^{l}eta_jh_j(omega) \ end{align}$

KKT 條件（拉格朗日函數得到最優解需要滿足以下條件）：

$frac{partial{L(omega, alpha, eta)}}{partial{omega}} = 0$
$alpha_ig_i(omega) = 0$
$h_j(omega) = 0$

KKT 條件的推導過程如下：

因為 $alpha_i g_i(omega) leq 0, eta_jh_j(omega) = 0$ ，所以

$max_{alpha, eta} L(omega, alpha, eta) = f(omega)\ min_{omega}max_{alpha, eta} L(omega, alpha, eta) = min_{omega}f(omega)$ $min_{omega} max_{alpha, eta} L(omega, alpha, eta)$ 的對偶函數可以寫成為

$egin{align} max_{alpha, eta}min_{omega} L(omega, alpha, eta) &= max_{alpha, eta}[min_{omega}f(omega) + min_{omega}alpha g(omega) + min_{omega}eta h(omega)]\ & = min_{omega}f(omega) + max_{alpha, eta}min_{omega}alpha g(omega) end{align}$

又因為

$egin{equation} min_{omega}alpha g(omega) = left{egin{aligned} 0, if alpha = 0 or g(omega) = 0\ -infty, if alpha e 0 and g(omega) e 0 end{aligned} ight. end{equation}$

所以，當 $alpha = 0 or g(omega) = 0$ 時， $max_{alpha, eta}min_{omega} L(omega, alpha, eta) = min_{omega}f(omega)$

也即是： $min_{omega} max_{alpha, eta} L(omega, alpha, eta) = max_{alpha, eta} min_{omega} L(omega, alpha, eta)$

上式表明，當滿足一定條件時，原問題，對偶問題的解是相同的，且在最優解 $omega^*$ 處 $alpha = 0 or g(omega^*) = 0$ (即 $alpha g(omega^*) = 0$ )。可得：

$L(omega^*, alpha, eta) = min_{omega}L(omega, alpha, eta)$

所以 $omega^*$ 是函數 $L(omega, alpha, eta)$ 的極值點，也即 $frac{partial{L(omega, alpha, eta)}}{partial{omega}}vert_{omega = omega^*} = 0$

綜上所述：

$egin{equation} left{egin{aligned} & min_{omega} max_{alpha, eta} L(omega, alpha, eta) = max_{alpha, eta} min_{omega} L(omega, alpha, eta) = min_{omega}f(omega)= f(omega^*)\ & frac{partial{L(omega, alpha, eta)}}{partial{omega}}vert_{omega = omega^*} = 0 \ &alpha g(omega) = 0\ & h(omega) = 0 end{aligned} ight. end{equation}$

4. Dual SVM

對於Linear SVM 的目標函數

$egin{align} &min_{omega, b} frac{1}{2}|omega|^2 \ &s.t. y(omega^Tx+b) geq 1 end{align}$

對函數的約束條件引入拉格朗日乘子得到拉格朗日函數為：

$egin{align} &L(omega, b, alpha) = frac{1}{2}|omega|^2 + sum_{i = 1}^{n}alpha_i(1 - y_i(omega^Tx_i+b)) end{align}$

當滿足KKT條件時，原問題等價於其對偶問題

$egin{align} & max_{alpha}min_{omega, b} L(omega, b, alpha) = max_{alpha}min_{omega, b} frac{1}{2}|omega|^2 + sum_{i = 1}^{n}alpha_i(1 - y_i(omega^Tx_i+b)) end{align}$

令 $L(omega, b, alpha)$ 對 $omega$ 和b求偏導數得

$egin{align} frac{partial{}L(omega, b, alpha)}{partial{omega}} &= omega - sum_{i = 1}^{n}alpha_iy_ix_i = 0 \ omega & = sum_{i = 1}^{n}alpha_iy_ix_i \ frac{partial{}L(omega, b, alpha)}{partial{b}} &= sum_{i = 1}^{n}alpha_iy_i = 0 \ end{align}$

代入拉格朗日函數，消除 $omega$ 和b，得：

$egin{align} L(omega, b, alpha) &= frac{1}{2}|omega|^2 + sum_{i = 1}^{n}alpha_i - sum_{i = 1}^{n}alpha_iy_iomega^{*T}x_i - b sum_{i = 1}^{n}alpha_iy_i \ &= frac{1}{2}|omega|^2 + sum_{i = 1}^{n}alpha_i - sum_{i = 1}^{n}sum_{j = 1}^{n}alpha_ialpha_jy_iy_jx_i^Tx_j \ & = sum_{i = 1}^{n}alpha_i - frac{1}{2}sum_{i = 1}^{n}sum_{j = 1}^{n}alpha_ialpha_jy_iy_jx_i^Tx_j end{align}$

　　所以，對偶問題的目標函數可化為

$egin{align} & max_{alpha} sum_{i = 1}^{n}alpha_i - frac{1}{2}sum_{i = 1}^{n}sum_{j = 1}^{n}alpha_ialpha_jy_iy_jx_i^Tx_j \ &s .t. sum_{i = 1}^{n}alpha_iy_i = 0 \ & alpha_i geq 0, i =1, 2, ..., n end{align}$

根據KKT條件 $alpha_i^*(1 - y_i(omega^{*T}x_i+b^*)) = 0$

當 $alpha_i^* = 0$ 時，對應的樣本點 $x_i$ 不會對目標函數產生影響；

當 $alpha_i^* >0$ 時，則必有 $1 - y_i(omega^{*T}x_i+b^*) = 0$ ，所以

$egin{align} 1 &= y_i(omega^{*T}x_i+b^*) \ b^* &= y_i - omega^{*T}x_i, i in ext{index of support vector} \ omega^* & = sum_{i = 1}^{n}alpha_iy_ix_i = sum_{i in SV} alpha_iy_ix_i end{align}$

　　因此，對於 $alpha_i >0$ 的樣本點處於最大間隔邊界( $y_i(omega^{*T}x_i+b) = 1$ )上，也就是所謂的"支持向量"。

5. SMO

$egin{align} &max_{alpha} sum_{i = 1}^{n}alpha_i - frac{1}{2}sum_{i = 1}^{n}sum_{j = 1}^{n}alpha_ialpha_jy_iy_jx_i^Tx_j \ &s.t. sum_{i = 1}^{n}alpha_iy_i = 0,\ & alpha_igeq 0 , i = 1, 2, ..., n end{align}$

　　上述目標函數是一個二次規劃問題，可使用通用的二次規劃演算法來求解，但該問題的計算複雜度正比於訓練樣本的數目，可用SMO演算法高效求解：

未完待續（To be continue） ...

參考文獻

[1] 周志華. 機器學習

[2] Jun Wu. Web Search & Recommendation—SVM

[3] mo_wang. 深入理解拉格朗日乘子法（Lagrange Multiplier) 和KKT條件