SVM Kernel

來自專欄 機器學習

在之前的討論中，我們遇到的問題是輸入 是房屋居住面積，我們考慮採用 來進行回歸的到3次方程，為了將這兩組變數進行區分，我們稱：

1. 原始的輸入值為問題的input attribute(在這個問題中就是居住面積 )
2. 當input attribute映射到一個新的值並且直接傳遞給學習演算法，將這些新的值稱為input feature

我們用 表示feature mapping，將attribute映射到features，例如本例中

如果不想直接採用original input attribute 到SVM，我們希望採用一些feature 來進行學習，回顧之前的演算法，我們所有的 都用 進行替換即可。

然而演算法可以寫成內積的形式 ，我們將所有的內積替換為 ，因此給定一個feature mapping 我們定義對應的Kernel為：

我們只要將演算法中的形式 替換為 ，演算法就會採用映射後的特徵進行學習。

給定 ，確定 後取內積即可計算得到 ，但是通常 本身難於計算，因為其往往是一個extremely high dimeensional vector，而 是便於計算的。因此我們可以在不計算 的情況下讓SVM在high dimensional feature space來進行學習。

例如，假設 ，考慮 我們可以將其寫為

因此我們可以看到 特徵映射 為（以n=3為例）

顯然計算high-dimensional 需要 時間複雜度，而查找 只需要 時間複雜度。

我們考慮第二個相關的Kernel如下所示，對應的特徵映射如下所示

其中的參數c控制一階項 和二階項 之間的相對權重。

更加廣義的來說，Kernel 對應一個特徵映射到 維的特徵空間

我們從另一個角度來看到kernel，如果 足夠接近，那麼 就會很大；相反，如果 遠離，那麼 就會很小，因此我們可以將 看作是 相似度的一個衡量，或者 相似度的衡量。

在這個角度下，我們可以採用 來衡量相似度，這是一個很合理的衡量方式，當x、z足夠接近， ;當 分離很遠， .我們能否採用這個K來作為SVM中的kernel呢？答案是可以，這個Kernel被稱為Gaussian Kernel.對應一個無窮維特徵映射 .

進行推廣，給定一個函數K，我們如何區分是否是valid kernel，我們能否區分是否存在一個特徵映射 使得 對所有的 成立？下面介紹Mercer定理

Mercer定理：給定 ,K是一個valid kernel的充分必要條件是對於所有的 對應的kernel matrix是 symmetric positive semi-definite(對稱半正定矩陣).

證明：假設K是一個valid kernel對應某個feature mapping ，給定一個有限集合m個點 ，定義 矩陣 為Kernel Matrix，其中元素為 ，注意這裡我們重載了符號 ，既用來表示核函數 也表示Kernel Matrix

必要性證明：假設K是一個valid kernel，那麼

因此 是對稱矩陣；

讓 表示向量 的第k個元素，那麼對於任意的向量 有：

由於向量z是任意的，因此K是半正定的(positive semi-definite, )

充分性證明：這裡不做證明

常用核函數

多項式核函數(polynomial kernel function)

對應的支持向量機是一個p次多項式分類器，在此情形下，分類決策函數成為：

高斯核函數(Gaussian Kernel Function)

對應的支持向量機是高斯徑向基函數(radial basis function)分類器，在此情形下，分類決策函數成為：