第 08 章 核方法 (Kernel Methods)

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

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

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

与前序章节的联系：

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

---

目录

5. RBF 核：通往无穷维
6. 应用：核化一切
   • 6.1 表示定理
   • 6.2 核化的一般步骤
   • 6.3 案例：核岭回归
   • 6.4 其他可核化算法
7. 总结与展望

5. RBF 核：通往无穷维

5.1 径向基函数核的定义

RBF 核 (Radial Basis Function Kernel) 或高斯核 (Gaussian Kernel)：

$$K(x,z)=\exp \left(-\gamma \Vert x-z{\Vert }^2\right)$$

其中 $\gamma >0$ 是带宽参数。

常见形式（$\gamma =\frac{1}{2{\sigma }^2}$）：

$$K(x,z)=\exp \left(-\frac{\Vert x-z{\Vert }^2}{2{\sigma }^2}\right)$$

性质：

1. 对称性：$K(x,z)=K(z,x)$
2. 有界性：$0<K(x,z)\le 1$
3. 归一化：$K(x,x)=1$
4. 径向性：只依赖于 $\Vert x-z\Vert$，与方向无关

5.2 RBF 核对应无穷维特征空间

核心问题：$K(x,z)=\exp (-\gamma \Vert x-z{\Vert }^2)$ 对应的 $\varphi (x)$ 是什么？

定理：RBF 核对应于无穷维希尔伯特空间的内积。

证明（一维情况）：

设 $x,z\in \mathbb{R}$，$\gamma =\frac{1}{2}$：

$$K(x,z)=\exp \left(-\frac{1}{2}(x-z{)}^2\right)$$

步骤 1：展开平方项

$$K(x,z)=\exp \left(-\frac{1}{2}(x^2-2xz+z^2)\right)$$

分离变量：

$$K(x,z)=\exp \left(-\frac{x^2}{2}\right)\exp (xz)\exp \left(-\frac{z^2}{2}\right)$$

步骤 2：泰勒展开 $\exp (xz)$

$$\exp (xz)=\sum _{k=0}^{\infty }\frac{(xz{)}^k}{k!}=\sum _{k=0}^{\infty }\frac{x^k{z}^k}{k!}$$

步骤 3：代入

$$\begin{array}{rl}K(x,z)& =\exp \left(-\frac{x^2}{2}\right)\exp \left(-\frac{z^2}{2}\right)\sum _{k=0}^{\infty }\frac{x^k{z}^k}{k!}\\ & =\sum _{k=0}^{\infty }\frac{1}{k!}\left[\exp \left(-\frac{x^2}{2}\right)x^k\right]\left[\exp \left(-\frac{z^2}{2}\right)z^k\right]\end{array}$$

步骤 4：识别特征映射结构

观察步骤 3 的结果，我们可以直接定义特征映射：

$${\psi }_k(x)=\frac{1}{\sqrt{k!}}\exp \left(-\frac{x^2}{2}\right)x^k$$

则核函数变为：

$$\begin{array}{rl}K(x,z)& =\sum _{k=0}^{\infty }\frac{1}{k!}\left[\exp \left(-\frac{x^2}{2}\right)x^k\right]\left[\exp \left(-\frac{z^2}{2}\right)z^k\right]\\ & =\sum _{k=0}^{\infty }\left[\frac{1}{\sqrt{k!}}\exp \left(-\frac{x^2}{2}\right)x^k\right]\left[\frac{1}{\sqrt{k!}}\exp \left(-\frac{z^2}{2}\right)z^k\right]\\ & =\sum _{k=0}^{\infty }{\psi }_k(x){\psi }_k(z)=⟨\psi (x),\psi (z)⟩\end{array}$$

关键：归一化系数 $\frac{1}{\sqrt{k!}}$ 的作用

为什么需要 $\sqrt{k!}$ 而不是 $k!$？

• 泰勒展开给出 $\frac{x^k{z}^k}{k!}$，如果直接分配，每边得到 $\frac{1}{\sqrt{k!}}$
• 这保证了级数的平方收敛性（每个分量的 $L^2$ 范数有限）
• 物理意义：$\sqrt{k!}$ 正是厄米多项式（Hermite polynomials）归一化的来源

$$\psi (x)=\left(\begin{array}{c}{\psi }_0(x)\\ {\psi }_1(x)\\ {\psi }_2(x)\\ ⋮\end{array}\right)=\left(\begin{array}{c}\exp (-x^2/2)\\ \frac{\exp (-x^2/2)x}{\sqrt{1!}}\\ \frac{\exp (-x^2/2)x^2}{\sqrt{2!}}\\ \frac{\exp (-x^2/2)x^3}{\sqrt{3!}}\\ ⋮\end{array}\right)$$

这是一个无穷维向量！

步骤 5：验证收敛性与范数

级数的平方收敛性（$L^2$ 范数有限）：

$$\begin{array}{rl}\Vert \psi (x){\Vert }^2& =\sum _{k=0}^{\infty }{\psi }_k(x{)}^2\\ & =\sum _{k=0}^{\infty }{\left[\frac{\exp (-x^2/2)\cdot x^k}{\sqrt{k!}}\right]}^2\\ & =\exp (-x^2)\sum _{k=0}^{\infty }\frac{x^{2k}}{k!}\\ & =\exp (-x^2)\cdot \exp (x^2)\text{(泰勒展开)}\\ & =1\end{array}$$

完美！ 特征映射 $\psi (x)$ 的范数恒为 1，这意味着：

• 无穷维级数收敛（良定义）
• 所有点都被映射到单位超球面上
• RBF 核的归一化性质 $K(x,x)=1$ 在特征空间中对应 $\Vert \psi (x){\Vert }^2=1$

推导完毕：我们成功地将 RBF 核表示为无穷维希尔伯特空间中的内积。

5.3 多维推广

对于 $x,z\in {\mathbb{R}}^n$：

$$K(x,z)=\exp \left(-\gamma \Vert x-z{\Vert }^2\right)=\exp \left(-\gamma \sum _{i=1}^n(x_i-z_i{)}^2\right)$$

利用指数的乘法性：

$$K(x,z)=\prod _{i=1}^n\exp \left(-\gamma (x_i-z_i{)}^2\right)=\prod _{i=1}^n{K}_i(x_i,z_i)$$

每个 $K_i$ 是一维 RBF 核，对应无穷维特征。

根据核的乘积性质（见 4.6 节），总的特征空间是这 $n$ 个无穷维空间的张量积：

$$\varphi (x)={\varphi }_1(x_1)\otimes {\varphi }_2(x_2)\otimes \cdots \otimes {\varphi }_n(x_n)$$

维度爆炸：$\infty \otimes \infty \otimes \cdots \otimes \infty =\infty$（但仍可通过核技巧高效计算）

总结：RBF 核的三层魔法

1. 泰勒展开：将指数函数展开为无穷级数 $\exp (xz)={\sum }_{k=0}^{\infty }\frac{(xz{)}^k}{k!}$
2. 分离变量：将交叉项 $x^k{z}^k$ 分配给两个特征向量 ${\psi }_k(x)$ 和 ${\psi }_k(z)$
3. 归一化：用 $\sqrt{k!}$ 保证级数收敛（单位范数）

最终效果：用 $O(n)$ 的计算（计算 $\Vert x-z{\Vert }^2$ 和一次指数运算）实现无穷维空间的内积。

5.4 RBF 核的威力与风险

为什么 RBF 核这么强大？

1. 无穷维表达能力：可以拟合任意复杂的决策边界
2. 计算高效：$K(x,z)$ 只需 $O(n)$ 时间（计算 $\Vert x-z{\Vert }^2$）
3. 参数简单：只有一个参数 $\gamma$（或 $\sigma$）
4. 万能逼近：在适当条件下可以逼近任意连续函数

参数 $\gamma$ 的影响：

• $\gamma$ 很大（$\sigma$ 很小）：

  • 核函数"尖锐"，只有非常接近的点才有非零值
  • 决策边界非常复杂，每个训练点都是一个"孤岛"
  • 过拟合风险高

• $\gamma$ 很小（$\sigma$ 很大）：

  • 核函数"平坦"，所有点的相似度都接近 1
  • 决策边界趋于线性
  • 欠拟合风险高

实践建议：

• 初始值：$\gamma =\frac{1}{n\cdot \text{Var}(X)}$
• 范围：$\gamma \in [10^{-4},10^1]$（对数尺度搜索）
• 使用交叉验证选择

5.5 常见核函数总结

核函数	公式	特征空间维度	适用场景
线性核	$K(x,z)=x^{T}z$	$n$	线性可分问题
多项式核	$K(x,z)=(x^{T}z+c{)}^d$	$\left(\genfrac{}{}{0ex}{}{n+d}{d}\right)$	多项式模式
RBF 核	$K(x,z)=\exp (-\gamma |x-z{|}^2)$	$\infty$	通用，默认首选
Sigmoid 核	$K(x,z)=\tanh (\alpha x^{T}z+c)$	-	模拟神经网络
拉普拉斯核	$K(x,z)=\exp (-\gamma |x-z{|}_1)$	$\infty$	对异常值鲁棒

---

6. 应用：核化一切

6.1 表示定理 (Representer Theorem)

核心洞察：许多机器学习算法的最优解都可以表示为训练样本的线性组合。

表示定理：

考虑正则化经验风险最小化问题：

$$\underset{w\in \mathcal{H}}{\min }\left[\sum _{i=1}^{m}L(y_i,⟨w,\varphi (x_i)⟩)+\lambda \Omega (\Vert w\Vert )\right]$$

其中：

• $L$ 是损失函数
• $\Omega$ 是单调递增的正则化项
• $\lambda >0$ 是正则化参数
• $\mathcal{H}$ 是希尔伯特空间

定理：最优解 $w^{\ast }$ 必然在训练样本张成的子空间中，即：

$$w^{\ast }=\sum _{i=1}^m{\alpha }_i\varphi (x_i)$$

证明：

步骤 1：将 $w$ 分解

将 $w$ 分解为两部分：

$$w=w_{\parallel }+w_{\perp }$$

其中：

• w ∥ ∈ span { ϕ ( x 1 ) , … , ϕ ( x m ) } w_\parallel \in \text{span}\{\phi(x_1), \ldots, \phi(x_m)\} w∥​∈span{ϕ(x1​),…,ϕ(xm​)}（数据子空间）
• w ⊥ ⊥ span { ϕ ( x 1 ) , … , ϕ ( x m ) } w_\perp \perp \text{span}\{\phi(x_1), \ldots, \phi(x_m)\} w⊥​⊥span{ϕ(x1​),…,ϕ(xm​)}（正交补空间）

步骤 2：分析损失项

对于任意 $i$：

$$⟨w,\varphi (x_i)⟩=⟨w_{\parallel }+w_{\perp },\varphi (x_i)⟩=⟨w_{\parallel },\varphi (x_i)⟩+\underset{=0}{\underbrace{⟨w_{\perp },\varphi (x_i)⟩}}$$

因为 $w_{\perp }$ 垂直于 $\varphi (x_i)$。

所以：

$$\sum _{i=1}^{m}L(y_i,⟨w,\varphi (x_i)⟩)=\sum _{i=1}^{m}L(y_i,⟨w_{\parallel },\varphi (x_i)⟩)$$

步骤 3：分析正则化项

$$\Vert w{\Vert }^2=\Vert w_{\parallel }{\Vert }^2+\Vert w_{\perp }{\Vert }^2\ge \Vert w_{\parallel }{\Vert }^2$$

因此：

$$\Omega (\Vert w\Vert )\ge \Omega (\Vert w_{\parallel }\Vert )$$

（因为 $\Omega$ 单调递增）

步骤 4：结论

目标函数：

$$\sum _{i=1}^{m}L(y_i,⟨w,\varphi (x_i)⟩)+\lambda \Omega (\Vert w\Vert )=\sum _{i=1}^{m}L(y_i,⟨w_{\parallel },\varphi (x_i)⟩)+\lambda \Omega (\Vert w\Vert )\ge \sum _{i=1}^{m}L(y_i,⟨w_{\parallel },\varphi (x_i)⟩)+\lambda \Omega (\Vert w_{\parallel }\Vert )$$

取 $w_{\perp }=0$（即 $w=w_{\parallel }$）时，目标函数更小。

因此最优解必然在 span { ϕ ( x 1 ) , … , ϕ ( x m ) } \text{span}\{\phi(x_1), \ldots, \phi(x_m)\} span{ϕ(x1​),…,ϕ(xm​)} 中：

$$w^{\ast }=\sum _{i=1}^m{\alpha }_i\varphi (x_i)$$

证毕。

6.2 核化的一般步骤

任何算法的核化遵循以下步骤：

1. 应用表示定理：证明 $w^{\ast }={\sum }_{i=1}^m{\alpha }_i\varphi (x_i)$
2. 代入目标函数：将 $w$ 用 $\alpha$ 表示
3. 引入核矩阵：将所有 $⟨\varphi (x_i),\varphi (x_j)⟩$ 替换为 $K(x_i,x_j)$
4. 求解对偶问题：优化关于 $\alpha$ 的问题
5. 预测：$f(x)={\sum }_{i=1}^m{\alpha }_{i}K(x_i,x)$

6.3 案例：核岭回归 (Kernel Ridge Regression)

6.3.1 原始岭回归

给定数据 $\{(x_i,y_i){\}}_{i=1}^m$，岭回归求解：

$$\underset{w}{\min }\sum _{i=1}^m(y_i-w^T{x}_i{)}^2+\lambda \Vert w{\Vert }^2$$

解析解（第 5 章）：

$$w^{\ast }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$$

其中 $X=[x_1,\dots ,x_m{]}^T\in {\mathbb{R}}^{m\times n}$。

问题：

• 需要计算 $n\times n$ 矩阵的逆（$n$ 是特征维度）
• 如果 $n$ 很大（或无穷大），无法计算

6.3.2 核化推导

假设数据映射到特征空间 $\varphi (x)$，优化问题变为：

$$\underset{w}{\min }\sum _{i=1}^m(y_i-⟨w,\varphi (x_i)⟩{)}^2+\lambda \Vert w{\Vert }^2$$

记 $\Phi =[\varphi (x_1),\dots ,\varphi (x_m){]}^T\in {\mathbb{R}}^{m\times D}$（$D$ 可能是 $\infty$）。

步骤 1：应用表示定理

$$w={\Phi }^T\alpha =\sum _{i=1}^m{\alpha }_i\varphi (x_i)$$

步骤 2：代入目标函数

$$\begin{array}{rl}⟨w,\varphi (x_i)⟩& =⟨\sum _{j=1}^m{\alpha }_j\varphi (x_j),\varphi (x_i)⟩=\sum _{j=1}^m{\alpha }_j⟨\varphi (x_j),\varphi (x_i)⟩\\ & =\sum _{j=1}^m{\alpha }_{j}K(x_j,x_i)=(\mathbf{K}\alpha {)}_i\end{array}$$

其中 ${\mathbf{K}}_{ij}=K(x_i,x_j)$。

正则化项：

$$\Vert w{\Vert }^2=⟨{\Phi }^T\alpha ,{\Phi }^T\alpha ⟩={\alpha }^T\Phi {\Phi }^T\alpha ={\alpha }^T\mathbf{K}\alpha$$

步骤 3：核化的目标函数

$$\underset{\alpha }{\min }\Vert y-\mathbf{K}\alpha {\Vert }^2+\lambda {\alpha }^T\mathbf{K}\alpha$$

步骤 4：求导

$$\frac{\partial }{\partial \alpha }\left[(y-\mathbf{K}\alpha {)}^T(y-\mathbf{K}\alpha )+\lambda {\alpha }^T\mathbf{K}\alpha \right]=0$$

展开：

$$-2{\mathbf{K}}^T(y-\mathbf{K}\alpha )+2\lambda \mathbf{K}\alpha =0$$

因为 $\mathbf{K}$ 对称（${\mathbf{K}}^T=\mathbf{K}$）：

$$\mathbf{K}(y-\mathbf{K}\alpha )+\lambda \mathbf{K}\alpha =0$$

$$\mathbf{K}y={\mathbf{K}}^2\alpha +\lambda \mathbf{K}\alpha =\mathbf{K}(\mathbf{K}+\lambda I)\alpha$$

假设 $\mathbf{K}$ 可逆（或使用伪逆）：

$$y=(\mathbf{K}+\lambda I)\alpha$$

解得：

$$\boxed{{\alpha }^{\ast }=(\mathbf{K}+\lambda I{)}^{-1}y}$$

6.3.3 预测

对于新样本 $x_{\text{new}}$：

$$\begin{array}{rl}{\hat{y}}_{\text{new}}& =⟨w^{\ast },\varphi (x_{\text{new}})⟩\\ & =\sum _{i=1}^m{\alpha }_i^{\ast }⟨\varphi (x_i),\varphi (x_{\text{new}})⟩\\ & =\sum _{i=1}^m{\alpha }_i^{\ast }K(x_i,x_{\text{new}})\end{array}$$

定义 $k_{\text{new}}=[K(x_1,x_{\text{new}}),\dots ,K(x_m,x_{\text{new}}){]}^T$：

$$\boxed{{\hat{y}}_{\text{new}}=k_{\text{new}}^T{\alpha }^{\ast }=k_{\text{new}}^T(\mathbf{K}+\lambda I{)}^{-1}y}$$

6.3.4 算法总结

核岭回归算法：

输入：

• 训练集 $\{(x_i,y_i){\}}_{i=1}^m$
• 核函数 $K(\cdot ,\cdot )$
• 正则化参数 $\lambda$

训练：

1. 计算核矩阵 $\mathbf{K}\in {\mathbb{R}}^{m\times m}$：${\mathbf{K}}_{ij}=K(x_i,x_j)$
2. 求解：$\alpha =(\mathbf{K}+\lambda I{)}^{-1}y$

预测 $x_{\text{new}}$：

1. 计算核向量 $k_{\text{new}}$：$k_{\text{new},i}=K(x_i,x_{\text{new}})$
2. 预测：${\hat{y}}_{\text{new}}=k_{\text{new}}^T\alpha$

复杂度分析：

操作	原始形式	对偶形式（核化）
训练	$O(n^{2}m+n^3)$	$O(m^{2}n+m^3)$
预测	$O(n)$	$O(mn)$
特征维度限制	必须有限	可以无穷

何时使用核化：

• 当 $m\ll n$（样本少、特征多）
• 当 $n=\infty$（RBF 核等无穷维特征）
• 当数据非线性可分

6.3.5 线性岭回归 vs 核岭回归：完整对比

以下表格展示了第 5 章的线性岭回归与核岭回归的对偶呼应：

维度	线性岭回归（第 5 章）	核岭回归（本章）
优化问题	${\min }_w|y-Xw{|}^2+\lambda |w{|}^2$	${\min }_w|y-\Phi w{|}^2+\lambda |w{|}^2$
特征空间	原始空间 ${\mathbb{R}}^n$	隐式高维空间 $\mathcal{H}$ (可能 $\infty$ 维)
参数形式	直接求 $w\in {\mathbb{R}}^n$	表示为 $w={\sum }_{i=1}^m{\alpha }_i\varphi (x_i)$
解析解	$w^{\ast }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$	${\alpha }^{\ast }=(\mathbf{K}+\lambda I{)}^{-1}y$
矩阵维度	$(X^{T}X)$: $n\times n$	$\mathbf{K}$: $m\times m$
求逆复杂度	$O(n^3)$	$O(m^3)$
预测公式	$\hat{y}=w^{T}x$	$\hat{y}={\sum }_{i=1}^m{\alpha }_{i}K(x_i,x)$
预测复杂度	$O(n)$	$O(mn)$
适用场景	$n\ll m$（特征少、样本多）	$m\ll n$ 或 $n=\infty$
模型能力	线性决策边界	非线性决策边界
可解释性	高（可查看 $w$ 的每个系数）	低（$w$ 在隐式空间）
数学本质	在原始空间正则化	在特征空间正则化 + 核技巧

核心洞察：

1. 互补性：$n$ 和 $m$ 的角色互换

   • 线性：复杂度取决于特征数 $n$
   • 核化：复杂度取决于样本数 $m$

2. 统一性：当使用线性核 $K(x,z)=x^{T}z$ 时，核岭回归退化为线性岭回归（见下方推导）

3. 表达力权衡：

   • 线性岭回归：快速、可解释，但表达力受限
   • 核岭回归：强大、灵活，但计算成本更高

特殊情况：线性核的统一

当 $K(x,z)=x^{T}z$（线性核）时：

$$\begin{array}{rl}\mathbf{K}& =X{X}^T\in {\mathbb{R}}^{m\times m}\\ {\alpha }^{\ast }& =(X{X}^T+\lambda I{)}^{-1}y\\ w^{\ast }& =X^T{\alpha }^{\ast }=X^T(X{X}^T+\lambda I{)}^{-1}y\end{array}$$

根据 Woodbury 矩阵恒等式：

$$X^T(X{X}^T+\lambda I{)}^{-1}=(X^{T}X+\lambda I{)}^{-1}{X}^T$$

因此：

$$w^{\ast }=(X^{T}X+\lambda I{)}^{-1}{X}^{T}y$$

这正是线性岭回归的解！两者在线性核下完全等价。

6.3.6 Python 实现示例

import numpy as np

class KernelRidgeRegression:
    def __init__(self, kernel='rbf', gamma=1.0, lambda_=1.0):
        self.kernel = kernel
        self.gamma = gamma
        self.lambda_ = lambda_

    def _kernel_function(self, X1, X2):
        """计算核矩阵"""
        if self.kernel == 'rbf':
            # RBF 核: exp(-gamma * ||x - z||^2)
            # ||x - z||^2 = ||x||^2 + ||z||^2 - 2 x^T z
            X1_norm = np.sum(X1**2, axis=1).reshape(-1, 1)
            X2_norm = np.sum(X2**2, axis=1).reshape(1, -1)
            K = np.exp(-self.gamma * (X1_norm + X2_norm - 2 * X1 @ X2.T))
        elif self.kernel == 'linear':
            K = X1 @ X2.T
        elif self.kernel == 'poly':
            # 多项式核: (x^T z + 1)^d
            K = (X1 @ X2.T + 1) ** self.gamma
        return K

    def fit(self, X, y):
        """训练"""
        self.X_train = X
        self.y_train = y

        # 计算核矩阵
        K = self._kernel_function(X, X)

        # 求解 alpha = (K + lambda I)^{-1} y
        m = len(y)
        self.alpha = np.linalg.solve(K + self.lambda_ * np.eye(m), y)

        return self

    def predict(self, X):
        """预测"""
        # 计算核向量 k(x)
        K_new = self._kernel_function(X, self.X_train)

        # 预测 y = k(x)^T alpha
        return K_new @ self.alpha

# 使用示例
X_train = np.random.randn(100, 5)
y_train = np.sin(X_train[:, 0]) + 0.1 * np.random.randn(100)

model = KernelRidgeRegression(kernel='rbf', gamma=0.5, lambda_=0.1)
model.fit(X_train, y_train)

X_test = np.random.randn(20, 5)
y_pred = model.predict(X_test)

6.4 其他可核化算法

算法	核化版本	应用
线性回归	核回归	非线性回归
岭回归	核岭回归	高维非线性回归
逻辑回归	核逻辑回归	非线性分类
PCA	核 PCA (KPCA)	非线性降维
LDA	核 LDA	非线性判别分析
感知机	核感知机	在线学习
K-means	核 K-means	非线性聚类

核心思想一致：表示定理 + 核技巧 + 对偶优化。

---

7. 总结与展望

7.1 核方法的本质

核方法是一种**“计算的艺术”**：

1. 升维的智慧：将非线性问题转化为高维空间的线性问题
2. 计算的技巧：通过核技巧避免显式计算高维特征
3. 数学的优雅：Mercer 定理保证了核函数的合法性

核心等式：

$$\boxed{K(x,z)=⟨\varphi (x),\varphi (z)⟩}$$

左边是 $O(n)$ 的计算，右边可能是 $O(\infty )$ 的内积。

7.2 三大支柱定理

核方法的数学基础由三大定理构成，它们共同回答了"为什么核技巧可行"：

1. Cover 定理：高维空间更可能线性可分

   • 回答：为什么要升维？
   • 本质：维度的诅咒反转为祝福

2. Mercer 定理：核函数 $\iff$ 半正定核矩阵 $\iff$ 存在特征映射 $\varphi$

   • 回答：什么样的函数可以当核？
   • 本质：特征分解逆向构造隐藏空间

3. 表示定理：最优解在数据子空间中，即 $w^{\ast }={\sum }_i{\alpha }_i\varphi (x_i)$

   • 回答：为什么只需要核矩阵就够了？
   • 本质：正则化保证解的有限性

三者协同：Cover 定理驱动升维，Mercer 定理保证合法性，表示定理实现核技巧。

7.3 核方法的优势

1. 处理非线性：无需手工设计特征
2. 计算高效：避免维度爆炸
3. 理论坚实：有完整的数学基础
4. 应用广泛：可核化几乎所有线性算法

7.4 核方法的局限

1. 核矩阵存储：$O(m^2)$ 空间（大数据困难）
2. 核矩阵求逆：$O(m^3)$ 时间复杂度
3. 核函数选择：需要领域知识或交叉验证
4. 可解释性差：无穷维特征难以可视化

7.5 实践建议

核函数选择指南：

情况	推荐核	原因
数据线性可分	线性核	最简单，不易过拟合
特征有明确意义	多项式核	可解释性好
不清楚数据结构	RBF 核	通用，几乎总是好的起点
文本、序列数据	字符串核	专门设计

参数调优：

• RBF 核：$\gamma \in [10^{-4},10^1]$（对数尺度）
• 正则化：$\lambda \in [10^{-5},10^2]$
• 使用交叉验证

7.6 现代发展

大规模核方法：

• 随机特征 (Random Features)：用随机投影近似核函数
• Nyström 方法：用子采样近似核矩阵
• FastFood：快速近似 RBF 核

深度学习时代的核方法：

• 神经切线核 (Neural Tangent Kernel)：无限宽神经网络等价于核方法
• 深度核学习：用神经网络学习核函数
• 核与注意力机制：Transformer 可以看作核方法的变体

7.7 与其他方法的关系

核方法 vs 神经网络：

方面	核方法	神经网络
非线性建模	隐式（核技巧）	显式（层级组合）
训练	凸优化	非凸优化
可扩展性	受限于 $O(m^2)$	可处理大数据
可解释性	差	更差（但有进步）
特征工程	核函数选择	自动学习

7.8 最后的思考

核方法的哲学：

“当问题在低维空间难以解决时，升维；
当计算在高维空间难以承受时，核化。”

这不仅仅是一个技巧，而是一种思维方式：

• 通过改变问题的表示空间来简化问题
• 通过数学变换来降低计算复杂度
• 在表达能力和计算效率之间找到平衡

核方法提醒我们：机器学习的核心不是暴力计算，而是巧妙的数学洞察。

---

思考题：

1. 为什么 $K(x,z)=-\Vert x-z{\Vert }^2$ 不是合法核函数？

2. 证明：如果 $K_1,K_2$ 是核，则 $K(x,z)=K_1(x,z)+K_2(x,z)$ 也是核。

3. RBF 核的 $\gamma \to 0$ 和 $\gamma \to \infty$ 分别对应什么情况？

4. 设计一个"字符串核"：给定两个字符串，如何度量它们的相似度？

5. 为什么说神经网络可以看作"可学习的核方法"？

---

延伸阅读：

📚 经典教材

1. Schölkopf & Smola (2002). Learning with Kernels
   • 推荐理由：核方法领域的"圣经"。由 SVM 的核心贡献者撰写，全面覆盖了支持向量机、正则化、优化理论等。适合想要深入这一领域的读者。
2. Shawe-Taylor & Cristianini (2004). Kernel Methods for Pattern Analysis
   • 推荐理由：侧重于算法分析和模式识别应用，特别是对核矩阵的性质（如特征值分布）有深入讨论。

🚀 现代突破

3. Rahimi & Recht (2007). Random Features for Large-Scale Kernel Machines
   • 核心贡献：提出了"随机傅里叶特征" (Random Fourier Features)，证明了用随机投影可以逼近 RBF 核。这打破了核方法无法处理大数据的瓶颈，也是现代"大模型"思想的先驱之一。
   • 论文链接

🧠 深度学习连接

4. Jacot et al. (2018). Neural Tangent Kernel: Convergence and Generalization in Neural Networks
   • 核心贡献：证明了无限宽的深度神经网络在训练过程中演化为一个线性核模型（NTK）。这篇论文是连接深度学习与核方法理论的最重要桥梁。
   • 论文链接