SVM 原理: Level 1 Max Margin Linear Classifier

by allenlu2007

本文參考

1. Wiki SVM

2. CS231n note

3. SVM 導論

 

SVM 一些基本特性

1. Non-probabilistic binary linear classifier  (similar to least square error optimization)

2. Can generalize to multi-class classification (similar to logistic regression to softmax regression)

3. Can generalize to nonlinear classification using the kernel trick (similar to the logistic regression map feature)

4. Can generalize to the infinite dimension using the kernel trick and vector dot product. 

5. Mostly convex optimization (linear case, similar to logistic regression).  In some case, not convex (e.g. nonlinear kernel trick)?

 

SVM 的本質 (Vector Dot Product)

SVM 最基本的特性就是 linear separator 如下圖。主要就是基於 vector dot product (data vector dot product with linear function 的 normal vector!)

如果是 H1, 無法 sparate two classes (dot product of black data 非相同正/負號).

H2, 可以 separate two classes (dot product of back data and white data 分正負號)

H3, 同 H2, 但有更好的 margin (minimum dot product 比 H2 好)

1. SVM 基本上就是 max margin linear classifier (H3)!!

2. 後面我們會推廣到 not linearly separable case: define hinge loss function

    再引入 Lagrange primal and dual problems for optimization.

3. 最後用 kernel trick 解 nonlinear classification.

 

=> Linear Separable Classification 的 Procedure 如下

把所有的 data points (black and white) 都和 Hx 的 normal (稱為 Wx) 作 dot products.

1.  Make sure all black data (and white data) 的 dot products 都同號

2.  Makke sure black data 的 dot products 和 white data 的 dot products 是異號

3. Minimum black data 和 minimum white data dot products 愈大愈好 (optimization) 

NewImage

以上的 procedure 仍有盲點。主要是以 boundary 為主 (e.g. H3).  

 

如果有多個 classes 如何處理?

明顯不能只靠一個 boundary.  p 種 classes in general 需要 p boundaries.

p 為 2 是 special case, 可以用 1 個 boundary (W2 = -W1,  Weq = W2-W1).

 

下圖包含 3 種 classes (cat, dog, ship),  對應 3 個 Wi (bias can be absorbed).  

注意只是 example, 最後的結果是錯的。貓的分數遠低於狗以及船。

SVM 是用第二種方式。

   NewImage

 

SVM Loss Function

SVM 是 non-probabilistic classifier (對比於 logistic regression 是 probabilistic classifier).  

SVM 所定義的 general loss function 如下 (不管是 linear or nonlinear, separable or not separable):

NewImage

D 是 margin.  用實例來解釋比較清楚。

假設某一個 xi 所對應的 scores f(xi, W) = [13, -7, 11].  假設正確的 yi 是 0 (第一值)。D=10

Li = max(0, -7-13+10)  +  max(0, 11-13+10) = 0 + 8 = 8

意即每一個 loss item 代表: 正確比錯誤得分超過 margin 失分 0;  正確比錯誤得分小於 margin 失正分。

結論正確比錯誤超過 margin 會被 clamp 在 0.  反之失分無上限。

因此上述的 max(0, -) 的 loss function 也稱為 hinge loss function.

另一個常用的 loss function 是 max(0, -)^2  (or L2-SVM), penalizes violated margins quadratically.

 

Loss function always 是正值。但愈小愈好 (失分小)。從 energy 來看,可以 exp(-L) 代表 probability.

 

假設 score function 是線性函數,Loss function 可以簡化為:

NewImage 

當然更複雜的 function 可能就沒有 close form.

 

Loss Function 釋意圖

NewImage

對於每一個 trained dataset (xi), 是要讓 correct class score 大於 other class scores by at least margin.  如果 other class score 落在紅色區域,就會有 loss.  最後的目標是讓找到最佳的 W to minimize total loss.  這是一個 optimization 問題。

 

  

Regularization

在 linear regression or logistic regression loss function 加上 regularization 基本上是 common sense.

好處是 fix over-fit (parameter space 太大) condition.  如果從 Bayesian 來看,regularization 相當於 prior distribution (Gaussian).

但在 SVM hinge loss function, regularization 除了解決 over-fit 問題,多了一個功能。和 margin 有關。

舉例而言,W meet 所有的 trained dataset 的 margin requirement.  λW (λ>1) 也可以滿足 margin requirement (margin 更大 assuming linear)。反過來說,如果 W 有 excess margin λΔ (λ>1), 我們可以 scale W 讓 excess margin disappear.    因此加上 regularization loss 會自動消除 excess margin. 

NewImage

展開來:

NewImage

如上所述,假設 W 有 excess margin, 第二項 regularization loss 會 scale down W (assuming f(xi;W) is linear w.r.t. W.  λ 最終是由 cross-validation 來決定。Δ and λ 是 parameters to be determined, 但是相互關連如上所述。一般會把  Δ 設為 1. 把所有 effect lump 到 W and λ.

 

Optimal Margin Classifier

詳細的 Reference (Andrew Ng CS229 note3)

L2 norm (regularization) penalty leads to the appealing max margin property in SVM.

 

再強調 regularization 的好處

1. Less overfitting

2. Reduce excess margin

3. Max(optimal) margin classifier

 

我們先從最簡的 classification 開始

 

Binary Linear SVM (Optimal/Maximum Margin Linear Classifier)

假設兩個 classes (y = +1 or -1), 同時是 linear SVM.  Δ=1.

假說是 linear separable, 相關參數的幾何意義如下圖。

NewImage

Hyperplane (linear) separator:

w x – b = 0  加上 margin Δ=1;  

w x – b = +1   or   w x – b = -1  的 Hyperplane 如上。實際的 gap (距離) = 2 / ||w||

如果用 Δ,  實際的 gap = 2Δ / ||w||.  也就是不管什麼 Δ (1 or 100) 都可以用 ||w|| 來 offset.

以 linear system 而言,就把 ||w|| scale 1 or 100 即可。因此就設定 Δ=1.

 

做為 classifier

w x – b > 1  if  yi = +1

w x – b < -1 if yi = -1

可以濃縮為:

NewImage

加上 regularization 可以簡化 optimization problem:

NewImage

因為 gap 是 2/||w||,  Minimize ||w|| 也同時証明這是 maximum margin linear classifier.

可以改為 min 1/2||w||^2 subject to yi(w xi – b) >= 1.   

因為 objective function 是二次式。Constraints 是 linear.  所以是一個 convex quadratic programming.

可以直接用 QP (quadratic programming) optimization software 來求解。

 

在找到 optimal w and b 後,(test) classifier is defined as:  

NewImage

以上是 Level 1 的 SVM, 就是 maximum margin linear separable classifier. 

 

Soft-Margin for Not Linearly Separable Classifier

如何把 SVM 延伸到 not linearly separable classifier, 就是用 hinge loss function.

NewImage

Optimization 問題變為:

NewImage

明顯比 linear separable case 複雜。此時不是 maximum margin classifier?

CS231 的 note 有同樣結果。

NewImage

兩點要注意:  C = 1/λ;   bias trick 可以把 b 吸收在 w 內。

 

 

 

 

 

 

 

Advertisements