Kernel method - webdancer's Blog

Kernel method

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

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

ebalbharati 10th Cl 说:
2023年9月24日 20:50

Maha Board High School Students Summers Holidays Don’t Waste Time 10th Standard Pursuing Students can Download the Textbooks and take the hard copy for further use, we will update the Latest Information on this page. Maharashtra e-Books 2024 Latest Version to be Upload Every Year in Online Mode.Maharashtra Board High School Textbooks 2024 are Very Important to Students on the ebalbharati 10th Class Textbook 2024 Preparations of the Monthly and Final Examination. Here, we are Providing the Latest Edition of MH Class Book 2024 which is Published by the Balbharati. All the chapters can be Downloaded in form of PDFs.Maharashtra High School Students Follows.


登录 *


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