SVM 原理: Level 3 Kernel Trick

by allenlu2007

 

前文 (SVM 原理: Level 2) 的 Lagrange primal and dual 問題 summary 如下。

NewImage

 

NewImage

NewImage 

NewImage

NewImage

 

關鍵的重點:

(1) 只有少數的 αi > 0, 對應的 xi 稱為 support vectors.  大多數 αi = 0, 省略大量的計算如 objective function, 

      prediction 的 classification.

(2) 還有一個重點是不論是 optimization 或是 prediction 都只要算 vector dot product <xi, xj> or <xi, x>.

      結合 (1) 可以大量簡化計算。沒有任何單獨的 x or xi.  這是非常重要的特性,在 kernel trick 非常有用。

(3) 在 kernel trick map to higher dimensions 結合 (1) 省大量計算; (2) 不用管 phi(x), 只要管 K(xi, xj) = <phi(x), phi(x’)>  到底什麼是 phi(x) 不重要!!!  phi(x) 可以是 infinite dimensions!!

 

Kernel Trick

199x who extends the above Lagrange dual form to general kernel function. 

NewImage

對於 not linear separable 的 case, 有時可以 map 到 high dimension and become linear separable. 

如何 map, 非常簡單。就是  x ->  𝝓(x)   𝝓(x) 的 dimension > x dimension

 

Lagrange Primal on SVM with Kernel

數學上非常直觀。就是讓 x’ = 𝝓(x), 重寫原來的公式如下。

注意新的 w 的 dimension = x’ dimension >  原來的 x (and w) dimension

NewImage

和 logistic regression 的 map feature 比較。也是把 x –> 𝝓(x) 從 low dimension to higher dimension. 

再來也是在 higher dimension 來計算新的 w (in higher dimension).  道理似乎一樣。

因為新的 w dimension 比原來大很多 (如 2 dim -> 28 dim for 6th order polynomial mapping, 見前文),

因此計算新的 w and b (or θ) computation 複雜度大增。另外在新的 x prediction 同樣 computation 也更複雜。

 

所以 SVM 做  x –> x’= 𝝓(x) 有什麼不同?  差很大!!  見下面 dual problem:

 

Dual Problem 如下

NewImage

K(xi, xj) = <x’i, x’j> = <𝝓(xi), 𝝓(xj)> 

 

對於分類函數也變成

NewImage

代入 w 如下 (但 x –> x’ =  𝝓(x))

NewImage

NewImage

NewImage

 

乍看之下好像和 logistic regression feature map 沒什麼不同。

重點是不論在 learning or prediction 時,我們只要計算 K(x, z) = <𝝓(x), 𝝓(z)>

完全不用計算 x -> 𝝓(x)!!   問題是如何計算 <𝝓(x), 𝝓(z)>  而不用算 𝝓(x)?

天才和庸才的差別在此!  我們根本不用管什麼是 𝝓(x) or 𝝓(z). 而是直接定義 K(x, z). 

甚至對應的 𝝓(x) 長什麼樣或存不存在都沒有關係!

 

不過 K(x, z) 仍需要滿足一些 math properties 才能被定義為 kernel function.  TBA.

 

如何直接定義 K(x, z)?  最重要是要在 low dimension 計算。

Example 1:  K(x, z) = (<x, z> + 1)^2     –> low dimension computation

可以找到對應的  𝝓(a,b)=[ sqrt(2)*a, a*a, sqrt(2)*b, b*b, sqrt(2)*a*b, 1 ]  從 2-D map to 6-D.

 

Example 2: K(x, z) = exp(-ϒ ||x-z||^2)  –> low dimension computation

沒有對應的 𝝓(x) 的 close form!  不過可以斷定 𝝓(x) 是 infinite dimensions!

因為 exp 的展開式包含所有的 polynomials. 

但 physical insight to be added!

 

Update from NTUCS prof. cjlin’s talk when x is 1-D.

NewImage 

In summary

Key concept:  kernel trick 是在 low dimension 做計算!!!!

==> 在 kernel trick, 不需要計算 𝝓(x),  只要計算 k(x, x’) = <𝝓(x), 𝝓(x’)>.

更重要的是,k(x, x’) 基本上可以隨意定義!!!! 所以可以定義成 k(x, x’) 計算在 low dimension 而不需要算 𝝓(x).   𝝓(x) 可以是 infinite dimension (如 Gaussian).  

 

Example 1:  同上 Example 1

NewImage

NewImage

NewImage

NewImage

NewImage

NewImage

 

常用的核函數

NewImage

NewImage

* 最後還有 sigmoid kernel.  TBA. 

Advertisements