为什么核方法可以避免显式特征映射：核技巧与Mercer定理

输入 一份线性不可分的数据集，比如二维平面上的两类点，一个类别分布在圆心附近，另一个类别分布在外围的环形区域。尝试 用一条直线去划分，必然失败。转向 一种常规思路：把数据映射到更高维空间，在高维空间做线性划分。但 计算 映射后的坐标会带来巨大的开销，甚至某些映射的目标空间是无限维的，根本无法显式写出坐标。

1. 显式特征映射的代价

理解 一个简单的显式映射例子。取 二维样本 $x = (x_1, x_2)$，定义 映射到三维多项式特征空间：

$$ \phi(x) = (x_1^2,\ \sqrt{2}x_1x_2,\ x_2^2) $$

计算 两个样本 $x$ 和 $z$ 映射后的内积：

$$ \langle \phi(x), \phi(z) \rangle = x_1^2 z_1^2 + 2x_1x_2 z_1z_2 + x_2^2 z_2^2 $$

看出 中间项需要分别算出 $\sqrt{2}x_1x_2$ 和 $\sqrt{2}z_1z_2$，再相乘。当维度升高到 $d$，多项式阶数升高到 $p$，显式构造 $\phi(x)$ 的维度是 $O(d^p)$，执行 一次内积的复杂度也随之爆炸。更极端的情况，比如高斯核对应的特征映射是无限维的，映射 函数 $\phi(x)$ 根本没有可写的闭式表达式。

核心结论：显式特征映射的行不通之处在于——映射本身的计算成本过高，甚至不可能实现。

2. 核技巧：只计算内积，不碰映射

观察 上述内积表达式可以重新整理：

$$ x_1^2 z_1^2 + 2x_1x_2 z_1z_2 + x_2^2 z_2^2 = (x_1z_1 + x_2z_2)^2 $$

发现 原式等于 $\langle x, z \rangle^2$。这意味着 计算 高维空间的内积，可以直接用低维空间的点积平方完成，完全不需要构造 $\phi(x)$。定义 这个直接计算内积的函数为核函数：

$$ k(x, z) = \langle \phi(x), \phi(z) \rangle $$

使用 核函数 $k(x,z) = (\langle x, z \rangle)^2$，替代 显式映射后的点积。这就是核技巧的本质：凡是算法中只出现内积的地方，全部替换为核函数求值。常见的核函数对应如下映射：

强调 高斯核的 $\phi$ 是无限维的，但 $k(x,z)$ 的值只需一次指数运算即可得到。这就是“避免显式映射”的直接收益。

3. Mercer定理：为什么可以这样做

追问 是否任意一个二元函数都能写成某个 $\phi$ 的内积？答案 是否定的。引入 Mercer 定理来划定边界。

定理表述：设 $X \subset \mathbb{R}^n$，$k: X \times X \to \mathbb{R}$ 是一个连续对称函数。若对于任意有限个点 $\{x_1, \dots, x_m\}$，对应的 Gram 矩阵

$$ K_{ij} = k(x_i, x_j) $$

是半正定的，则 $k$ 可以展开为一致收敛的级数：

$$ k(x,z) = \sum_{i=1}^{\infty} \lambda_i \phi_i(x) \phi_i(z) $$

其中 $\lambda_i \ge 0$，$\{\phi_i\}$ 是一组正交函数。定义 特征映射为：

$$ \Phi(x) = \left( \sqrt{\lambda_1}\phi_1(x),\ \sqrt{\lambda_2}\phi_2(x),\ \dots \right) $$

验证 此时 $\langle \Phi(x), \Phi(z) \rangle = \sum_{i=1}^{\infty} \lambda_i \phi_i(x)\phi_i(z) = k(x,z)$。得出 半正定是核函数能被“内积化”的充要条件。满足该条件的函数被称作 Mercer 核。

操作要点：使用 一个核函数前，检查 其半正定性。选取 以下常用方式验证矩阵半正定：

1. 计算 所有特征值。确认 每个特征值都大于等于 0。
2. 计算 任意向量 $c$ 满足 $c^T K c \ge 0$。采用 数值上更稳定的方式，如 Cholesky 分解，判断 是否能成功执行。
3. 利用 已知核的封闭运算规则。例如，两个 Mercer 核的和与积仍是 Mercer 核，核函数的非负线性组合仍是 Mercer 核。

理解 定理的实践意义：它保证了“内积替换”的合法性。只要核函数满足条件，就等价于在某个特征空间（可能是无限维）中做内积，无需 知道 $\Phi$ 的具体形式。

4. 在算法中的具体操作

选取 一个依赖内积的算法，例如 SVM。执行 以下步骤应用核技巧：

1. 写出 原始优化问题中的内积项。对 SVM，决策函数为：
   $$ f(x) = \operatorname{sign}\left( \sum_{i=1}^{m} \alpha_i y_i \langle x_i, x \rangle + b \right) $$
2. 替换 所有 $\langle x_i, x \rangle$ 为 $k(x_i, x)$：
   $$ f(x) = \operatorname{sign}\left( \sum_{i=1}^{m} \alpha_i y_i k(x_i, x) + b \right) $$
3. 训练 过程中同样替换对偶问题中的内积为核函数。求解 得到参数 $\alpha_i$ 和 $b$。
4. 预测 时对新样本 $x$ 直接调用核函数计算与所有支持向量的相似度。

注意 核技巧不仅限于 SVM。应用 到 PCA，得到 核 PCA：先计算中心化核矩阵，再对其做特征分解，提取主成分对应的方向。应用到 逻辑回归或岭回归，得到 核岭回归。关键在于 识别 算法中所有内积出现的位置，并 统一替换 为指定的核函数。

效率对比：显式映射后内积复杂度为 $O(\dim(\phi))$，而核函数求值复杂度通常为 $O(d)$ 或 $O(d \log d)$，$d$ 是原始维度。选择 高斯核时，显式映射不可行，而核求值仅需 $O(d)$ 的指数运算。