不要引用“没有免费的午餐定理”了

来源：AI科技评论

本文约4000字，建议阅读8分钟。

机器学习科学家 Andreas Mueller 最近撰文表示大家都引用错定理了，其实事情比这更复杂，也有更深远的启示。

编者按：没有免费的午餐定理一度是机器学习界最常被谈起的定理之一（真正长期被谈起的自然是更多的数据等于更好的表现）。不过机器学习科学家 Andreas Mueller 最近撰文表示大家都引用错定理了，其实事情比这更复杂，也有更深远的启示。

Andreas Mueller 是哥伦比亚大学数据科学研究院的助理研究科学家，也是《Introduction to machine learning with Python》一书的作者；他还是 scikit-learn 机器学习库的核心开发者之一。

小编把他的这篇博客全文编译如下。

首先一句话概括我这篇文章要说什么：大家以后尽量不要再引用 Wolpert 的没有免费的午餐定理了。如果你已经在哪里引用过，那你很有可能用它支持了错误的结论。他的句话实际上想表达的是你不可能在没有假设的情况下从数据中学习。

提出没有免费的午餐定理这个概念的，实际上是 David H. Wolpert 的《The Lack of A Priori Distinctions Between Learning Algorithms》（https://www.mitpressjournals.org/doi/abs/10.1162/neco.1996.8.7.1341）这篇论文。

机器学习领域里有不少论文，它们经常被引用，但是没什么人认真读过论文内容；这篇论文就是其中之一。大多数机器学习领域内的人提起这篇论文的时候都是想要说明某个模型不可能在每个方面都是最好的，或者某个模型不会在每个方面都比另一个模型强。但实际上这并不是 Wolpert 的这篇论文、这个定理真正想要表达的内容，所以大家未来不应该这样引用这个定理，我会在下文里仔细说明这件事；以及，即便单独考虑大众想要说明的某个模型不可能在每个方面都是最好的，其实这个结论也是有问题的。

多个定理，同一个名字

首先，据我所知至少有两个定理都叫做没有免费的午餐（no free lunch）。一个是 Wolpert 提出的，首次在《The Lack of A Priori Distinctions Between Learning Algorithms》论文里出现；另一个是 Shalev-Shwarz 和 Ben-David 提出的，在《Understanding Machine Learning》这本书里（这本书很棒，http://www.cs.huji.ac.il/~shais/UnderstandingMachineLearning/）。

Wolpert 还发表过一篇《No Free Lunch in Optimization》，不过我们只关注谈监督学习的那个定理就好了。

《Understanding Machine Learning》里提出的那个定理和 Wolpert 的很不一样，我的理解是， Shalev-Shwarz 和 Ben-David 两人提出这个定理就是为了给没有免费的午餐提出与 Wolpert 不同的、新的诠释，而其实他们的定理内容是某个模型不可能在每个方面都是最好的，不过他们的表达方式非常具体。

某种程度上说，他们描述这个定理的方式要比我们从现在的字面上所能感受到的要清晰明确得多。但我不太赞同他们用一个已有的名字来命名这个定理的做法。

这个定理本来在说什么？

Wolpert 最早的那篇论文的主要内容可以总结为在这个定理的假设之下，任何两个预测函数的泛化能力都是相同的。这里有两个关键部分：假设和结论。

只看结论任何两个预测函数的泛化能力都是相同的的话，经常会有人理解为类似梯度提升不会总是最好的这样。但实际上它想说的是梯度提升几乎每次都能找到出现频率最高的类或者神经网络几乎每次都能预测到出现频率最低的类。显然这和我们的机器学习实践经验是冲突的。但根据这个定理的说法，在泛化性质方面它就和你能找到的最好的模型一样。所以这是怎么回事？

关键是假设

理解这个定理的关键是理解定理中的假设。这个定理中的假设并不是机器学习研究中常用的那个数据来自某个给定分布中的独立同分布假设，恰恰相反，Wolpert 假设数据是一个有限集，而且训练和测试是独立的、各自对应不同分布的数据。这个假设并非没有合理之处，在实际中我们的数据总是有限的，而且我们希望看看模型在此前从未见过的新数据上表现如何。这样的假设让 Wolpert 能够考虑到所有可能的数据集的情况。那么，这个定理就是阐述在这个假设下、在所有可能的数据集上对比两个算法的表现。

虽然这个假设对于机器学习研究来说有一些合理之处，但其实问题也不小：

• 假设中说测试数据和训练数据是统计不同的，也就是说测试数据和训练数据根本没什么关系

• 数据标签和数据特征也没有什么关系（因为在考虑所有可能的标签的平均情况）。

说成这样以后，我们就能看出来这些假设对于任何预测建模都算不上有利。

这个定理的实际意思

那么现在我们可以尝试总结一下，或者重新表述一下 Wolpert 的没有免费的午餐定理到底想要说什么。单独看结论得到的每个模型在预测成员较少的那个分类时都有同样的表现可以理解为说学习是不可能的。再组合上我们对于他的假设的理解的话，就成了如果训练数据集和测试数据集没有什么关系，而且特征和标签之间也没有什么关系，那么学习就是不可能的。这听起来简直自然而然，不过也就和平时大家谈论的没有免费的午餐定理的内容大相径庭。

也有一种对这个定理的解读是为了让学习变得可能，你需要做出一些假设。

只不过，在这篇论文里 Wolpert 做出的假设恰恰是训练数据集和测试数据集没有什么关系，而且特征和标签之间也没有什么关系，这样一来学习反而变得不可能了。所以，如果你想要说明的观点是学习需要假设的话，那你就不应该引用这一篇论文。

我对 Wolpert 的“没有免费的午餐定理”的解读

在我看来，这篇论文最大的意义是挑战了独立同分布假设。Wolpert 用很好的理由说明了为什么他认为这个假设不怎么妥当，以及为什么机器学习理论需要探索其它的理论框架。尤其是，如果数据集容量是有限的，他就提出了一个确实值得考虑的情况。在这种情况下，独立同分布假设会允许一个点同时出现在训练集和测试集中，显然这也就没办法讨论泛化性了。那么 Wolpert 提出训练集和测试集没有什么联系，也就是合理的。

不过，他提出训练集和测试集（以及标签）是相互完全独立的，这事还是有点奇怪的。我不确定他是否真的认为这是一个好的思考机器学习问题的框架。我猜测他提出这个的动机是希望整个领域重新考虑独立同分布假设是否合理，并且尝试寻找能够更好地反映机器学习实践的假设。如今许多年后回头来看，我觉得很可惜，没有更多的研究者沿着他的思路做更多的讨论，而且他提出的定理也显然被大批机器学习实践者误读了。

另一个“没有免费的午餐定理”

在文章开头我提到过还有另一个没有免费的午餐定理。和 Wolpert 非常不同的是，它评价模型的时候使用了独立同分布假设；在其它方面则有相似之处，在没有其它额外假设的前提下，如果你只能看到一部分数据，那么其余的数据的标签仍然是具有任意的可能的。所以，具体地来说，这个由 Shalev-Shwarz 和 Ben-David 提出的没有免费的午餐定理的内容是，对于任意一个指定的预测算法，都会有它表现很糟糕的数据集，也就是说在这个数据集上别的学习者会有更好的表现。不过这没法阻挡有人提出算法 A 永远都比算法 B好之类的说法，因为真正表现更好的那个算法是无法实现的（它应当是那个无需查看数据就总能生成完全正确答案的算法）。在这个思考框架里可以很轻松地证明，在一个不平衡的数据集中，预测出现频率较高的类比预测频率较低的类要更容易；而这个结论是无法在 Wolpert 的框架中得到的。

如何引用这些定理

我觉得，不论你想要说明的结论是什么，几乎都不会需要引用 Wolpert 的论文。如果你想说明的是有适当的假设就可以进行学习，那你大概可以引用 Shalev-Shwarz 和 Ben-David 的那一整章的内容，我也不确定有没有更正式的方法来引用。如果你非常想的话，你也可以引用 Wolpert，但我觉得这带来的困惑要比帮助多多了。而如果你想说的是对于有限数据来说，独立同分布的假设也太奇怪了，那你就一定要引用 Wolpert！

最后，如果你想要说的是梯度提升不可能永远比神经网络强，因为有没有免费的午餐定理，那在我看来你搞错了，没有任何证据可以支持这样的陈述。我其实也不觉得在常用的机器学习算法之间有任何的总是更好或者总是更糟糕的优劣关系，但我同时也没听说过有任何的机器学习理论能禁止这样的事情发生（只要是在学习是可行的框架下讨论）。

附言

如果你对机器学习理论感兴趣，Shalev-Shwarz 和 Ben-David 的那本书其实很棒。除此之外我还很喜欢 Mehryar Mohri, Afshin Rostamizadeh 和 Ameet Talwalkar 合著的《Foundations of Machine Learning》（https://cs.nyu.edu/~mohri/mlbook/）。

我自己并不是一个做理论研究的人，但我觉得有一些理论基础能在思考算法的时候有一些好的思想框架。你想读一读 Wolpert 的那篇论文也不错，虽然我觉得你的最大收获会是了解他为什么不喜欢独立同分布假设，实际上论文中更多地是对机器学习理论的哲学的思考，而不是一般的机器学习理论讨论。

via https://peekaboo-vision.blogspot.com/2019/07/dont-cite-no-free-lunch-theorem.html

编辑：王菁