核函数原理深度解析：从定义到应用
核函数原理深度解析：从定义到应用
核函数是机器学习和统计学中的一个重要概念，特别是在支持向量机（SVM）和其他基于核方法的算法中。它通过一个隐式的方式将数据映射到一个高维空间，从而使得在该高维空间中线性不可分的问题变得线性可分。本文将通过一个具体的二分类问题实例，深入解析核函数的核心原理和应用。
核函数的定义
核函数（Kernel Function）是一个定义在输入空间中的函数，满足
[ K(x, y) = \phi(x) \cdot \phi(y) ]
其中 $\phi$ 是一个从输入空间映射到高维特征空间的映射，$\cdot$ 表示高维空间中的内积。
核函数的作用
核函数通过计算输入数据在高维空间中对应点的内积，而不需要显式进行映射。这种方法被称为“核技巧”（Kernel Trick）。
核函数的诞生
让我们通过一个具体的二分类问题来理解核函数的诞生背景和作用。
假设我们现在正在处理一个二分类问题，红蓝两类样本在原始空间 $\mathcal{X}$ 中的分布如左图所示。如果要在原始空间中将两类样本分开，需要一个复杂的椭圆方程作为划分线。显然，这种方法比较麻烦。我们最理想的划分方式是通过一条直线就将两类样本划分开来。但这在原始空间 $\mathcal{X}$ 中是不可实现的。
那如果我们将原始空间中的所有样本点，通过一个映射关系 $\phi$，从原始空间 $\mathcal{X}$ 中“送到”右边的映射空间 $\mathcal{H}$ 中，就可以找到一个“平面”将两类样本划分开。这个映射过程，用数学语言描述就是：
[ \phi: \mathcal{X} \rightarrow \mathcal{H} ]
经过映射之后，$\mathcal{X}$ 中的每个样本的点的坐标就由 $x$ 变为了 $\phi(x)$。于是刚刚在 $\mathcal{X}$ 空间中用于划分红蓝两类样本的椭圆方程 $f(x)$ 映射到 $\mathcal{H}$ 空间中后就变成了后面这个方程 $f(\phi(x))$。
现在我们令原始空间中红色类别中的任意一个样本点为 $x_1$，任意一个蓝色类别样本点为 $x_2$。于是在 $\mathcal{H}$ 空间中，任意一个红色样本与任意一个蓝色样本取的内积就可以表示为：
[ \phi(x_1) \cdot \phi(x_2) ]
这个时候你会发现，这不就是原空间 $\mathcal{X}$ 中的内积的平方吗？于是可以再写成:
[ (\phi(x_1) \cdot \phi(x_2))^2 ]
也就是说，如果想要算出高维度空间 $\mathcal{H}$ 中的内积，其实可以先算出原始空间 $\mathcal{X}$ 中的内积再平方。我们要找的核函数其实就是：
[ K(x_1, x_2) = (\phi(x_1) \cdot \phi(x_2))^2 ]
因此，我们就可以求出在 $\mathcal{H}$ 空间中两点之间的距离：
[ ||\phi(x_1) - \phi(x_2)||^2 ]
相应的，我们也可以求出在 $\mathcal{H}$ 空间中两向量的夹角：
[ \cos(\theta) = \frac{\phi(x_1) \cdot \phi(x_2)}{||\phi(x_1)|| \cdot ||\phi(x_2)||} ]
同时，我们也可以求出在 $\mathcal{H}$ 空间中的所有点相互内积组成的 $n \times n$ 矩阵，又称内积矩阵或核矩阵：
[ K = \begin{bmatrix}
K(x_1, x_1) & K(x_1, x_2) & \cdots & K(x_1, x_n) \
K(x_2, x_1) & K(x_2, x_2) & \cdots & K(x_2, x_n) \
\vdots & \vdots & \ddots & \vdots \
K(x_n, x_1) & K(x_n, x_2) & \cdots & K(x_n, x_n)
\end{bmatrix} ]
接下来，可以通过一个简单的例子来展示核函数 $K$ 在分类上的作用。
假设现在我们有训练集:
[ {(x_1, y_1), (x_2, y_2), \ldots, (x_n, y_n)} ]
这个训练集属于 $d$ 维空间，每个样本可能对应的标签是 -1 和 1。这就是一个简单的二分类问题。
现在我们通过 $\phi$ 将原始空间 $\mathcal{X}$ 中的点送到映射空间 $\mathcal{H}$ 中。于是训练集就变成了:
[ {(\phi(x_1), y_1), (\phi(x_2), y_2), \ldots, (\phi(x_n), y_n)} ]
假设“+”标记点属于正类（$y=1$），“○”标记点属于负类（$y=-1$）。因此我们可以分别求出正负两类点的中心位置分别为：
[ \mu_+ = \frac{1}{n_+} \sum_{i \in \mathcal{P}} \phi(x_i) ]
[ \mu_- = \frac{1}{n_-} \sum_{i \in \mathcal{N}} \phi(x_i) ]
知道了中心点，根据“三角形法则”就可以求出由负类中心点指向正类中心点的红色向量为：
[ \Delta = \mu_+ - \mu_- ]
有了 $\Delta$ 就可以在其 1/2 的位置做一条垂线，那现在如果有一个新的样本 $x$（图中绿色五角星）进来，我们该如何预测它的类别呢？
我们需要判断图中 $\angle \Delta x$ 的角度大小即可。如果是小于 90 度，则属于正类，即：
[ \Delta \cdot x > 0 ]
如果是大于 90 度，则属于负类，则：
[ \Delta \cdot x < 0 ]
最后将 $\Delta \cdot x$ 算出来的值通过信号函数 $sgn$ 处理之后就可以得到类别。
到这里，很容易知道，我们只要能算出 $\Delta \cdot x$ 就可以对未知样本进行分类。于是：
[ \Delta \cdot x = (\mu_+ - \mu_-) \cdot x ]
将 $\mu_+$ 和 $\mu_-$ 带入上式：
[ \Delta \cdot x = \left( \frac{1}{n_+} \sum_{i \in \mathcal{P}} \phi(x_i) - \frac{1}{n_-} \sum_{i \in \mathcal{N}} \phi(x_i) \right) \cdot x ]
我们又嗅到了熟悉的味道，前面部分又可以用 $K$ 来计算，于是：
[ \Delta \cdot x = \frac{1}{n_+} \sum_{i \in \mathcal{P}} K(x_i, x) - \frac{1}{n_-} \sum_{i \in \mathcal{N}} K(x_i, x) ]
现在，我们只需要找到核函数 $K$ 就可以进行计算并进行分类。
于是又有以下的疑问：
- $\phi$ 是不是必须要知道？ No！
- 我们是不是只需要 $K$ 就可以进行求解？ Yes！
- 那么什么样的 $K$ 是符合要求的，具有什么性质？ 有限半正定的(一会讲解)
- 给定一个映射 $\phi$，我们能不能找到一个相关的核函数 $K$ 计算 $\mathcal{H}$ 空间中的内积? Yes!
- 给定一个核函数 $K$，我们能不能构建一个特征空间 $\mathcal{H}$？ Yes!
什么是有限正半定函数？
首先我们先了解清楚什么是半正定矩阵：
一个对称矩阵 $A$ 被称为半定矩阵，如果对于所有非零向量 $x$，都有：
[ x^T A x \geq 0 ]
换句话说，任何向量与这个矩阵做双线性乘积的结果总是非负的。
然后我们来说什么什么样的函数有资格称为核函数，也就是上面说的一个函数的内积矩阵是半正定矩阵。
常用的核函数
- 线性核函数：$K(x, y) = x \cdot y$
- 多项式核函数：$K(x, y) = (x \cdot y + c)^d$
- 高斯核函数（RBF核）：$K(x, y) = \exp(-\gamma ||x - y||^2)$
- Sigmoid核函数：$K(x, y) = \tanh(\alpha x \cdot y + c)$
本文主要参考了李政轩老师系列视频：https://www.youtube.com/watch?v=p4t6O9uRX-U&list=PLt0SBi1p7xrRKE2us8doqryRou6eDYEOy&index=1