点击量：6972

引言

很多人介绍核技巧时总会扯上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定理的函数也可以是核函数。