機器學習筆記029 | 核函數

1 低維映射到高維解決線性不可分問題

常常我們碰到的一些分類問題，是線性不可分的，例如下圖這樣：

對於這樣的情況，通過之前的學習，我們了解到可以通過多項式回歸結合邏輯回歸的方式得到想要的結果：

為什麼增加了高階多項式之後，這樣的分類問題就能夠解決呢？

我們來舉一個簡單的例子，例如我們的數據是一維的：

我們沒有辦法使用一根直線將數據區分開來，因為不管怎麼分，都會出現錯誤分類的情況：

如果原來的數據是 x ，我們給它增加一個維度 x2，從一維變成二維，數據就變成了這樣：

我們可以用 y = x 這麼一條直線將兩者區分開來，這裡設置 x2 為 y 軸。

回到一維中，其實就是這樣的一條曲線 x2 - x = 0：

多項式回歸通過將數據從低維映射到高維，將原本線性不可分的情況變成了線性可分的情況。

2 利用核函數降低運算複雜度

不過使用多項式回歸，隨著維度的增加，會存在一個問題，那就是計算量會以幾何級數增加。

而下面說到的核函數（Kernel Function）有助於解決這一個問題。

所謂的核函數，其實是一種計算的技巧，所以又被稱為 Kernel Trick 。

如果 φ(x) 是 x 在高維的映射，那麼我們定義核函數為：

為了方便演示，我們進行簡單的假設。

假設 x 為一個 特徵維度為 2 的向量：

假設 x 的映射 φ(x) 為：

那麼我們對核函數的計算過程，是這樣的：

類似的，如果特徵維度為 n ，映射的階數為 d，那我們可以得到的結果是：

你會發現先將特徵映射到高維，然後在高維計算內積，和直接計算特徵內積，然後進行高階運算，兩者的結果是一樣的。

不同之處就在於，前者運算的時間複雜度是O(nd)，而後者是O(n)。

3 是否核函數的判定

映射必須要滿足一定的條件，我們才能進行這樣的公式變換。就拿上面的推導為例，如果映射是

兩者的計算結果是不相等的。

但問題是，尋找映射 φ(x) ，然後進行推導計算非常麻煩。

那對於核函數的判定，還有沒有別的辦法呢？

根據Mercer定理，任何半正定的函數都可以作為核函數。

例如對於上面所說的函數：

有 m 個訓練樣本 { x(1)，x(2)，x(3)，… ，x(m) } ，我們可以將任意的兩個 x(i) 和 x(j) 代入到函數中得到：

i 和 j 都可以從 1 到 m，計算到的函數矩陣 K 是一個 m × m 的矩陣。

如果該函數的矩陣 K 是半正定的，那麼該函數就是核函數。

根據向量的運算規則 ATB = BTA ，我們可以推導得到：

也就是該函數矩陣 K 是一個對稱矩陣。

特徵維度為 n ，我們用 φk(x) 代表映射函數 φ(x) 第 k 維的屬性值。

那麼對於任意 m × 1 的向量 z 來說，可以進行如下推導：

所以該函數矩陣 K 是一個半正定的矩陣。

綜合來看，矩陣 K 是對稱半正定的，滿足Mercer定理，所以這個函數是核函數。

Mercer定理不是核函數必要條件，只是一個充分條件，也就是說還有不滿足Mercer定理的函數也可以是核函數。

4 常用的核函數

核函數有很多，最常用的是高斯核函數：

高斯核函數可以將原始的特徵空間映射到無窮維的特徵空間。

對於樣本 { x(1)，x(2)，x(3)，… ，x(m) } ，l 的取值是所有的 x 。

高斯核函數計算的是每一個 x(j) ，和所有的 l(i) 之間的距離關係：

上圖中突起的點代表著就是 l(i) 的位置，而 x(j) 在圖中落點的高度，就是核函數的值。

如果 x(j) 與 l(i) 距離很近，那麼 || x(j) - l(i) ||2 ≈ 0，核函數的值為 1；如果 x(j) 與 l(i) 距離很遠，那麼 || x(j) - l(i) ||2 >> 0，核函數的值為 0 。

同樣距離下，核函數變化的敏感度，可以通過 σ 來控制。

σ 越小，同樣距離下核函數的結果就越小：

σ 越大，同樣距離下核函數的結果就越大：

如果 σ 選擇過小，可以將任意數據映射得線性可分，進而導致過度擬合。

如果 σ 選擇過大，相當於一個低維度的空間，容易欠擬合。

文章提前發布在公眾號：止一之路

推薦閱讀：