Kernel Dual Representation

最近在又重新去研究了一下Gaussian Process和Kernel Method的方法，主要是為了看懂兩篇將GP和Kernel變為Deep的過程，從而可以得到一些傳統模型嵌入到Deep的啟發，這兩篇論文分別是Deep Gaussian Process和Deep Kernel Learning。

Kernel Method應用很廣泛，一般的線性模型經過對偶得到的表示可以很容易將Kernel嵌入進去，從而增加模型的表示能力。一般地，只要演算法的訓練和預測過程只涉及到數據的內積操作，就可以將核函數嵌入進去，使用核函數的性質，可以認為核函數衡量了兩個數據樣本經過非線性變換映射到高維空間後的相似度。由於使用核函數可以無需知道的具體形式，因而使用起來有比較完美的數學表達形式，並且增加了模型的表示能力。

線性回歸問題Linear Regression經過核技巧可以演化為Kernel Linear Regression，對數幾率回歸Logistic Regression也有其對應的Kernel Logistic Regression。當然，熟悉的Linear SVM和Linear PCA也有其相應的核版本，分別為Kernel SVM和Kernel PCA。

下面以回歸問題為例，推導一下線性問題變為核版本的一般套路。首先定義回歸問題為下面的優化問題：

$min_w J(w) = frac{1}{2} sum_{i=1}^N left( w^Tphi(x_i) - t_i ight)^2 + frac{lambda }{2}w^Tw$

回歸問題採用MSE損失函數，為要學習的權重，是樣本的非線性表示，是要回歸的目標，是正則化權重。

首先，二範數正則的回歸問題（嶺回歸，Ridge）是有閉式解的，對上式關於求導可以得到：

$sum_{i=1}^N left( w^Tphi(x_i) - t_i ight)phi(x_i) + lambda w = 0$

然後上式可以重新寫為下面的式子，可以看出，最優的權重可以由線性加權得到，其中 $alpha_i = -frac{1}{lambda} left( w^Tphi(x_i) - t_i ight)$ 是加權的係數，是所有樣本非線性變換後的矩陣表示，第 i 行為：

$w = -frac{1}{lambda}sum_{i=1}^N left( w^Tphi(x_i) - t_i ight)phi(x_i) = sum_{i=1}^N alpha_i phi(x_i) = Phi^Talpha$

將代入得到：

$J(w) = frac{1}{2}alpha^TPhi Phi^T Phi Phi^T alpha - alpha^T Phi Phi^T t + frac{1}{2} t^Tt + frac{lambda}{2}alpha^T Phi Phi^T alpha$

上式有點複雜，解釋一下，上面式子的最後一項是正則項，前面三項是二次方MSE展開的結果，其中第一項對應的是：

$frac{1}{2}sum_{i=1}^N (w^Tphi(x_i))^2 = frac{1}{2} || Phi w ||_2^2 = frac{1}{2}w^TPhi^T Phi w = frac{1}{2}alpha^TPhi Phi^T Phi Phi^T alpha$

從的表達形式來看，可以看出可以作為一個整體來看，我們記它為Gram Matrix，即，其中有 $K_{ij} = K(x_i, x_j) = langle phi(x_i), phi(x_j) angle$ ，那麼用核函數表達的形式為：

$J(w) = J(alpha) = frac{1}{2}alpha^T KK alpha -alpha^TKt + frac{1}{2}t^Tt + frac{lambda}{2} alpha^TKalpha$

給定數據 ${ (x_i, t_i)}$ 和核函數，上式就是一個關於的二次函數，有閉式解：

$alpha = (K + lambda I_N)^{-1}t$

引入核函數的線性回歸問題的訓練過程就是求得，通過上式即可求得閉式解。然後在預測過程中有：

$y(x) = w^Tphi(x) = alpha^T Phi phi(x) = K(x, cdot)^Talpha = sum_{i = 1}^N alpha_i K(x, x_i)$

因此可以看出上述推導的線性回歸的訓練和預測過程中，將內積變為核函數即可得到核版本的線性回歸，由於核函數可以近似看作非線性映射到高維空間的內積，因此是非線性的方法，增加了表示能力。

在線性回歸問題中，原始的問題是求得回歸係數，即在特徵維度上建立模型，每個特徵對應一項權重；而在覈版本中，訓練過程要求得，即在樣本維度上建立模型，每個樣本對應一項權重。

式子 $sum_{i = 1}^N alpha_i K(x, x_i)$ 具有可解釋性，首先訓練樣本中，每個樣本對應一項值，新來一個要預測的樣本，根據樣本之間相似度計算權重，然後加權得到預測值。這一步驟也可以理解為Attention操作，其中 ${x_i}$ 對應的是Key， ${alpha_i}$ 對應的是Value，則是Query。