归纳问题与“无免费午餐”——为什么机器学习能泛化？

问题
简短结论
可信度
一、哲学战场：归纳问题仍然硬
二、形式战场：从 NFL 到 Solomonoff
三、经验战场：深度学习泛化之谜
四、世界战场：结构假设与过度外推
五、红队：误读、循环论证与过度外推
六、裁决：三足鼎立与诚实缺口
七、Codex 审核与修正（2026-06-26 追加）
参考来源
关联笔记

问题

从有限样本到未见样本的泛化，是机器学习、科学推理与日常认知共同面临的“归纳问题”。休谟指出，这一跳跃无法被理性证明；而“无免费午餐”（No Free Lunch, NFL）定理则把休谟的怀疑形式化：若对目标函数不加任何结构假设，所有学习算法在平均意义下等价。那么，为什么深度神经网络在图像、语言、蛋白质折叠等真实任务上能够惊人地泛化？PAC/VC、Solomonoff 归纳、贝叶斯主义与“世界有结构”的说法各能解释多少？这些解释又有哪些是被过度推销的？

简短结论

归纳问题在哲学上仍然硬。 休谟的两难没有被任何后来的方案取消：Popper 的证伪主义放弃了归纳；Reichenbach 的实用辩护只在“极限频率存在”的狭窄前提下成立；Carnap 的归纳逻辑把“自然齐一性”偷换成语言框架内的对称性；贝叶斯方案的核心张力仍然是“先验问题”。Mayo 的严重检验提供了一条非贝叶斯、非 Popper 的频率主义路径，但它把“归纳”替换为“方法能否发现错误”。[文献较稳]

NFL / PAC / VC / Solomonoff / MDL 这些形式定理为真，但解释范围窄。 Wolpert 的 NFL 定理精确地说明：没有先验偏置就没有平均意义上的泛化优势；Valiant 的 PAC 框架与 Blumer 等人的 VC 界说明，在“目标属于某个有界容量假设类 + i.i.d.”的前提下，有限样本保证是可能的；Solomonoff 归纳给出了不可计算的普适预测方案；Mitchell 与 Rissanen 的 MDL 思路把“简单性”操作化为描述长度。它们共同把“额外假设不可避免”形式化，却没有解决“为什么现实世界的额外假设是对的”这一归纳问题本身。[文献较稳]

深度学习确实突破了经典泛化图景，但机制尚未闭合。 Zhang 等人（2017）的随机标签实验表明，模型族复杂度加显式正则化不足以解释泛化；Belkin 与 Nakkiran 等人的双下降曲线说明“插值即过拟合”的教条失效；Bartlett 等人在线性模型中给出了良性过拟合的精确条件；Mallinar 等人发现真实深度网络多为“tempered overfitting”；grokking 现象揭示了记忆与泛化之间可能存在尖锐转换。然而，隐式偏置的具体机制（SGD 噪声、平坦/尖锐极小值、参数范数、特征学习）仍然众说纷纭，且各自遭遇反例。[文献较稳 / 理论整合]

“世界有结构”是必要但非充分的一足，不能滑向“世界简单”或“AGI 必然”。 流形假设、对称/等变性、数据协方差/核谱的幂律衰减都有真实证据，能够打破 NFL 的最坏情况均匀性；Elesedy 与 Zaidi 在线性模型中严格证明了等变性带来的泛化增益。但组合性在 SCAN/COGS 等任务上暴露系统性失败；scaling laws 是经验上稳健的唯象律，幂律身份却很少被严格检验，指数普适性未确立；natural abstractions 的 universality、discreteness、low-dimensionality 仍缺乏定理支持。Schaeffer 等人（2023）对“涌现能力”的研究表明，许多看似突然的跨尺度能力可以用评估指标的非线性来解释。[文献较稳 / 仍不确定]

真正的答案是“形式约束 + 隐式偏置 + 世界结构”三足鼎立，且三者都不是无代价的。 形式约束（模型类、VC 维、先验、正则化）划定可学习性的边界；隐式偏置（优化器、初始化、架构、训练动力学）在欠定问题中选择具体解；世界结构（低维流形、对称、组合、幂律谱）打破 NFL 的均匀平均，使某些偏置在真实分布上确实更好。任何把成功单独归给其中一足的叙述都是过度简化。[理论整合 / 个人判断]

对“通用智能 / AGI 必然涌现”应保持对称红队。 Legg 与 Hutter 的通用智能定义、Sutton 的“苦涩教训”、Hutter 的 AIXI 框架都强调搜索与规模的力量；但 Mitchell（2021）指出 AI 研究中存在“窄智能→通用智能”“简单任务容易”“愿望性 mnemonic”“智能全在大脑”四种谬误；Schaeffer 等人说明大模型的“涌现能力”高度依赖指标选择。DL 成功不能推出“世界简单”或“规模必然通向 AGI”。[文献较稳 / 理论整合]

可信度

稳健部分：Hume / Popper / Reichenbach / Carnap / Mayo 的二手叙述（主要来自 SEP 与权威综述）；Wolpert NFL 定理、Valiant PAC、Blumer VC、Vapnik-Chervonenkis 一致收敛定理的原始陈述；Zhang 2017、Belkin 2019、Nakkiran 2020、Bartlett 2020、Mallinar 2022 等深度学习泛化实验；Solomonoff 1964 与 Mitchell 1980 的原文关键句；Schaeffer 2023 与 Mitchell 2021 的完整摘要。
理论整合：三足鼎立框架；“tempered overfitting”对真实 DNN 的描述；grokking 的多解释并存；世界结构假设的必要但非充分性；AGI/涌现的批判。
仍不确定 / 弱：Nagarajan & Kolter 2019、Razin & Cohen 2020、Chiang et al. 2023 等全文未逐字核对；natural abstractions 的多个子假设缺乏定理；scaling law 指数的第一性原理来源；真实语言/视觉数据中组合性的因果机制。

一、哲学战场：归纳问题仍然硬

1.1 Hume：归纳无法被理性证明

David Hume 在 An Enquiry Concerning Human Understanding（1748）§4.2 与 A Treatise of Human Nature（1739）1.3.6 中提出经典两难：从“过去观察到的规律”到“未来/未观察案例也如此”的推断，既不能是先验演绎（“自然进程改变”并不自相矛盾），也不能是经验归纳（任何经验证明都已预设“未来像过去”，循环论证）。Hume 最终把归纳归于“custom or habit”——一种不可回避的心理学机制，而非理性证明 SEP The Problem of Induction。

“All reasonings may be divided into two kinds, namely, demonstrative reasoning, or that concerning relations of ideas, and moral reasoning, or that concerning matter of fact and existence.”（Enquiry §4.2.18）

“it implies no contradiction that the course of nature may change, and that an object seemingly like those which we have experienced, may be attended with different or contrary effects.”（Enquiry §4.2.18）

“When the mind, therefore, passes from the idea or impression of one object to the idea or belief of another, it is not determin’d by reason, but by certain principles, which associate together the ideas of these objects, and unite them in the imagination.”（Treatise 1.3.6.12）

Hume 的论证至今没有被取消。任何声称“解决了归纳问题”的方案，要么收窄了问题范围，要么悄悄引入了额外假设。

1.2 Popper：用证伪替代归纳

Karl Popper 接受 Hume 批判，并进一步主张科学中从未真正使用归纳 SEP Karl Popper。他以可证伪性作为科学与非科学的划界标准：全称命题无法被经验证实，但可被单一反例逻辑证伪；科学通过大胆猜想与严峻检验进步，检验结果只提供“corroboration（确证）”而非概率确认。

“Popper is unusual amongst contemporary philosophers in that he accepts the validity of the Humean critique of induction, and indeed, goes beyond it in arguing that induction is never actually used in science.”（SEP §3）

“it is logically impossible to verify a universal proposition by reference to experience (as Hume saw clearly), but a single genuine counter-instance falsifies the corresponding universal law.”（SEP §3）

Popper 的代价是：确证不保证未来可靠性。他后来引入 Tarski 式“verisimilitude（逼真度）”说明科学向真理逼近，但 Miller 与 Tichý（1974）证明该形式定义对假理论失效（比较条件只能在两理论皆为真时满足）。

1.3 Reichenbach：实用辩护收窄问题

Hans Reichenbach 在 Experience and Prediction（1938）与 The Theory of Probability（1949）中把概率解释为极限相对频率，并提出“直规则”（straight rule）：把观察到的相对频率直接当作总体极限频率的估计。他的实用辩护是：如果事件序列存在极限频率，直规则在极限下必收敛到该值；若世界毫无规律，则任何方法都无法预测，因此“如果未来可言说，直规则能带我们到达”。

“Primary or fundamental inductive inference consists of taking observed relative frequencies as probabilities, that is, as limiting relative frequencies. This procedure, referred to as the ‘straight rule’, implies that one should take the current empirical distribution to resemble the limiting distribution.”（SEP Hans Reichenbach §3.2）

“if it is possible to make statements about the future we shall find them by means of this method.”（Reichenbach 1949: 475，转引）

但 SEP 也指出：任何“相对频率 + 一个趋于 0 的修正项”的方法都会收敛，所以直规则并不唯一；且该辩护对有限样本与收敛速度无话可说。Reichenbach 把归纳问题收窄为“在极限频率存在的前提下如何收敛”，并未证明极限频率存在。

1.4 Carnap：把自然齐一性语言化

Rudolf Carnap 在 Logical Foundations of Probability（1950/1962）与 The Continuum of Inductive Methods（1952）中把“概率₁”（确认度）视为逻辑/语义关系，把 Hume 的“自然齐一性”替换为语言框架内的对称性。最简单的确认函数 c* 对每个 structure-description 赋等概率；1952 年的 λ-连续统用参数 λ 调节先验权重与证据权重之比：

\[ c_{\lambda}(\text{individual } s+1 \text{ is } P_j \mid s_j \text{ of first } s \text{ are } P_j) = \frac{s_j + \lambda/k}{s + \lambda}. \]

“The higher the value of λ, the less impact evidence has: induction from what is observed becomes progressively more swamped by a classical-style equal assignment to each of the k possibilities.”（SEP Interpretations of Probability §3.2.1）

Carnap 的方案使“从经验学习”在语言框架内成为分析性要求，但代价明显：语言选择、λ 取值无法由逻辑单独决定；在无限个体语言中，普遍定律的确认度恒为 0；Goodman 的 grue 问题进一步威胁语言依赖方案。

1.5 Mayo：严重检验作为第三条路

Deborah Mayo 与 Aris Spanos（2006）以及 Mayo（2018）把 Neyman-Pearson 的误差概率重新解释为“检验的严格性/探测性”（severity/probativeness）。一个推断被支持，当且仅当该假设通过了严峻检验：若假设为假，检验有很大概率会发现其错误。

“A statistical hypothesis H passes a severe test T with data x₀ if, (S-1) x₀ agrees with H, and (S-2) with very high probability, test T would have produced a result that accords less well with H than x₀ does, if H were false.”（Mayo & Spanos 2006 §1.3）

“In the severe testing view, probability arises in scientific contexts to assess and control how capable methods are at uncovering and avoiding erroneous interpretations of data.”（Mayo 2018 Preface, xii）

严重检验不依赖先验分布，但把“归纳”替换为“方法论的严格探测”。它对“未来会像过去”这一核心问题保持沉默，转而问：在当前方法下，若我的假设为假，我能否发现？

1.6 贝叶斯主义：形式真理与先验问题

现代贝叶斯认识论的核心规范是 Probabilism（置信度符合概率演算）与 Conditionalization（新证据通过条件化更新）SEP Bayesian Epistemology。de Finetti 表示定理说明：若无限序列的联合分布在排列下不变（可交换），则它可写成某个参数分布上的混合，数据在该参数下表现得像 i.i.d. 抽样。

“De Finetti proved a general representation theorem that if the joint probability distribution of an infinite sequence of random variables is assumed to be exchangeable, then it can be written as a mixture of distribution functions from each of which the data behave as if they are independent random draws.”（SEP Problem of Induction §3.3）

“The assumption of exchangeability may be seen as a natural formalization of Hume’s assumption that the past resembles the future.”（SEP Problem of Induction §3.3）

但 Probabilism + Conditionalization alone 无法决定先验分布；不同先验会导致枚举归纳方向相反。

“Probabilism and the Principle of Conditionalization, alone, are too weak to entitle us to say whether one’s credence ought to change inductively or counter-inductively in the above example.”（SEP §1.5）

“So, besides the coherence norms (such as Probabilism), are there any other norms that govern one’s prior? This is known as the problem of the priors.”（SEP §1.5）

主观贝叶斯主义允许任意相干先验；客观贝叶斯主义诉诸无差异原则等约束，但这些原则本身充满争议。贝叶斯方案把归纳问题转化为先验问题，而没有解决它。

二、形式战场：从 NFL 到 Solomonoff

2.1 Wolpert 的 NFL 定理：没有先验偏置就没有平均优势

David Wolpert 在 “The Lack of A Priori Distinctions Between Learning Algorithms”（1996）中证明：在有限输入空间上，对所有可能目标函数取均匀平均时，任意两个学习算法的期望 off-training-set（OTS）误差相等 DOI:10.1162/neco.1996.8.7.1341。Wolpert 与 Macready（1997）把 NFL 推广到优化问题 DOI:10.1109/4235.585893。

“The no free lunch (NFL) theorems … state that … uniformly over all f, E_f{ R̂_X,f^(n)(L_1) − R̂_X,f^(n)(L_2) } = 0.”（教科书对 Wolpert 1996 的转述）

前提包括：有限输入空间；对所有目标函数均匀平均；评价指标为 OTS 期望风险；损失函数同质。结论是：任何两个算法的期望 OTS 性能差为零；若 A 在某类问题上更好，则必存在另一类问题使其更差。

关键边界在于“均匀平均”。一旦对函数空间引入非均匀先验（如偏好光滑、低复杂度、对称等），NFL 不再禁止算法差异。因此 NFL 不是说“所有算法一样好”，而是说“在没有结构假设时，你无法先验地偏好任何算法”。

2.2 Sterkenburg & Grünwald：从“数据驱动”到“模型相对”的辩护

Tom Sterkenburg 与 Peter Grünwald 在 “The No-Free-Lunch Theorems of Supervised Learning”（Synthese 1999:9979–10015, 2021）中澄清：NFL 的悲观结论依赖于把学习算法视为“纯数据驱动”（data-only）的函数；而许多标准算法（如 ERM、交叉验证）实际上是“模型依赖”（model-dependent）的，它们除了数据还需要输入一个模型/假设类作为偏置 arXiv:2202.04513。

“The no-free-lunch theorems promote a skeptical conclusion that all possible machine learning algorithms equally lack justification. But how could this leave room for a learning theory, that shows that some algorithms are better than others? Drawing parallels to the philosophy of induction, we point out that the no-free-lunch results presuppose a conception of learning algorithms as purely data-driven. On this conception, every algorithm must have an inherent inductive bias, that wants justification. We argue that many standard learning algorithms should rather be understood as model-dependent: in each application they also require for input a model, representing a bias. Generic algorithms themselves, they can be given a model-relative justification.”（Sterkenburg & Grünwald 2021 Abstract）

他们还指出，Wolpert 的“所有算法等价”解释依赖于对学习情境的均匀分布假设，而这种均匀分布等价于“学习不可能”的宇宙。

“the uniform concept distribution … in which every possible classification of unseen cases is equally likely … is the definition of a uniformly random universe, in which learning is impossible.”（Rao, Gordon & Spears 1995, p. 475，转引自 Sterkenburg & Grünwald）

因此，一个更弱的、无需均匀分布假设的 NFL 表述是：不存在 universal data-only learning algorithm——任何纯数据驱动的算法都必须在某些情境下失败。

“For any data-only learning algorithm, there exists a learning situation in which this algorithm does not perform well, while in this same situation another data-only learning algorithm does perform well.”（Sterkenburg & Grünwald 2021, §2.5）

2.3 Valiant 的 PAC 框架：在假设类内给出保证

Leslie Valiant 在 “A theory of the learnable”（Communications of the ACM 27(11):1134–1142, 1984）中提出 PAC（Probably Approximately Correct）学习框架 DOI:10.1145/1968.1972。一个概念类是可学习的，当且仅当存在算法，对任意数据分布、任意目标概念，能以高概率学到误差不超过 ε 的假设，且样本量对 1/ε、1/δ 和概念类复杂度多项式增长。

“A theory of the learnable. Commun. ACM, 27:11, 1134-1142.”（Valiant 1984）

PAC 把“可学习性”形式化为模型相对的保证：只要目标确实落在假设类内，并且假设类的容量（VC 维）有限，就存在有限样本算法。它不提供“世界一定简单”的形而上学保证，而是在“问题已被正确建模”的前提下给出边界。

2.4 Blumer 等人：VC 维刻画样本复杂度

Blumer, Ehrenfeucht, Haussler & Warmuth（1989）证明：若概念类 C 的 VC 维为 d，则任何输出一致假设的学习器可用样本量

\[ m(\varepsilon, \delta) = \max\left( \frac{4}{\varepsilon} \log \frac{2}{\delta}, \; \frac{8d}{\varepsilon} \log \frac{13}{\varepsilon} \right) \]

达到误差不超过 ε、置信度 1−δ DOI:10.1145/76359.76371。

“It is shown that the essential condition for distribution-free learnability is finiteness of the Vapnik-Chervonenkis dimension, a simple combinatorial parameter of the class of concepts to be learned. Using this parameter, the complexity and closure properties of learnable classes are analyzed, and the necessary and sufficient conditions are provided for feasible learnability.”（Blumer et al. 1989 Abstract）

Vapnik 与 Chervonenkis（1971）更早证明了经验频率到真实概率的一致收敛 DOI:10.1137/1116025。VC 维把“模型复杂度”操作化为可 shattered 的最大点数，使“简单性”与样本效率产生精确联系。但这一切的前提是：目标概念属于所选假设类，且数据分布没有未被模型捕捉的结构。

2.5 Mitchell：偏置是泛化的必要条件

Tom Mitchell 在 1980 年的技术报告 The Need for Biases in Learning Generalizations 中直接论证：如果一致性是选择假设的唯一标准，学习系统无法对未见过实例做出非任意分类；偏置是泛化的必要条件 PDF。

“If consistency with the training instances is taken as the sole determiner of appropriate generalizations, then a program can never make the inductive leap necessary to classify instances beyond those it has observed. Only if the program has other sources of information, or biases for choosing one generalization over the other, can it non-arbitrarily classify instances beyond those in the training set.”（Mitchell 1980, §1）

“An unbiased generalization system cannot make classifications of instances other than the training instances. An unbiased system is one whose inferences logically follow from the training instances, whereas classifications of the new instances do not logically follow from the classifications of the training instances.”（Mitchell 1980, §3）

Mitchell 把偏置分为：领域知识、预期用途、训练数据来源、对简单/一般性的偏好、类比等。这一分类至今仍是理解机器学习偏置的底层框架。

2.6 Solomonoff 归纳：不可计算的普适预测

Ray Solomonoff 在 “A Formal Theory of Inductive Inference”（Information and Control 7:1–22, 224–254, 1964）中提出：用通用图灵机（UTM）的输入长度来定义序列的“简单性”，并据此分配先验概率——短描述对应高概率 PDF Part I, DOI Part I90223-2), DOI Part II90131-7)。

“A priori probabilities are assigned to strings of symbols by examining the manner in which these strings might be produced by a universal Turing machine. Strings with short and/or numerous ‘descriptions’ … are assigned high a priori probabilities. Strings with long, and/or few descriptions are assigned small a priori probabilities.”（Solomonoff 1964, §2 Introduction）

“On a direct intuitive level, the high a priori probability assigned to a sequence with a short description corresponds to one possible interpretation of ‘Occam’s Razor.’”（Solomonoff 1964, §3）

Solomonoff 预测在数据无限时具有普适收敛性：不同 UTM 的 Solomonoff 先验彼此绝对连续，Blackwell-Dubin 定理保证它们几乎必然在总变差距离下收敛。但存在两个根本限制：

UTM 选择依赖：先验相对于所选 UTM；不同 UTM 在有限数据上给出不同预测。Solomonoff 的支持者常回应说，不同 UTM 在极限下会收敛；但这无法解决有限样本问题。
不可计算：Solomonoff 先验需要对所有程序求和并判断停机，因此不可计算。

Neth（2023）在 Philosophy of Science 中论证，这两个回应相互冲突：可计算近似并不保证相互收敛 DOI:10.1017/psa.2022.72。

“First, the Solomonoff prior is relative to a choice of universal Turing machine. Second, the Solomonoff prior is not computable. … I argue that there is a deep tension between these two responses. This is because different computable approximations to Solomonoff prediction do not always converge.”（Neth 2023 Abstract）

“Either they have to give up universal convergence, which leads to problems of language dependence and subjectivity, or they have to accept that Solomonoff prediction is essentially uncomputable and so cannot be of any help in guiding the inferences of human and artificial agents.”（Neth 2023 Abstract）

2.7 MDL / Occam’s Razor：简单性的操作化

最小描述长度（MDL）与 Rissanen 的随机复杂度把模型选择转化为编码长度问题：在数据给定的情况下，选择总描述长度（模型编码 + 数据在模型下编码）最短的假设。Sterkenburg（2016）在 “Solomonoff Prediction and Occam’s Razor” 中论证，Solomonoff 预测并不能为 Occam’s Razor 提供独立的哲学辩护，因为“简单性”本身已被定义为描述长度 DOI:10.1086/687257。

在统计学习理论中，MDL、VC 界、PAC-Bayes 等可以给出“模型相对”的保证：如果你选择了一个假设类，并且数据确实来自该类中的某个分布，那么可以在有限样本内控制泛化误差。但这些保证都不回答“为什么假设类是对的”。

三、经验战场：深度学习泛化之谜

3.1 Zhang 等人：模型复杂度加显式正则化不够解释泛化

Zhang, Bengio, Hardt, Recht & Vinyals（2017）在 “Understanding deep learning requires rethinking generalization” 中通过系统实验表明：SOTA 卷积网络能轻易拟合随机标签和随机像素输入；显式正则化（weight decay、dropout、data augmentation）对这一现象只有定性影响 arXiv:1611.03530。

“Through extensive systematic experiments, we show how these traditional approaches fail to explain why large neural networks generalize well in practice. Specifically, our experiments establish that state-of-the-art convolutional networks for image classification trained with stochastic gradient methods easily fit a random labeling of the training data. This phenomenon is qualitatively unaffected by explicit regularization, and occurs even if we replace the true images by completely unstructured random noise.”（Zhang et al. 2017 Abstract）

他们还给出理论构造：两层 ReLU 网络在参数数 p = 2n + d 时即可对任意 n 个 d 维样本实现任意标签。这说明“模型族复杂度 + 显式正则化”不是泛化的充分解释，但并不直接刻画 SGD 具体偏好哪类函数。

3.2 双下降与有效模型复杂度

Belkin, Hsu, Ma & Mandal（2019）提出“双下降”风险曲线：模型容量超过插值阈值后，测试风险再次下降，从而调和现代实践“越大越好”与经典理论的矛盾 DOI:10.1073/pnas.1903070116。

“The main finding of this work is a pattern for how performance on unseen data depends on model capacity and the mechanism underlying its emergence. … This dependence, empirically witnessed with important model classes including neural networks and a range of datasets, is summarized in the ‘double descent’ risk curve shown in Figure 1(b).”（Belkin et al. 2019）

Nakkiran 等人（2020/2021）进一步发现双下降不仅随模型容量出现，还随训练轮数（epoch-wise double descent）和样本量（sample non-monotonicity）出现；他们定义“有效模型复杂度（EMC）”统一三类现象 arXiv:1912.02292, DOI:10.1088/1742-5468/ac3a74。

“We show that double descent occurs not just as a function of model size, but also as a function of the number of training epochs. We unify the above phenomena by defining a new complexity measure we call the effective model complexity and conjecture a generalized double descent with respect to this measure.”（Nakkiran et al. 2020）

3.3 良性过拟合与三分法

Bartlett, Long, Lugosi & Tsigler（2020）在高维线性回归中给出最小范数插值解的泛化误差刻画：当数据协方差 Σ 的低方差方向有效秩显著超过样本量时，即使完美拟合含噪训练数据，预测误差仍可接近最优 DOI:10.1073/pnas.1907378117。

“We give a characterization of linear regression problems for which the minimum norm interpolating prediction rule has near-optimal prediction accuracy. The characterization is in terms of two notions of the effective rank of the data covariance. It shows that overparameterization is essential for benign overfitting in this setting.”（Bartlett et al. 2020）

Mallinar 等人（2022）进一步提出过拟合三分法：良性（渐近 Bayes 最优）、tempered（渐近风险有限但高于 Bayes）、灾难性（风险发散），并发现实际训练到插值的深度网络多为 tempered arXiv:2207.06569。

“We first explore this phenomenon in the context of kernel (ridge) regression (KR) by obtaining conditions on the ridge parameter and kernel eigenspectrum under which KR exhibits each of the three behaviors. We find that kernels with power-law spectra, including Laplace kernels and ReLU neural tangent kernels, exhibit tempered overfitting.”（Mallinar et al. 2022）

3.4 Grokking：记忆到泛化的尖锐转换

Power 等人（2022）发现，在小规模算法数据集（模运算表）上训练 Transformer，网络会先完美记忆训练集但验证准确率接近随机，经过远多于记忆所需步数后突然跳到完美泛化；数据越少，泛化所需优化步数增长越快 arXiv:2201.02177。

“In some situations we show that neural networks learn through a process of ‘grokking’ a pattern in the data, improving generalization performance from random chance level to perfect generalization, and that this improvement in generalization can happen well past the point of overfitting.”（Power et al. 2022）

后续研究给出不同解释：Rubin, Seroussi & Ringel（2024）将其映射为一阶相变 arXiv:2310.03789；Kumar 等人（2024）将其解释为 lazy → rich 的特征学习转换 arXiv:2310.06110；Lyu 等人（2024）用齐次网络早期/晚期隐式偏置二分严格证明 grokking 可在简单网络上出现 arXiv:2311.18817。Zhang, Shang, Yang & Zhang（2025）则把 grokking 框架为“计算玻璃弛豫”，挑战一阶相变解释 arXiv:2505.11411。当前 grokking 的物理/几何解释并存且部分冲突，尚未统一。

3.5 隐式偏置：核心但易受质疑

Soudry 等人（2018）证明：在线性可分数据上，无正则化逻辑回归配合梯度下降，参数方向收敛到 ℓ2 最大间隔分类器 JMLR 19(70):1–57, arXiv:1710.10345。

“we show that even without any explicit regularization, for all linearly separable datasets, when minimizing logistic regression problems using gradient descent, we have that w(t)/||w(t)|| converges to the L2 maximum margin separator, i.e. to the solution of the hard margin SVM for homogeneous linear predictors.”（Soudry et al. 2018）

Neyshabur, Tomioka & Srebro（2015）研究范数容量控制，发现 per-unit ℓ1 正则可实现 size-independent 容量控制，但深度导致指数依赖 PMLR v40。

但隐式偏置解释面临多个反例：

Dinh 等人（2017）：对 ReLU 网络，利用对称性可以把平坦极小值重参数化为任意尖锐的等价极小值，因此常见 flatness 定义不能直接解释泛化 arXiv:1703.04933。
Geiping 等人（2021/2022）：全批量训练在现代架构上可达到与 SGD 相当的泛化，说明 SGD 噪声并非必要 arXiv:2109.14119。
Nagarajan & Kolter（2019）、Razin & Cohen（2020）、Chiang 等人（2023） 等进一步质疑一致收敛框架与范数解释（这些文献全文未逐字核对，仅作为待核线索）。

3.6 Lottery Ticket 与 NTK：两个边界条件

Frankle & Carbin（2019）的彩票假设表明，稠密随机初始化网络中存在“中奖子网络”，单独训练时能在相同迭代次数内达到与原网络相当的测试精度 arXiv:1803.03635。Jacot, Gabriel & Hongler（2018）的神经正切核（NTK）理论说明，无限宽度网络在 lazy 区等价于核方法 arXiv:1806.07572。

两者都是边界条件：LTH 说明初始化与稀疏结构共同决定可训练性，但其在极大规模预训练中的适用范围仍受限；NTK 解释无限宽度 lazy 区，但真实深度网络的特征学习发生在离开 lazy 区之后。

四、世界战场：结构假设与过度外推

4.1 NFL 之后必须引入世界结构

Wolpert 的 NFL 定理说明：若对目标函数不加结构假设，所有算法在平均意义下等价。因此，要谈泛化，必须先假设目标不是最坏情况。但“世界有结构”不是循环论证的空话，而是获得泛化保证的必要前提。

真实数据分布通常具有低维流形、对称/等变、组合性、幂律谱等结构。这些结构能够打破 NFL 的均匀平均，使特定算法优于随机猜测。但它们本身不等于泛化保证：PAC/VC 告诉我们，即使假设类有限，也需要数据分布与目标匹配、训练算法能找到好的假设。

4.2 流形假设：可检验但非严格

Fefferman, Mitter & Narayanan（2016）首次给出“流形假设”的严格统计检验框架：给定 i.i.d. 样本，可以在样本复杂度仅依赖内蕴维度 d、体积 V、reach τ，而不依赖环境维度 p 的情况下，判断数据是否落在某个低维流形附近 arXiv:1310.0425, DOI:10.1090/jams/852。

“We show that it is possible to test the manifold hypothesis … the sample complexity of the test depends only on the intrinsic dimension, volume, and reach of the manifold, and not on the ambient dimension.”（Fefferman et al. 2016 Abstract）

Tenenbaum, de Silva & Langford（2000）的 Isomap 为“高维数据位于低维流形上”提供了早期经验算法 DOI:10.1126/science.290.5500.2319。但真实数据可能是有奇点、多尺度或分形结构，“流形”只是统计近似。

4.3 对称与等变：最干净的结构→泛化链路

Cohen & Welling（2016）把卷积从平移群推广到任意离散群，提出 G-CNN，利用对称性提升统计效率 PMLR v48。

Elesedy & Zaidi（2021）在线性模型中首次对等变/不变模型给出非零、严格的泛化增益定量定理：强制等变性会降低有效参数维度，从而降低期望测试误差 PMLR v139, arXiv:2102.10333。

“we prove that equivariant/invariant models strictly outperform generic models, in terms of expected test error, on a broad class of learning problems with group symmetries.”（Elesedy & Zaidi 2021 Abstract）

这是世界结构与模型偏置协同的清晰例子：前提是目标确实具有该对称性；若目标并不真正等变，强制等变会带来近似误差。

4.4 组合性：局部成功与系统性失败并存

Lake & Baroni（2018）的 SCAN 数据集显示，标准 seq2seq 在随机拆分上可达 99.7%，但在需要组合泛化的 add-jump 拆分上最佳模型仅 1.2% PDF。Kim & Linzen（2020）的 COGS 基准显示，Transformer 在分布内准确率 96%，但泛化集仅 35% arXiv:2010.05465, ACL Anthology。

“In experiments with Transformers and LSTMs, we found that in-distribution accuracy on the COGS test set was near-perfect (96–99%), but generalization accuracy was substantially lower (16–35%).”（Kim & Linzen 2020）

LLM 在更大规模上表现出部分组合能力，但“是学到了组合规则还是记住了大量子图模式”仍无定论。组合性是标准神经网络并不自动获得的偏置。

4.5 Scaling Laws：经验稳健但机制多解

Kaplan 等人（2020）首次系统报告大型语言模型的测试损失随模型规模 N、数据量 D、计算量 C 呈幂律下降，跨 7+ 数量级 arXiv:2001.08361。Hoffmann 等人（2022）的 Chinchilla 工作修正了最优 N/D 配比，指出在固定计算预算下两者应大致等比例增长 arXiv:2203.15556。

Bahri 等人（2024）指出，当数据协方差矩阵具有幂律谱时，核回归/随机特征模型会呈现出幂律学习曲线，把 scaling laws 联系到数据谱的衰减 DOI:10.1073/pnas.2311878121。

“We identify variance-limited and resolution-limited scaling behavior for both dataset and model size, for a total of four scaling regimes. … The resolution-limited regime can be explained by positing that models are effectively resolving a smooth data manifold.”（Bahri et al. 2024）

但 scaling laws 是经验上稳健的唯象律，幂律身份很少被严格统计检验，指数普适性未确立，受数据质量、任务定义、度量方式影响。把它外推为“无限 scaling 通向 AGI”是过度推断。

4.6 Natural Abstractions：研究纲领而非已立理论

Chan, Lang & Jenner（2023）对 John Wentworth 的 Natural Abstractions 议程进行系统梳理，区分 Universality Hypothesis（不同认知系统学到相似抽象）与 Redundant Information Hypothesis（自然抽象可用冗余/守恒信息函数刻画），并指出多个理论缺口 LessWrong, PDF。

“There are no selection theorems implying any form of the Universality Hypothesis (Claim 1) yet. None of the results show any discreteness of natural abstractions (Claim 1b). The theorems don’t show that redundant information abstractions are low-dimensional (Claim 2c).”（Chan et al. 2023）

natural abstractions 与物理中的有效理论、信息瓶颈、因果抽象有概念联系，但尚不能作为世界结构的硬证据。

五、红队：误读、循环论证与过度外推

5.1 NFL 的常见误读

NFL 定理常被误读为“所有算法一样好”或“AI 研究无用”。Wolpert 本人在 “What the NFL theorems really mean”（2013）中澄清：NFL 只是在施加具体问题概率结构之前，算法平均性能无差别；真正重要的是“imposed probability distributions of a particular context” DOI:10.1145/2555235.2555237。

“while the NFL theorems have strong implications—if one believes in a uniform distribution over optimization problems—in no sense should they be interpreted as advocating such a distribution.”（Wolpert 2013）

Goldblum 等人（2023）进一步指出：虽然 NFL 常被用来论证“每个问题都需要专门归纳偏置”，但几乎所有均匀采样得到的数据集都具有高复杂度，而真实世界问题 disproportionately 生成低复杂度数据；神经网络架构本身也偏好低复杂度 arXiv:2304.05366。

5.2 隐式偏置不是唯一解释

第 3.5 节已列出多个反例。这里再次强调：把深度学习的泛化功劳单独归于 SGD 的隐式偏置证据不足。Geiping 等人（2021/2022）的全批量实验、Dinh 等人（2017）对 flatness 的对称性破坏，都说明架构、数据、显式正则化、优化调参共同作用。

5.3 “世界有规律”的解释循环

SEP The Problem of Induction §3.4 明确将 NFL 定理视为休谟第一角的计算机科学版本：

“The idea is also given formal expression in the so-called ‘No-Free-Lunch theorems’ (Wolpert 1992, 1996, 1997). These can be interpreted as versions of the argument in Hume’s first fork since they establish that there can be no contradiction in the algorithm not performing well, since there are a priori possible situations in which it does not.”（SEP §3.4）

Andrews（2024）从科学哲学角度指出：ML 泛化必须以“世界有结构/有规律”为前提，但这条前提本身既是经验发现也是理论预设；数据本身永远理论负载，测量与标注过程都会注入规律性 PMC11573791。

“The world is structured. It contains regularity. All natural data, therefore, contain some measure of regularity. We have to work very hard to produce data containing no learnable regularity.”（Andrews 2024）

这构成一个弱循环：不是逻辑上的严格循环论证，而是解释上的退行。NFL 的批评价值在于限制过度泛化——禁止从“算法在若干任务上成功”跳到“算法普遍有效”——但不禁止在特定问题结构下的有效学习。

5.4 贝叶斯 / Solomonoff 先验的困境

贝叶斯方案把归纳问题转化为先验问题。Gelman & Shalizi（2013）反对“贝叶斯 = 主观归纳信念更新”的标准哲学，主张贝叶斯数据分析应置于误差统计/假说演绎框架：先验不是个人信念，而是模型假设的一部分；模型是可检验的 DOI:10.1111/j.2044-8317.2011.02037.x。

“We view Bayesian data analysis—the iterative process of model building, posterior inference, and model checking—as fitting well within an error-statistics or hypothetico-deductive philosophy of science, with posterior inference playing the role of ‘normal science,’ model checking allowing falsification, and model building providing the potential for progress in normal science.”（Gelman & Shalizi 2013）

“We do not think of a Bayesian prior distribution as a personal belief; rather, it is part of a hypothesized model, which we posit as potentially useful and abandon to the extent that it is not.”（Gelman & Shalizi 2013）

Solomonoff 先验同时面临 UTM 选择依赖与不可计算问题（第 2.6 节）。Neth（2023）论证这两个回应相互冲突：可计算近似破坏普适收敛，不可计算则无法成为 AI/科学的操作基础。

5.5 AGI 与“涌现能力”：幻觉还是指标产物？

Shane Legg 与 Marcus Hutter（2007）在 “Universal Intelligence: A Definition of Machine Intelligence” 中把智能定义为“在广泛环境中实现目标的能力”，并把它与 AIXI 等普适最优学习代理联系起来 arXiv:0712.3329。Hutter（2000/2005）的 AIXI 框架把 Solomonoff 归纳与序贯决策理论结合，给出理论上最优但不可计算的通用智能 arXiv:cs/0004001, Springer 2005。

“Intelligence measures an agent’s ability to achieve goals in a wide range of environments.”（Legg & Hutter 2007）

Richard Sutton 在 “The Bitter Lesson”（2019）中主张，AI 研究的长期进步来自利用可扩展计算的一般方法（如搜索与学习），而非人类知识的手工编码 Sutton 博客。

“The biggest lesson that can be read from 70 years of AI research is that general methods that leverage computation are ultimately the most effective, and by a large margin.”（Sutton 2019）

但 Melanie Mitchell（2021）在 “Why AI is Harder Than We Think” 中警告 AI 研究中的四种谬误：

窄智能与通用智能在同一连续统上；
容易的事容易、困难的事困难（忽视 Moravec 悖论）；
愿望性 mnemonic（用人类智能词汇命名程序）；
智能全在大脑中（忽视具身认知与社会性）。

“The four fallacies I have described reveal flaws in our conceptualizations of the current state of AI and our limited intuitions about the nature of intelligence.”（Mitchell 2021）

Schaeffer 等人（2023）对“涌现能力”的研究进一步削弱“规模必然带来新能力”的叙事。他们指出，大语言模型中许多所谓“涌现能力”（突然出现、不可预测）是研究者所选非线性/不连续度量造成的假象；换用线性或连续度量后，性能随规模平滑变化 arXiv:2304.15004。

“we present an alternative explanation for emergent abilities: that for a particular task and model family, when analyzing fixed model outputs, emergent abilities appear due the researcher’s choice of metric rather than due to fundamental changes in model behavior with scale.”（Schaeffer et al. 2023 Abstract）

“we provide evidence that alleged emergent abilities evaporate with different metrics or with better statistics, and may not be a fundamental property of scaling AI models.”（Schaeffer et al. 2023 Abstract）

这些工作共同说明：DL 成功不能推出“世界简单”或“规模必然通向 AGI”。涌现叙事需要更谨慎的指标、统计与机制分析。

六、裁决：三足鼎立与诚实缺口

6.1 三足鼎立的裁决

综合哲学史、形式定理、深度学习经验与世界结构证据，最稳健的结论是：

归纳泛化需要“形式约束 + 隐式偏置 + 世界结构”三足鼎立。

支柱	角色	关键形式/经验资源
形式约束	划定可学习性边界；把“额外假设不可避免”形式化	Hume/PAC/VC/NFL/Solomonoff/MDL；模型类、VC 维、先验、正则化
隐式偏置	在欠定问题中选择具体解；连接训练误差与测试误差	SGD、初始化、架构、训练动力学；max-margin、特征学习、grokking
世界结构	打破 NFL 的均匀平均；使某些偏置在真实分布上更好	低维流形、对称/等变、幂律谱、组合性（部分）

三者相互依赖：没有形式约束，我们无法谈论可学习性；没有隐式偏置，表达能力过强的模型会在训练集上任意插值；没有世界结构，任何偏置都只是某种先验，无法解释为什么在真实任务上确实有效。

6.2 对各方的红队限定

对 NFL 虚无主义：NFL 不是说“机器学习无法泛化”，而是说“没有偏置就无法保证泛化”。真实数据分布通常不是最坏情况，特定算法可以优于随机。
对深度学习的过度推销：DNN 能拟合随机标签，说明表达能力不是泛化的解释；双下降、grokking 等现象说明经典图景失效，但隐式偏置机制尚未闭合。
对世界结构循环论证：世界结构是必要前提，但“模型泛化好是因为世界有规律”容易滑入解释退行。必须用新数据、分布外测试、因果干预来检验结构假设，而非用成功反推。
对贝叶斯/Solomonoff 普适主义：先验问题与不可计算问题没有被取消。在实践中，模型与先验是可检验的假设，而非无争议的理性基础。
对 AGI/涌现叙事：涌现能力可以用指标选择解释；窄任务成功不等于通用智能；规模是必要条件，但不是充分条件。

6.3 诚实缺口

一手文献未全部细读：Hume / Popper / Reichenbach / Carnap 的关键段落依赖 SEP 与二手综述；Nagarajan & Kolter 2019、Razin & Cohen 2020、Chiang et al. 2023 全文未逐字核对；Wolpert 1996 原始证明细节依赖教科书转述。
数学边界待进一步核实：Bartlett 2020 有效秩的常数依赖；Mallinar 2022 universality 假设；Lyu 2024 misgrokking 条件；Solomonoff semi-measure / normalized measure 对收敛的影响。
概念操作化较弱：Goldblum 2023 用 Kolmogorov 复杂度度量“真实世界问题的低复杂度偏好”在经验上可检验性有限；natural abstractions 的多个子假设缺乏定理。
经验外推缺口：grokking 的 toy 任务与真实任务迁移关系未建立；LTH 在 GPT-scale 预训练中的有效性尚无系统证据；NTK 对有限宽度 Transformer 仅近似成立；组合性在真实自然语言中的因果机制仍缺乏系统性证据。
scaling laws 的物理地位：幂律身份未严格检验，指数第一性原理来源未确立，真实 LLM 数据协方差谱与 scaling 指数的定量关系未闭合。

七、Codex 审核与修正（2026-06-26 追加）

7.1 总裁决保留，但若干表述需要降权

本轮审核不推翻主裁决：机器学习泛化仍应理解为“形式约束 + 隐式偏置 + 世界结构”的三足鼎立。但原报告中有几处容易被读成“定论更硬”“外推更强”的地方，需要加边界。修正后的口径是：三足鼎立是一套高质量整合框架，不是学界统一定理；它适合做总入口，但不能替代各子领域的精确定理与实验证据。

7.2 Valiant / PAC 的历史边界

原报告写“Valiant 的 PAC 框架”作为简写可以接受，但需要更精确：Valiant 1984 开创的是“可学习理论 / PAC 传统”的源头，和后来教科书中的标准 PAC 表述并不完全等同。现代常见的“i.i.d. 正负例 + 双边 0-1 错误 + VC 维刻画样本复杂度”的形式，是 Valiant 之后经 VC 理论、Blumer 等工作进一步标准化的结果。

因此应读成：

Valiant 1984：提出“可学习性可以被概率、近似正确和计算复杂度形式化”的纲领性突破；
VC / Blumer 等后续工作：给出分布无关 PAC 学习中假设类复杂度、样本复杂度和 VC 维之间的经典连接；
不能读成：现代 PAC/VC 理论在 1984 一步到位。

7.3 VC 样本复杂度公式不是通用泛化公式

报告引用 Blumer 等人的样本复杂度上界有代表性，但它依赖特定前提：目标概念在假设类内、样本 i.i.d.、学习器输出一致假设、主要处在可实现（realizable）分类设置。它适合作为“有限 VC 维带来有限样本保证”的经典例子，不应被读成所有机器学习任务的统一样本复杂度公式。

更稳妥的写法是：VC 理论证明了容量受控假设类可以获得分布无关泛化保证，但具体界的形式、常数和适用条件随任务设置而变。

7.4 “世界结构”应从“低维流形”放宽为“低复杂度 / 可压缩结构”

原报告把流形、对称、组合性、幂律谱并列为世界结构，这是合理的。但“真实数据分布通常具有低维流形”容易读得过强。更准确应写为：真实数据常常具有低复杂度、局部连续、多尺度、对称、稀疏因果或可压缩结构；低维光滑流形只是其中一种重要近似。

原因是：真实语言、社会数据、生物数据和视觉数据未必严格落在光滑低维流形上，它们可能有离散结构、奇点、分形/多尺度结构、混合分布、长尾和强上下文依赖。因此“流形假设”应保留为可检验候选，而不是世界结构的总名。

7.5 Schaeffer 的“涌现幻象”不能推出一切涌现皆假

Schaeffer 等人关于 LLM 涌现能力的工作，最稳妥支持的是：许多看似突然出现的能力，可能由非线性 / 不连续评估指标和统计处理造成。 但它不证明所有涌现能力都是幻象，也不取消物理、复杂系统和 AI 中“有效涌现”的解释价值。

修正后的红线是：

可以用 Schaeffer 反对“规模一到，能力神秘跳出”的神话；
不能用 Schaeffer 反对所有层级现象、相变式转变或宏观有效描述；
与我们此前“涌现、量变质变与 AI 涌现幻象”篇一致：命名式涌现要红队，有效涌现仍然成立。

7.6 “规模是必要条件”只限当前深度学习路线

原报告写“规模是必要条件，但不是充分条件”时，容易被理解成对所有通用智能的逻辑断言。更准确应改成：对当前大模型 / scaling 路线而言，规模、数据和计算是关键条件；但对广义智能或 AGI，规模不是逻辑上的必要条件，更不是充分条件。

这一区分很重要：

Sutton 的“苦涩教训”支持“可扩展方法长期很强”；
scaling laws 支持“当前深度学习路线中规模非常重要”；
但二者都不能推出“只要继续放大就必然 AGI”，也不能排除具身、因果、主动学习、记忆、工具使用、社会交互等非纯规模因素。

7.7 Solomonoff 与 Natural Abstractions 继续降为“理论灯塔 / 研究纲领”

Solomonoff 归纳的哲学价值很高，因为它把奥卡姆剃刀和算法复杂度接起来；但不可计算性和 UTM / 先验依赖使它不能直接充当现实 AI 的操作基础。更稳口径：Solomonoff 是归纳理论的理想上限和认识论灯塔，不是工程算法。

Natural abstractions 同样应降权：它很适合连接“世界结构、有效理论、信息瓶颈、因果抽象、不同认知系统是否学到相似概念”，但目前仍是研究纲领。universality、discreteness、low-dimensionality 等关键主张尚未有足够强的定理和实验证据支撑。

7.8 Goodman 的 grue 问题应补为缺口

本报告的哲学战场覆盖 Hume、Popper、Reichenbach、Carnap、Mayo 和贝叶斯主义，但 Goodman 的新归纳之谜应放得更显眼。它问的是：为什么“绿色”是可投射谓词，而“grue（某时点前绿、之后蓝）”不是？这直接对应机器学习里的一个核心问题：

哪些特征、谓词、抽象和数据切分具有样本外可投射性？

这比单纯说“世界有结构”更锋利。机器学习泛化失败，很多时候不是因为模型没发现规律，而是发现了训练分布里“可用但不可投射”的伪规律。Goodman 问题可作为后续补强本报告的哲学接口。

7.9 修正后的落点

修正后，本篇应被定位为归纳 / 泛化 / 世界结构 / AI 外推的总入口报告，而不是任何一个子领域的最终报告。它的主结论仍保留：

泛化不是免费发生的；学习系统必须带偏置，世界必须有可投射结构，训练过程必须把模型推向可迁移解。

但所有强外推都要加脚注：

PAC/VC 是条件性保证，不是现实世界必可学的证明；
深度学习泛化机制尚未闭合；
世界结构是必要假设，但不能用成功泛化反推出结构真实；
scaling laws 是强经验规律，不是 AGI 必然性定理；
Solomonoff / natural abstractions 是理论灯塔，不是已落地机制。

参考来源

哲学与认识论

Hume, D. (1748). An Enquiry Concerning Human Understanding. §4.2. SEP The Problem of Induction
Hume, D. (1739). A Treatise of Human Nature. 1.3.6.
Popper, K. (1934/1959). Logik der Forschung / The Logic of Scientific Discovery. SEP Karl Popper
Reichenbach, H. (1938). Experience and Prediction; (1949). The Theory of Probability. SEP Hans Reichenbach
Carnap, R. (1950/1962). Logical Foundations of Probability; (1952). The Continuum of Inductive Methods. SEP Rudolf Carnap
Mayo, D. G., & Spanos, A. (2006). Severe testing as a basic concept in a Neyman–Pearson philosophy of induction. BJPS 57(2):323–357. PDF
Mayo, D. G. (2018). Statistical Inference as Severe Testing. CUP.
SEP Bayesian Epistemology. https://plato.stanford.edu/entries/epistemology-bayesian/
Gelman, A., & Shalizi, C. R. (2013). Philosophy and the practice of Bayesian statistics. BJMSP 66(1):8–38. DOI
Gelman, A., & Hennig, C. (2017). Beyond subjective and objective in statistics. JRSSA 180(4):967–1033. DOI

形式学习理论与 NFL

Wolpert, D. H. (1996). The lack of a priori distinctions between learning algorithms. Neural Computation 8(7):1341–1390. DOI
Wolpert, D. H., & Macready, W. G. (1997). No free lunch theorems for optimization. IEEE TEVC 1(1):67–82. DOI
Wolpert, D. H. (2013). What the NFL theorems really mean. Ubiquity 2013(December):1–15. DOI
Sterkenburg, T. F., & Grünwald, P. D. (2021). The no-free-lunch theorems of supervised learning. Synthese 199:9979–10015. DOI, arXiv
Valiant, L. G. (1984). A theory of the learnable. CACM 27(11):1134–1142. DOI
Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K. (1989). Learnability and the Vapnik-Chervonenkis dimension. JACM 36(4):929–965. DOI
Vapnik, V. N., & Chervonenkis, A. Ya. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory of Probability & Its Applications 16(2):264–280. DOI
Mitchell, T. M. (1980). The need for biases in learning generalizations. Rutgers CS tech report CBM-TR-117. PDF
Solomonoff, R. J. (1964). A formal theory of inductive inference. Information and Control 7:1–22, 224–254. PDF Part I, DOI Part I90223-2), DOI Part II90131-7)
Neth, S. (2023). A dilemma for Solomonoff prediction. Philosophy of Science 90(2):288–306. DOI
Sterkenburg, T. F. (2016). Solomonoff prediction and Occam’s razor. Philosophy of Science 83(4):459–479. DOI

深度学习泛化

Zhang, C., Bengio, S., Hardt, M., Recht, B., & Vinyals, O. (2017). Understanding deep learning requires rethinking generalization. ICLR. arXiv
Belkin, M., Hsu, D., Ma, S., & Mandal, S. (2019). Reconciling modern machine-learning practice and the classical bias–variance trade-off. PNAS 116(32):15849–15854. DOI, arXiv
Nakkiran, P., Kaplun, G., Bansal, Y., Yang, T., Barak, B., & Sutskever, I. (2020/2021). Deep double descent. ICLR 2020; JSTAT 2021(12):124003. arXiv, DOI
Bartlett, P. L., Long, P. M., Lugosi, G., & Tsigler, A. (2020). Benign overfitting in linear regression. PNAS 117(48):30063–30070. DOI, arXiv
Mallinar, N., et al. (2022). Benign, tempered, or catastrophic: A taxonomy of overfitting. NeurIPS. arXiv
Power, A., et al. (2022). Grokking: Generalization beyond overfitting on small algorithmic datasets. ICLR MATH-AI Workshop. arXiv
Rubin, N., Seroussi, I., & Ringel, Z. (2024). Grokking as a first order phase transition in two layer networks. ICLR. arXiv
Kumar, T., Bordelon, B., Gershman, S. J., & Pehlevan, C. (2024). Grokking as the transition from lazy to rich training dynamics. ICLR. arXiv
Lyu, K., et al. (2024). Dichotomy of early and late phase implicit biases can provably induce grokking. ICLR. arXiv
Zhang, X., Shang, Y., Yang, E., & Zhang, G. (2025). Is grokking a computational glass relaxation? NeurIPS Spotlight. arXiv
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., & Srebro, N. (2018). The implicit bias of gradient descent on separable data. JMLR 19(70):1–57. PDF, arXiv
Neyshabur, B., Tomioka, R., & Srebro, N. (2015). Norm-based capacity control in neural networks. COLT. PDF
Dinh, L., Pascanu, R., Bengio, S., & Bengio, Y. (2017). Sharp minima can generalize for deep nets. ICML. arXiv
Geiping, J., Goldblum, M., Pope, P. E., Moeller, M., & Goldstein, T. (2022). Stochastic training is not necessary for generalization. ICLR. arXiv
Nagarajan, V., & Kolter, J. Z. (2019). Uniform convergence may be unable to explain generalization in deep learning. NeurIPS. arXiv
Razin, A., & Cohen, N. (2020). Implicit regularization in deep learning may not be explainable by norms. NeurIPS. arXiv
Chiang, P.-Y., et al. (2023). Loss landscapes are all you need: Neural network generalization can be explained without the implicit bias of gradient descent. ICLR. arXiv
Frankle, J., & Carbin, M. (2019). The lottery ticket hypothesis. ICLR. arXiv
Jacot, A., Gabriel, F., & Hongler, C. (2018). Neural tangent kernel: Convergence and generalization in neural networks. NeurIPS. arXiv

世界结构与涌现

Fefferman, C., Mitter, S., & Narayanan, H. (2016). Testing the manifold hypothesis. JAMS. arXiv, DOI
Tenenbaum, J. B., de Silva, V., & Langford, J. C. (2000). A global geometric framework for nonlinear dimensionality reduction. Science 290(5500):2319–2323. DOI
Cohen, T., & Welling, M. (2016). Group equivariant convolutional networks. ICML. PMLR
Elesedy, B., & Zaidi, S. (2021). Provably strict generalisation benefit for equivariant models. ICML. arXiv, PMLR
Lake, B., & Baroni, M. (2018). Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks. ICML. PDF
Kim, N., & Linzen, T. (2020). COGS: A compositional generalization challenge based on semantic interpretation. EMNLP. arXiv, ACL Anthology
Lin, H. W., Tegmark, M., & Rolnick, D. (2017). Why does deep and cheap learning work so well? J. Stat. Phys. 168(6):1223–1247. arXiv, DOI
Kaplan, J., et al. (2020). Scaling laws for neural language models. arXiv:2001.08361
Hoffmann, J., et al. (2022). Training compute-optimal large language models. arXiv:2203.15556
Bahri, Y., et al. (2024). Explaining neural scaling laws. PNAS 121(27). DOI
Chan, L., Lang, L., & Jenner, E. (2023). Natural abstractions: Key claims, theorems, and critiques. LessWrong, PDF

AGI / 通用智能 / 涌现批判

Legg, S., & Hutter, M. (2007). Universal intelligence: A definition of machine intelligence. arXiv:0712.3329
Hutter, M. (2000/2005). Universal Artificial Intelligence: Sequential Decisions Based on Algorithmic Probability. Springer. arXiv:cs/0004001, DOI
Sutton, R. (2019). The Bitter Lesson. http://www.incompleteideas.net/IncIdeas/BitterLesson.html
Mitchell, M. (2021). Why AI is harder than we think. arXiv:2104.12871. arXiv
Schaeffer, R., et al. (2023). Are emergent abilities of large language models a mirage? arXiv:2304.15004
Andrews, M. (2024). The reanimation of pseudoscience in machine learning and its ethical repercussions. Patterns 5(3). PMC
Goldblum, M., et al. (2023). No Free Lunch in Neural Architecture Search? arXiv:2304.05366