目录
- 1. 说明与去重
- 2. 关键来源
- 2.1 Valiant (1984) —「可学习理论」的原始模型
- 2.2 Vapnik & Chervonenkis (1971) — 一致收敛的充要条件
- 2.3 Sauer (1972) / Shelah (1972) / VC (1971) — 增长函数多项式界
- 2.4 Blumer, Ehrenfeucht, Haussler & Warmuth (1989) — VC 维刻画 PAC 可学性
- 2.5 Ehrenfeucht, Haussler, Kearns & Valiant (1989) — 样本复杂度下界
- 2.6 Haussler, Littlestone & Warmuth (1994) — One-inclusion graph 上界
- 2.7 Hanneke (2016) — 最优样本复杂度的闭合
- 2.8 Vapnik (1998) —《Statistical Learning Theory》中的风险最小化框架
- 2.9 MDL / Occam 剃刀与 PAC 的接口
- 2.10 NFL 与 PAC/VC 的边界关系
- 3. 定理族之间的关系图
- 4. 诚实缺口与后续核对清单
- 5. 可验证链接汇总
- 6. 对总课题的接口结论（临时，非最终裁决）
日期：2026-06-23 任务：总课题「归纳问题与『无免费午餐』——为什么机器学习能泛化」之子课题 B2 前期文献核查 状态：初步文献笔记（非最终报告） 标签：PAC 学习 / VC 维 / 一致收敛 / 样本复杂度 / Sauer-Shelah 引理 / 统计学习理论
1. 说明与去重
本笔记覆盖子课题 B2 的核心定理族：
- Valiant (1984) 原始 learnable 模型与标准 PAC 的形成；
- Vapnik & Chervonenkis (1971) 一致收敛定理；
- Sauer (1972) / Shelah (1972) / Perles 增长函数引理；
- Blumer, Ehrenfeucht, Haussler & Warmuth (1989) 的 PAC 上界；
- Ehrenfeucht, Haussler, Kearns & Valiant (1989) 的样本复杂度下界；
- Haussler, Littlestone & Warmuth (1994) 的 one-inclusion graph 上界；
- Hanneke (2016) 对最优样本复杂度的闭合；
- Vapnik (1998) Statistical Learning Theory 中的泛化框架；
- MDL / Occam 剃刀与 PAC 的接口；
- NFL 与 PAC/VC 的边界关系。
旧线已覆盖、本处仅接口：
2026-06-22-probability-bayesianism-foundation-stress-test.md：已覆盖 Solomonoff 归纳、NFL、贝叶斯先验批判；2026-06-23-philosophical-problem-of-induction-literature-notes.md：已覆盖归纳问题的哲学史；2026-06-23-deep-learning-generalization-mystery-subtopic-c.md：已覆盖深度学习泛化之谜；2026-06-23-criticism-redteam-nfl-implicit-bias-world-structure-bayesian-priors.md：已覆盖 NFL 误读、隐式偏置质疑。
因此本笔记聚焦 PAC/VC 的精确前提、结论、边界、原始关键句与数字，为最终裁决提供可验证底板，不展开哲学/深度学习红队讨论。
2. 关键来源
2.1 Valiant (1984) —「可学习理论」的原始模型
来源：Valiant, L. G. (1984). “A theory of the learnable.” Communications of the ACM, 27(11), 1134–1142. DOI：https://doi.org/10.1145/1968.1972 arXiv 历史注：Cornell CS-TR-84-639 重印版与 ACM 版内容一致，arXiv:2605.13840 讨论了原始模型与后来标准 PAC 的差异。
中文摘要：Valiant 首次将「学习」形式化为一个组合/概率问题：从 oracle 提供的例子出发，以多项式时间和多项式样本获得一个高概率近似正确的假设。原始论文的模型与今天教科书里的标准 PAC 有微妙差别：它允许 membership query、只接收正例、要求输出的假设没有假阳性（one-sided error）。后人（Kearns & Vazirani 1994；Shalev-Shwartz & Ben-David 2014 等）把模型简化为「允许正负例、允许双边错误」的标准 PAC，VC 维才成为刻画可学性的核心工具。
原始关键句/数字：
“This paper is concerned with the computational complexity of learning from examples. We introduce a formal model of learning that is naturally motivated by the problem of machine learning.”（Valiant 1984 Abstract）
“A class of concepts is learnable from examples in time T if there is an algorithm that, for each concept in the class and any distribution, with high probability finds a good approximation to the concept in time T.”（Valiant 1984 §1，大意）
数学/模型边界：
- 前提：Oracle EX(c, D) 按分布 D 产生被接受目标概念 c 标记的正例；允许等价查询（membership query）；假设空间 H 包含目标概念类 C；要求输出 h 满足：h(x)=0 必蕴含 c(x)=0（无假阳性）。
- 结论：若概念类可被「短」布尔公式表达，则存在多项式时间算法从示例中学习它；给出了单调 DNF、k-CNF 等类的可学性结果。
- 边界：该模型不等于标准 PAC。标准 PAC 用 i.i.d. 样本、允许假阳性与假阴性、用 0-1 损失度量误差；VC 维是标准 PAC 的判定参数，但只是 Valiant 原始模型的后续发展。
- 证据标签：[文献较稳]（Valiant 1984 原始文本与 arXiv:2605.13840 历史分析一致）；[理论整合/推断]（「原始模型≠标准 PAC」的表述基于二手历史分析，原始论文逐字核对仅限摘要与引论）。
2.2 Vapnik & Chervonenkis (1971) — 一致收敛的充要条件
来源：Vapnik, V. N., & Chervonenkis, A. Ya. (1971). “On the Uniform Convergence of Relative Frequencies of Events to their Probabilities.” Theory of Probability and Its Applications, 16(2), 264–280. DOI：https://doi.org/10.1137/1116025 英文重印：Vapnik, V. N. (2000). The Nature of Statistical Learning Theory（第 2 版）附录；Measuring the VC-Dimension 课程讲义（https://www.cs.bu.edu/faculty/mcchung/teaching/3_Foundations/papers/vc_1971.pdf）转述了核心定理。
中文摘要：VC 1971 给出事件族相对频率一致收敛到其概率的必要且充分条件。它引入增长函数（growth function，亦称 shattering coefficient）和 VC entropy，证明当且仅当「平均对数增长函数除以样本量趋于零」时，一致收敛成立；等价地，有限 VC 维（即增长函数多项式增长）是充分条件。这一工作为后来的 PAC 样本复杂度上界提供了概率工具。
原始关键句/数字：
“We say that the relative frequencies of events in a class S converge uniformly to their probabilities over the class S if …” “Theorem: For uniform convergence of relative frequencies to probabilities over a class of events S it is necessary and sufficient that the equality …”（VC 1971，定理表述；具体依赖二手讲义转述）
从 TTIC 讲义（https://home.ttic.edu/~tewari/lectures/lecture11.pdf）转述：
“VCdim(H) = d. Then for all m ≤ d, Π_F(m) = 2^m. The lemma … implies that for m > d, Π_F(m) = O(m^d).” “Finite VCdim implies uniform convergence.”
从开放课程 PDF（https://pub.ista.ac.at/~chl/courses/SML_W20/ml2020-08.pdf）转述的关键不等式：
\[ \Pi_H(n) \leq \sum_{k=0}^{VCdim(H)} \binom{n}{k}, \quad \text{且对 } n \geq d, \quad \Pi_H(n) \leq \left(\frac{en}{d}\right)^d. \]
数学/定理边界：
- 前提：样本 i.i.d. 来自某概率分布；事件族（或指示函数族）满足可测性条件（well-behaved class）。
- 结论：一致收敛 ⇔ 平均 VC entropy 趋于 0；充分条件：VC 维 d < ∞。此时对足够大的样本量 n，
\[
\sup_{h\in H} |R(h) – \hat{R}_n(h)| \xrightarrow{a.s.} 0.
\] - 边界：原始论文的充要条件用增长函数/entropy 表述，VC 维只是更容易计算的充分判据；对不可数或病态函数类，需要额外可测性假设（见 Dudley 1984、Pollard 1984 的 empirical process 理论）。
- 证据标签：[文献较稳]（VC 1971 的定理地位在教材与综述中一致）；[仍不确定/待核对]（本笔记未逐字阅读 VC 1971 俄文/英文 PDF 全文，部分表述依赖讲义与教材转述）。
2.3 Sauer (1972) / Shelah (1972) / VC (1971) — 增长函数多项式界
来源：
- Sauer, N. (1972). “On the density of families of sets.” Journal of Combinatorial Theory, Series A, 13(1), 145–147. DOI: https://doi.org/10.1016/0097-3165(72)90019-2
- Shelah, S. (1972). “A combinatorial problem; stability and order for models and theories in infinitary languages.” Pacific Journal of Mathematics, 41(1), 247–261. URL: https://projecteuclid.org/euclid.pjm/1102968478
- 该组合引理有时也称 Sauer-Shelah-Perles 引理（Perles 有未发表早期证明）。
中文摘要：若集合族（或二值函数族）的 VC 维为 d，则它在任意 n 点集上能产生的不同限制（dichotomies）数——即增长函数 Π_H(n)——被组合数和 (en/d)^d 控制。这个多项式上界是 VC 一致收敛证明的核心：它把「无穷假设空间」的有效规模压到关于样本量 n 的多项式级别，从而可用联合界控制泛化误差。
原始关键句/数字：
从 UBC 讲义（https://www.cs.ubc.ca/~dsuth/532S/22/slides/05-more-vc.pdf）转述：
“Sauer-Shelah lemma: when n > d, τ_H(n) ≤ (en/d)^d = O(n^d).” “Either VCdim(H) = ∞ and τ_H(n) = 2^n, or VCdim(H) = d and τ_H(n) = O(n^d).”
从 ScienceDirect Topics 转述：
“LEMMA 5 Vapnik, Chervonenkis, Sauer, Shelah. Let F be a function class with finite VC dimension d. Then N(F, n) ≤ Σ_{i=0}^d (n choose i) for all n ∈ ℕ. In particular, for all n ≥ d we have N(F, n) ≤ (en/d)^d.”
数学/定理边界：
- 前提：H 是定义在输入空间 X 上的二值函数族（或集合族）；VCdim(H) = d < ∞。
- 结论：Π_H(n) ≤ Σ_{i=0}^d C(n, i) ≤ (en/d)^d 对 n ≥ d 成立。
- 边界：该引理只给出组合计数，本身不含概率；它必须与 Hoeffding/Chernoff 不等式结合才能导出泛化界。
- 证据标签：[文献较稳]
2.4 Blumer, Ehrenfeucht, Haussler & Warmuth (1989) — VC 维刻画 PAC 可学性
来源：Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). “Learnability and the Vapnik-Chervonenkis dimension.” Journal of the ACM, 36(4), 929–965. DOI：https://doi.org/10.1145/76359.76371 PDF 入口：https://www.ccs.neu.edu/home/vip/teach/MLcourse/4_boosting/materials/Blumer_VCdim_learnability.pdf
中文摘要：这篇论文是标准 PAC 理论与 VC 维之间的关键桥梁。它证明：一个概念类 C 可被学习（分布无关、双边误差）当且仅当它的 VC 维有限；并给出用 VC 维表示的显式样本复杂度上界。任何「与样本一致」的算法（即经验风险最小化，ERM）都能达到该样本复杂度，尽管它未必是多项式时间可计算的。
原始关键句/数字：
从 NEU PDF（Blumer_VCdim_learnability.pdf）转述：
“We show that there is a learning function satisfying (3) if and only if the VC dimension of C is finite. Moreover, if C does have finite VC dimension d then there is a learning function for C, uniformly achieving error no more than ε with probability at least 1−δ, using sample size m(ε,δ) = max(4/ε log(2/δ), 8d/ε log(13/ε)). In fact, any function from samples into the class C that always gives hypotheses consistent with the sample is a learning function for C and has sample complexity bounded by m(ε,δ).”（Blumer et al. 1989, JACM 摘要/§2）
“For a finite concept class C ⊂ 2^X, Theorem 2.1 gives an upper bound on the sample complexity required for learning the class C. This upper bound is linear in ln|C|.” “Theorem 2.2 (BEHW89): Let C be a well-behaved concept class. If the VC dimension of C is d < ∞, then for 0 < ε, δ < 1 and for sample size at least max(4/ε log(2/δ), 8d/ε log(13/ε)), C is learnable by any algorithm that finds a concept from C consistent with the sample sequence.”（Floyd 1993 技术报告 UCSC-CRL-93-13 转述）
数学/定理边界：
- 前提：标准 PAC 设置；概念类 C 定义在输入空间 X 上；目标概念 c ∈ C；样本 i.i.d. 来自未知分布 D；损失为 0-1 损失；要求「well-behaved」可测性。
- 结论：
1. C PAC 可学 ⇔ VCdim(C) < ∞；
2. ERM 的样本复杂度满足
\[
m(\varepsilon, \delta) = O\!\left(\frac{1}{\varepsilon}\left(d \log\frac{1}{\varepsilon} + \log\frac{1}{\delta}\right)\right),
\]
更具体地，Blumer et al. 给出的显式界为
\[
m \geq \max\!\left(\frac{4}{\varepsilon}\log\frac{2}{\delta},\; \frac{8d}{\varepsilon}\log\frac{13}{\varepsilon}\right).
\] - 边界：
- 该上界含一个 d log(1/ε) 项，与后来的下界相比在 log(1/ε) 因子处不紧；
- 仅保证「存在学习函数」，不保证该函数可在多项式时间内计算（计算可学性是另一个问题）；
- 要求真实目标概念在 C 内（realizable setting），对 agnostic（不可知/带噪声）设置需要 VC 一致收敛的另一种形式。
- 证据标签：[文献较稳]
2.5 Ehrenfeucht, Haussler, Kearns & Valiant (1989) — 样本复杂度下界
来源：Ehrenfeucht, A., Haussler, D., Kearns, M., & Valiant, L. (1989). “A general lower bound on the number of examples needed for learning.” Information and Computation, 82(3), 247–261. DOI：https://doi.org/10.1016/0890-5401(89)90002-3 PDF 入口：https://www.cis.upenn.edu/~mkearns/teaching/COLT/EhrenfeuchtHausslerKearnsValiant.pdf
中文摘要：EHKV 1989 证明：任何学习算法在 VC 维为 d 的概念类上，要达到 ε 精度、1−δ 置信度，至少需要 Ω((1/ε)(d + log(1/δ))) 个样本。该下界与 Blumer et al. 1989 的上界之间只相差一个 log(1/ε) 因子，这个差距在 2016 年被 Hanneke 闭合。
原始关键句/数字：
从 UPenn PDF 逐字转述：
“Theorem 1. Let C be a concept class of Vapnik-Chervonenkis dimension d. Let L be an algorithm that learns C from examples. Then if d ≤ 2n, L must use at least d/(256ε) examples to learn C to within error ε for some 0 < ε < 1/8 and some distribution on X^n, where 0 < δ ≤ 1/100.”（EHKV 1989, p.4, Theorem 1）
“Theorem 2. Let C be a concept class of Vapnik-Chervonenkis dimension d, and let L be an algorithm that learns C from examples. Then for 0 < ε < 1/2 and 0 < δ < 1, L must use at least (1−ε)/ε · ln(1/δ) examples to learn C to within error ε and with confidence at least 1−δ for some distribution on X^n.”（EHKV 1989, p.4, Theorem 2）
从 Hanneke 2016 综述整合：
“A second lower bound of (d−1)/(32ε) was supplied by Ehrenfeucht, Haussler, Kearns, and Valiant (1989), for 0 < ε ≤ 1/8 and 0 < δ ≤ 1/100. Taken together, these results imply that, for any ε ∈ (0,1/8] and δ ∈ (0,1/100], M(ε,δ) ≥ max{(d−1)/(32ε), (1−ε)/ε ln(1/δ)} = Ω((1/ε)(d + log(1/δ))).”（Hanneke 2016, JMLR 17/15-389）
数学/定理边界：
- 前提：标准 PAC realizable 设置；概念类 C 的 VC 维为 d；学习算法 L 可以输出任意假设（不必在 C 内，即 improper learning 也包含在内）。
- 结论：任何算法都需要至少
\[
\Omega\!\left(\frac{1}{\varepsilon}\left(d + \log\frac{1}{\delta}\right)\right)
\]
个样本，且存在某个目标概念与分布迫使其实现该下界。 - 边界：
- 常数在不同转述中有差异（EHKV 原文用 256，Hanneke 综述用 32；差异可能来自后续简化或对 δ 范围的调整）；
- 仅适用于 0 < ε ≤ 1/8、0 < δ ≤ 1/100 等参数范围；
- 对 improper learning 也成立，因此上界改进不能靠扩大假设空间来规避。
- 证据标签：[文献较稳]
2.6 Haussler, Littlestone & Warmuth (1994) — One-inclusion graph 上界
来源：Haussler, D., Littlestone, N., & Warmuth, M. K. (1994). “Predicting {0,1}-functions on randomly drawn points.” Information and Computation, 115(2), 248–292. DOI：https://doi.org/10.1006/inco.1994.1097 综述转述：Hanneke (2016) §1 与 Warmuth (2004) 猜想。
中文摘要：HLW 1994 提出 one-inclusion graph 算法，给出样本复杂度 \[ O\!\left(\frac{d}{\varepsilon} \log\frac{1}{\delta}\right), \] 该上界在 δ 方向上优于 Blumer et al. 1989 的 \[ O((1/ε)(d\log(1/ε) + \log(1/δ))), \] 但在 ε 方向上是否最优仍由 log(1/ε) 差距悬而未决。HLW 的结果也建立了 PAC 学习与样本压缩（sample compression）之间的深刻联系。
原始关键句/数字：
从 Hanneke 2016 转述：
“A sometimes-better upper bound was established by Haussler, Littlestone, and Warmuth (1994): M(ε,δ) = O((d/ε) Log(1/δ)). This bound is achieved by a modified variant of the one-inclusion graph prediction algorithm, a learning algorithm also proposed by Haussler, Littlestone, and Warmuth (1994), which has been conjectured to achieve the optimal sample complexity (Warmuth, 2004).”
数学/定理边界：
- 前提：标准 PAC realizable 设置；VC 维 d。
- 结论：存在算法使
\[
M(\varepsilon, \delta) = O\!\left(\frac{d}{\varepsilon} \log\frac{1}{\delta}\right).
\] - 边界：该界不含 d log(1/ε) 项，因此在 ε 很小、δ 不太小时可能优于 ERM；Warmuth 猜想 one-inclusion graph 可能达到最优 Θ((1/ε)(d + log(1/δ)))，但尚未完全证明。
- 证据标签：[文献较稳]
2.7 Hanneke (2016) — 最优样本复杂度的闭合
来源：Hanneke, S. (2016). “The Optimal Sample Complexity of PAC Learning.” Journal of Machine Learning Research, 17, 1–15. URL：https://www.jmlr.org/papers/volume17/15-389/15-389.pdf arXiv：https://arxiv.org/abs/1507.00473
中文摘要：Hanneke 证明标准 PAC 学习的最优样本复杂度为 \[ \Theta\!\left(\frac{1}{\varepsilon}\left(d + \log\frac{1}{\delta}\right)\right), \] 从而将 Blumer et al. 1989 上界中的多余 log(1/ε) 因子去除。结果同时适用于 proper 与 improper 学习，并澄清了 ERM 并非在所有情况下都最优。
原始关键句/数字：
“Our objective in this work is to establish sharp sample complexity bounds. … Taken together, these results imply that, for any ε ∈ (0,1/8] and δ ∈ (0,1/100], M(ε,δ) ≥ max{(d−1)/(32ε), (1−ε)/ε ln(1/δ)} = Ω((1/ε)(d + log(1/δ))).”（Hanneke 2016, §1）
“In particular, Vapnik (1982) and Blumer, Ehrenfeucht, Haussler, and Warmuth (1989) established an upper bound of M(ε,δ) = O((1/ε)(d Log(1/ε) + Log(1/δ))). They proved that this sample complexity bound is in fact achieved by any algorithm that returns a classifier h ∈ C[(X_{1:m}(P), f*(X_{1:m}(P)))], also known as a sample-consistent learning algorithm (or empirical risk minimization algorithm).”（Hanneke 2016, §1）
“We prove that for any concept space C with VC dimension d, the sample complexity satisfies M(ε,δ) = Θ((1/ε)(d + log(1/δ))) …”（Hanneke 2016, Abstract）
数学/定理边界：
- 前提：标准 PAC realizable 设置；概念类 C 的 VC 维为 d。
- 结论：最优样本复杂度
\[
M(\varepsilon, \delta) = \Theta\!\left(\frac{1}{\varepsilon}\left(d + \log\frac{1}{\delta}\right)\right).
\] - 边界：
- 该结果描述的是信息论样本复杂度，不保证算法时间效率；
- 当概念空间可数或有限时， achievability 构造较复杂，涉及离散化与专家聚合；
- 对 agnostic 设置，最优样本复杂度不同（通常为 Θ((1/ε²)(d + log(1/δ)))）。
- 证据标签：[文献较稳]
2.8 Vapnik (1998) —《Statistical Learning Theory》中的风险最小化框架
来源：Vapnik, V. N. (1998). Statistical Learning Theory. Wiley. ISBN: 978-0-471-03003-4.
中文摘要：Vapnik 1998 把经验风险最小化（ERM）与结构风险最小化（SRM）系统化，提出「从有限样本推断」的三条原则：
- 经验风险最小化：在假设空间 H 中选择训练误差最小的 h；
- 一致收敛：保证训练误差逼近真实风险；
- 结构风险最小化：把 H 嵌套为复杂度递增的序列 H_1 ⊂ H_2 ⊂ …，在最小化经验风险的同时惩罚 VC 维，以控制泛化 gap。
书中还讨论了 VC 维的多种变体（ε-entropy、growth function、annealed entropy），并给出带显式常数的泛化界。
原始关键句/数字：
从 ScienceDirect Topics / 教材转述：
“The main purpose of the VC dimension is to characterize the growth behavior of the shattering coefficient using a single number.”（Vapnik-Chervonenkis Dimension overview, ScienceDirect Topics）
“Vapnik, Statistical Learning Theory (1998), §4.8. Sin-classifier example and explicit VC constants.”（TheoremPath VC Dimension page）
数学/框架边界：
- 前提：i.i.d. 样本；损失函数有界；假设空间满足可测性。
- 结论：
- ERM 一致性的充分条件：有限 VC 维；
- 泛化界（以 0-1 损失为例，简化形式）：
\[
R(h) \leq \hat{R}_n(h) + O\!\left(\sqrt{\frac{d \log(n/d) + \log(1/\delta)}{n}}\right).
\] - SRM 通过最小化
\[
\hat{R}_n(h) + \text{complexity penalty}(VCdim(H_k), n, \delta)
\]
来选择模型。 - 边界：
- 书中给出的显式常数依赖于具体定理版本与损失函数；
- SRM 要求模型结构预先给定，且惩罚项的校准对实际性能敏感；
- 对深度学习这类 VC 维极大或无限的模型，VC/SRM 界通常是空泛的（vacuous），需要其他工具（Rademacher 复杂度、稳定性、隐式偏置等）。
- 证据标签：[文献较稳]（框架与定理地位稳定）；[仍不确定/待核对]（具体章节 §4.8 的 sin-classifier 例子与显式常数未逐字核对）。
2.9 MDL / Occam 剃刀与 PAC 的接口
来源：
- Rissanen, J. (1978). “Modeling by shortest data description.” Automatica, 14(5), 465–471. DOI: https://doi.org/10.1016/0005-1098(78)90005-5
- Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1987). “Occam’s razor.” Information Processing Letters, 24(6), 377–380. DOI: https://doi.org/10.1016/0020-0190(87)90114-1
- Grünwald, P. (2007). The Minimum Description Length Principle. MIT Press. ISBN: 978-0-262-07281-0
- Takeuchi, J. (2015). “MDL Principle.” In A Mathematical Approach to Research Problems of Science and Technology (pp. 351–358). Springer. DOI: https://doi.org/10.1007/978-4-431-55342-7_31
中文摘要：MDL 把奥卡姆剃刀形式化为数据压缩：选择使「模型描述长度 + 给定模型下数据描述长度」最小的假设。Blumer et al. (1987) 的「Occam’s Razor」定理证明：若一个学习算法总能找到比训练数据更短描述的假设，则它在 PAC 意义下具有泛化保证。Rissanen 1978 的原始 MDL 则用于模型选择，后被 Grünwald 发展为通用编码与统计学习理论的统一框架。
原始关键句/数字：
从 Grünwald 教程（https://homepages.cwi.nl/~paulv/course-kc/mdlintro.pdf）转述：
“Equating ‘learning’ with ‘finding regularity’, we can therefore say that the more we are able to compress the data, the more we have learned about the data.” “MDL chooses a model that trades-off goodness-of-fit on the observed data with ‘complexity’ or ‘richness’ of the model. As such, MDL embodies a form of Occam’s Razor.”
从 Takeuchi 2015 转述：
“Rissanen proposed MDL criterion for statistical model selection based on information theory in 1978.” “The MDL principle is a mathematical formulation of Occam’s razor. It says ‘simple explanations of a given phenomenon are to be preferred over complex ones.'”
从 Blumer et al. 1987（标题与摘要，未逐字全文核对）转述：
“Occam’s Razor” — 若假设的描述长度以样本量的某次多项式压缩，则该算法是 PAC 可学的。
数学/定理边界：
- 前提（Blumer et al. 1987 Occam 定理）：存在一致编码，使得对任意大小为 m 的样本，算法输出的假设 h 满足 |h| ≤ p(m) 且 h 与样本一致；编码满足前缀码 / Kraft 不等式。
- 结论：该算法以样本复杂度 O(p(m)/ε) 或类似形式 PAC 学习。
- 边界：
- 对无限 VC 维的假设空间，MDL/Occam 论证仍可能有效（若存在压缩方案），但经典 VC 界不再适用；
- 实际 MDL 需要指定编码/先验，编码选择本身引入主观性；
- 对神经网络，不存在通用的短描述，因此 MDL 解释需要诉诸隐式压缩/隐式偏置。
- 证据标签：[文献较稳]；[仍不确定/待核对]（Blumer et al. 1987 的具体样本复杂度公式未逐字核对原文）。
2.10 NFL 与 PAC/VC 的边界关系
来源：子课题 E 已详细覆盖，见 2026-06-23-criticism-redteam-nfl-implicit-bias-world-structure-bayesian-priors.md。本节只给出接口。
中文摘要：PAC/VC 理论通过「限制假设空间」打破了 NFL 的均匀平均：NFL 说对所有可能 target function 取均匀平均时任何算法期望性能相同；而 PAC 只要求对某一固定但未知分布 D 和目标概念类 C 有好的表现，并把样本复杂度用 VC 维量化。因此 PAC 可学性隐含了一个非均匀的先验：真实世界的问题来自低 VC 维/可压缩的函数类。
关键边界：
- NFL 的均匀平均前提 ≠ PAC 的固定未知分布前提；
- PAC 的分布无关性（distribution-free）仍是非常强的保证，它要求算法对所有 D 都表现好，但只要目标概念在 C 内；
- 若目标概念不在 C 内（agnostic/realizable 失败），PAC 界不再成立，需要 agnostic learning 或额外假设。
证据标签：[理论整合/推断]
3. 定理族之间的关系图
VC 1971 一致收敛
│
├── 增长函数 Π_H(n)
│ └── Sauer-Shelah 1972: Π_H(n) ≤ (en/d)^d
│
└── 对 ERM: R(h) ≈ R̂_n(h) 一致地
│
├── 上界：Blumer et al. 1989
│ m = O((1/ε)(d log(1/ε) + log(1/δ)))
│
├── 改进上界：Haussler-Littlestone-Warmuth 1994
│ m = O((d/ε) log(1/δ))
│
├── 下界：Ehrenfeucht et al. 1989
│ m = Ω((1/ε)(d + log(1/δ)))
│
└── 闭合：Hanneke 2016
m = Θ((1/ε)(d + log(1/δ)))
Valiant 1984 原始 learnable 模型
└── 后人发展为标准 PAC
└── VC 维成为可学性判据（Blumer et al. 1989）
Vapnik 1998 SRM
└── 用 VC 维惩罚模型复杂度，选择经验风险 + 复杂度惩罚最小者
MDL / Occam 剃刀
└── 用描述长度替代 VC 维，提供另一种复杂度控制（Blumer et al. 1987; Rissanen 1978）4. 诚实缺口与后续核对清单
- VC 1971 原始论文：未逐字阅读英文/俄文 PDF，一致收敛的「必要且充分」条件表述依赖讲义与教材转述；建议下载 JSTOR 或 SIAM 全文核对定理 1、2 的精确表述。
- Blumer et al. 1989 全文：已核对 NEU 提供的 PDF 摘要与 Floyd 1993 转述，但部分命题（如 Theorem 2.1 对有限类的界、§3 计算可学性）未全文细读。
- Blumer et al. 1987 Occam’s Razor 论文：只核对了标题/摘要/二手转述，具体样本复杂度公式与编码条件未逐字核对。
- Vapnik 1998 §4.8：sin-classifier 例子与显式 VC 常数未核对；如需写入最终裁决，应翻开原书或 Anthony & Bartlett (1999) 的显式版本。
- EHKV 下界常数：EHKV 原文用 256，Hanneke 综述用 32，差异来源未完全厘清（可能与 δ 范围、improper vs proper、或后续简化有关），最终报告应谨慎表述为「存在某常数 c 使得下界为 Ω(…)」。
- Agnostic / 不可知 PAC：本笔记主要覆盖 realizable 设置；对带噪声 setting，样本复杂度为 Θ((1/ε²)(d + log(1/δ)))，来源（Anthony & Bartlett 1999; Mohri et al. 2018）未在本次任务范围内深入。
- 可测性假设：VC 理论对不可数函数类需要「well-behaved」或 PVM（permissible）条件，具体细节未展开；若涉及非标准输入空间，应补充 Dudley/Pollard 的 empirical process 条件。
5. 可验证链接汇总
6. 对总课题的接口结论（临时，非最终裁决）
- PAC/VC 为什么能解释泛化：它不是免费的。解释力来自两个受限前提：
1. 真实目标概念属于某个低 VC 维的假设类 C（或数据分布支持这种低复杂度结构）；
2. 学习算法执行 ERM 或某种等价的一致收敛控制。
在这两个前提下，有限样本足以高概率保证未见风险接近训练风险。 - 与 NFL 的兼容性：NFL 对「所有可能问题均匀平均」成立；PAC/VC 通过把问题限制在低 VC 维类里，把 NFL 的均匀平均替换为「对任意固定分布都成立」的分布无关保证。这并不意味着「没有先验」，而是把先验编码进了假设空间 C 的选择。
- 与深度学习的张力：现代深度网络的参数/VC 维极大，VC 界通常是空泛的。这说明 PAC/VC 本身不足以解释深度学习的泛化，必须结合子课题 C（隐式偏置、双下降、良性过拟合）与子课题 D（世界结构假设）才能给出完整图景。
- 诚实度：上述接口结论是理论整合/推断，而非已严格证明的单一定理。