kernel method是一种比较古老的统计方法，可以追溯到几十年前。不过最近的流行要归功到SVM在机器学习中的流行，最初SVM处理的是向量化的数据，不过很快人们发现借助Kernel，人们很容易的处理各种形式的数据，这给SVM这类的方法强大的威力。下面我们就来看一下kernel method方法。

kernel method的框架

kernel method 提供了一种模块化的学习框架，可以分为一下两步：

1. 使用kernel function计算数据集的kernel matrix，数据集的数据可以是各种各样的，甚至是异构的(heterogenous)。
2. 使用各种处理kernel matrix的算法，用来分析数据。

注意到我们的预测函数$f(x)$的形式，它与前面已经提到过的linear model， neural network有很大不同，在线性模型和神经网络中，我们的模型是满足某种形式的（线性的或是通过神经网络结构决定的非线性），我们都是通过训练，得到模型中的参数，只使用我们得到的模型，而不用去管训练数据是什么，就可以去做预测了。但是在kernel method中训练数据，预测函数不用假定为某种具体的函数，而是由核函数插值得到，在预测的时候，需要使用数据，这种方法称为“memory-based method”。

kernel

从上面看，kernel method与我们前面讨论的算法有一个明显的不同，算法处理的是kernel matrix,而不像我们linear regression或是logistic regression中，选择的基函数，将我们表示的数据表示为特征空间中的点（向量）；而是通过构造一个kernel matrix来表示要处理的数据。如下图所示：

在构造kernel matrix的时候，我们使用到了kernel,所谓的kernel就是$\mathcal{X}\to \mathbb{R}$的函数，其中$\mathcal{X}$是数据集合的取值范围。为了使得kernel matrix是一个正定矩阵（特征值非负），kernel function需要满足两个条件：

1. $\kappa(x,x^{'})=\kappa(x^{'},x)$
2. $\sum_i^{n}\sum_i^{n}c_ic_j\kappa(x_i,x_j) \geq 0$，对于$n>0$，$x_1,x_2,..,x_n  \in \mathcal {X}$；$c_1,c_2,...,c_n  \in \mathbb R$

满足上面两个条件成为正定核。

将数据表示为kernel matrix，有几个明显的好处：

1. 算法可以不用针对不同类型的数据，很好的可扩展性。在处理不同的问题时候，我们只要选择合适的核函数即可，而不用去改变算法
2. kernel matrix 的大小总是$n \times n$，对于那些特征维数很大的问题，可以有效的降低存储空间和计算的时间
3. 对于一些问题来说，找kernel要比找一个向量化的函数$\phi(x)$容易的多

只要是任何正定的矩阵，都可以当作kernel matrix，不过针对具体的问题，选择有效的核函数好像目前并没有什么理论的基础，很多时候都是测试不同的核。

kernel as dot product in feature space

在上面将kernel的时候，知道$\phi(x)$可以将一个数据点映射到特征空间，其实kernel与高维的特征空间密切相关，这是一种理解kernel的常用方法：将kernel理解为特征空间的点乘积。在高维的特征空间我们并不关系他们的坐标，而是关心它们之间的点乘积。

正如上面所示的，在映射到高位特征空间后，原来不线性可分的数据在高维的特征空间变为线性可分的。其实，比处理非线性更重要的一点是kernel可以处理各种类型的数据，有些数据是很难向量化表示的，借助kernel我们可以很容易的进行处理。上面的表述形式话就是：

对于任何一个kernel $\kappa$ ，$x \in \mathcal{X}$，总存在一个Hilbert space $\mathcal {F}$和一个函数$\phi(x)$，使得

\[
\kappa(x,x^{'})= \langle\phi(x),\phi(x^{'}) \rangle
\]

为了好理解，我们可以从简单的在原来空间的线性核$\kappa(x,x^{'})=x^Tx^{'}$，扩展到特征空间的线性核$\kappa(x,x^{'})=\phi(x)^T\phi(x^{'})$来理解。$\kappa(x,x^{'})=x^Tx^{'}$满足kernel必须满足的两个条件，

$\kappa(x,x^{'})=\kappa(x^{'},x)$；

\[
\sum_i^{n}\sum_i^{n}c_ic_j\kappa(x_i,x_j)=\sum_i^{n}\sum_i^{n}c_ic_jx_i^Tx_j=\sum_i^{n}c_ix_i\sum_i^{n}c_jx_j=\|\sum_i^{n}c_ix_i\|^2 \geq 0
\]

所以$\kappa(x,x^{'})=x^Tx^{'}$是一个核函数，拓展到特征空间以后，很容易证明$\kappa(x,x^{'})=\phi(x)^T\phi(x^{'})$也是一个核函数，实际上我们在思考很多问题时，可能就是将数据映射到特征空间，看一下是否方法能够用核函数的方法来解决。

kernel trick

有了上面的分析，我们知道核函数可以看作特征空间的点乘积，那么只要模型中出现了这样的“模式”，就可以使用kernel来替代，这样我们就可以扩展很多的算法，使其kernel化了。

常用的kernel

kernel真的很多，根据需要选择不同的核函数，有时候我们需要根据我们自己的问题，创造新的核函数。常用的核函数有：

1. 多项式核：$ \kappa(x_1,x_2) = \left(\langle x_1,x_2\rangle + R\right)^d$
2. 高斯核：$\kappa(x_1,x_2) = \exp\left(-\frac{\|x_1-x_2\|^2}{2\sigma^2}\right)$
3. 线性核：$ \kappa(x_1,x_2) = \langle x_1,x_2\rangle$

当然还有其他非常多的核函数。

dual representations

实际上很多的模型，本身就很容易用kernel形式表示，这样的表示称为dual representation，下面就看一下linear regression model的dual representation。

从前面的模型我们已将知道，linear regression要优化的目标函数是

\[
 J(\theta)=\frac{1}{2}\sum_{n=1}^{N}\{t^{(n)}-\theta^{T} \phi(X^{(n)})\}^2 + \frac{1}{2}\lambda\|\theta\|^2
\]

对上面的目标函数求导数，可以得到：

\[
\sum_{n=1}^{N}\{\theta^{T}\phi(X^{(n)})-t^{(n)}\}\phi(X^{(n)})+\lambda\theta=0
\]

这样我们就可以将参数$\theta$重写为

\[
\theta=\sum_{n=1}^{N}a^n\phi(X^{(n)})=\Phi^T\mathbf a
\]

其中，$\Phi^T(n,:)=\phi(X^{(n)})^T,\mathbf a=(a_1,a_2,..,a_n)$

这样我们就可以将目标函数 $J(\theta)$用$J(\mathbf a)$来表示

\[
\begin{eqnarray}
J(\mathbf a) &=&\frac{1}{2}\sum_{n=1}^{N}\{t^{(n)}- \mathbf a^T\Phi \phi(X^{(n)})\}^2 + \frac{1}{2}\mathbf a^T\Phi\Phi^T\mathbf a\\
&=&\frac{1}{2}\mathbf a^T\Phi\Phi^T\Phi\Phi^T\mathbf a-\mathbf a^T\Phi\Phi^T\mathbf t+\frac{1}{2}\lambda \mathbf a^T\Phi\Phi^T\mathbf a\\
&=&\frac{1}{2}\mathbf a^T\mathbf K\mathbf K\mathbf a-\mathbf a^T\mathbf K\mathbf t+\frac{1}{2}\lambda \mathbf a^T\mathbf K\mathbf a
\end{eqnarray}
\]

[引用]

1.http://www.kernel-methods.net/tutorials/KMtalk.pdf

2.a primer on kernel method

3.http://blog.pluskid.org/?p=685