【机器学习教程】第08章_核方法【上】

香芋Yu

494人浏览 · 2026-02-01 03:02:58

香芋Yu · 2026-02-01 03:02:58 发布

第 08 章核方法 (Kernel Methods)

“The curse of dimensionality is the blessing of kernel methods.”

很多时候，我们在低维空间撞得头破血流（比如 XOR 问题），却不知道只要退后一步，升到一个更高的维度，一切都会因为稀疏而变得线性可分。

核方法是机器学习中**“升维打击”**的数学实现。它的魔力在于：我们可以在无限维的空间中挥舞利剑，却只需要支付有限维的计算代价。本章将揭示这个"免费午餐"背后的数学秘密——核技巧 (Kernel Trick)。

与前序章节的联系：

第 5 章（线性回归） 为我们建立了岭回归的原始形式： $w^* = (X^T X + \lambda I)^{-1} X^T y$
本章将展示如何通过核技巧将其推广到无穷维特征空间： $\alpha^* = (\mathbf{K} + \lambda I)^{-1} y$
两者通过对偶性完美呼应：线性岭回归在特征空间优化，核岭回归在样本空间优化

1. 直觉：维度打击

1.1 XOR 问题：二维空间的绝望

考虑经典的 XOR (异或) 问题：

$x_1$	$x_2$	类别
0	0	0
0	1	1
1	0	1
1	1	0

问题：在二维平面上，不存在一条直线能够将两个类别分开。

无论你怎么尝试，任何线性分类器 $w_1 x_1 + w_2 x_2 + b = 0$ 都会犯错。这是线性模型的根本局限。

在这里插入图片描述

1.2 升维的魔法：三维空间的救赎

定义映射 $\phi: \mathbb{R}^2 \to \mathbb{R}^3$ ：

$\phi(x) = \phi\begin{pmatrix} x_1 \\ x_2 \end{pmatrix} = \begin{pmatrix} x_1 \\ x_2 \\ x_1 x_2 \end{pmatrix}$

将 XOR 数据映射到三维空间：

$\begin{aligned} \phi\begin{pmatrix} 0 \\ 0 \end{pmatrix} &= \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix} \quad &\text{(类别 0)} \\[0.5em] \phi\begin{pmatrix} 0 \\ 1 \end{pmatrix} &= \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix} \quad &\text{(类别 1)} \\[0.5em] \phi\begin{pmatrix} 1 \\ 0 \end{pmatrix} &= \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \quad &\text{(类别 1)} \\[0.5em] \phi\begin{pmatrix} 1 \\ 1 \end{pmatrix} &= \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix} \quad &\text{(类别 0)} \end{aligned}$

奇迹发生：在三维空间中，一个简单的平面 $z_3 = 0.5$ 就能完美分割两个类别！

1.3 推导：为什么升维有效？

Cover 定理 (Cover’s Theorem)：

将复杂模式投射到高维空间，模式更可能线性可分。

直觉：

在 $d$ 维空间中， $n$ 个点被随机二分的方式有 $2^n$ 种
用超平面线性可分的方式数量随着维度 $d$ 增加而增加
当 $\geq n-1$ 时，几乎所有的二分都是线性可分的

数学表达：

在 $d$ 维空间中， $n$ 个一般位置的点，线性可分的二分数量为：

$\sum_{k=0}^{d} \binom{n-1}{k}$

当 $d = n - 1$ 时， $C(n, d) = 2^n$ ，即所有二分都可分！

XOR 的验证：

对于 XOR， $n = 4$ ，原始维度 $d = 2$ ：

$2(\binom{3}{0} + \binom{3}{1} + \binom{3}{2}) = 2(1 + 3 + 3) = 14 < 2^4 = 16$

升维到 $d = 3$ ：

$2(\binom{3}{0} + \binom{3}{1} + \binom{3}{2} + \binom{3}{3}) = 2(1 + 3 + 3 + 1) = 16 = 2^4$

所有二分都可分，包括 XOR！

2. 代价：维度的诅咒

2.1 多项式特征的维度爆炸

假设我们要将 $n$ 维输入映射到 $d$ 阶多项式特征空间。

例子：2 维输入 $x = (x_1, x_2)$ ，2 阶多项式映射：

$\phi(x) = (1, x_1, x_2, x_1^2, x_1 x_2, x_2^2)$

维度从 $\to 6$ 。

一般情况： $n$ 维输入， $d$ 阶多项式，特征空间维度为：

$\text{dim}(\phi(x)) = \binom{n+d}{d} = \frac{(n+d)!}{n! \, d!}$

推导：

$d$ 阶多项式的单项式数量，等价于将 $d$ 个相同的球放入 $n$ 个不同的盒子（允许空盒），即多重集合问题：

$\binom{n+d}{d} = \binom{n+d}{n}$

2.2 复杂度爆炸实例

$n$ (维度)	$d$ (阶数)	特征维度	增长倍数
10	2	66	6.6×
10	3	286	28.6×
10	5	3,003	300×
100	2	5,151	51.5×
100	3	176,851	1,769×
100	5	79,208,745	792,087×

问题：

存储开销：需要 $O(\binom{n+d}{d})$ 空间存储 $\phi(x)$
计算开销：计算 $\phi(x)$ 需要 $O(\binom{n+d}{d})$ 时间
内积开销：计算 $\phi(x)^T \phi(z)$ 需要 $O(\binom{n+d}{d})$ 次乘法

当 $n = 100$ , $d = 3$ 时，每个内积需要 176,851 次乘法！

2.3 无穷维的梦魇

如果我们想要包含所有阶数的多项式特征（类似泰勒展开）：

$\phi(x) = (1, x_1, x_2, \ldots, x_1^2, x_1 x_2, \ldots, x_1^3, \ldots)$

特征空间变成无穷维！

这似乎是不可能计算的。但核方法会告诉我们：这不仅可能，而且高效。

3. 救赎：核技巧 (Kernel Trick)

3.1 核心观察：我们不需要 $\phi(x)$

回顾线性分类器的决策函数（如 SVM）：

$w^T \phi(x) + b$

关键发现：在很多算法中（SVM、岭回归等），最优解 $w$ 可以表示为：

$\sum_{i=1}^m \alpha_i \phi(x_i)$

代入决策函数：

$\sum_{i=1}^m \alpha_i \phi(x_i)^T \phi(x) + b = \sum_{i=1}^m \alpha_i \underbrace{\langle \phi(x_i), \phi(x) \rangle}_{K(x_i, x)} + b$

结论：我们只需要计算内积 $\phi(x_i)^T \phi(x)$ ，而不需要知道 $\phi(x)$ 本身！

3.2 核函数的定义

定义：核函数 $\mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 满足：

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

其中 $\phi: \mathcal{X} \to \mathcal{H}$ 是从输入空间到某个希尔伯特空间的映射。

核技巧的承诺：

如果 $K (x, z)$ 可以在原始空间（低维）中高效计算，我们就可以：

避免显式计算 $\phi(x)$ （避免维度爆炸）
避免在高维空间中存储和计算（节省空间和时间）
享受高维空间的表达能力（解决非线性问题）

3.3 核心推导：多项式核

目标：证明 $x^T z)^2$ 等价于某个二阶多项式映射的内积。

设 $x = (x_1, x_2)^T$ ， $z = (z_1, z_2)^T$ 。

步骤 1：展开内积的平方

$x^T z)^2 = (x_1 z_1 + x_2 z_2)^2$

步骤 2：展开平方

$\begin{aligned} (x^T z)^2 &= (x_1 z_1)^2 + 2(x_1 z_1)(x_2 z_2) + (x_2 z_2)^2 \\ &= x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 \end{aligned}$

步骤 3：配成内积形式

注意到可以写成：

$(x^T z)^2 = x_1^2 z_1^2 + (\sqrt{2} x_1 x_2)(\sqrt{2} z_1 z_2) + x_2^2 z_2^2$

步骤 4：识别特征映射

定义：

$\phi(x) = \begin{pmatrix} x_1^2 \\ \sqrt{2} x_1 x_2 \\ x_2^2 \end{pmatrix}, \quad \phi(z) = \begin{pmatrix} z_1^2 \\ \sqrt{2} z_1 z_2 \\ z_2^2 \end{pmatrix}$

则：

$\phi(x)^T \phi(z) = x_1^2 z_1^2 + 2 x_1 x_2 z_1 z_2 + x_2^2 z_2^2 = (x^T z)^2$

验证完毕：

$\boxed{K(x, z) = (x^T z)^2 = \langle \phi(x), \phi(z) \rangle}$

计算复杂度对比：

方法	计算 $\phi(x)$	计算内积	总计
显式映射	$O(n^2)$	$O(n^2)$	$O(n^2)$
核函数	-	$O (n)$	$O (n)$

对于 $n = 100$ ，这是 100 倍的加速！

3.4 一般多项式核

$d$ 阶多项式核：

$K(x, z) = (x^T z + c)^d$

其中 $\geq 0$ 是常数。

特征空间维度： $\binom{n+d}{d}$

计算复杂度： $O (n)$ （计算 $x^T z$ 然后取 $d$ 次方）

加速比： $\frac{\binom{n+d}{d}}{n} \approx \frac{n^d}{d! \cdot n} = \frac{n^{d-1}}{d!}$

例子： $n = 100$ , $d = 3$

特征维度：176,851
核计算：100 次乘法 + 1 次立方
加速比：约 1,769 倍

3.5 核技巧的威力总结

核技巧的本质：

用 $O (n)$ 的计算代价，获得 $O(n^d)$ 甚至 $O(\infty)$ 维空间的表达能力。

这是机器学习中少有的"免费午餐"——不是真的免费，而是数学的巧妙重组。

在这里插入图片描述

4. Mercer 定理：什么样的函数能当核？

4.1 问题的提出

不是任意函数都能作为核函数。

反例 1： $K(x, z) = -x^T z$

如果这是核函数，应该有 $\|\phi(x)\|^2 \geq 0$ 。

但 $K(x, x) = -x^T x = -\|x\|^2 < 0$ （当 $\neq 0$ ）。

矛盾！所以它不是核函数。

反例 2： $K(x, z) = (x^T z)^3$ （在某些情况下）

虽然看起来像多项式核，但对于某些数据，核矩阵可能不是半正定的。

问题：什么样的函数 $K (x, z)$ 能保证对应某个 $\phi$ ？

4.2 核矩阵 (Gram Matrix)

给定数据集 $\{x_1, \ldots, x_m\}$ 和核函数 $K$ ，定义核矩阵：

$\mathbf{K} = \begin{pmatrix} K(x_1, x_1) & K(x_1, x_2) & \cdots & K(x_1, x_m) \\ K(x_2, x_1) & K(x_2, x_2) & \cdots & K(x_2, x_m) \\ \vdots & \vdots & \ddots & \vdots \\ K(x_m, x_1) & K(x_m, x_2) & \cdots & K(x_m, x_m) \end{pmatrix}$

性质：

对称性： $\mathbf{K}_{ij} = K(x_i, x_j) = K(x_j, x_i) = \mathbf{K}_{ji}$
如果 $K$ 是核，则 $\mathbf{K}$ 应该满足什么性质？

4.3 Mercer 定理（标准形式）

Mercer 定理 (Mercer’s Theorem)：

一个对称函数 $\mathcal{X} \times \mathcal{X} \to \mathbb{R}$ 是核函数，当且仅当对于任意有限数据集 $\{x_1, \ldots, x_m\}$ ，核矩阵 $\mathbf{K}$ 是半正定 (positive semi-definite) 的。

半正定的定义：

矩阵 $\mathbf{K}$ 是半正定的，如果对于任意向量 $\alpha \in \mathbb{R}^m$ ：

$\alpha^T \mathbf{K} \alpha = \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j K(x_i, x_j) \geq 0$

直觉解释：为什么半正定矩阵能分解成内积？

这是线性代数中特征分解的优美应用：

半正定 ⇒ 非负特征值：半正定矩阵 $\mathbf{K}$ 的所有特征值 $\lambda_i \geq 0$
特征分解 = 坐标系旋转：分解 $\mathbf{K} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T$ 等价于在新坐标系下重新表示数据
构造特征映射：将每个点 $x_i$ 映射到 $\phi(x_i) = \sqrt{\mathbf{\Lambda}} \mathbf{U}_{i,:}^T$ ，本质是用特征值"拉伸"各维度
内积恢复核：新坐标系下的内积 $\langle \phi(x_i), \phi(x_j) \rangle$ 恰好等于原核矩阵元素 $K(x_i, x_j)$

本质：半正定矩阵 $\mathbf{K}$ 可以看作是某个隐藏特征空间中的"距离/相似度矩阵"，特征分解帮我们逆向工程出这个隐藏空间的坐标 $\phi(x)$ 。

直观例子：

考虑 3 个点的核矩阵：

$\mathbf{K} = \begin{pmatrix} 1.0 & 0.8 & 0.3 \\ 0.8 & 1.0 & 0.5 \\ 0.3 & 0.5 & 1.0 \end{pmatrix}$

特征分解后得到： $\lambda_1 = 1.95, \lambda_2 = 0.73, \lambda_3 = 0.32$ （均非负 ✓）

构造特征映射：

$\phi(x_1) = \begin{pmatrix} \sqrt{1.95} \cdot u_{11} \\ \sqrt{0.73} \cdot u_{12} \\ \sqrt{0.32} \cdot u_{13} \end{pmatrix}$

则 $K(x_1, x_2) = \phi(x_1)^T \phi(x_2) = 0.8$ 自动满足！

这就是 Mercer 定理的构造性证明：从核矩阵反推特征空间。

4.4 定理的证明（充分性）

命题：如果 $\langle \phi(x), \phi(z) \rangle$ ，则 $\mathbf{K}$ 半正定。

证明：

$\begin{aligned} \alpha^T \mathbf{K} \alpha &= \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j K(x_i, x_j) \\ &= \sum_{i=1}^m \sum_{j=1}^m \alpha_i \alpha_j \langle \phi(x_i), \phi(x_j) \rangle \\ &= \left\langle \sum_{i=1}^m \alpha_i \phi(x_i), \sum_{j=1}^m \alpha_j \phi(x_j) \right\rangle \\ &= \left\| \sum_{i=1}^m \alpha_i \phi(x_i) \right\|^2 \geq 0 \end{aligned}$

最后一步使用了范数的非负性。

4.5 定理的证明（必要性）

命题：如果 $\mathbf{K}$ 半正定，则存在 $\phi$ 使得 $\langle \phi(x), \phi(z) \rangle$ 。

证明（构造性）：

步骤 1：对 $\mathbf{K}$ 进行特征值分解

由于 $\mathbf{K}$ 对称半正定：

$\mathbf{K} = \mathbf{U} \mathbf{\Lambda} \mathbf{U}^T$

其中：

$\mathbf{\Lambda} = \text{diag}(\lambda_1, \ldots, \lambda_m)$ ， $\lambda_i \geq 0$
$\mathbf{U} = [u_1, \ldots, u_m]$ 是正交矩阵

步骤 2：构造特征映射

定义 $\phi: \mathcal{X} \to \mathbb{R}^m$ ，对于 $x_i$ ：

$\phi(x_i) = \sqrt{\mathbf{\Lambda}} \mathbf{U}_{i,:}^T = \sum_{k=1}^m \sqrt{\lambda_k} u_{ik} \, e_k$

其中 $e_k$ 是标准基向量， $\mathbf{U}_{i,:}$ 是 $\mathbf{U}$ 的第 $i$ 行。

更直观地写成列向量形式：

$\phi(x_i) = \begin{pmatrix} \sqrt{\lambda_1} u_{i1} \\ \sqrt{\lambda_2} u_{i2} \\ \vdots \\ \sqrt{\lambda_m} u_{im} \end{pmatrix}$

几何直觉：

$\mathbf{U}_{i,:}$ （第 $i$ 行）是 $x_i$ 在特征向量基下的旋转坐标
$\sqrt{\mathbf{\Lambda}}$ 对每个坐标轴进行拉伸（拉伸量 = $\sqrt{\lambda_k}$ ）
结果： $x_i$ 被映射到一个 $m$ 维空间，使得点之间的内积恰好等于原始核值

这正是**主成分分析（PCA）**的几何：特征值 = 方差，特征向量 = 主方向。

步骤 3：验证内积

$\begin{aligned} \langle \phi(x_i), \phi(x_j) \rangle &= \sum_{k=1}^m (\sqrt{\lambda_k} u_{ik})(\sqrt{\lambda_k} u_{jk}) \\ &= \sum_{k=1}^m \lambda_k u_{ik} u_{jk} \\ &= (\mathbf{U} \mathbf{\Lambda} \mathbf{U}^T)_{ij} \\ &= \mathbf{K}_{ij} = K(x_i, x_j) \end{aligned}$

证毕。

可视化建议：

Mercer 定理的核心可以用以下流程图表示：

核矩阵 K (m×m)
    ↓
特征分解 K = UΛU^T
    ↓
构造特征映射 φ(xᵢ) = √Λ Uᵢ,:^T
    ↓
验证内积 ⟨φ(xᵢ), φ(xⱼ)⟩ = Kᵢⱼ ✓

这个过程展示了如何从"观测到的相似度矩阵 $\mathbf{K}$ “逆向工程出"隐藏的特征空间坐标 $\phi(x)$ ”。

4.6 核函数的组合性质

定理：如果 $K_1, K_2$ 是核函数，则以下也是核函数：

线性组合： $\alpha K_1(x,z) + \beta K_2(x,z)$ ，其中 $\alpha, \beta \geq 0$
乘积： $K_1(x,z) \cdot K_2(x,z)$
函数复合： $K(x,z) = f(x) K_1(x,z) f(z)$ ，其中 $f$ 是任意函数
指数： $K(x,z) = \exp(K_1(x,z))$ （如果 $K_1$ 有界）
多项式： $K(x,z) = p(K_1(x,z))$ ，其中 $p$ 是非负系数多项式

证明（乘积）：

设 $K_1(x,z) = \langle \phi_1(x), \phi_1(z) \rangle$ ， $K_2(x,z) = \langle \phi_2(x), \phi_2(z) \rangle$ 。

设 $\phi_1(x) \in \mathbb{R}^{d_1}$ ， $\phi_2(x) \in \mathbb{R}^{d_2}$ 。

定义 $\phi(x) = \phi_1(x) \otimes \phi_2(x)$ (张量积)，即：

$\phi(x) = \begin{pmatrix} \phi_1^{(1)}(x) \phi_2^{(1)}(x) \\ \phi_1^{(1)}(x) \phi_2^{(2)}(x) \\ \vdots \\ \phi_1^{(i)}(x) \phi_2^{(j)}(x) \\ \vdots \\ \phi_1^{(d_1)}(x) \phi_2^{(d_2)}(x) \end{pmatrix} \in \mathbb{R}^{d_1 \times d_2}$

则：

$\begin{aligned} \langle \phi(x), \phi(z) \rangle &= \sum_{i=1}^{d_1} \sum_{j=1}^{d_2} \phi_1^{(i)}(x) \phi_2^{(j)}(x) \phi_1^{(i)}(z) \phi_2^{(j)}(z) \\ &= \left(\sum_{i=1}^{d_1} \phi_1^{(i)}(x) \phi_1^{(i)}(z)\right) \left(\sum_{j=1}^{d_2} \phi_2^{(j)}(x) \phi_2^{(j)}(z)\right) \\ &= K_1(x,z) \cdot K_2(x,z) \end{aligned}$

证毕。

亚马逊云科技技术品牌专区

更多推荐

基于STM32的全屋环境智能监测与预警终端设计

亚马逊云科技技术品牌专区

Keras：面向人类的深度学习库

Keras3支持多后端（TensorFlow、PyTorch、JAX），通过设置环境变量切换，兼容指定版本。pip安装后可用Sequential API快速构建CNN模型，如MNIST分类示例，实

亚马逊云科技技术品牌专区

AI行业日报｜2026-09-25：5个热点事件

本期行业动态聚焦于端侧算力重构、自主智能体工作流、开发工具经济模型、网络隔离架构设计与公共部门合规审查。以下结合一线技术场景进行结构化梳理，供 AI 研究员与软件工程团队参考。 PrismML 正将其轻量级语言模型适配至搭载高通处理器的智能眼镜终端 1 。该平台的核心战略指向开源权重模型的本地化运行，旨在最大化挖掘穿戴设备现有算力的利用效率 1 。对于嵌入式与边缘计算开发者而言，此类微型模型向低功