核技巧(The Kernel Trick)

点击量:608

引言

很多人介绍核技巧时总会扯上SVM,大概是很多人第一次碰到核技巧就是在SVM里吧。其实,核技巧是一个非常纯粹的数学方法,不应该一上来就扯上SVM。因为这个技巧不仅应用在SVM中,还有其他领域也有应用。它解决了数据映射到高维空间之后点积的计算量过于复杂的问题。很多人啰啰嗦嗦说了一大堆,把原本很简单的东西搞的很复杂,其实这玩意很好理解。

问题描述

给定两个向量\(x_i\)和\(x_j\),我们的目标是要计算他们的内积\(I = <x_i, x_j>\)。现在假设我们通过某种非线性变换:

$$
\Phi : x \rightarrow \phi(x)
$$

把他们映射到某一个高维空间中去,那么映射后的向量就变成:\(\phi(x_i)\)和\(\phi(x_j)\),映射后的内积就变成:\(I’ = <\phi(x_j),\phi(x_j)>\)。现在改如何计算映射后的内积呢?传统方法是先计算映射后的向量\(\phi(x_i)\)和\(\phi(x_j)\),然后再计算它俩的内积。但是这样做计算很复杂,因为映射到高维空间后的数据维度很高。比如,假设\(x_i\)和\(x_j\)在映射之后都是一个\( 1 \times 10000\)维的向量,那么他们的内积计算就需要做\(10000\)次加法操作和\(10000\)次乘法操作,显然复杂度很高。于是,数学家们就想出一个办法:能不能在原始空间找到一个函数\(K(x_i,x_j)\)使得\(K(x_i,x_j) = <\phi(x_j),\phi(x_j)>\)呢? 如果这个函数存在,那么我们只需要在低维空间里计算函数\(K(x_i,x_j)\)的值即可,而不需要先把数据映射到高维空间,再通过复杂的计算求解映射后的内积了。庆幸的是,这样的函数是存在的。这样一来计算的复杂度就大大降低了,这种简化计算的方法被称为核技巧(The Kernel Trick),而函数\(K\)就是核函数(Kernel Function)。

与SVM的关系

之前的一篇介绍支持向量机的文章里我们说过:支持向量机为了解决数据在低维度不容易线性分割的情况下,会通过某非线性变换 \(\phi(x)\),将输入空间映射到高维特征空间。于是,就得到如下求解公式:

$$
\sum_{i=1}^{N}\sum_{j=1}^{N}\alpha_i\alpha_jy_iy_j\phi(x_i)^{T}phi(x_j)-\sum_{i=1}^{N}\alpha_i\\\text{s.t.}\\0\leq\alpha_1\leq C\\ \sum_{i=1}^{N} y_{i}\alpha _{i}=0
$$

观察上面的公式你会发现里面有一个内积运算

$$
\phi \left ( x_{i} \right )^{T}\phi \left ( x_{j} \right )
$$
于是,为了降低计算复杂度,解决映射后可能产生的维度爆炸问题,我们在求解的时候引入了核技巧。核技巧并不仅仅应用在SVM中,在其他需要处理高维映射计算的问题中也有很多应用。

常用的核函数

主要有以下几种:

  • 线性核,其实就是没有映射
    \(\kappa \left ( x_{1},x_{2} \right ) = \left \langle x{1},x{2} \right \rangle\)

  • 高斯核函数,使用最为广泛,它能够把原始特征映射到无穷维。
    \(\kappa \left ( x_{1},x_{2} \right ) = \exp \left ( -\frac{\left | x_{1}-x_{2} \right |^{2}}{2\sigma ^{2}} \right )\)

  • 多项式核函数,它能把数据映射到\(C_{n+d}^{n}\)维。
    \(\kappa \left ( x_{1},x_{2} \right ) = \left ( \left \langle x_{1},x_{2} \right \rangle +R\right )^{d}\)

由此可见:选择什么样的核函数将会决定你把数据映射到什么样的维度。

核函数的满足条件

Mercer 定理:任何半正定的函数都可以作为核函数。所谓半正定的函数\(f(x_i,x_j)\),是指拥有训练数据集合\(x_1,x_2,…x_n\),我们定义一个矩阵的元素\(a_{ij} = f(x_i,x_j)\),这个矩阵是\(n \times n\)的,如果这个矩阵是半正定的,那么\(f(x_i,x_j)\)就称为半正定的函数。

这个mercer定理不是核函数必要条件,只是一个充分条件,即还有不满足mercer定理的函数也可以是核函数。

核技巧(The Kernel Trick)》上有2条评论

  1. Chloe Wang

    您好:
    请问文中的“假设xi和xj都是一个1×10000维的向量,那么他们的内积计算就需要做10000×10000次乘法操作,显然复杂度很高”,不是很理解为什么是10000×10000次乘法操作呢。内积不是两个向量对应位置上的值相乘求和即可吗,也就是10000次乘法再全部相加。
    盼回复,谢谢!

    回复
    1. fanyy 文章作者

      童鞋你好,感谢你的指正啊,这段描述确实有误,应该是10000次加法和10000次乘法操作。我当时写的时候没仔细想内积是如何运算的,我已改正,多谢。

      回复

发表评论

电子邮件地址不会被公开。 必填项已用*标注