Python · SVM（三）· 核方法

（考試周寫專欄真有種忙裡偷閒的感覺 _(:з」∠)_）

關於核方法的比較嚴謹的敘述，個人建議觀眾老爺們可以看看這個問題下面的前幾個回答；在這裡的話，我們就還是只注重直觀和應用層面

什麼是核方法？

往簡單里說，核方法是將一個低維的線性不可分的數據映射到一個高維的空間、並期望映射後的數據在高維空間里是線性可分的。我們以異或數據集為例：在二維空間中、異或數據集是線性不可分的；但是通過將其映射到三維空間、我們可以非常簡單地讓其在三維空間中變得線性可分。比如定義映射：

該映射的效果如下圖所示：

可以看到，雖然左圖的數據集線性不可分、但顯然右圖的數據集是線性可分的，這就是核工作原理的一個不太嚴謹但仍然合理的解釋

從直觀上來說，確實容易想像、同一份數據在越高維的空間中越有可能線性可分，但從理論上是否確實如此呢？1965 年提出的 Cover 定理從理論上解決了這個問題，我們會在文末附上相應的公式，這裡暫時按下不表

至此，似乎問題就轉化為了如何尋找合適的映射、使得數據集在被它映射到高維空間後變得線性可分。不過可以想像的是，現實任務中的數據集要比上文我們拿來舉例的異或數據集要複雜得多、直接構造一個恰當的的難度甚至可能高於解決問題本身。而核方法的巧妙之處就在於，它能將構造映射這個過程再次進行轉化、從而使得問題變得簡易：它通過核函數來避免顯式定義映射。往簡單里說，核方法會通過用能夠表示成的核函數替換各算式中出現的內積來完成將數據從低維映射到高維的過程。換句話說、核方法的思想如下：

• 將演算法表述成樣本點內積的組合（這經常能通過演算法的對偶形式實現）
• 設法找到核函數，它能返回樣本點、被作用後的內積
• 用替換、完成低維到高維的映射（同時也完成了從線性演算法到非線性演算法的轉換）

當然了，不難想像的是，並不是所有的函數都能夠對應一個映射（亦即不是所有的都能拆成；比如說，顯然至少需要是一個對稱函數）。幸運的是，1909 年提出的 Mercer 定理解決了這個問題，它的具體敘述會在文末給出

Mercer 定理為尋找核函數帶來了極大的便利。可以證明如下兩族函數都是核函數：

• 多項式核
  

• 徑向基（Radial Basis Function，常簡稱為 RBF）核：
  

那麼核方法的應用場景有哪些呢？在 2002 年由 Scholkopf 和 Smola 證明的表示定理告訴我們它的應用場景非常廣泛。定理的具體內容同樣會附在文末，這裡就暫時按下不表

核模型的表現

還是用 GIF 來說明問題最為形象。當我們對感知機應用核方法後，它就能對非線性數據集（比如螺旋線數據集）進行分類了，訓練過程將如下：

怎麼應用核方法？

簡單來說，就是把演算法中涉及到樣本（）的地方都通過某種變換、弄成樣本的內積形式（）。以感知機為例，感知機的原始損失函數為

為了讓損失函數中的樣本都變成內積形式，考慮令

則

在此之上應用核方法是平凡的：設核函數為，只需把所有的換成即可：

於是優化問題變為

預測步驟則變為

對於 LinearSVM 而言，用同樣的手法不難得出其核形式：

預測步驟則仍然是

（有沒有發現核形式和對偶形式很像？( σω)σ）

如何訓練核模型？

【注意：為簡潔，從此往後的推導和實現均以核感知機為例，核 SVM 的相關討論會放在下一章介紹 SMO 演算法時進行】

簡潔起見，我們還是用梯度下降法來進行訓練，為此我們需要進行求導工作。假設當前模型參數為，在參數下的預測值為，則：

為了加速訓練，我們需要將該算式向量化，為此我們需要定義核矩陣。假設現在我們有兩組樣本：和，那麼它們的核矩陣即為

對於訓練過程而言，我們關心的是訓練樣本之間的核矩陣

利用它，不難寫出相應的向量化代碼：

# 假設 k_mat 存儲著原樣本之間的核矩陣n# 1、計算損失nerr = -y * (k_mat.dot(alpha) + b)n# 2、找出使得損失不小於 0 的樣本nmask = err >= 0n# 3、進行相應梯度下降，lr 是學習速率ndelta = lr * y[mask]nalpha += np.sum(delta[..., None] * k_mat[mask], axis=0)nb += np.sum(delta)n

對於預測過程，我們關心的是原樣本和新樣本之間的核矩陣。假設新樣本為，則

那麼預測過程即為

@staticmethodndef _poly(x, y, p):n return (x.dot(y.T) + 1) ** pn

但對於 RBF 來說就沒那麼直觀了，用到了 Numpy 的高級實用技巧之一——升維：

@staticmethodndef _rbf(x, y, gamma):n return np.exp(-gamma * np.sum((x[..., None, :] - y) ** 2, axis=2))n

當然直接用 for 來實現也是可以的，不過那將會非常非常慢……

核模型的實現

如果思路能夠整理清楚，那麼核模型相比原模型來說只有如下兩點改變：

• 需要定義核函數並計算出核矩陣
• 計算預測值時不是，而是，其中
• 在訓練時，為原樣本之間的核矩陣
• 在測試時，為原樣本和新樣本的核矩陣

所以實現起來的話會有許多重複代碼，這裡就只展現其中最核心的部分（仍以核感知機為例）：

# 訓練代碼ndef fit(...):n ...n self._alpha = np.zeros(len(x))n self._b = 0.n self._x = xn # self._kernel 即為核函數，能夠計算兩組樣本的核矩陣n k_mat = self._kernel(x, x)n for _ in range(epoch):n err = -y * (self._alpha.dot(k_mat) + self._b)n if np.max(err) < 0:n continuen mask = err >= 0n delta = lr * y[mask]n self._alpha += np.sum(delta[..., None] * k_mat[mask], axis=0)n self._b += np.sum(delta)nn# 預測代碼ndef predict(self, x, raw=False):n x = np.atleast_2d(x).astype(np.float32)n # 計算原樣本與新樣本的核矩陣並根據它來計算預測值n k_mat = self._kernel(self._x, x)n y_pred = self._alpha.dot(k_mat) + self._bn if raw:n return y_predn return np.sign(y_pred).astype(np.float32)n

相關數學理論

1）Cover 定理

若設 d 維空間中 N 個點線性可分的概率為，那麼就有：

其中

證明從略（也就是說我不會）（喂），但是不難從中看出，它證明了當空間的維數 d 越大時、其中的 N 個點線性可分的概率就越大，這構成了核方法的理論基礎之一

2）Mercer 定理

若是對稱函數（亦即）的話，那麼它具有 Hilbert 空間中內積形式的充要條件有以下兩個：

• 對任何平方可積的函數、滿足
  

• 對含任意 N 個樣本的數據集，核矩陣：
  
  是半正定矩陣

【注意：通常我們會稱滿足這兩個充要條件之一的函數為 Mercer 核函數而把核函數定義得更寬泛。不過如果不打算在理論上深入太多的話，將 Mercer 核函數簡稱為核函數是可以的。此外，雖說 Mercer 核函數確實具有 Hilbert 空間中的內積形式、但此時的 Hilbert 空間並不一定具有「維度」這麼好的概念（或說、可以認為此時 Hilbert 空間的維度為無窮大；比如說 RBF 核，它映射後的空間就是無窮維的）】

3）表示定理

設為核函數對應的映射後的空間（RKHS），表示中的範數，那麼對於任意單調遞增的函數和任意非負損失函數、優化問題

的解總可以表述為核函數的線性組合

這意味著對於任意一個損失函數和一個單調遞增的正則化項組成的優化問題、我們都能夠對其應用核方法

下一篇文章我們則會拋開梯度下降這個有些「偷懶」的做法，並介紹一種叫序列最小最優化（SMO）的演算法

希望觀眾老爺們能夠喜歡~

（猛戳我進入下一章！( σω)σ ）
推薦閱讀：