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。