念
No Free Lunch 定理
No Free Lunch — 不存在在所有问题上都优于其他算法的”通用”学习算法
在所有逻辑可能数据序列上取均匀分布，任何学习算法的泛化误差期望 = 1/2（等于随机猜测）。这是休谟归纳问题第一角的精确数学化身：无法先验证明任何算法的泛化能力。Wolpert 1992/1996。
NFL ↔ 休谟归纳问题
休谟第一角归纳结论的否定不构成矛盾——存在自然进程改变的可能世界
⟺
NFL 定理存在算法失败的数据序列——无法先验论证任何算法的泛化能力
直接推论：归纳偏置不可回避 贝叶斯先验 先验概率选择 = 学习算法的归纳偏置——两者结构同构 PAC 学习 在特定假设类上有样本复杂度保证——模型相对辩护仍然可能 缩放定律 预测力依赖特定分布假设——NFL 提醒：这些假设可能失效 误差级联 多步推理中归纳偏置不匹配被级联放大
→ Induction Problem · Bayesian Induction · Scaling LawsWolpert (1996)
No Free Lunch 定理
定义
No Free Lunch（NFL）定理是机器学习中的一组基础性不可能性结果：在所有逻辑可能的数据序列上取均匀分布，任何学习算法的泛化误差期望值为 1/2——不比随机猜测好（Wolpert 1992, 1996, 1997）。换言之，不存在在所有问题上都优于其他算法的”通用”学习算法。
与归纳问题的关系
- 休谟第一角：归纳结论的否定不构成矛盾——存在自然进程改变的可能世界。因此先验推理无法建立归纳。
- NFL 定理：存在算法失败的数据序列（先验可能的情况）——因此无法先验地论证任何算法的泛化能力。
结构完全同构：两者都表明，在不排除任何可能性的前提下，无法建立从过去到未来的保证。
归纳偏置的不可回避
NFL 定理的直接推论：有效的学习算法必须具有”归纳偏置”（inductive bias）——关于问题域的先验假设，限制了搜索空间（Mitchell 1997）。
这在哲学上等价于承认：
模型相对辩护
NFL 排除的是普遍的、模型无关的辩护。但模型相对的（model-relative）学习保证仍然可能：
- 给定特定先验和模型假设，贝叶斯算法的收敛性可被证明
- PAC 学习理论给出在特定假设类上的样本复杂度保证
- 形式学习理论证明特定方法在特定假设空间中最优收敛
这就是哲学上的”部分解”——不是证明归纳总是可靠，而是证明在特定假设下的特定归纳方法是最优的。
与本 wiki 其他概念的关系
- 归纳问题：NFL 是归纳问题的数学形式化
- 贝叶斯归纳：NFL 解释了为什么先验概率不可回避
- 齐一性原则：归纳偏置是 UP 的工程化身
- 缩放定律：缩放定律的预测力依赖于特定的分布假设，NFL 提醒我们这些假设可能失效
- 误差级联：多步推理中每步的归纳偏置不匹配会被级联放大
References
- Wolpert, D. H., 1996, “The lack of a priori distinctions between learning algorithms”, Neural Computation, 8: 1341–1390.
- Wolpert, D. H., 1997, “No free lunch theorems for optimization”, IEEE Transactions on Evolutionary Computation, 1: 67–82.
- Mitchell, Tom, 1997, Machine Learning, McGraw-Hill.
- Sterkenburg, Tom and Peter Grünwald, 2021, “The no-free-lunch theorems of supervised learning”, Synthese, 199: 9979–10015.
- Stanford Encyclopedia of Philosophy, “The Problem of Induction”, Section 3.4, https://plato.stanford.edu/entries/induction-problem/