📑 本页目录（点开跳转）
09 · PAC 学习：要多少数据才够
⏱ 30 分钟 ｜ ⭐⭐ 唯一能回答"要多少数据"的理论
🎯 一句话
PAC = Probably Approximately Correct（大概率地、近似正确）。 它承认两件事：你不可能保证完全正确，也不可能保证每次都成功—— 但你可以保证：大概率地（1−δ），错误率不超过 ε。
🧠 一、为什么必须是"大概率"和"近似"
Q：为什么不能保证"一定正确"？
A：你的训练集是【随机抽】的。
万一手气极差，抽到一堆不具代表性的样本，谁也救不了你
→ 所以只能说"大概率"（概率 ≥ 1−δ）
Q：为什么不能保证"完全正确"？
A：有限数据永远无法完全确定一个函数
（总有些区域你一个样本都没见过）
→ 所以只能说"近似"（误差 ≤ ε）
💡 这两个让步不是学术保守，是数学上的必然。 承认它们之后，才能得到真正有用的结论——这是理论成熟的标志。
📐 二、PAC 的正式定义
对一个学习算法，如果它能：
$$P\Big(\underbrace{\text{err}_{\mathcal{D}}(h)}_{\text{真实误差}} \le \varepsilon\Big) \ge 1-\delta$$
且所需样本数和运行时间是 $\frac{1}{\varepsilon}, \frac{1}{\delta}$ 的多项式，就说这个问题是 PAC 可学习的。
| 符号 | 含义 | 记法 | 典型取值 |
|---|---|---|---|
| ε | 允许的误差上限 | Approximately correct | 0.01 ~ 0.1 |
| δ | 允许的失败概率 | Probably | 0.01 ~ 0.05 |
| $\text{err}_\mathcal{D}$ | 在真实分布上的误差 ⭐ | — |
⚠️ 最容易搞混的一点：
err_D是在整个真实分布上的误差，不是训练集上的。PAC 理论的全部意义就是：从你能测量的（训练误差）推出你真正关心的（泛化误差）。
🔢 三、⭐ 核心结论：样本复杂度界
对有限假设空间 $\mathcal{H}$，且存在一个完美假设（可实现情况）：
$$m \ge \frac{1}{\varepsilon}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right)$$
💡 人话翻译：
需要的样本数 ∝ (假设空间的对数) 除以 (要求的精度)。
三个直觉，每个都很有用：
| 因素 | 关系 | 直觉 |
|---|---|---|
| 假设空间 |H| 越大 | 对数 ⭐ | 候选模型越多，越容易碰巧蒙对一个，需要更多数据排除 |
| ε 越小（要求越准） | 反比 | 精度要求翻倍，数据量翻倍 |
| δ 越小（要求越可靠） | 对数 ⭐ | 想更保险，代价很便宜 |
🔑 最实用的一条洞察
|H| 大 1000 倍 → ln(1000) ≈ 6.9 → 只需多【7 倍左右】数据
δ 从 0.1 → 0.001 → ln 从 2.3 到 6.9 → 只需多【3 倍】数据
但 ε 从 0.1 → 0.01 → 1/ε 从 10 到 100 → 数据要多【10 倍】💰
⭐ 精度是最贵的东西。
实践含义：
❌ 「我要把准确率从 95% 提到 99%」
→ 别只想着换模型，先看看数据量够不够
→ 误差从 5% 降到 1%，数据量大致要 5 倍
✅ 「我要把置信度从 90% 提到 99%」
→ 这个便宜，多一点数据就行
📐 这个界怎么来的（想看再点，只用了两个工具）
第一步：一个"坏假设"（真实误差 > ε）在一个随机样本上碰巧正确的概率 ≤ 1−ε。
第二步：在 m 个独立样本上全部正确的概率 ≤ $(1-\varepsilon)^m \le e^{-\varepsilon m}$ （用了 $1-x \le e^{-x}$）。
第三步：用联合界（union bound）——「至少有一个坏假设通过了全部 m 个样本」的概率：
$$\le |\mathcal{H}|\cdot e^{-\varepsilon m}$$
第四步：要让这个概率 ≤ δ：
$$|\mathcal{H}|e^{-\varepsilon m} \le \delta \;\Longrightarrow\; m \ge \frac{1}{\varepsilon}\left(\ln|\mathcal{H}| + \ln\frac{1}{\delta}\right)$$
💡 注意这个推导只用了两个工具：一个指数不等式 + 联合界。 整个统计学习理论的地基就这么简单。 而
ln|H|中的对数，正是从「联合界把 |H| 个概率加起来」来的。
🧮 四、算个具体的数
例 1：学习布尔合取式
任务：从 n 个布尔特征中学一个合取式（如 x₁ ∧ ¬x₃ ∧ x₇）
假设空间大小：每个特征三种状态（出现/取反/不出现）
→ |H| = 3ⁿ
→ ln|H| = n·ln3 ≈ 1.1n
要求 ε = 0.1（误差≤10%），δ = 0.05（95% 把握）：
n = 10 → m ≥ (1/0.1)(11 + 3) = 140 个样本
n = 100 → m ≥ (1/0.1)(110 + 3) = 1130 个样本
💡 特征数翻 10 倍，样本需求只翻约 8 倍（线性）——因为 ln|H| = n·ln3 是线性的。
这类问题是"好学"的。
例 2：一个对比（说明 |H| 的影响）
如果假设空间是【所有】布尔函数：|H| = 2^(2ⁿ)
→ ln|H| = 2ⁿ·ln2 → 【指数级】
n = 20 时，ln|H| ≈ 70 万
→ 需要 700 万个样本才能学 20 个布尔特征的任意函数 💀
⭐ 对比：合取式只要 226 个
→ 这就是【归纳偏置的价值】：
限制假设空间 = 大幅降低样本需求
🔗 这是第 11 章「没有免费的午餐」的定量版本： 偏置不是缺点，它是让学习在有限数据下变得可能的前提。
⚠️ 五、这个界的三个局限（必须知道）
| 局限 | 说明 |
|---|---|
| 极其宽松 ⭐ | 实践中实际需要的样本量往往比界小 10~100 倍。它是个「最坏情况」保证 |
| 只适用于有限 |H| | 线性模型的假设空间是无限的，ln|H| = ∞，这个界直接失效 → 需要 VC 维（第 10 章） |
| 假设可实现 | 要求存在完美假设。现实中往往不存在（数据有噪声） |
关于第三点：agnostic PAC
现实中通常没有完美假设。放宽后的版本：
$$\text{err}_{\mathcal{D}}(\hat h) \le \min_{h\in\mathcal{H}}\text{err}_{\mathcal{D}}(h) + \varepsilon$$
💡 人话：我不保证你误差小于 ε，只保证你比「假设空间里最好的那个」差不了 ε。
样本复杂度变成：
$$m \ge \frac{1}{2\varepsilon^2}\left(\ln|\mathcal{H}| + \ln\frac{2}{\delta}\right)$$
⚠️ 注意 ε 从一次方变成了平方——agnostic 情况下精度更贵（ε 减半，数据要 4 倍）。
那学它还有什么用？
① 【定性关系】是对的 ⭐
ε 反比（精度贵）、|H| 和 δ 对数（便宜）
→ 指导你判断"该加数据还是该降低精度要求"
② 它是 VC 维和现代泛化理论的【地基】
③ 它给出了"复杂度 ↔ 数据量"这个权衡的第一个严格表述
④ 它量化了【归纳偏置的价值】（例 2）
🔗 六、和你已学的联系
| 相关的地方 | PAC 的解释 |
|---|---|
| 模型越复杂越容易过拟合 | 复杂 = |H| 大 = 需要更多样本，数据不够就是过拟合 |
| 数据越多越不容易过拟合 | m 增大，界收紧 |
| 正则化能防过拟合 ⭐ | 正则化在缩小有效假设空间 |
| 简单模型在小数据上更好 | |H| 小，样本需求低 |
| CNN 在图像上比 MLP 好 | 归纳偏置缩小了假设空间（例 2 的定量版） |
| 基础教程第 5 章的学习曲线 | 曲线形状就是这个界的经验版本 |
🔑 一个很漂亮的重新理解： 正则化 = 缩小假设空间 = 降低样本复杂度需求。
结合第 2 章（正则化=先验）、 第 8 章（正则化=故意引入偏差换方差）和 第 10 章（正则化=复杂度罚款）， 你现在有四种理解正则化的方式，它们说的是同一件事。
🔗 这一章连到哪里
| 去哪 | 为什么 |
|---|---|
| ML基础 05 | 这一章的经验版：样本复杂度界解释的正是那边「验证集要留多大」 |
| Kaggle 22 | ⭐ shake-up 的数学原因：公榜样本太少，泛化界松到没有约束力 |
| 上线之后 12 | 同一件事的实验版 —— MDE 反算样本量，问的也是「要多少样本才敢下结论」 |
✅ 检查点
- PAC 里的 P 和 AC 分别指什么？为什么必须做这两个让步？
err_D是在什么上算的？PAC 理论的核心目的是什么？- 样本复杂度界里，ε、δ、|H| 各以什么关系影响样本量？
- 三者中哪个最"贵"？举一个实践场景说明。
- 这个界的推导只用了哪两个工具？
ln|H|里的对数从哪来？ - 「学任意布尔函数」和「学合取式」的样本需求差多少？说明了什么？
- agnostic PAC 和标准 PAC 的区别？它的 ε 关系有什么变化？
👀 答案
- P=Probably（大概率成功，≥1−δ）、AC=Approximately Correct（近似正确，误差≤ε）。因为训练集是随机抽的可能手气差（只能大概率），有限数据无法完全确定函数（只能近似）。
- 在整个真实分布上算的，不是训练集。核心目的：从你能测量的训练误差，推出你真正关心的泛化误差。
- m ≥ (1/ε)(ln|H| + ln(1/δ))。ε 是反比，|H| 和 δ 都是对数关系。
- ε（精度）最贵。场景：把准确率从 95% 提到 99%（误差 5%→1%），数据量大致要 5 倍；而把置信度从 90% 提到 99% 只需多几倍——很便宜。
- 指数不等式（1−x ≤ e^(−x)）+ 联合界（union bound）。对数来自联合界把 |H| 个概率加起来后取对数。
- 学任意布尔函数 |H|=2^(2ⁿ)，n=20 需要 700 万样本；学合取式只要 226 个。说明归纳偏置（限制假设空间）能大幅降低样本需求——偏置是让学习可能的前提。
- 标准 PAC 假设存在完美假设；agnostic 不假设，只保证「比假设空间里最好的差不了 ε」。ε 从一次方变成平方——agnostic 下精度更贵（ε 减半要 4 倍数据）。
🛑 可以停在这里
⚡ 走神救援
PAC = Probably Approximately Correct：大概率地（≥ 1−δ）、近似正确（误差 ≤ ε）——两个让步是数学必然（训练集随机抽可能手气极差；有限数据无法完全确定函数）。⚠️
err_D是真实分布上的误差，不是训练集上的；⭐PAC 的全部意义就是：从你能测量的训练误差，推出你真正关心的泛化误差。⭐⭐核心界（有限 |H|、存在完美假设）：m ≥ (1/ε)(ln|H| + ln(1/δ))，推导只用了指数不等式＋联合界两个工具（ln|H|的对数就来自联合界）。三个关系：|H| 是对数（大 1000 倍只需多约 7 倍数据）、δ 是对数（0.1→0.001 只多 3 倍，想更保险很便宜）、⭐ε 是反比——精度是最贵的东西（0.1→0.01 数据要多 10 倍）。所以准确率 95%→99%（误差 5%→1%）数据大致要 5 倍，别只想着换模型；而置信度 90%→99% 很便宜。算个数：合取式|H| = 3ⁿ，ε=0.1、δ=0.05 时 n=10 只要 140 个样本、n=100 要 1130 个；而学任意布尔函数|H| = 2^(2ⁿ)，n=20 时 → 要 700 万个样本，合取式只要 226 个 ⭐ 这就量化了归纳偏置的价值：限制假设空间＝大幅降低样本需求。⚠️三个局限：界极其宽松，实际需要的样本常比它小 10~100 倍（最坏情况保证，别拿它算具体样本量）；只对有限 |H| 成立（线性模型ln|H| = ∞→ 需要 VC 维）；要求存在完美假设，agnostic 版只保证"比假设空间里最好的差不了 ε"，且⚠️ε 从一次方变成平方——精度更贵，ε 减半要 4 倍数据。该带走的是定性关系，和⭐正则化＝缩小假设空间＝降低样本需求这个重新理解。
下一节 👉 10-VC维.md ⭐⭐