機器學習: Kernel 函數

在機器學習內，一般說到kernel函數都是在SVM中去介紹，主要原因是SVM必須搭配kernel l函數才能讓SVM可以在分類問題中得到非常好的效能，因此kernel trick是SVM學習內非常重要的部份，當然也會衍生出很多問題(後面會提到)。

Kernel trick在機器學習的角色就是希望當不同類別的資料在原始空間中無法被線性分類器區隔開來時，經由非線性投影後的資料能在更高維度的空間中可以更區隔開。

下圖是一般看到kernel介紹都會看到的圖，我們無法在原始空間(Rd)中適當的找到一個線性分類器將兩類區隔開，這時後此需要找到一個非線性投影(φ)將資料進行轉換到更高維度的空間，此時在高維度的空間中只需要一個線性分類器/hyperplane就可以完美分類。

而這個更高維度的空間則稱為Hilbert space(H)。

但我們又很難直接去設計一個好的非線性投影(φ)公式，因此需要kernel函數來輔助。

Kernel函數定義:

只要對所有的資料，有一個函數可以滿足
k(x,y)=⟨φ(x),φ(y)⟩
這個k(x,y)就是一個kernel函數，⟨a, b⟩表示向量a和b做內積。

但我們怎麼知道什麼函數可以滿足這個條件，所以有個定理(Mercer’s theorem)說如果有一個函數(φ)存在，這個k必需滿足Mercer’s condition，k就是kernel函數。

但說法還是很玄，簡化說就是如果所有的資料帶到這個kernel function中的和必須大於等於0：

k就滿足Mercer’s condition。

理論上，一個Kernel matrix(K, Gram matrix)是半正定矩陣(positive semi-definite)，這個k就是kernel function。

比較常用的kernel函數:

d為正整數(通常在call api時，這個部份都會稱為degree)，σ為非0的實數(通常在call api時，這個部份都會稱為gamma)
Note: RBF kernel有的api會定義成下:

下面舉一個用polynomial kernel function次方項為2次方，截距為0 (d=2, c=0)的例子。

左圖為原始空間，很明顯的圓圈內是一類，圓圈是一類，此時單純用線性分類器是無法有效分類的，因此有沒有辦法找到一個非線性分類器讓兩類可以分開。

這邊用的kernel function比較簡單

此時可以經由簡單的推導得到投影函數(φ)，如下

因此我們可以看到用polynomial kernel function將資料投影到feature space後的情況，此時已經將資料從2維空間轉換到3維空間。

在feature kernel space時，很明顯只要一個Hyperplane(線性分類)就可以完美分類，如下左圖(水藍色的平面)，而其對應到原始空間(下右圖)則是中間分類的那個圓圈。

RBF kenel function 投影函數轉換

上述用的Polynomial kernel function轉換成投影函數(φ)比較簡單。

RBF kernel function也可以經由簡單的推導得到投影函數(φ)，但稍為複雜一點，會用到泰勒級數(Taylor series)。理論參考。

Recall: 泰勒級數是在函數f(x)在一個實數或複數a上可微分函數的power級數如下:

RBF kernel function會用到的泰勒級數是在

這邊舉一個1維度的資料讓大家熟悉RBF的拆解，這邊熟悉後比較容易轉換到高維度的想法去看

後面要來說明高維度的資料怎麼拆解，如果你對上面拆解很熟，你應該會意識到RBF轉換到更高維度的空間是看你泰勒級數要展到幾階層，假設你資料是2維，你想在3維空間看RBF轉換，泰勒級數就展開到0~2階，投影函數(φ)的每一個element公式如下

n代表第n階。投影函數(φ)實際寫出來如下:

這邊舉一個2維資料用RBF kernel function拆解出的投影函數(φ):

這邊我用圖示法，將2維資料投影到3維空間上，也就是泰勒級數取到2階就好。

Kernel的手法只是將資料投到更高維度的空間，然後在這高維度的空間進行你想做的事情，不一定要直接在高維度空間做分類(此例是在高維度空間分類)，也可以在高維度空間進行降維(dimension reduction)，關鍵字kernel PCA, kernel LDA。

Kernel trick很有趣，但剛有提到它有衍生性的問題，這個問題其實很簡單

「有這麼多種類的kernel，你要用什麼kernel函數在你的資料上?你挑到kernel了，kernel參數怎麼調整？」

還有人一直在研發不同種的kernel函數，比如合成的kernel，要怎麼挑，這個問題很簡單，最傳統的方式就是用gird search，就是你想的到的kernel函數和參數你都用training data跑一次，看哪組kernel和參數你training data performance最好就用哪一組。大家有發現一個問題嗎？如果kernel有100個，參數也都各100個，這樣你要try 100*100=10000次。如果你有跑過SVM，你就知道這樣會玩多久了。

因此有人會研發更快找到參數的方法，我們以前也玩過，之後有空再來寫一篇我們怎麼玩的。