L1 SVM and L2 SVM Primal and Dual

by allenlu2007

本文參考 CJ Hsieh, KW Chang, and CJ Lin “A Dual Coordinate Descent Method for Large Scale Linear SVM

 

前文提到的 SVM 都是 L1 SVM, 意即 loss function 是 hinge-loss function.

另外還有 L2 SVM, loss function 是 quadratic hinge-loss function. 

最主要的好處是 L2 SVM 是 differentiable (在原點)。

在 numerical computation 的 stability 比較好。

在某一些應用,如 combine with deep learning (reference Tang) 有好處。

 

NewImage

 

L2 的缺點是什麼?

A. 之前的 kernel trick 還在嗎?  To be checked.

B. 是否有快速的算法 (SMO?)?  Yes, Dual coordinate descent method (見 reference)

 

L1-SVM 遠比 L2-SVM 更常使用

 

Lagrange Primal Optimization 

以下是結合 L1 and L2 的 primal form. 

eta 是 loss function 或是 slack variable. 

NewImage

 

Bias trick:  如果有 bias, 可以被 w 吸收。

NewImage

 

Dual form 如下:

NewImage

For L1-SVM,  比較前文結果(如下) 一致 (好像少了 sum(ai yi)=0 的 constraints?) 

NewImage

 

For L2-SVM, 展開後如下:

NewImage

 

注意在 L2-SVM dual problem 的 Hessian matrix Q 因為加了 diagonal 1/C, 所以一定是 positive definite.

L1-SVM 則是 positive semi-definite.  因此 L2-SVM computationally stability 更好一點。但收歙速度不一定比較快。(reference)

 

Advertisements