機器學習_學習筆記系列(17)：核函數支撐向量機(Kernel Support Vector Machine) — Polynomial Kernel & Gaussian Kernel
在上一篇文章，我們進入到SVM解決非線性分類的問題，但是我們可以看到，在進行特徵轉換的時候，在計算的過程中，特徵長度D還是大大的影響我們的運算時間。
假設我們總共有N筆資料，每一筆資料總共有M個特徵
對於二維特徵轉換
對於三維特徵轉換
而在進行Q矩陣運算的時候我們知道
我們可以看到，對於二維做內積，我們的計算複雜度為O(M²)，對於三維則上升到O(M³)，所以當我們的特徵轉換次方數上升到越高，我們的計算時間就會變得非常大。對於此我們對我們的特徵做一些分解
對於二維
對於三維
由上面我們可以看到我們的計算複雜度降到了O(M)。所以當進行二次規劃的時候，要進行t次方的特徵轉換時，我們的Q矩陣中，每個元素可以寫成
而當我們求解最後的SVM方程式的時候，就可以寫成
其中
(note:計算SVM方程式時，是把所有的support vector拿出來做運算，其他的就可以忽略。計算b時，則是support vector裡面隨便挑一個即可)
所以我們總結一下，我們利用Kernel function的拆解，在進行Q矩陣運算的時候，Q矩陣裡面每個元素的計算複雜度降為O(M)，如此一來就達到減少我們的運算時間。
Polynomial Kernel
而在上述我們列出了二維和三維特徵轉換，為Polynomial Kernel方程式的內積，其分別為
那相信這邊大家應該可以利用一些直覺去想，如果我們今天引入一些新的參數gamma和zeta，是不是可以使得
來更簡化我們kernel function的計算。
那相信大家一定會想問，為什麼可以這樣做。其原理就是，我們今天做的是特徵轉換，也就是將原本的數據x做相乘、平方、延伸，所以說我們今天引入gamma和zeta對於解決分類問題來說，是OK的，只是最後出來的曲線會有些許的不同。
所以我們的Polynomial Kernel方程式為
帶入二次規劃的q矩陣為
最後可以得出方程式為
接下來我們用Python實現。這裡我們探討的是平面二元分類問題，特徵轉換的次方數為15次方，zeta=1。
由上圖我們可以看到，不同的gamma值，曲線會隨之改變
Gaussian Kernel
上面介紹了Polynomial Kernel後，那我們試想，今天如果想要讓次方數到無限大，顯然原本的polynomial方法是不可行的，所以我們要介紹另一種kernel function，其叫做Gaussian Kernel，也叫做Radial Basis Kernel。其可以寫成
為什麼這個Gaussian Kernel就可以讓我們的特徵轉換可以到無限大呢？沒關係，如果一樣不知道為什麼，我們就暴力展開就對了。
首先我們知道
所以
如此一來，我們的特徵轉換就可以延伸到無限次方。而在這邊我們一樣也可以引入一個參數gamma使得
所以這裡帶入二次規劃，則q為
最後我們就可以推出，最後的方程式
接下來我們用Python實現，來探討的是平面二元分類問題
由上圖我們可以看到，不同的gamma值，曲線也會隨之改變
Python Sample Code:
Github:
Reference:
[1] Coursera, 機器學習技法, 林軒田 教授
