文章目錄
- 引入
- 1 了解線性分類器
- 2 函數間隔和集合間隔
- 3 最大間隔分類器
- 4 從原始問題到對偶問題
- 5 K.K.T.條件
- 6 對偶問題求解
- 7 線性不可分的情況
- 8 核函數
- 9 使用松弛變量處理outliers
- 10 SMO算法
引入
調包俠近日開始深入了解SVM背後的故事，所參照文章為《支援向量機通俗導論–了解SVM 的三層境界》。需要說明的是，這裡主要記錄的是SVM的推導過程，且文中公式的編号與原文完全一緻。
1 了解線性分類器
令 x \boldsymbol{x} x表示資料點， y ∈ { + 1 , − 1 } y\in\{+1,-1\} y∈{+1,−1}表示類别，一個線性分類器的學習目标則是在 n n n維的資料空間中找到一個超平面，其表示為：
w T x + b = 0 (1.1) \tag{1.1} \boldsymbol{w}^T\boldsymbol{x}+b=0 wTx+b=0(1.1) 一個簡單的例子如下：已有一個二維平面，平面上有兩種不同的資料，分别用圈和叉表示。這些資料是線性可分的，即可以用一條直接将兩類資料劃分開，即超平面，并表示為 f ( x ) = w T x + b f(x)=\boldsymbol{w}^T\boldsymbol{x}+b f(x)=wTx+b。
根據函數取值的不同，有以下三種對應情況：
- x x x是超平面上的點 ⇔ f ( x ) = 0 \Leftrightarrow f(\boldsymbol{x})=0 ⇔f(x)=0；
- y = 1 y=1 y=1的資料點 ⇔ f ( x ) > 0 \Leftrightarrow f(\boldsymbol{x})>0 ⇔f(x)>0；
- y = − 1 y=-1 y=−1的資料點 ⇔ f ( x ) < 0 \Leftrightarrow f(\boldsymbol{x})<0 ⇔f(x)<0；
2 函數間隔和集合間隔
目前的推導，均假設資料集是線性可分的。在超平面 w T x + b \boldsymbol{w}^T\boldsymbol{x}+b wTx+b确定的情況下， ∣ w T x + b ∣ |\boldsymbol{w}^T\boldsymbol{x}+b| ∣wTx+b∣能夠表示點 x \boldsymbol{x} x到超平面的遠近，并可以通過觀察 w T x + b \boldsymbol{w}^T\boldsymbol{x}+b wTx+b與标簽 y y y的一緻性來判斷分類是否正确。是以，引入函數間隔如下：
γ ^ = y ( w T x + b ) = y f ( x ) (1.6) \tag{1.6} \hat{\gamma}=y\left(\boldsymbol{w}^{T} \boldsymbol{x}+b\right)=y f(\boldsymbol{x}) γ^=y(wTx+b)=yf(x)(1.6)而超平面關于資料集 T T T種所有樣本點 ( x i , y i ) (\boldsymbol{x}_i,y_i) (xi,yi)的的函數間隔最小值，即超平面關于資料集 T T T的函數間隔：
γ ^ = min γ ^ i , ( i = 1 , … , n ) (1.7) \tag{1.7} \hat{\gamma}=\min\hat{\gamma}_i,(i=1,\dots,n) γ^=minγ^i,(i=1,…,n)(1.7) 函數間隔的缺點在于如果成比例的改變 w \boldsymbol{w} w和 b b b，函數間隔的值也會相應增加。是以需要引入幾何間隔，其通過對 w \boldsymbol{w} w加入限制來定義真正點到超平面的距離。一個例子如下圖：
令 x 0 \boldsymbol{x}_0 x0表示 x \boldsymbol{x} x在超平面上的垂直投影點，則有 x = x 0 + γ w ∥ w ∥ \boldsymbol{x}=\boldsymbol{x}_0+\gamma\frac{\boldsymbol{w}}{\|\boldsymbol{w}\|} x=x0+γ∥w∥w。由于 x 0 \boldsymbol{x}_0 x0在超平面上的點，滿足 f ( x 0 ) = 0 f(\boldsymbol{x}_0)=0 f(x0)=0，代入超平面的方程 w T x + b = 0 \boldsymbol{w}^{T} \boldsymbol{x}+b=0 wTx+b=0，可以得到：
γ = w T x + b ∥ w ∥ = f ( x ) ∥ w ∥ (1.8) \tag{1.8} \gamma=\frac{\boldsymbol{w}^{T} \boldsymbol{x}+b}{\|\boldsymbol{w}\|}=\frac{f(\boldsymbol{x})}{\|\boldsymbol{w}\|} γ=∥w∥wTx+b=∥w∥f(x)(1.8) 為了得到 γ \gamma γ的定義，令 γ \gamma γ乘上類别 y y y，即得到集合間隔的定義：
γ ~ = y γ = γ ^ ∥ w ∥ \tilde{\gamma}=y\gamma=\frac{\hat{\gamma}}{\|\boldsymbol{w}\|} γ~=yγ=∥w∥γ^
3 最大間隔分類器
對一個資料集進行分類，如下圖，當超平面離資料點的間隔越大，分類的确信度也越大，是以，定義最大間隔分類器的優化目标如下：
max γ ~ (1.10) \tag{1.10} \max\tilde{\gamma} maxγ~(1.10) 同時需要滿足以下條件：
y i ( w T x i + b ) = γ ^ i ≥ γ ^ , i = 1 , … , n (1.11) \tag{1.11} y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)=\hat{\gamma}_i\geq\hat{\gamma}, i=1,\dots,n yi(wTxi+b)=γ^i≥γ^,i=1,…,n(1.11)
進一步，令函數間隔 γ ^ = 1 \hat{\gamma}=1 γ^=1，則目标函數轉化為：
max 1 ∥ w ∥ , s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , … , n (1.12) \tag{1.12} \max\frac{1}{\|\boldsymbol{w}\|},\ \ \ \ s.t.\ \ \ \ y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\geq1,i=1,\dots,n max∥w∥1, s.t. yi(wTxi+b)≥1,i=1,…,n(1.12) 一個例子如下，中間的實作代表尋找到的最優超平面，其到兩條虛線的距離相等，這個距離便是幾何間隔 γ ~ \tilde{\gamma} γ~，兩條虛線之間的距離等于 2 γ ~ 2\tilde{\gamma} 2γ~。虛線上的點，在SVM中，則對應于支援向量。
4 從原始問題到對偶問題
由于求 1 / ∥ w ∥ 1/\|\boldsymbol{w}\| 1/∥w∥的最大值等價于求 1 2 ∥ w ∥ 2 \frac{1}{2}\|\boldsymbol{w}\|^2 21∥w∥2的最小值，是以優化目标等價于
min 1 2 ∥ w ∥ 2 , s . t . y i ( w T x i + b ) ≥ 1 , i = 1 , … , n (2.2) \tag{2.2} \min\frac{1}{2}\|\boldsymbol{w}\|^2,\ \ \ \ s.t.\ \ \ \ y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\geq1,i=1,\dots,n min21∥w∥2, s.t. yi(wTxi+b)≥1,i=1,…,n(2.2) 由于目前優化目标結構的特殊性，可以通過拉格朗日對偶性變換到對偶變量的優化問題。這樣的好處在于：
1）對偶問題往往更容易求解；
2）可以自然地引入核函數，進而推廣到非線性分類問題。
融合拉格朗日函數的目标函數如下：
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 ) \mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha})=\frac{1}{2}\|\boldsymbol{w}\|^2-\sum_{i=1}^n\alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1) L(w,b,α)=21∥w∥2−i=1∑nαi(yi(wTxi+b)−1) 然後令：
θ ( w ) = max α i ≥ 0 L ( w , b , α ) \theta(\boldsymbol{w})=\max_{\alpha_i\geq0}\mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha}) θ(w)=αi≥0maxL(w,b,α) 當某個限制條件不滿足時，例如 y i ( w T x i + b ) < 1 y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)<1 yi(wTxi+b)<1，那麼隻需令 α i = ∞ \alpha_i=\infty αi=∞，則有 θ ( w ) = ∞ \theta(\boldsymbol{w})=\infty θ(w)=∞。是以，當所有限制條件均滿足時，有 θ ( w ) = 1 2 ∥ w ∥ 2 \theta(\boldsymbol{w})=\frac{1}{2}\|\boldsymbol{w}\|^2 θ(w)=21∥w∥2，亦即最初要最小化的量。
是以，在要求滿足限制條件的情況下最小化 1 2 ∥ w ∥ 2 \frac{1}{2}\|\boldsymbol{w}\|^2 21∥w∥2，等價于：
min w , b θ ( w ) = min w , b max α i ≥ 0 L ( w , b , α ) = p ∗ \min_{\boldsymbol{w},b}\theta(\boldsymbol{w})=\min_{\boldsymbol{w},b}\max_{\alpha_i\geq0}\mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha})=p^* w,bminθ(w)=w,bminαi≥0maxL(w,b,α)=p∗其中 p ∗ p^* p∗表示這個問題的最優值，且和最初的問題是等價的。
為了友善求解，這裡将最大和最小交換以下位置：
max α i ≥ 0 min w , b L ( w , b , α ) = d ∗ \max_{\alpha_i\geq0}\min_{\boldsymbol{w},b}\mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha})=d^* αi≥0maxw,bminL(w,b,α)=d∗ 交換後的問題是原始問題的對偶問題，最優質用 d ∗ d^* d∗來表示，且有 d ∗ ≤ p ∗ d^*\leq p^* d∗≤p∗。
5 K.K.T.條件
K.K.T.條件的意義在于：它是一個非線性規劃問題有最優解的充要條件。
對于标準的最優化問題，有：
min f ( x ) s.t. h j ( x ) = 0 , j = 1 , … , p g k ( x ) ≤ 0 , k = 1 , … , q x ∈ X ⊂ ℜ n (2.7) \tag{2.7} \begin{array}{ll} \min & f(x) \\ \text { s.t. } & h_{j}(x)=0, \quad j=1, \ldots, p \\ & g_{k}(x) \leq 0, \quad k=1, \ldots, q \\ & x \in \mathcal{X} \subset \Re^{n} \end{array} min s.t. f(x)hj(x)=0,j=1,…,pgk(x)≤0,k=1,…,qx∈X⊂ℜn(2.7)其中 f ( x ) f(x) f(x)是優化目标， h ( x ) h(x) h(x)是等式限制， g ( x ) g(x) g(x)是不等式限制， p p p和 q q q分别為等式和不等式限制的數量。
同時需要了解凸優化的概念： X ⊂ ℜ n \mathcal{X}\subset\Re^n X⊂ℜn為一凸集， f : X → ℜ f:\mathcal{X}\to\Re f:X→ℜ為一凸函數，凸優化就是要找到一點 x ∗ ∈ X x^*\in\mathcal{X} x∗∈X，使得 ∀ x ∈ X , f ( x ∗ ) ≤ f ( x ) \forall x\in\mathcal{X},f(x^*)\leq f(x) ∀x∈X,f(x∗)≤f(x)。
K.K.T.條件則是指上面最優化标準模型中的最小點 x ∗ x^* x∗必須滿足：
1） h j ( x ∗ ) = 0 , j = 1 , … , p , g k ( x ∗ ) ≤ 0 , k = 1 , … , q h_j(x^*)=0,j=1,\dots,p,\quad g_k(x^*)\leq0,k=1,\dots,q hj(x∗)=0,j=1,…,p,gk(x∗)≤0,k=1,…,q
2） Δ f ( x ∗ ) + ∑ j = 1 p λ j Δ h j ( x ∗ ) + ∑ k = 1 q μ k Δ g k ( x ∗ ) = 0 , λ j ≠ 0 , μ k ≥ 0 , μ k g k ( x ∗ ) = 0 \Delta f\left(x^{*}\right)+\sum_{j=1}^{p} \lambda_{j} \Delta h_{j}\left(x^{*}\right)+\sum_{k=1}^{q} \mu_{k} \Delta g_{k}\left(x^{*}\right)=0, \lambda_{j} \neq 0, \mu_{k} \geq 0, \mu_{k} g_{k}\left(x^{*}\right)=0 Δf(x∗)+∑j=1pλjΔhj(x∗)+∑k=1qμkΔgk(x∗)=0,λj=0,μk≥0,μkgk(x∗)=0
當然，我們這裡的優化目标是滿足條件的。
6 對偶問題求解
首先固定 α \alpha α，要讓 L \mathcal{L} L關于 w \boldsymbol{w} w和 b b b最小化，分别對 w \boldsymbol{w} w和 b b b求偏導：
∂ L ∂ w = 0 ⇒ w = ∑ i = 1 n α i y i x i (2.8) \tag{2.8} \frac{\partial L}{\partial \boldsymbol{w}}=0\Rightarrow\boldsymbol{w}=\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i ∂w∂L=0⇒w=i=1∑nαiyixi(2.8) ∂ L ∂ b = 0 ⇒ ∑ i = 1 n α i y i = 0 (2.9) \tag{2.9} \frac{\partial L}{\partial b}=0\Rightarrow\sum_{i=1}^n\alpha_iy_i=0 ∂b∂L=0⇒i=1∑nαiyi=0(2.9) 代入 L \mathcal{L} L：
L ( w , b , α ) = 1 2 ∥ w ∥ 2 − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 ) = 1 2 w T w − ∑ i = 1 n α i y i w T x i − ∑ i = 1 n α i y i b + ∑ i = 1 n α i = 1 2 w T ∑ i = 1 n α i y i x i − ∑ i = 1 n α i y i w T x i − ∑ i = 1 n α i y i b + ∑ i = 1 n α i = 1 2 w T ∑ i = 1 n α i y i x i − w T ∑ i = 1 n α i y i x i − ∑ i = 1 n α i y i b + ∑ i = 1 n α i = − 1 2 w T ∑ i = 1 n α i y i x i − ∑ i = 1 n α i y i b + ∑ i = 1 n α i = − 1 2 w T ∑ i = 1 n α i y i x i − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = − 1 2 ( ∑ i = 1 n α i y i x i ) T ∑ i = 1 n α i y i x i − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = − 1 2 ∑ i = 1 n α i y i ( x i ) T ∑ i = 1 n α i y i x i − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = − 1 2 ∑ i , j = 1 n α i y i ( x i ) T α j y j x j − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = − 1 2 ∑ i , j = 1 n α i y i α j y j x i T x j − b ∑ i = 1 n α i y i + ∑ i = 1 n α i = ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j (2.10) \tag{2.10} \begin{aligned} \mathcal{L}(\boldsymbol{w},b,\boldsymbol{\alpha})&=\frac{1}{2}\|\boldsymbol{w}\|^2-\sum_{i=1}^n\alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1)\\ &=\frac{1}{2}\boldsymbol{w}^T\boldsymbol{w}-\sum_{i=1}^n\alpha_iy_i\boldsymbol{w}^T\boldsymbol{x}_i-\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i\\ &=\frac{1}{2}\boldsymbol{w}^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-\sum_{i=1}^n\alpha_iy_i\boldsymbol{w}^T\boldsymbol{x}_i-\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i\\ &=\frac{1}{2}\boldsymbol{w}^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-\boldsymbol{w}^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}\boldsymbol{w}^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-\sum_{i=1}^n\alpha_iy_ib+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}\boldsymbol{w}^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-b\sum_{i=1}^n\alpha_iy_i+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}(\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i)^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-b\sum_{i=1}^n\alpha_iy_i+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}\sum_{i=1}^n\alpha_iy_i(\boldsymbol{x}_i)^T\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i-b\sum_{i=1}^n\alpha_iy_i+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}\sum_{i,j=1}^n\alpha_iy_i(\boldsymbol{x}_i)^T\alpha_jy_j\boldsymbol{x}_j-b\sum_{i=1}^n\alpha_iy_i+\sum_{i=1}^n\alpha_i\\ &=-\frac{1}{2}\sum_{i,j=1}^n\alpha_iy_i\alpha_jy_j\boldsymbol{x}_i^T\boldsymbol{x}_j-b\sum_{i=1}^n\alpha_iy_i+\sum_{i=1}^n\alpha_i\\ &=\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j\\ \end{aligned} L(w,b,α)=21∥w∥2−i=1∑nαi(yi(wTxi+b)−1)=21wTw−i=1∑nαiyiwTxi−i=1∑nαiyib+i=1∑nαi=21wTi=1∑nαiyixi−i=1∑nαiyiwTxi−i=1∑nαiyib+i=1∑nαi=21wTi=1∑nαiyixi−wTi=1∑nαiyixi−i=1∑nαiyib+i=1∑nαi=−21wTi=1∑nαiyixi−i=1∑nαiyib+i=1∑nαi=−21wTi=1∑nαiyixi−bi=1∑nαiyi+i=1∑nαi=−21(i=1∑nαiyixi)Ti=1∑nαiyixi−bi=1∑nαiyi+i=1∑nαi=−21i=1∑nαiyi(xi)Ti=1∑nαiyixi−bi=1∑nαiyi+i=1∑nαi=−21i,j=1∑nαiyi(xi)Tαjyjxj−bi=1∑nαiyi+i=1∑nαi=−21i,j=1∑nαiyiαjyjxiTxj−bi=1∑nαiyi+i=1∑nαi=i=1∑nαi−21i,j=1∑nαiαjyiyjxiTxj(2.10) 最終的優化問題為：
min α ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j s.t. α i ≥ 0 , i = 1 , … , n ∑ i = 1 n α i y i = 0 (2.15) \tag{2.15} \begin{array}{ll} \min\limits_{\boldsymbol\alpha} &\sum\limits_{i=1}^n\alpha_i-\frac{1}{2}\sum\limits_{i,j=1}^n\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j \\ \text { s.t. } & \alpha_i\geq0,i=1,\dots,n \\ & \sum\limits_{i=1}^n\alpha_iy_i=0 \end{array} αmin s.t. i=1∑nαi−21i,j=1∑nαiαjyiyjxiTxjαi≥0,i=1,…,ni=1∑nαiyi=0(2.15)
7 線性不可分的情況
根據目前的推導，有：
w ∗ = ∑ i = 1 n α i y i x i (2.18) \tag{2.18} \boldsymbol{w}^*=\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i w∗=i=1∑nαiyixi(2.18) 是以分類函數為
f ( x ) = ( ∑ i = 1 n α i y i x i ) T x + b = ∑ i = 1 n α i y i ⟨ x i , x ⟩ + b (2.19) \tag{2.19} \begin{aligned} f(x)&=(\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i)^T\boldsymbol{x}+b\\ &=\sum_{i=1}^n\alpha_iy_i\langle\boldsymbol{x}_i,\boldsymbol{x}\rangle+b \end{aligned} f(x)=(i=1∑nαiyixi)Tx+b=i=1∑nαiyi⟨xi,x⟩+b(2.19) 這種形式的有趣之處在于，對于新點 x \boldsymbol{x} x的預測，隻需要計算它與訓練資料點的内積。這一點至關重要，是之後使用核函數進行非線性推廣的基本前提。
事實上，支援向量也在這裡顯示，因為所有非支援向量所對應的 α \alpha α都是零。是以對于新點的内積計算實際上隻需要針對少量的支援向量。非支援向量的 α \alpha α均為零的原因是它們對超平面是沒有影響的。
目前的分類器是線性不可分的。
8 核函數
首先介紹使用原始的方法，用線性學習器學習一個非線性關系：需要選擇一個非線性特征集，并且将資料寫成新的表達形式。這等價于應用一個固定的非線性映射，将資料映射到特征空間，在特征空間中使用線性學習器。
是以，考慮以下分類函數：
f ( x ) = ∑ i = 1 n w i ϕ i ( x ) + b (2.21) \tag{2.21} f(\boldsymbol{x})=\sum_{i=1}^nw_i\phi_i(\boldsymbol{x})+b f(x)=i=1∑nwiϕi(x)+b(2.21)其中 ϕ : X → F \phi:\mathcal{X}\to\mathcal{F} ϕ:X→F是輸入空間到特征空間的映射。
進一步，決策規則使用測試點和訓練點的内積來表示：
f ( x ) = ∑ i = 1 n α i y i ⟨ ϕ ( x i ) , ϕ ( x ) ⟩ + b (2.22) \tag{2.22} f(\boldsymbol{x})=\sum_{i=1}^n\alpha_iy_i\langle\phi(\boldsymbol{x}_i),\phi(\boldsymbol{x})\rangle+b f(x)=i=1∑nαiyi⟨ϕ(xi),ϕ(x)⟩+b(2.22) 如果有一種方式可以在特征空間中直接計算内積 ⟨ ϕ ( x i ) , ϕ ( x ) ⟩ \langle\phi(\boldsymbol{x}_i),\phi(\boldsymbol{x})\rangle ⟨ϕ(xi),ϕ(x)⟩，就像在原始輸入點的函數中一樣，就可以直接建立一個非線性的學習器。這樣直接計算的方法就稱為核函數方法。
核函數是一個函數 K K K，對于所有 x , z ∈ X \boldsymbol{x},\boldsymbol{z}\in\mathcal{X} x,z∈X，滿足 K ( x , z ) = ⟨ ϕ ( x ) , ϕ ( z ) ⟩ K(\boldsymbol{x},\boldsymbol{z})=\langle\phi(\boldsymbol{x}),\phi(\boldsymbol{z})\rangle K(x,z)=⟨ϕ(x),ϕ(z)⟩。是以，這時的分類問題變為：
f ( x ) = ∑ i = 1 n α i y i K ( x i , x ) + b (2.27) \tag{2.27} f(\boldsymbol{x})=\sum_{i=1}^n\alpha_iy_iK(\boldsymbol{x}_i,\boldsymbol{x})+b f(x)=i=1∑nαiyiK(xi,x)+b(2.27) 相應的對偶問題為：
max α ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j K ( x i , x j ) s.t. α i ≥ 0 , i = 1 , … , n ∑ i = 1 n α i y i = 0 (2.34) \tag{2.34} \begin{array}{ll} \max\limits_{\alpha} & \sum\limits_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum\limits_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} K\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) \\ \text { s.t. } & \alpha_{i} \geq 0, i=1, \ldots, n \\ & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{array} αmax s.t. i=1∑nαi−21i,j=1∑nαiαjyiyjK(xi,xj)αi≥0,i=1,…,n∑i=1nαiyi=0(2.34)
9 使用松弛變量處理outliers
我們将偏離正常位置很遠的點，稱之為outlier。如下圖，黑圈圈起來的藍色點就是一個outlier，它偏離了自己原本所應該在的那個半空間，如果直接忽略它，原來的分隔超平面還是挺好的。
為了處理這種情況，SVM允許資料點在一定程度上偏離一下超平面。例如上圖中，黑色實線所對應的距離就是該outlier的偏離距離。于是，考慮到outlier問題，限制條件就變為：
y i ( w T x i + b ) ≥ 1 − ξ i , i = 1 , … , n (2.36) \tag{2.36} y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)\geq1-\xi_i,\quad i=1,\dots,n yi(wTxi+b)≥1−ξi,i=1,…,n(2.36)其中 ξ i \xi_i ξi稱為松弛變量，對應于資料點 x i \boldsymbol{x}_i xi允許便宜的量。當然，如果允許 ξ i \xi_i ξi任意大的話，那麼任意的超平面都是符合條件的。是以，我們需要使得 ξ i \xi_i ξi的總和最小：
min 1 2 ∥ w ∥ 2 + C ∑ i = 1 n ξ i (2.37) \tag{2.37} \min\frac{1}{2}\|\boldsymbol{w}\|^2+C\sum_{i=1}^n\xi_i min21∥w∥2+Ci=1∑nξi(2.37)其中 C C C是用于控制目标函數中兩項的權重，需要實作确定。是以，加入松弛變量的優化問題為
min 1 2 ∥ w ∥ 2 + C ∑ i = 1 n ξ i s.t. y i ( w T x i + b ) ≥ 1 − ξ i , i = 1 , … , n ξ i ≥ 0 , i = 1 , … , n (2.38) \tag{2.38} \begin{array}{cl} \min & \frac{1}{2}\|\boldsymbol{w}\|^{2}+C \sum\limits_{i=1}^{n} \xi_{i} \\ \text { s.t. } & y_{i}\left(\boldsymbol{w}^{T} \boldsymbol{x}_{i}+b\right) \geq 1-\xi_{i}, i=1, \ldots, n \\ & \xi_{i} \geq 0, i=1, \ldots, n \end{array} min s.t. 21∥w∥2+Ci=1∑nξiyi(wTxi+b)≥1−ξi,i=1,…,nξi≥0,i=1,…,n(2.38) 得到新的拉格朗日函數：
L ( w , b , ξ , α , r ) = 1 2 ∥ w ∥ 2 + C ∑ i = 1 n ξ i − ∑ i = 1 n α i ( y i ( w T x i + b ) − 1 + x i i ) − ∑ i = 1 n r i ξ i (2.39) \tag{2.39} \mathcal{L}(\boldsymbol{w},b,\boldsymbol\xi,\boldsymbol\alpha,\boldsymbol{r})=\frac{1}{2}\|\boldsymbol{w}\|^2+C\sum_{i=1}^n\xi_i-\sum_{i=1}^n\alpha_i(y_i(\boldsymbol{w}^T\boldsymbol{x}_i+b)-1+xi_i)-\sum_{i=1}^nr_i\xi_i L(w,b,ξ,α,r)=21∥w∥2+Ci=1∑nξi−i=1∑nαi(yi(wTxi+b)−1+xii)−i=1∑nriξi(2.39) 首先針對 w \boldsymbol{w} w、 b b b和 ξ \xi ξ最小化：
∂ L ∂ w = 0 ⇒ w = ∑ i = 1 n α i y i x i ∂ L ∂ b = 0 ⇒ ∑ i = 1 n α i y i = 0 ∂ L ∂ ξ i = 0 ⇒ C − α i − r i = 0 , i = 1 , … , n (2.40) \tag{2.40} \begin{aligned} \frac{\partial{L}}{\partial{\boldsymbol{w}}}&=0\Rightarrow\boldsymbol{w}=\sum_{i=1}^n\alpha_iy_i\boldsymbol{x}_i\\ \frac{\partial L}{\partial b}&=0\Rightarrow\sum_{i=1}^n\alpha_iy_i=0\\ \frac{\partial L}{\partial{\xi_i}}&=0\Rightarrow C-\alpha_i-r_i=0,\quad i=1,\dots,n \end{aligned} ∂w∂L∂b∂L∂ξi∂L=0⇒w=i=1∑nαiyixi=0⇒i=1∑nαiyi=0=0⇒C−αi−ri=0,i=1,…,n(2.40) 代入 L \mathcal{L} L，擷取和原來一阿姨那個的目标函數：
max α ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j (2.43) \tag{2.43} \max_\boldsymbol\alpha\sum_{i=1}^n\alpha_i-\frac{1}{2}\sum_{i,j=1}^n\alpha_i\alpha_jy_iy_j\boldsymbol{x}_i^T\boldsymbol{x}_j αmaxi=1∑nαi−21i,j=1∑nαiαjyiyjxiTxj(2.43) 由于 C − α i − r i = 0 C-\alpha_i-ri=0 C−αi−ri=0且 r i ≥ 0 r_i\geq0 ri≥0，則有 α i ≤ C \alpha_i\leq C αi≤C，是以：
max α ∑ i = 1 n α i − 1 2 ∑ i , j = 1 n α i α j y i y j x i T x j s.t. 0 ≤ α i ≤ C , i = 1 , … , n ∑ i = 1 n α i y i = 0 (2.44) \tag{2.44} \begin{array}{ll} \max \limits_{\boldsymbol\alpha} & \sum\limits_{i=1}^{n} \alpha_{i}-\frac{1}{2} \sum\limits_{i, j=1}^{n} \alpha_{i} \alpha_{j} y_{i} y_{j} \boldsymbol{x}_{i}^{T} \boldsymbol{x}_{j} \\ \text { s.t. } & 0 \leq \alpha_{i} \leq C, i=1, \ldots, n \\ & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{array} αmax s.t. i=1∑nαi−21i,j=1∑nαiαjyiyjxiTxj0≤αi≤C,i=1,…,n∑i=1nαiyi=0(2.44)
10 SMO算法
首先定義特征到結果的輸出函數：
u = ⟨ w , x ⟩ − b (3.24) \tag{3.24} u=\langle\boldsymbol{w},\boldsymbol{x}\rangle-b u=⟨w,x⟩−b(3.24) 重新定義優化目标為：
min w , b 1 2 ∥ w ∥ 2 s . j . y i ( ⟨ w , x i ⟩ − b ) ≥ 1 , ∀ i (3.25) \tag{3.25} \min_{\boldsymbol{w},b}\frac{1}{2}\|\boldsymbol{w}\|^2\quad s.j.\quad y_i(\langle\boldsymbol{w},\boldsymbol{x}_i\rangle-b)\geq1,\forall_i w,bmin21∥w∥2s.j.yi(⟨w,xi⟩−b)≥1,∀i(3.25) 求導有：
w = ∑ i = 1 n y i α i x i , b = ⟨ w , x k ) − y k ， for some α k > 0 \boldsymbol{w}=\sum_{i=1}^ny_i\alpha_i\boldsymbol{x}_i,\quad b=\langle\boldsymbol{w},\boldsymbol{x}_k)-y_k，\text{for some }\alpha_k>0 w=i=1∑nyiαixi,b=⟨w,xk)−yk，for some αk>0 得到 u = ∑ j = 1 n y j α j K ( x j , x ) − b u=\sum_{j=1}^ny_j\alpha_jK(\boldsymbol{x}_j,\boldsymbol{x})-b u=∑j=1nyjαjK(xj,x)−b。
轉換為對偶問題并加入松弛變量：
min α Ψ ( α ) = min α 1 2 ∑ i = 1 n ∑ j = 1 n α i α j y i y j K ( x i , x j ) − ∑ i = 1 n α i s.t. 0 ≤ α i ≤ C , i = 1 , … , n ∑ i = 1 n α i y i = 0 (3.29) \tag{3.29} \begin{aligned} \min _{\boldsymbol\alpha} \Psi(\boldsymbol{\alpha})=& \min _{\boldsymbol\alpha} \frac{1}{2} \sum_{i=1}^{n} \sum_{j=1}^{n} \alpha_{i} \alpha_{j}y_{i} y_{j} K\left(\boldsymbol{x}_{i}, \boldsymbol{x}_{j}\right) -\sum_{i=1}^{n} \alpha_{i} \\ \text { s.t. } & 0 \leq \alpha_{i} \leq C, i=1, \ldots, n \\ & \sum_{i=1}^{n} \alpha_{i} y_{i}=0 \end{aligned} αminΨ(α)= s.t. αmin21i=1∑nj=1∑nαiαjyiyjK(xi,xj)−i=1∑nαi0≤αi≤C,i=1,…,ni=1∑nαiyi=0(3.29) 接下來要解決的問題是：在 α i ∈ { α 1 , … , α n } \alpha_i\in\{\alpha_1,\dots,\alpha_n\} αi∈{α1,…,αn}求上述目标函數的最小值。為求解這些乘子，每次從中任意抽取兩個乘子 α i \alpha_i αi和 α j \alpha_j αj，然後固定餘下乘子，使得目标函數隻是關于 α i \alpha_i αi和 α j \alpha_j αj的函數。這樣，不斷的從一堆乘子中任意抽取兩個求解，不斷地疊代求解子問題，最終達到求解原問題的目的。
而原對偶問題的子問題的目标函數可以表達為：
Φ = 1 2 K i j α i 2 + 1 2 K j j α j 2 + K i j α i α j − α i − α j + Φ c o n s t a n t (3.30) \tag{3.30} \Phi=\frac{1}{2}K_{ij}\alpha_i^2+\frac{1}{2}K_{jj}\alpha_j^2+K_{ij}\alpha_i\alpha_j-\alpha_i-\alpha_j+\Phi_{constant} Φ=21Kijαi2+21Kjjαj2+Kijαiαj−αi−αj+Φconstant(3.30)