6.2.2　核方法的简要介绍

在机器学习算法中，我们使用核方法一般是为了将低维的线性不可分数据转换到高维空间的线性可分情形，从而学习到更好的分类器。又因为数据经过高维映射后，输入数据和输出结果的函数关系将是非线性的，这样的核方法分类器一般称为非线性分类器。而我们知道，常用的非线性分类器是深度神经网络，然而深度神经网络过大的参数量使其无法很好地应用到实际的场景中，特别是联邦学习场景。基于核方法的支持向量机是除深度神经网络之外，性能最好的非线性分类器之一。我们接下来简要介绍核函数及核方法。

定义6.1　记是输入空间（即欧几里得空间的子集或者离散集合），又记为特征空间（即希尔伯特空间），如果存在一个从到的映射函数：ϕ（x）:→，使得其对于所有xi，xj∈，函数k（·，·）满足条件k（xi，xj）=ϕ（xi）·ϕ（xj），则称函数k为核函数，ϕ为映射函数，式中的ϕ（xi）·ϕ（xj）为ϕ（xi）和ϕ（xj）的内积。

这种考虑的特殊点在于，我们在学习和预测的时候只需定义核函数k而不用显式地定义映射函数ϕ，因为在一般情况下，直接计算k比较容易。

然而，并不是所有的函数都可以做核函数。表6-2给出一些常见的核函数。

定理6.1　令是输入空间，k（·，·）是定义在×的对称函数，那么k是核函数，当且仅当对于任意数据D={x1，x2，···，xn}∈，核矩阵K总是半正定的：

定理6.1表明，只要一个对称函数所对应的核矩阵半正定，它就可以作为核函数使用。事实上，对于一个半正定核矩阵，其总能找到一个与之对应的映射函数ϕ。也就是说，任何一个核函数都隐式地定义了一个RKHS。该RKHS是一个完备的内积空间，并具有再生核的性质：f·k（x，·）=f（x），k（x，·）·k（y，·）=k（x，y）。

通常，我们把半正定核矩阵对应的核函数称为正定核。由上面的讨论可知，我们希望样本在映射后的特征空间中线性可分，所以特征空间的好坏就直接影响了核方法的性能。因此，核函数的选取方法就成为关键。如表6-2所示，常用的核函数有线性核、多项式核、高斯核、拉普拉斯核、Sigmoid核。此外，我们还可以通过核函数间的线性组合、直积等方式获得更多的核函数。

完成了核函数的相关定义，我们有表示定理（Representation Theorem）这种对损失函数更普遍的结论，即对于像式（6.1）的优化问题，我们有如下定理。

定理6.2　为核函数k对应的RKHS，为定义在中关于f的范数。对于具有任意非负的损失函数l:→[0，∞]和任意单调递增函数∆:[0，∞]→：

其解总可以写为f（x）=∑iαik（xi，·）。

像线性的支持向量机等模型，我们可以将其划分超平面的模型记为f（x）=wTx+b，其中w和b为模型参数。令ϕ（x）为将x映射后的向量，那么线性模型就变为非线性模型（特征空间线性可分模型）f（x）=wTϕ（x）+b，从而其优化目标就从

变为

其解也相应地从

变为

因为b为常数项，我们可以将解表示为定理6.2中核函数线性组合的形式。

所以，仍然记ϕ为低维到高维的映射函数，我们就可以将定理6.2中的解表示为高维线性可分的形式，即f（x）=ω⊤ϕ（x），其中ω=∑iαiϕ（xi）。换句话说，样本点xi和xj在高维特征空间的内积ϕ（xi）·ϕ（xj）等于它们在原始样本空间的核函数计算结果。然而，这种传统的核方法在大规模或者高维数据集上计算缓慢。为了加速核函数的计算，研究者们提出了使用核函数的傅里叶变换得到的基函数内积来近似它，并取得了不错的效果。我们在6.2.3节将对这种方法进行详细介绍。