没有免费的午餐定理是什么？没有对所有问题都最好的算法

没有免费的午餐定理（No Free Lunch Theorem，NFL）是机器学习和优化理论中的一个重要结论：如果对所有可能的问题一视同仁地进行平均，那么所有的学习算法或优化算法的平均表现都是一样的。换句话说，不存在一个在所有问题上都比其他算法更好的“万能”算法：一个算法在某些问题上表现得好，必然会在另一些问题上表现得差。这个名字来自一句英语俗语“天下没有免费的午餐”，意思是任何好处都要付出代价。

它的来历

美国学者 David Wolpert 在 1996 年针对监督学习提出了这一定理；1997 年，Wolpert 和 William Macready 又针对搜索和优化算法提出了相应的版本。在优化的版本中，他们证明：在所有可能的目标函数上进行平均，任何两个优化算法找到好解的平均效率都是相同的，即使是精心设计的复杂算法，平均来说也不比随机搜索更好。

一个直观的理解

周志华《机器学习》中用一个简单的例子说明了这一点：假设有两个学习算法，算法甲倾向于学到一条平滑的曲线，算法乙学到的是一条起伏的曲线。如果真实的规律恰好是平滑的，算法甲在新的数据上会表现得更好；但如果真实的规律恰好是起伏的，算法乙就会表现得更好。训练数据只覆盖了有限的几个点，在这些点之外，真实的规律可能是任何样子。如果我们对真实的规律没有任何了解，认为所有可能的规律都是同样可能的，那么平均来说，两个算法在训练数据之外的表现就是一样好的。书中通过数学推导证明了：在所有可能的真实目标函数上取平均，任何学习算法在训练集之外的期望误差都相同，与算法本身无关。

它真正的含义

没有免费的午餐定理并不是说所有的算法在实际中都一样好，也不是说机器学习没有用处。它的关键前提是“对所有可能的问题一视同仁”，而在现实中，我们面对的问题并不是从所有可能的问题中均匀地抽取出来的，它们通常具有特定的结构和规律：比如自然界中的很多关系是平滑的，相似的输入通常有相似的输出；图像中相邻的像素往往密切相关；语言有语法和语义的规律。一个算法如果能够很好地利用这些结构，就会在这类现实问题上表现出色。因此，这个定理真正告诉我们的是：脱离具体的问题来谈论“什么算法更好”是没有意义的；一个学习算法之所以成功，是因为它的归纳偏好，也就是它对什么样的规律更可能为真的倾向，恰好与所要解决的问题的特点相匹配。

对实践的启示

没有万能的算法：在面对一个新的问题时，不能简单地认为某个算法一定是最好的，而应该根据问题的特点进行选择，并通过实验来比较不同的方法。理解问题很重要：了解数据的特点和领域的知识，有助于选择或设计出与问题相匹配的方法。比如卷积神经网络之所以在图像任务上非常成功，正是因为它的结构，局部连接和权重共享，恰好契合了图像的特点；Transformer 能够灵活地捕捉序列中任意位置之间的关系，适合语言等数据。先验知识的价值：引入关于问题的先验知识，本质上就是在选择一种合适的归纳偏好。值得一提的是，近年来大规模的预训练模型似乎在许多不同的任务上都表现得很好，这看起来像是一种“通用”的算法。但这并不违反没有免费的午餐定理：这些模型是在现实世界的海量数据上训练的，它们学到的是现实世界中普遍存在的规律，而现实世界中的任务恰好共享着这些规律。