Machine Learning – Kernel Trick for CV

by allenlu2007

Ref:  Richard Hartley paper

 

SVM, PCA, FDA (Fisher Discriminant analysis), k-means clustering and ridge regression can apply kernel trick.   and even on Riemannian manifold for computer vision.

 

 

Kernel Method on Riemannian Manifold with Gaussian RBF Kernel (reference)

 

SVM Refresh

之前 kernel method (e.g. SVM) 都是假設 data 是在 multi-dimensional (Euclidean) space.  以下 2D (features) 為例:

NewImage

SVM 就是要找到 maximum margin 的直線 (boundary) 分開。這個最大 margin 的 optimization principal problem 如下。其實 Lagrange dual problem 更好解,就是找出 (sparse!, 因為 L1 norm) support vectors, 也就是上圖雙圈的黑白點。

NewImage

 

Lagrangian Dual:

NewImage

重點是大多數的 αi 都是 0!!  非 0 (大於 0) 的就是 supporting vectors.  Hyperplane 如下:

NewImage

 

更普遍的情況是更高維的 features, 需要找到 support hyperplane (直線的推廣).  這很直觀。數學上也簡單。變成處理 sparse matrix 問題 (decomposition/factorization?  or eigenvalue problem? TBC)

 

Kernel Trick

比較麻煩也是有趣的 case 是 data 本身為非線性要如何處理?  如下圖左。

NewImage

1. Brute-force:  仍用 linear hyperplane 處理。就是 agree data is non-separable case.  引入誤差項 ξi

NewImage

此時 Lagrangian dual problem 基本上沒有變,只是多了一個 upper bound!!!!!  請參考前文。

 

以上的方法對於比較非線性的 data 顯然不是好方法。在某一些情況根本是無解。如下圖左。

NewImage

 

明顯的答案就是找出 nonlinear decision boundary! 

如何找出 nonlinear decision boundary? 當然不是用眼睛看。

2.  把 data (feature) map 到更高維 feature space, using Φ(x).  重要的是 Φ 必須是 nonlinear mapping!!

因為 linear mapping 不會產生更多的 features (?).  在高維 feature space 我們可以找到 linear hyperplane 分開 data (如上圖右).  如果把高維的 decision boundary project 回原來的 decision boundary 就變成 nonlinear decision boundary. 

Nonlinear Φ 有很多種。常見的是 polynomial expansion.  顯然愈多項代表愈高維,也代表計算量愈多。如果要無窮多維度顯然是 mission impossible!

天才發現了並不需要直接算 Φ(x)!!  只要算 <Φ(xi), Φ(xj)> = K(xi, xj) 也就是 kernel trick!!!!  可以在低維的空間計算而得到高維 (無窮多維也可!) 空間的結果。 最常見的 kernel 就是 polynomial, expotential, Gaussian/RBF (Radial based f?) kernels.  當然 K(xi, xj) 需要滿足 HIlbert space inner product (?) 的一些要求。就是 Mercer’s condition, K(xi, xj) 必須是 symmetrical and semi-positive definite!

 

3. 另一個想法是 data 就是在 (nonlinear) manifold 中。例如上述 data 是在一個錐面 (或球面) 上。所謂的直線 boundary 就對應 manifold 上的 geodesic boundary!!!

三個問題:

(a) 如何找到 manifold : manifold learning problem. 

看一個更明顯的例子 (Swiss roll) 如下圖。如果能 learn 出 swiss roll manifold.  就可以 unwrap the swiss roll.  找到 decision boundary.

NewImage

(b) 為什麼要 geodesic distance.  第一是 manifold 上的直線就是 geodesic.  另外是在 manifold 上 geodesic distance 比較和 data 相關。如上圖 (A) and (B) 是 Euclidean distance 最短。看似相關係最強。實際上展開後是最遠 (in terms of geodesic distance).   在 manifold 上應該要用 geodesic distance 來衡量相關性。

 

Graph-Based method for manifold learning

NewImage

(c) 如何 unwrap the swiss roll, 或是 unwrap the manifold?

另一個角度就是另一種 nonlinear mapping, Φ(x) from manifold to Hilbert space.  此時的含義和之前不同。之前是把 Euclidean linear space 的低維 data (nonlinear) map 到高維的 Euclidean linear space.

現在是把低維 manifold data (nonlinear) map 到高維的 Hilbert space (也是 Euclidean and linear?).  同樣的問題是如何避免做實際的 mapping, 而可以用 K(xi, xj) = <Φ(xi), Φ(xj)>  kernel 來簡化 mapping?

因此要討論 manifold 上的 kernel operation 如何進行?   

 

 

 

Kernel and manifold 的關係?

Φ(x) 是把 manifold map to Hilbert space with inner product. 顯然 Φ 和 manifold M 直接相關。

K(xi, xj) = <Φ(xi), Φ(xj)>

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

天才發明了 kernel trick!

 

 

 

Advertisements