Probably Approximately Correct
Valiant 的问题（1984）
Leslie Valiant 提出了一个看似简单的问题：机器学习意味着什么？不是“能否记忆？”不是“能否完美预测？”而是：能否从有限样本中，以高概率、在多项式时间内近似地学好？
这一框架为他赢得了 2010 年图灵奖，并奠定了计算学习理论的基础。
两个旋钮
ε（epsilon）——误差容忍度。 近似正确意味着误差 ≤ ε。ε 越小，学习要求越严格。
δ（delta）——置信参数。 概率正确意味着成功概率 ≥ 1 − δ。δ 越小，要求的置信度越高。
[BLOCK_TYPE SECTION/STEP]
定义
[BLOCK_TYPE SECTION/STEP]如果存在某个算法，使得对于任意数据分布 D 和任意目标概念 c ∈ C，给定从 D 中抽取并由 c 标记的 m 个样本，该算法返回的假设 h 满足： [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
P[error(h) ≤ ε] ≥ 1 − δ [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
其中 m 是 1/ε、1/δ 和概念大小的多项式。 [BLOCK_TYPE SECTION/STEP]
In English: feed it enough examples & it gets close enough often enough, & 'enough' doesn't blow up exponentially.
有限假设空间的样本复杂度
如果我们的假设空间 H 包含有限个候选假设，经典分析给出：
m ≥ (1/ε)(ln|H| + ln(1/δ))
把这个公式理解为一个预算。ε 减半，所需样本数翻倍。δ 减半，增加一个常数。|H| 翻倍，增加 ln(2) 个样本——对数级增长，增长非常温和。
假设类样本量计算
一个垃圾邮件过滤器从 |H| = 1,000,000 个候选规则集中进行选择。我们希望误差 ε ≤ 0.05，置信度 1 − δ = 0.99（即 δ = 0.01）。
打散与 VC 维
当假设空间变为无限
当 |H| = ∞ 时，m ≥ (1/ε)(ln|H| + ln(1/δ)) 这一界限不再成立。大多数有用的假设类（ℝᵈ 中的线性分类器、决策树、神经网络）都包含无限多个候选假设。Vapnik 与 Chervonenkis 在 1971 年左右用更丰富的复杂度度量解决了这一问题：VC 维。
打散
如果假设类 H 能够产生某 n 个点的所有可能标记（全部 2ⁿ 种二分法），则称 H 打散 这 n 个点。ℝ² 中的线性分类器可以打散处于一般位置的任意 3 个点：对于这 3 个点的 8 种可能的 +/− 标记，均存在一条直线能正确分离。
但 ℝ² 中的线性分类器 无法 打散呈 XOR 排列的 4 个点。没有直线能将对角线上的点对与反对角线上的点对分开。
VC 维
VC(H) = H 能打散的某 n 点集的最大 n 值。 对于二维线性分类器：VC = 3。对于二维轴对齐矩形：VC = 4。对于具有 W 个权重的神经网络：VC ≤ O(W² log W)（Bartlett & Anthony 1999）。
基于 VC 维的样本复杂度
将 PAC 界中的 ln|H| 替换为 VC 维 d：
m = O((d/ε) log(1/ε) + (1/ε) log(1/δ)) [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
VC 维数可视为无限假设类的“有效复杂度”。VC 维数较低的假设类只需少量样本即可泛化；VC 维数较高的类则需要更多数据。 [BLOCK_TYPE SECTION/STEP]
VC 维数作为有效假设数量 [BLOCK_TYPE SECTION/STEP]
一个神经网络有 W = 10⁹ 个权重。根据 Bartlett-Anthony 界，VC ≤ O(W² log W)。近似取 VC ≈ W² log₂ W。 [BLOCK_TYPE SECTION/STEP]
放弃可实现性，假设上的后验分布
两个重要的泛化
经典 PAC 假设目标概念 c 存在于假设类 H 中。真实数据包含噪声、错误标签以及我们假设类无法表示的概念。以下两种扩展可以处理这种情况。
不可知 PAC
放弃 c ∈ H 的假设。现在与我们 最优类别 假设 h* = argmin_{h ∈ H} risk(h) 竞争。界限形式发生变化：不再接近完美，而是接近 H 内可能达到的最佳水平。
不可知界：P[risk(h) ≤ risk(h*) + ε] ≥ 1 − δ，样本复杂度 m = O(1/ε² × (VC(H) + log(1/δ)))。注意分母中的 ε² 而非 ε：不可知学习需要更多样本才能达到相同精度。
PAC-Bayes（McAllester 1999）
从选择单个假设转向选择 假设分布。从先验 P 开始，观察数据后得到后验 Q。PAC-Bayes 界给出 Q 下期望风险的界：
𝔼_{h~Q}[risk(h)] ≤ 𝔼_{h~Q}[empirical_risk(h)] + √[(KL(Q‖P) + ln(2√n/δ)) / 2n]
KL(Q‖P) 衡量后验分布相对于先验分布移动的距离。有两种解释：
1. 压缩视角。 后验分布接近先验分布（KL 较小）时泛化性能好——信息成本小 = 泛化差距小。
2. 贝叶斯视角。 强先验 + 弱数据更新 = 紧致的界；弱先验 + 强数据更新 = 较松的界。
PAC-Bayes 为什么重要。 经验 PAC-Bayes 界（Catoni 2007，Dziugaite & Roy 2017）为真实神经网络提供了数值上有意义的泛化保证，而经典 PAC 界在此场景下通常失效。它们仍然是我们对过参数化模型泛化能力最紧致的理论工具。
阅读 PAC-Bayes 界
假设我们用 n = 50,000 个有标签样本训练网络。训练后，我们的后验分布 Q 相对于高斯先验 P 的 KL(Q‖P) = 200 nats。Q 下的经验风险为 0.10。设 δ = 0.05。
过参数化与双下降
经典 PAC 的灾难性预测
经典 PAC 理论预测：参数数量多于样本数量 = 灾难性过拟合。在训练数据上完美学习，在测试数据上随机泛化。VC 界预测会出现“死记硬背”而非真正学习。
现代神经网络的参数数量通常比训练样本多 10 倍到 1000 倍，却依然能很好地泛化。按照经典理论，这不应该发生，但它确实发生了。
我们被教过的 U 型曲线
经典偏差-方差权衡：随着模型容量增加，训练误差单调下降；测试误差先下降（欠拟合减轻），达到最小值后上升（过拟合）。VC 理论预测的 U 形曲线。
实际发生的情况 —— 双重下降
Belkin 等人（2019）表明，测试误差在达到插值阈值（容量 = 样本数）之前遵循经典 U 形曲线，超过该阈值后再次下降。高度过参数化的模型泛化性能优于刚好足够大的模型。
为什么经典 PAC 理论未能捕捉到这一点
1. 无分布假设过于悲观。 真实数据具有结构（低内在维度、流形几何）。PAC 界限适用于最坏情况分布；真实分布利用了 SGD 同样会利用的结构。
2. 隐式正则化。 在过参数化网络上，SGD 找到的是最小范数或最小复杂度插值解，而非任意解。经典理论假设最坏情况的经验风险最小化器；真实算法会选择良性解。
3. 假设类定义错误。 SGD 实际探索的有效假设类远小于名义权重空间。PAC-Bayes 后验能捕捉这一点，而 VC 维无法做到。
现代理论工作（Bartlett, Long, Lugosi, Tsigler 2020 关于良性过拟合；Nakkiran et al 2020 关于双重下降）正在构建后 PAC 泛化理论，以适应我们的过参数化 regime。
诊断经典 PAC 的失效
一个研究团队在 100,000 个标注样本上训练一个 10 亿参数的网络。经典 PAC 给出空泛的界，而实测测试准确率达到 95%。
Kaplan、Chinchilla 与自动化通用智能的规模化 [BLOCK_TYPE SECTION/STEP]
从界限到经验缩放定律
[BLOCK_TYPE SECTION/STEP]经典 PAC 从理论上预测数据集大小且结果无效。经验缩放定律通过观测预测数据集大小且实际有效。它们已取代 PAC，成为我们为大型模型进行实际规模估算的工具。 [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
Kaplan et al (2020)
损失随参数量 N、数据集 token 数 D 和计算量 C 呈幂律关系：
L(N) ≈ (Nc/N)^αN L(D) ≈ (Dc/D)^αD L(C) ≈ (Cc/C)^αC
参数量翻倍会使损失按固定乘积因子下降。数据量翻倍也会使损失按另一个固定因子下降。这些指数（αN、αD、αC）可衡量并预测跨多个数量级的领先模型行为。
Hoffmann et al 2022 (Chinchilla)
Chinchilla 研究表明，Kaplan 的指数对参数数量的权重过高。计算最优训练大致需要 20 tokens per parameter：
D_opt ≈ 20 × N
GPT-3（175B 参数）仅在约 300B tokens 上训练——根据 Chinchilla 的计算严重欠训练。一个计算最优的 175B 参数模型需要约 3.5 万亿 tokens。
The Data Wall
扩展参数量需要按比例扩展 token 量。公开网页爬取可获得约 10¹³ 个有效 token。一个假设的 10¹⁵ 参数自动化通用智能模型将需要约 2×10¹⁶ 个 token——比现有网页数据高出三个数量级。 [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
这就是我们的数据墙。 缩放定律预测，我们在遇到算力短缺之前就会先遇到语料短缺。合成数据、多模态语料（视频、音频、传感器流）以及环境强化学习都旨在突破这一限制。 [BLOCK_TYPE SECTION/STEP]
[BLOCK_TYPE SECTION/STEP]
经典 PAC 理论（错误地）告诉我们需要 10²¹ 个样本。缩放定律（根据现实校准）告诉我们需要 2×10¹⁶ 个样本。这两个数字都远超现有文本量。前沿工作目前正致力于弥合这一差距。
估算自动化通用智能语料库 [BLOCK_TYPE SECTION/STEP]
假设一家前沿实验室提出一个 10¹⁴ 参数模型，并声称它将达到自动化通用智能。我们希望根据 Chinchilla 规则确定其训练语料库的大小。
从理论界限到生产测量
停止计算界限；开始测量它们
经典 PAC 界限通常无效。PAC-Bayes 界限在难以验证的假设下可能较紧。一种实用的替代方案是：在真实分布上经验性地测量 ε，并在系统运行过程中持续更新。
想法 1 — 将覆盖率视为经验 PAC
make coverage 目标会将 N 个留出问题送入你的查询系统，并测量以下两项比率：
- cache_hit_rate — 系统找到已知答案的比例
- i_dont_know_rate — 系统诚实放弃回答的比例
每次测量 = 一次伯努利试验。根据观测到的计数，计算真实比率的 Wilson 置信区间。示例：N = 1000 次查询，观测到的 i_dont_know_rate = 0.20 → 95% CI ≈ [0.177, 0.226]。上界 0.226 完全等价于 δ = 0.05 时的 PAC ε，它来自真实分布的真实数据，而非最坏情况的理论分析。
经典 PAC 术语适用（ε、δ、置信度）。所用数学工具不同（二项式集中不等式 vs. VC 理论）。由于真实分布具有可利用的结构，结果更紧。
思路 2 — 通过证伪事件进行 PAC-Bayes 审计
将每次证伪（系统回答明显错误）视为更新真实错误率 ε 后验分布的证据：
1. 先验： ε ~ Beta(α₀, β₀)。选择弱先验，例如 Beta(1, 1) = 均匀分布。
2. 每个查询 产生一个伯努利结果：伪造 (1) 或保留 (0)。
3. n 次查询中出现 k 次伪造后的后验分布： Beta(α₀ + k, β₀ + n − k)。
4. 后验均值： (α₀ + k) / (α₀ + β₀ + n) → 当 n → ∞ 时趋近于经验伪造率。
5. ε 的 95% 可信区间 随 1/√n 收紧。
这给我们带来了什么
- 来自实际部署的真实世界 ε₀ 估计，而非最坏情况的理论
- 任意时刻有效的告警：当后验可信区间跨越合约阈值时，立即呼叫相关人员
- 单调置信：观测到的查询越多 → 可信区间越紧 → 保证越强
相关技术：带在线重校准的共形预测（Vovk）、序贯概率比检验（Wald）、在线 PAC-Bayes（Haddouche & Guedj 2022）。同属一类，但数学工具不同。
计算伪造数据的 Beta 后验
我们的团队对生产查询系统进行覆盖率审计。真实错误率 ε 的先验为 Beta(1, 1)（均匀分布）。在 200 个留出查询中观察到 8 次伪造。