一文读懂支持向量积核函数（附公式）

本文通过多个例子为你介绍支持向量积核函数，助你更好地理解。

核函数（Kernels）

考虑我们最初在“线性回归”中提出的问题，特征是房子的面积x，这里的x是实数，结果y是房子的价格。

假设我们从样本点的分布中看到x和y符合3次曲线，那么我们希望使用x的三次多项式来逼近这些样本点。

那么首先需要将特征x扩展到三维(x,x^{2},x^{3}) ，然后寻找特征和结果之间的模型。我们将这种特征变换称作特征映射（feature mapping）。映射函数称作\Phi ，在这个例子中

我们希望将得到的特征映射后的特征应用于SVM分类，而不是最初的特征。这样，我们需要将前面W^{T}x+b 公式中的内积从<x^{(i)},x> ，映射到<\Phi(x^(i)),\Phi(x)> 。

至于为什么需要映射后的特征而不是最初的特征来参与计算，上面提到的（为了更好地拟合）是其中一个原因，另外的一个重要原因是样例可能存在线性不可分的情况，而将特征映射到高维空间后，往往就可分了。（在《数据挖掘导论》Pang-Ning Tan等人著的《支持向量机》那一章有个很好的例子说明）

将核函数形式化定义，如果原始特征内积是<x,z> ，映射后为<\Phi(x),\Phi(z)> ，那么定义核函数（Kernel）为

到这里，我们可以得出结论，如果要实现该节开头的效果，只需先计算\Phi(x) ，然后计算\Phi(x)^T\Phi(z) 即可，然而这种计算方式是非常低效的。

比如最初的特征是n维的，我们将其映射到n^2 维，然后再计算，这样需要O(n^2) 的时间。那么我们能不能想办法减少计算时间呢？

先看一个例子，假设x和z都是n维的，

展开后，得

这个时候发现我们可以只计算原始特征x和z内积的平方（时间复杂度是O(n)），就等价与计算映射后特征的内积。也就是说我们不需要花O(n^2) 时间了。

现在看一下映射函数（n=3时），根据上面的公式，得到

也就是说核函数

只能在选择这样的\Phi 作为映射函数时才能够等价于映射后特征的内积。

再看一个核函数

对应的映射函数（n=3时）是

更一般地，核函数

对应的映射后特征维度为

由于计算的是内积，我们可以想到IR中的余弦相似度，如果x和z向量夹角越小，那么核函数值越大，反之，越小。因此，核函数值是\Phi(x) 和\Phi(z) 的相似度。

再看另外一个核函数

这时，如果x和z很相近（ \lVert x-z\lVert \thickapprox 0 ），那么核函数值为1，如果x和z相差很大（\lVert x-z\lVert \gg 0 ），那么核函数值约等于0。

由于这个函数类似于高斯分布，因此称为高斯核函数，也叫做径向基函数(Radial Basis Function 简称RBF)。它能够把原始特征映射到无穷维。

既然高斯核函数能够比较x和z的相似度，并映射到0到1，回想logistic回归，sigmoid函数可以，因此还有sigmoid核函数等等。

下面有张图说明在低维线性不可分时，映射到高维后就可分了，使用高斯核函数。

来自Eric Xing的slides

注意，使用核函数后，怎么分类新来的样本呢？线性的时候我们使用SVM学习出w和b，新来样本x的话，我们使用W^{T}x+b 来判断，如果值大于等于1，那么是正类，小于等于是负类。

在两者之间，认为无法确定。如果使用了核函数后，W^{T}x+b 就变成了W^{T}\Phi(x)+b ，是否先要找到\Phi(x) ，然后再预测？答案肯定不是了，找\Phi(x) 很麻烦，回想我们之前说过的

只需将<x^{i},x> 替换成K<x^{i},x> ，然后值的判断同上。

核函数有效性判定

问题：给定一个函数K，我们能否使用K来替代计算\Phi(x)^T\Phi(z) ，也就说，是否能够找出一个\Phi ，使得对于所有的x和z，都有 K(x,z)=\Phi(x)^{T}\Phi(z) ？

比如给出了K(x,z)=(x^{T},z)^{2} ，是否能够认为K是一个有效的核函数。

下面来解决这个问题，给定m个训练样本\{x^{1},x^{2},.....,x^{m}\} ，每一个x^{(i)} 对应一个特征向量。

那么，我们可以将任意两个x^{(i)} 和x^{j} 带入K中，计算得到

。I可以从1到m，j可以从1到m，这样可以计算出m*m的核函数矩阵（Kernel Matrix）。

为了方便，我们将核函数矩阵和K(x,z) 都使用K来表示。

如果假设K是有效地核函数，那么根据核函数定义

可见，矩阵K应该是个对称阵。让我们得出一个更强的结论，首先使用符号\Phi_{k}(x) 来表示映射函数\Phi(x) 的第k维属性值。那么对于任意向量z，得

最后一步和前面计算K(x,z)=(x^(T)z)^2 时类似。从这个公式我们可以看出，如果K是个有效的核函数（即K(x,z) 和\Phi(x)^{T}\Phi(z) 等价），那么，在训练集上得到的核函数矩阵K应该是半正定的（K\geqq 0 ）

这样我们得到一个核函数的必要条件：

K是有效的核函数 ==> 核函数矩阵K是对称半正定的。

可幸的是，这个条件也是充分的，由Mercer定理来表达。

Mercer定理： 如果函数K是

上的映射（也就是从两个n维向量映射到实数域）。那么如果K是一个有效核函数（也称为Mercer核函数），那么当且仅当对于训练样例\{x^{1},x^{2},.....,x^{m}\} ，其相应的核函数矩阵是对称半正定的。

Mercer定理表明为了证明K是有效的核函数，那么我们不用去寻找\Phi ，而只需要在训练集上求出各个K_{ij} ，然后判断矩阵K是否是半正定（使用左上角主子式大于等于零等方法）即可。

许多其他的教科书在Mercer定理证明过程中使用了L^{2} 范数和再生希尔伯特空间等概念，但在特征是n维的情况下，这里给出的证明是等价的。

核函数不仅仅用在SVM上，但凡在一个模型后算法中出现了<x,z> ，我们都可以常使用k<x,z>去替换，这可能能够很好地改善我们的算法。