SVM 原理: Level 2 Not Linear Separable and Lagrange Duality

by allenlu2007

前文提到 SVM 在 (binary) linear separable classifier 是 optimal (maximum) margin classifier.

對於 not linear separable classifier, 有兩種 cases:  (1) nonlinear separable; 以及 (2) not separable (linear or nonlinear).  

針對 (1), 可以用 kernel trick maps to higher dimensions (or infinite dimensions) and make it linear separable.  在後文會介紹。

針對 (2) define hinge loss function,  then do minimum hinge loss optimization.  From hard margin to soft margin.  Soft margin 可以和 kernel trick 結合,用在 nonlinear classification.  

本文 focus 在 method 2.

 

Linear Separable (Hard Margin) Lagrange Multiplier and Dual Problem

 

先 Review binary linear separable SVM (存在 hyperplane 可以分開不同 classes), object function and constraints 如下:

NewImage  

這是一個 QP 問題, subset of convex optimization.  標準解法是用 Lagrange multiplier 把所有 constraints 整合到一個 objective function:

NewImage

如果違反任何的不等式 constraints ,只要讓對應的 αi 變為無窮大,max𝓛 也變成無窮大。

最理想的情況是所有的不等式都滿足(假設 linear separable)。只要讓所有的 αi=0 就可得到

max𝓛 = 1/2 ||ω||^2.

 

因此原來的 optimation with inequality constraints, 最後可以轉換為以下的等式的 optimization,  min 𝛳(ω).

NewImage

 

下一個問題是如何求解 Lagrange Primal 問題?

第一個方法是用 QP (quadratic programming), 可以參考 wiki,  此處略過不表。

第二個方法則是用 Lagrange duality 轉換 primal problem 為 dual problem

NewImage 

也就是 dual problem 提供的至少是 lower bound.  在某一些情形下 (KKT 條件),  d* = p*.  這也是 CVX 以及其他 optimization package 用來做 numerical validation 的方式。

 

KKT 條件是什麼?

此處只做 hand-waving 的直覺式說明。丞上文就是要 min_x max_a f(x, a) = max_a min_x f(x, a).

KKT 是充分且必要條件。不過我們只說充分 (i.e. –> 為 true) 條件。

 

就是任何 x,a 的 domain (定義域!) 是 convex set (任兩點都有 line-of-sight) 以及所對應的 f(x,a) (值域) 是 convex function.   Convex set 以及 convex function 定義可以參考 Stanford Boyd 的 convex optimization lecture.

簡化來說 f(x,a) 在所有的 x,a domain 都是 convex.  以及 x,a 本身定義域也是 convex.   

 

f(x,a) 是 convex function 很容易理解。Convex function 的 local minimum 就是 global minimum (全定義域)。所以 min_x max_a 可以交換。附帶條件是 x and a 本身定義域也要是 convex.

 

偏微分解 Dual Problem

上述(和本文)的 optimization objective and constraint functions 都滿足 KKT 條件。可以參考 reference.

先解 min 𝓛, 對 w and b 偏微分,再把結果代回:

NewImage 

NewImage

NewImage

因此 dual problem 如下。解完後再求 w and b. 

NewImage

NewImage 

NewImage

在 predict phase:

NewImage

sgn (w.x + b) = sgn (sigma( αi yi xi . x + b) )  ==>  b 可以在 training 事先算出。因此在 predicting 只需要算出少數 αi>0 的 xi . x (dot product of non-zero items!!!).   這些 αi>0 的 xi 稱為 support vector.

 

下一個問題是如何求解 Lagrange Dual 問題?

Dual problem 如上,就是要找 { α1, α2, .. αn }.  光從 i=j 可以看出所有的平方項都是負值。

但 subject to the linear constraint.  並沒有 close form solution.  但有 numerical method.

最直接是用 QP 來解,不過又回到原點。更有效率的算法是 SMO (Sequential minimal optimization).

 

如果單純從算法角度來看,Lagrange primal 轉換為 dual problem 似乎沒有什麼好處。最多是更有效率的算法 (SMO?).   這是天大的錯誤!!  代表沒有 catch 到 SVM (support vector machine) 最重要的精髓。

什麼是 support vector machine?  machine 大概是指 machine learning, etc.?

Vector 似乎是指 data vector and dot product?  但 support 是指什麼?  

再看下圖 SVM example, maximum margin classifier.  有趣的是並非所有的 data points 一樣重要。

事實上只有三個 data points (1 black, 2 white) 真正決定了最後的 classifier.  其他所有的 data points 對於 classifier   完全沒有貢獻!!  這三個 data points 稱為 support vector!!!

1. 當然我們無法事先知道那一些 data points 是 support vectors.  在 training 時仍然需要所有的 data points computation 才能得到那一些 data pints 是 support vectors (αi > 0); 但有效率算法 (SMO).  對於非 support vectors (αi = 0), 我們可以完全忽略,在之後的的 predicting 計算也完全用不到。

2. 一但找到 support vector (where αi > 0), 之後的 predict 就非常容易。在 predict phase:

NewImage

NewImage 

NewImage

sgn (w.x + b) = sgn (Σ(αi yi xi . x) + b)  ==>  b 可以在 training 事先算出。在 predicting 只需要算出少數 αi>0 的 xi . x (dot product of non-zero items!!!).   

3. 在用 kernel trick 之後,w map 到更高維 (or infinite dimensions)。同樣如上。只需要管 support vector items  αi>0.

4. 和其他 classifier 比較。如 logistic classification, 基本上要考慮所有的 data points, 只是 transition 的 data points 機率部份佔比例高 (linear regression 每個 data point 一樣)。在 predict phase 也要考慮 high dimension 時計算比較複雜 (e.g. 如果是 1000 dimension 的 logistic regression).

 NewImage

 

再次回到 Dual Program.  最重要就是  αi > 0 的 data point 稱為 support vector.

有大量的 αi=0,  因此會讓 training 和 predict 算法都非常有效率。

Training 算法:  SMO

Predict 算法: dot product between x and xi (support vector)

 

Not Linear Separable (Soft Margin) Lagrange Multiplier and Dual Problem

上述都是假設存在 linear separable hyperplane, 也就是 optimal/maximum margin classifier.

實務上很多情形不存在 linear separable hyperplane, 例如 (1) data/feature 本身不是 linear separable; (2) data/feature 包含 error or noise; (3) model 本身是 probabilistic; (4) 有一些 outliner data.

Case 1: 如果 data/feature 非 linear separable, 但是 non-linear separable, 我們可以用 kernel trick, 見後文。

Case 2, 3, 4: 導入 hinge loss function and soft margin 觀念。

Hinge loss function:

NewImage

此時 optimization 問題的 objective function 變為:

NewImage

 

——————————————————————————————————————–

和之前的 linear separable optimization 問題比較:

NewImage

在 linear separable 情況,只要有任何 yi(w’ xi + b) < 1,  就可以讓 αi 變成無窮大而讓 𝓛 變無窮大。

也就是 loss 無窮大。這是無法接受的 condition, 因此這是 hard margin.

相較而言,Hinge loss function 可以容許 1-ξ <= yi(w’ xi + b) < 1, 只是 penalize 超過的部分: 

max(0, 1-yi (w’ xi + b)).    這是 soft margin.

——————————————————————————————————————–

 

我們可以修改原來的 constraints;

NewImage      NewImage

Hinge loss function 變成 max(0, ξ )=ξ.  ξ 稱為 slack variable, 對應 xi 允許偏離 functional margin 的量。 

因此新的 primal optimization 問題變成:

NewImage 

也可以從 hinge loss function 得到一模一樣的 objective function. 

NewImage

 

Soft Margin Dual Problem

請參考本文 for 推導過程。Soft margin 結果如下:

NewImage

和之前 Hard margin 比較如下。唯一的差別是 αi < C!! 其他基本都一樣。

有趣的是個別的 ξi 完全無影響!! 只有 Σξi (所有的 ξi summation) 反應在 C 上。 

NewImage

 

最後再整理一次:

NewImage

  

Outliner

mso

Multi-class SVM?

Non-linear SVM? (下文)

Kernel function is the same for both logistic regression and SVM?

SVM only needs to compute supporting vectors (?) dot product;  logistic regression needs to compute all?

 

Advertisements