SVM Kernel Trick Insight

by allenlu2007

本文主要參考 Zisserman “Lecture 3: SVM dual, kernels, and regression

 

 

Primal and Dual

先從 linear classifier

NewImage

Primal problem (by solving w in d-dimension)

NewImage


Dual problem (by solving α in n-dimension)

NewImage

以上是在 learn 的階段。 

 

最後在 test (or predict) 階段,也就是 classifier:

Primal 看來很容易如下,就是 w’ * x, 僅是 FIR filter with d 乘法。 

NewImage

 

Dual 乍看比較複雜如下。不但要 N 個乘法,還要計算所有的 xi’ * x  inner products.

w and f(x) 如下

NewImage

NewImage

 

幾個重點:

1.  Primal 要 learn w (d 個特徵點,或 parameter dimensions).  Dual 要 learn α (N parameters for sample size).

2. 如果 N << d,  計算 dual (α) 會比計算 primal (w) 更有效率。

更重要的是 α 包含大量的 0 不用計算。只需要算 non-zero 的部份,也就就是 support vectors.

3. Dual form 並不需要 w, 只需要算 <xi, xj>.  這是另一個重點。如果把 x map 到 high dimension 特別有用。

下圖可看出 support vectors 只有四個。也就是 α 只有 4 個 non-zero components.  所以 <xi, x> 也只需要算 4 個。

NewImage

 

Kernel Primal and Dual

Primal

NewImage

如果 D >> d,  w 的 dimension 也是 D.  Primal 問題的複雜度會大幅增加。

 

Dual

NewImage 

Kernel Trick

重點是 Kernel trick 的 dual 和 D 無關,只 depends on N.

NewImage 

 

NewImage

 

NewImage

下面幾張圖說明 C and σ 的作用。

首先 C = ∞ 代表 hard margin.  只有 data separable 才 OK.  雙圈是 support vector.

NewImage

C = 100, 代表可以有 soft margin.  可以看到雙圈多了三個 support vectors.

NewImage

C = 10, 代表可以有 soft margin.  可以看到雙圈也就是 support vectors 多了一些。

NewImage

相反如果 σ 變小,代表更高維 (因為 Gaussian 的 decay 變慢)。也就是 boundary 變得更 non-linear.

NewImage

如果 σ 變更小,反而無法定義清楚的 bounary. 

NewImage

 

 

Linear combination of Gaussian kernel of supporting vector.

Similar to SVD?  but using training data as a base?

Kernel function needs to satisfy some math properties. 

 

Mercer’s Theorem

Kernel function needs to be positive semi-definite (psd).

注意 Mercer’s Theorem 是 if and only if condition.  只要是 psd, 就可以定義 kernel function.

NewImage

Advertisements