机器学习数学推导（一）：绪论与数学基础

本章要做的事

2005 年，Google Research 在公开机器翻译评测中表明：一个仅靠双语语料训练的统计模型，可以击败语言学家精雕细琢数十年的规则系统。结论令人不安，却也极具数学美感——一个从未被告知语法的系统，只要数据足够多，就能把语法 “推” 出来。为什么？

这并不是工程上的某种巧合，而是一个定理。本章要做的事，就是从第一性原理出发，搭建那一部分使学习成为可能的数学：什么时候能学、需要多少数据、根本的极限在哪里。

读完之后，你应当能够：

1. 把一个学习问题形式化成"在假设类上做的概率优化"。
2. 对有限假设类，叙述并证明 PAC 可学习的样本复杂度。
3. 用 VC 维把同样的论证推广到无限假设类（线性分类器、神经网络）。
4. 把任意预测器的测试误差分解成偏差、方差、不可约噪声三部分。
5. 通过 No Free Lunch 定理理解：任何成功的算法，都必然带着某种归纳偏置（inductive bias）。

前置知识：微积分（导数、积分、Taylor 展开）、初等概率（期望、方差、Bayes 公式、独立性）、以及阅读数学符号的耐心。不需要任何先修的"学习理论"。

1. 学习问题的轮廓

1.1 三大类问题

正式定义之前，先把"舞台"画出来。本系列遇到的所有问题，几乎都属于以下三类之一。

• 监督学习：给定形如 $(x, y)$ 的样本对，目标是从 $x$ 预测 $y$。分类（$y$ 离散）和回归（$y$ 连续）是两个标准实例。
• 无监督学习：只给输入 $x$，要求恢复结构——聚类、低维流形、密度估计——而无需任何外部标签。
• 强化学习：智能体在环境中主动选择动作，并观察标量奖励。数据由智能体自身的策略生成，因此统计分析比监督设定更微妙。

本章把理论建立在监督设定之上——奠基性结果（PAC、VC、偏差-方差）在那里最干净。同样的工具，经过些许调整后可以推广到另外两类。

1.2 数学形式化

设存在一个未知的联合分布 $\mathcal{D}$，定义在输入空间 $\mathcal{X}$ 与输出空间 $\mathcal{Y}$ 的乘积上。一个学习算法是这样一个过程：吃下从 $\mathcal{D}$ 中独立同分布抽取的有限样本 $S = \{(x_i, y_i)\}_{i=1}^m$，吐出一个假设 $h: \mathcal{X} \to \mathcal{Y}$。$h$ 的好坏由损失函数衡量。

定义 1（损失函数）。任意可测映射 $\ell: \mathcal{Y} \times \mathcal{Y} \to \mathbb{R}_{\geq 0}$，把预测 $h(x)$ 与真值 $y$ 映射成非负惩罚 $\ell(h(x), y)$。

这是我们真正在意的量：模型在与训练数据同分布的全新样本上的平均损失。

这是我们唯一能算出来的量。

统计学习的核心矛盾：我们优化的是 $L_S$，被打分的却是 $L_{\mathcal{D}}$。本章后面几乎所有定理，都是在刻画 $L_S(h)$ 与 $L_{\mathcal{D}}(h)$ 之间何时、以什么速率彼此接近。

1.3 监督学习的三要素

任何监督算法都由一个三元组 $(\mathcal{H}, \ell, \mathcal{A})$ 决定：

• 假设类 $\mathcal{H}$：算法被允许输出的函数集合。$\mathcal{H}$ 越大，表达力越强，但统计上越难驾驭。
• 损失 $\ell$：把"预测好坏"翻译成可优化的标量。
• 算法 $\mathcal{A}$：从样本到假设的映射，$\mathcal{A}: (\mathcal{X} \times \mathcal{Y})^m \to \mathcal{H}$。

贯穿全系列的两个范式：

• 经验风险最小化（ERM）：$\;h_{\text{ERM}} = \arg\min_{h\in\mathcal{H}} L_S(h)$。
• 结构风险最小化（SRM）：$\;h_{\text{SRM}} = \arg\min_{h\in\mathcal{H}} \bigl[L_S(h) + \Omega(h)\bigr]$，其中 $\Omega$ 惩罚复杂度。

ERM 是最自然的起点。SRM 才是实际工程里默认使用的方法——为什么需要 $\Omega$，等到偏差-方差分解之后就一目了然。

1.4 损失的选择：回归与分类的代理函数

损失的选择不只是"形式问题"。它会改变优化曲面、统计效率，乃至最优解的位置。

回归损失（残差 $r = y - h(x)$）：

二分类损失（$y \in \{-1, +1\}$，间隔 $m = y \cdot h(x)$）：

表中所有分类代理损失，都是 0-1 损失的凸上界且关于间隔单调不增。Bartlett、Jordan、McAuliffe（2006）证明：只要代理函数满足"分类一致性"，最小化它在数据无限时收敛到 Bayes 最优分类器。

1.5 为什么需要理论：泛化间隙

把一个 100 次多项式拟合到 10 个有噪声的点上，可以做到 $L_S = 0$，却在任何新的 $x$ 上预测得一塌糊涂。$L_{\mathcal{D}}(h) - L_S(h)$ 的大小被称作泛化间隙（generalization gap），它的行为正是接下来两节要量化的对象。

左图是健康的情况：随训练样本增多，间隙逐渐缩小——这正是 PAC 学习要量化的现象。右图是过拟合：训练继续推进，但测试误差反而变大——这正是正则化、提前停止、偏差-方差权衡的用武之地。

学习理论给我们的工具是：

• 预测间隙何时会小；
• 用复杂度度量（基数、VC 维、Rademacher 复杂度）量化间隙；
• 通过模型选择和正则化控制间隙。

2. PAC 框架

2.1 “可学习"应该是什么意思

要谈"可学习”，必须先做三处让步：

• 不能要求完美预测器，只能要求与最优相差不超过 $\varepsilon$。
• 不能要求确定成功，只能要求以至少 $1 - \delta$ 的概率成功（概率取自训练样本的随机性）。
• 误差是相对真实分布 $\mathcal{D}$ 衡量的，不是相对训练集衡量的。

把这三点合在一起，就是 Probably Approximately Correct——Valiant 在 1984 年给出的形式化。

函数 $m_{\mathcal{H}}(\varepsilon, \delta)$ 称为样本复杂度：在 $m_{\mathcal{H}}(\varepsilon, \delta)$ 个样本之内，我们就能以 $\geq 1 - \delta$ 的概率，得到一个泛化误差与 $\mathcal{H}$ 中最优解相差至多 $\varepsilon$ 的假设。

2.2 有限假设类、可实现情况

先看最简单的非平凡情形：$\mathcal{H}$ 有限，并且存在 $h^\star \in \mathcal{H}$ 满足 $L_{\mathcal{D}}(h^\star) = 0$（可实现假设）。损失取 0-1 损失。

则以至少 $1 - \delta$ 的概率，所有 $L_S(h) = 0$ 的 $h \in \mathcal{H}$ 都满足 $L_{\mathcal{D}}(h) \leq \varepsilon$。特别地，ERM 算法是 $\mathcal{H}$ 的 PAC 学习算法。

证明。令 $\mathcal{H}_{\text{bad}} = \{h \in \mathcal{H} : L_{\mathcal{D}}(h) > \varepsilon\}$ 为坏假设集合。我们要界定的"坏事件"——“ERM 输出了一个坏假设”——包含在事件"存在某个坏假设在训练集上经验误差为 0"之中。

当 $m$ 满足 (8) 时，坏事件概率不超过 $\delta$，其补正是定理结论。$\blacksquare$

逐项品读：

• $\ln |\mathcal{H}|$：假设类越大，需要的样本越多，但只是对数级。
• $\ln(1/\delta)$：把置信度提一个量级，只多付出 $\ln 10 \approx 2.3$ 个样本。
• $1/\varepsilon$：把精度提高一倍，样本翻一倍。线性于精度。

2.3 不可知（agnostic）情况

可实现假设过于理想。不可知 PAC 把它去掉：不再要求 $\mathcal{H}$ 中存在零误差假设，只要求与 $\mathcal{H}$ 中最优解 $h^\star$ 比拼。

足以保证以至少 $1 - \delta$ 的概率有 $L_{\mathcal{D}}(h_{\text{ERM}}) \leq \min_{h \in \mathcal{H}} L_{\mathcal{D}}(h) + \varepsilon$。

对 $\mathcal{H}$ 做联合界，再代入 $t = \varepsilon/2$，立即得到 (9)。

2.4 为什么是 $1/\varepsilon^2$，不是 $1/\varepsilon$？

从可实现到不可知，$\varepsilon$ 的指数从 1 跳到 2。代价从哪里来？

可实现情形我们只需剔除坏假设：单一反例就足以摧毁它，因此"无反例"事件的概率随 $\varepsilon m$ 指数衰减。

这是中心极限定理的指纹。把 $\varepsilon$ 改善 10 倍，要付 100 倍样本。两种状态的对比如下：

左图说明 $\ln|\mathcal{H}|$ 只是对数加性项：从 $|\mathcal{H}| = 10^3$ 跳到 $10^6$，所需样本不过翻一倍。右图说明放弃可实现假设的代价：在对数-对数坐标下，不可知曲线斜率为 $-2$，可实现曲线斜率为 $-1$。

3. VC 维：把复杂度度量推广到无限假设类

3.1 为何需要新度量

$\ln |\mathcal{H}|$ 在任何"实数取值"的模型上都崩塌：$\mathbb{R}^d$ 的线性分类器有不可数多个，$\ln|\mathcal{H}| = \infty$，定理 2 完全无效。我们需要一个有限的复杂度度量，仍能刻画统计容量。

正确的度量是组合而非势数的：它不数假设个数，而数一个类在固定样本集上能产生的不同标记数。

3.2 打散

直觉：打散等于"$\mathcal{H}$ 在这一组特定的点上能造出所有可能的二分图样"，其表达力达到上限。

3.3 定义

若该上确界为 $\infty$，记 $\mathrm{VCdim}(\mathcal{H}) = \infty$。

两条不对称的证法：

• 存在性下界：要证 $\mathrm{VCdim}(\mathcal{H}) \geq d$，找到一组大小为 $d$ 的可打散点集即可。
• 普适性上界：要证 $\mathrm{VCdim}(\mathcal{H}) < d+1$，必须说明任何大小为 $d+1$ 的点集都不能被打散。

3.4 例：$\mathbb{R}^d$ 上的线性分类器

定理 3。仿射线性分类器 $\mathcal{H} = \{x \mapsto \mathrm{sign}(w^\top x + b) : w \in \mathbb{R}^d, b \in \mathbb{R}\}$ 的 VC 维为 $d + 1$。

证明。

此时 $w^\top 0 + b = b = \tfrac12 y_0$ 与 $y_0$ 同号；对 $i \geq 1$，$w^\top e_i + b = y_i + \tfrac12 y_0$ 的符号由 $y_i$ 决定（$\tfrac12 y_0$ 项太小，无法翻转符号）。所有标记均可实现，$d+1$ 个点被打散。

因为 $i \in I^+$ 时两个因子都为正，$i \in I^-$ 时两个因子都为负（乘积仍为正）。“严格正项之和等于 0”——矛盾。$\blacksquare$

直觉与几何完全吻合：$\mathbb{R}^d$ 中的超平面有 $d+1$ 个自由参数，每个参数恰好"买得到"一个标记自由度。

左侧 8 个面板枚举了 2D 中三点的全部 $2^3 = 8$ 种标记，每种都能找到分离直线。右侧面板是经典的 XOR：4 个点呈对角分布时，没有一条直线能把 $+$ 与 $-$ 分开；进一步的计数论证可证 2D 中任何 4 点都不可被打散。所以 2D 线性分类器的 $\mathrm{VCdim} = 3$，与公式 $d + 1$ 吻合。

3.5 VC 维样本复杂度界

只要 $m > d$，原本的指数 $2^m$ 立刻塌缩成多项式 $m^d$。把这条多项式增长率代入一致收敛论证（详见概率论一章），即得 (15)。

应用：$\mathbb{R}^{100}$ 中的线性分类器有 $\mathrm{VCdim} = 101$。要在不可知设定下达到 $\varepsilon = 0.05$、$\delta = 0.05$，所需样本量约为 $m \approx 10^5$——完全可承受。反之，VC 维为 $\infty$ 的类（例如全部可测函数）不是 PAC 可学习的，无论数据多少。

4. 偏差-方差分解

4.1 设置

即使一个类是 PAC 可学习的，某个具体学到的预测器，其测试误差也可分解成几个来源迥异的成分。这一分解，是实际做模型选择时的指南针。

固定平方损失，假设：

• 真函数 $f^\star: \mathcal{X} \to \mathbb{R}$。
• 观测 $y = f^\star(x) + \varepsilon$，其中 $\mathbb{E}[\varepsilon] = 0$，$\mathrm{Var}(\varepsilon) = \sigma^2$。
• 学习算法在样本 $S$ 上输出预测器 $\hat{f}_S$。

在固定测试点 $x$，对样本 $S$ 与噪声 $\varepsilon$ 同时取期望。

4.2 证明

对 $S$ 与 $\varepsilon$ 取期望，三项交叉项全部为零：

• $\mathbb{E}_S[2AB] = 2B \cdot \mathbb{E}_S[\hat{f} - \bar{f}] = 2B \cdot 0 = 0$，因为 $\mathbb{E}_S[\hat{f}] = \bar{f}$。
• $\mathbb{E}_{S,\varepsilon}[2AC] = 2\,\mathbb{E}_S[A] \cdot \mathbb{E}_\varepsilon[C] = 0$，因为 $S \perp \varepsilon$ 且两期望均为 0。
• $\mathbb{E}_\varepsilon[2BC] = 2B \cdot \mathbb{E}_\varepsilon[C] = 0$，因为 $\mathbb{E}[\varepsilon] = 0$。

剩下 $\mathbb{E}_S[A^2] + B^2 + \mathbb{E}_\varepsilon[C^2]$，恰好是方差、偏差²、噪声。$\blacksquare$

4.3 三项的含义

随模型容量增长，三个力量的竞争如下：

总期望误差呈 U 型。最优点左侧偏差占主导，是欠拟合；右侧方差占主导，是过拟合。最低点正是你要找的工作点——找到它（一般靠交叉验证），就是模型选择这件事的全部。

4.4 一个数值小验证

设 $f^\star(x) = \sin(\pi x)$ 在 $[-1, 1]$ 上，$\sigma = 0.3$，$m = 20$，重复 100 次随机训练集：

3 次多项式胜出，因为它是唯一同时把偏差与方差都压住的模型。注意噪声项在每行都相同——按定义如此。

4.5 诊断欠/过拟合

5. No Free Lunch 定理

5.1 定理陈述

Wolpert（1996）与 Wolpert-Macready（1997）把工程师们隐约感觉到的事写成了精确的命题：没有放之四海皆准的最优算法。

证明的核心很短。对任何未见过的 $x \notin S$，从 $\mathcal{F}$ 中均匀抽取 $f$ 时，$f(x)$ 是无偏的公平硬币：一半 $f$ 给 $f(x) = 0$，一半给 $f(x) = 1$。任何预测策略，在这一半上对、那一半上错，平均下来一律是 $\tfrac12$。

5.2 归纳偏置

既然没有算法能在所有问题上取胜，那么所有成功的算法都必然带着对世界的假设。这种假设有个名字——归纳偏置（inductive bias）。

下图把三种归纳偏置作用在同一组训练数据上：

线性拟合欠拟合——偏置太强；随机 ReLU 特征过拟合——偏置太弱；4 次多项式恰好匹配真函数的结构。三者并无内在的对错，取决于你对 $f^\star$ 的信念。

5.3 NFL 为何不让学习理论失效

NFL 是对所有可能函数取平均。我们真正遇到的函数——物理定律、自然语言、自然图像——只活在"全部函数"的一个极薄、高度结构化的子流形上。在那个子流形上，某些归纳偏置以巨大优势碾压其他偏置。

实践中，NFL 对你的要求是四件事：

1. 别再寻找万能算法，它不存在。
2. 弄清你的问题到底有什么结构。
3. 选择与之匹配的归纳偏置。
4. 在你真正关心的问题类上评测，而非最坏情况上评测。

6. 代码：线性回归的实证 PAC 与偏差-方差

下面这段自包含的脚本，把本章的核心预测在一个简单的线性回归问题上跑一遍：(i) 在可实现状态下验证测试误差按 $1/m$ 衰减；(ii) 分别度量偏差²、方差、噪声，并验证它们之和等于总期望误差。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51

import numpy as np
from sklearn.linear_model import LinearRegression
from sklearn.metrics import mean_squared_error

rng = np.random.default_rng(42)

def true_function(x):
    """未知的真函数：y = 2x + 1。"""
    return 2 * x + 1

def generate_data(n_samples, noise_std=0.5):
    """抽取一个 i.i.d. 样本 (X, y)，加性 Gaussian 噪声。"""
    X = rng.uniform(0, 10, n_samples).reshape(-1, 1)
    noise = rng.normal(0, noise_std, n_samples)
    y = true_function(X.ravel()) + noise
    return X, y

# 固定测试集，只抽一次
n_test = 1000
X_test, y_test_noisy = generate_data(n_test)
y_test_true = true_function(X_test.ravel())

sample_sizes = [5, 10, 20, 50, 100, 200, 500, 1000]
n_experiments = 100

print(f"{'m':>6} | {'训练 MSE':>10} | {'测试 MSE':>10} | "
      f"{'偏差²':>8} | {'方差':>10} | {'B²+V+σ²':>14}")
print("-" * 78)

sigma_sq = 0.5 ** 2  # 已知噪声方差，用于自检

for m in sample_sizes:
    train_err, test_err = [], []
    predictions = np.zeros((n_experiments, n_test))

    for k in range(n_experiments):
        X_train, y_train = generate_data(m)
        model = LinearRegression().fit(X_train, y_train)
        train_err.append(mean_squared_error(
            y_train, model.predict(X_train)))
        predictions[k] = model.predict(X_test)
        test_err.append(mean_squared_error(
            y_test_noisy, predictions[k]))

    mean_pred = predictions.mean(axis=0)
    bias_sq = np.mean((mean_pred - y_test_true) ** 2)
    variance = np.mean(np.var(predictions, axis=0))

    print(f"{m:>6d} | {np.mean(train_err):>10.4f} | "
          f"{np.mean(test_err):>10.4f} | {bias_sq:>8.4f} | "
          f"{variance:>10.4f} | {bias_sq + variance + sigma_sq:>14.4f}")

应当观察到的现象：

• 测试误差大约按 $1/m$ 衰减——可实现 PAC 的预测；线性模型规范设定下平方损失等价于参数估计问题。
• 偏差² 几乎为 0——线性假设类包含了真函数。
• 方差按 $1/m$ 衰减——数据越多，斜率截距越稳定。
• 偏差² + 方差 + $\sigma^2$ 与测试 MSE 在 Monte-Carlo 误差范围内吻合——验证了定理 5。

7. Q&A

Q1. ERM 既然这么简单，为什么不直接用？

因为 $L_S$ 与 $L_{\mathcal{D}}$ 在足够大的 $\mathcal{H}$ 上可以任意背离。“查表"假设——$h(x_i) = y_i$ 对 $i \leq m$，其余为 0——满足 $L_S = 0$，但 $L_{\mathcal{D}}$ 接近随机。PAC 理论告诉我们在什么条件下 $|L_S - L_{\mathcal{D}}|$ 小；结构风险最小化告诉我们如何用这些条件自适应地选择 $\mathcal{H}$。

Q2. 不可数的假设类，为什么 VC 维可以是有限的？

VC 维不数假设——它数有限点集上的可区分行为数。所有 2D 线性分类器构成一个不可数集，但在固定测试点上输出符号相同的两个分类器，对我们而言无法区分；而在 $m$ 个点上的可区分行为数至多 $\binom{m}{0} + \binom{m}{1} + \binom{m}{2} \leq O(m^2)$。Sauer-Shelah 引理把这一组合事实，转换成一个有限的复杂度上界。

Q3. 训练误差为 0 永远是坏事吗？

不一定。正确的问题是：你的模型类是否大到能记忆噪声？如果数据基本无噪、且类中包含真函数（比如用线性模型拟合线性数据），$L_S = 0$ 是正确的结果。如果 $\sigma^2 > 0$ 且类大到能内插，$L_S = 0$ 就是一个红色警报。一个有用的拇指法则：当 $m / \mathrm{VCdim}(\mathcal{H}) < 10$ 时，对低训练误差保持怀疑。

Q4. 常见模型的 VC 维分别是多少？

对现代深度网络，VC 界很松——网络能完美拟合随机标签（说明 VC 巨大），却仍能泛化。解释这一点是当前研究热点（PAC-Bayes、间隔界、神经正切核分析、隐式正则化理论）。

Q5. Hoeffding 不等式从哪里来？

它是对有界独立随机变量之和的次高斯（sub-Gaussian）集中不等式。我们将在第 3 章从矩生成函数出发干净地推导它，并把它作为本系列后续几乎所有一致收敛论证的主力工具。

总结

任何新项目的实战清单：

1. 把训练误差与验证误差作为 $m$ 的函数画出来——你处在哪个状态？
2. 估计 $\mathrm{VCdim}(\mathcal{H})$ 或有效参数数；目标是 $m / \mathrm{VCdim} \gtrsim 10$。
3. 用交叉验证选复杂度，不要凭训练曲线眼测。
4. 默认就用 SRM（带正则化），不要把正则化当事后补丁。
5. 选择归纳偏置匹配问题结构的 $\mathcal{H}$：图像选局部性、基因组选稀疏性、物理选平滑性。

参考文献

1. Valiant, L. G. (1984). A theory of the learnable. Communications of the ACM, 27(11), 1134-1142.
2. Vapnik, V. N. & Chervonenkis, A. Y. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications, 16(2), 264-280.
3. Blumer, A., Ehrenfeucht, A., Haussler, D. & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. Journal of the ACM, 36(4), 929-965.
4. Bartlett, P. L., Jordan, M. I. & McAuliffe, J. D. (2006). Convexity, classification, and risk bounds. Journal of the American Statistical Association, 101(473), 138-156.
5. Bartlett, P. L., Harvey, N., Liaw, C. & Mehrabian, A. (2019). Nearly-tight VC-dimension bounds for piecewise linear neural networks. Journal of Machine Learning Research, 20, 1-17.
6. Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms. Neural Computation, 8(7), 1341-1390.
7. Wolpert, D. H. & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE Transactions on Evolutionary Computation, 1(1), 67-82.
8. Shalev-Shwartz, S. & Ben-David, S. (2014). Understanding Machine Learning: From Theory to Algorithms. Cambridge University Press.
9. Mohri, M., Rostamizadeh, A. & Talwalkar, A. (2018). Foundations of Machine Learning (2nd ed.). MIT Press.
10. Zhang, C., Bengio, S., Hardt, M., Recht, B. & Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. ICLR.
11. 周志华 (2016). 机器学习. 清华大学出版社.
12. 李航 (2012). 统计学习方法. 清华大学出版社.

系列导航