学习的 No-Free-Lunch 原理

有限域证明 ​

令 $\mathcal{X}$ 有 $2m$ 个点，目标类含全部二元函数。任取使用 $m$ 个标注样本的算法。令 $D$ 在这些点上均匀，并先从 $2^{2m}$ 种标注中随机选目标 $F$。给定训练集后，未出现点的 $F(x)$ 仍是独立公平比特，算法在每个未见点上的平均错误为 $1/2$。样本最多覆盖 $m$ 个点，至少一半域质量未见，故平均风险至少 $1/4$。

由概率方法公理库概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。，随机目标上的平均下界意味着存在一个确定目标使该算法风险至少如此；算法随机性也可并入平均。再由有界随机变量的平均可推出常数概率的常数错误版本。

它没有否定什么 ​

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

定理不说机器学习不可能，也不说现实中所有算法一样好。限制阈值、半空间、低 VC 类或分布，加入平滑性、margin 与领域结构，正是在排除坏世界。它针对分布无关统一保证，也不同于优化 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$，则

$$\mathbb{E}R\le q\cdot 1+(1-q)\cdot \frac{1}{8},$$

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

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

参考资料

• David Wolpert, “The Lack of A Priori Distinctions Between Learning Algorithms,” 1996.
• Shalev-Shwartz, Ben-David, Understanding Machine Learning, Ch. 5.