Kernel method - webdancer's Blog

Kernel method

webdancer posted @ 2013年2月28日 20:44 in machine learning with tags Machine learning , 3193 阅读

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化了。smiley

常用的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}
\]

其中,$\mathbf K=\Phi\Phi^T$,是kernel matrix。通过上面的式子我们就用kernel的形式表达出来了。

对上面的式子求导,让其导数为0,可以得:

\[
\mathbf a=(\mathbf K+\lambda \mathbf I)^{-1}\mathbf t
\]

这样预测函数就可以用核函数表示:

\[
y(x)=\theta^T\phi(x)=\mathbf a^T\Phi \phi(x)=\mathbf k(x)^{T}(\mathbf K+\lambda \mathbf I)^{-1}\mathbf t^T
\]
从中可以看到对$x$的预测值是训练集目标值的一个线性组合。时间复杂性方面,主要的消耗在于计算矩阵的逆,上面的式子的时间复杂度为$O(N^3)$,而正规方程的时间复杂度为$O(M^3)$;除此之外,dual representation在SVM模型中非常的有用。

关于凸优化的dual  problem的知识,可以参考http://blog.pluskid.org/?p=702

 

[引用]

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

2.a primer on kernel method

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


登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter
Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee