核技巧是什么？不做映射也能算出高维空间里的内积

核技巧（Kernel Trick）是机器学习中一个非常巧妙的数学方法：它让我们可以在不真正把数据映射到高维空间的情况下，直接得到数据在高维空间中进行计算的结果。正是靠着核技巧，支持向量机等原本只能处理线性问题的方法，才能高效地解决复杂的非线性问题。

它要解决的问题

很多数据在原始的空间中无法用一条直线或一个平面分开，比如一类点在中间，另一类点在外面围成一圈。但如果把数据映射到一个更高维的空间中，它们往往就变得可以用一个平面分开了。问题在于，为了让数据线性可分，可能需要映射到维度非常高的空间。比如对于有 100 个特征的数据，如果要考虑所有特征两两相乘的组合，映射后就有五千多个维度；如果考虑三三相乘，就有十几万个维度；而有些映射甚至会得到无穷维的空间。在这样的空间中直接计算每个样本的新坐标，再做后续的运算，计算量和存储量都会大到无法承受。

核技巧的关键发现

研究者注意到，支持向量机、主成分分析、岭回归等很多算法在进行计算时，并不需要知道每个样本在高维空间中的具体坐标，它们只需要知道样本两两之间的内积。内积可以理解为衡量两个向量相似程度的一种方式。而核函数恰好就是这样一种函数：输入原始空间中的两个样本，它直接输出这两个样本映射到高维空间之后的内积。

举一个简单的例子：对于二维的数据，如果把每个点映射到包含原来两个坐标的平方以及它们乘积的三维空间中，那么映射后两个点的内积，正好等于原来两个点内积的平方。也就是说，只需要在二维空间中算一次内积再平方，就得到了三维空间中的内积，完全不需要真的去计算三维的坐标。这就是多项式核的一个特例。对于高斯核，它对应的特征空间是无穷维的，根本不可能显式地写出来，但用核函数计算内积却非常简单。

哪些函数可以作为核函数

并不是任意一个函数都能当作核函数。一个函数能作为核函数的条件是：对于任意一组样本，由它们两两之间的核函数值组成的矩阵，必须是对称的半正定矩阵，这由默瑟定理给出。满足这个条件的函数，一定对应着某个特征空间中的内积。常用的核函数包括线性核、多项式核、高斯核和 Sigmoid 核。

它的历史和意义

核函数的数学思想很早就已存在，1964 年，Aizerman 等人在研究势函数方法时就用到了类似的思想。1992 年，Bernhard Boser、Isabelle Guyon 和 Vladimir Vapnik 把核技巧与最大间隔分类器结合起来，提出了非线性的支持向量机，使核技巧在机器学习中广为人知。此后，核技巧被推广到了许多其他的线性算法中，形成了一整类“核方法”，比如核主成分分析、核岭回归、核 K 均值聚类等。核技巧的意义在于：它把“设计特征”的问题转化成了“设计相似度函数”的问题，人们只需要定义好两个样本之间的相似程度，就能隐式地获得一个强大的特征表示。它的局限是计算量随样本数量的平方增长，难以处理非常大规模的数据。