学习的 No-Free-Lunch 原理

所有函数类可完美记住训练集，失败却发生在没有任何联系的未见点。算法必须带归纳偏置，而全目标类总能挑出与该偏置冲突的世界。

定理不说机器学习不可能，也不说现实中所有算法一样好。限制阈值、半空间、低 VC 类或分布，加入平滑性、margin 与领域结构，正是在排除坏世界。它针对统计学习问题公理库统计学习问题Statistical learning problem从未知分布的有限观测中选择决策规则，并以样本外表现评价其质量。中的分布无关统一保证，也不同于优化 No-Free-Lunch。训练误差为零不与结论冲突，因为这里评价总体错误。

后续增长函数公理库增长函数与打散系数Growth function · Shattering coefficient计算二分类函数类在有限点集上能够实现的不同标注数。与 VC 维公理库VC 维Vapnik–Chervonenkis dimension · VC dimension二分类假设类能够完全打散的最大有限点集大小。将“能任意标注多少点”量化，而不是诉诸“模型复杂”口号。

从期望下界到概率下界 ​

从期望下界到概率下界还需一步。设随机目标与样本下算法风险 $R\in [0,1]$，且 $\mathbb{E}R\ge 1/4$。若 $\text{Pr}(R\ge 1/8)=q$，则

所以 $q\ge 1/7$。于是某个固定目标能让算法以常数概率承担至少常数错误；仅说“平均为 $1/4$”而直接写“高概率失败”会漏掉这段有界性论证。

限制结构后结论改变 ​

限制结构后结论立即改变。对实线阈值，观察到一正一负且位置相邻时，未见点标签不再是任意比特，而受单调切分约束；样本开始携带关于其他点的信息。No-Free-Lunch 的准确教训是必须说明归纳偏置从何而来，而不是用它否定带结构的学习。

分布无关学习保证必须以某种结构限制为代价：缩小假设类、限制数据分布、规定平滑或间隔，都会让已见样本开始约束未见点。样本复杂度定理中的维数、范数和覆盖数，正是在量化这种归纳偏置，而非绕开 No-Free-Lunch。

使用该下界时要保留量词：对每个学习算法，存在一个目标与分布使其失败；它不提供一份同时击败所有算法的固定现实数据集，也不声称特定结构化任务不可学习。把期望风险升级为常数概率失败，还必须像上面的有界性计算一样单独证明。