“没有免费午餐”定理在优化和机器学习领域经常被提及，但往往对其含义或暗示理解不深。
该定理指出，在所有可能问题的表现平均下来时，所有优化算法的表现都相同。
这意味着没有单一的最佳优化算法。由于优化、搜索和机器学习之间密切关联，这也意味着对于分类和回归等预测建模问题，没有单一的最佳机器学习算法。
在本教程中，您将了解用于优化和搜索的“没有免费午餐”定理。
完成本教程后，您将了解：
- “没有免费午餐”定理表明，在某些特定约束下，所有优化算法的性能是相同的。
- 可以证明，不存在单一的最佳优化算法或机器学习算法。
- 鉴于我们只对所有可能的目标函数的一小部分感兴趣，该定理的实际意义可能有限。
使用我的新书《机器学习优化》，包括分步教程和所有示例的Python源代码文件，来快速启动您的项目。
让我们开始吧。
机器学习的无免费午餐定理
照片作者：Francisco Anzola，保留部分权利。
教程概述
本教程分为三个部分；它们是：
- 什么是“没有免费午餐”定理？
- 对优化的启示
- 对机器学习的启示
什么是“没有免费午餐”定理？
“没有免费午餐”定理，通常缩写为 NFL 或 NFLT，是一项理论发现，它表明当在所有可能的目标函数上平均表现时，所有优化算法的表现都相同。
NFL 指出，在某些约束下，在所有可能问题的空间中，每种优化技术在平均表现上都与其他所有技术相同（包括随机搜索）。
— 第 203 页，《元启发式方法精要》，2011 年。
该定理适用于一般的优化和搜索问题，因为优化可以被描述或构建为搜索问题。
这意味着您最喜欢的算法的表现与完全朴素的算法（如随机搜索）完全相同。
粗略地说，我们证明了对于静态和时间依赖的优化问题，所有算法在所有可能问题上的平均性能完全相同。
— 《优化无免费午餐定理》，1997 年。
一个简单理解这一发现的方法是考虑一个像 Excel 表格一样的大表格。
在表格的顶部，每一列代表一个不同的优化算法。在表格的侧面，每一行代表一个不同的目标函数。表格中的每个单元格是算法在目标函数上的表现，使用任何您喜欢的性能度量，只要它在整个表格中保持一致。
“没有免费午餐”定理的算法和问题表述
您可以想象这个表格是无限大的。然而，在这个表格中，我们可以计算任何算法在所有列值上的平均表现，它将与任何其他算法列的平均表现相同。
如果一种算法在一个类别的有问题上比另一种算法表现更好，那么它将在另一个类别的有问题上表现更差。
— 第 6 页，《优化算法》，2019 年。
现在我们对“没有免费午餐”定理有了普遍的了解，让我们来看看它对优化的具体影响。
想要开始学习优化算法吗？
立即参加我为期7天的免费电子邮件速成课程（附示例代码）。
点击注册，同时获得该课程的免费PDF电子书版本。
对优化的启示
所谓的黑盒优化算法是通用的优化算法，可以应用于许多不同的优化问题，并且对目标函数假设很少。
黑盒算法的例子包括遗传算法、模拟退火和粒子群优化。
“没有免费午餐”定理是在 20 世纪 90 年代末提出的，当时人们经常声称一种黑盒优化算法优于另一种优化算法。该定理对此进行了反驳，指出没有最佳优化算法，这是可以证明不可能的。
该定理确实指出，平均而言，没有一种优化算法比其他任何优化算法更好。
……被称为“没有免费午餐”定理，它限制了一个学习者能达到的最佳程度。这个限制很低：没有任何学习者能比随机猜测做得更好！
— 第 63 页，《主算法》，2018 年。
关键在于算法的应用不假设任何关于问题的信息。事实上，算法被应用于目标函数，没有任何先验知识，甚至不知道目标函数是最小化还是最大化。这是该定理的一个严格限制。
我们通常对正在优化的目标函数有一些“了解”。事实上，如果在实践中我们对目标函数一无所知，我们就无法选择优化算法。
正如 Wolpert 和 Macready 的“没有免费午餐”定理所阐述的那样，除非我们对可能的目标函数的概率分布做出假设，否则没有理由偏爱一种算法胜过另一种。
— 第 6 页，《优化算法》，2019 年。
优化领域的初学者被建议尽可能多地学习和利用关于问题的知识来构建优化算法。
我们对问题了解得越多，并在算法中加以利用，该技术就越能针对特定问题进行定制，算法在该问题上的表现也越有可能良好。“没有免费午餐”定理支持这一建议。
我们不关心所有世界，只关心我们生活的世界。如果我们对世界有所了解并将其纳入我们的学习器中，它就比随机猜测具有优势。
— 第 63 页，《主算法》，2018 年。
此外，其性能是针对所有可能的目标函数和所有可能的优化算法进行平均的。然而在实践中，我们只对那些可能具有特定结构或形式的小部分目标函数感兴趣，并使用针对这些函数定制的算法。
……我们怎么强调都不为过，本文不对各种搜索算法在实践中的表现做任何声明。本文的重点在于在没有任何假设的情况下，仅凭数学原理可以说明搜索算法的效用。
— 《优化无免费午餐定理》，1997 年。
这些推论导致一些从业者指出该定理的实际价值有限。
这具有相当大的理论意义，但我认为实际价值有限，因为所有可能问题的空间可能包含许多极其不寻常和病态的问题，这些问题在实践中很少见到，甚至从未见过。
— 第 203 页，《元启发式方法精要》，2011 年。
现在我们已经回顾了“没有免费午餐”定理对优化的影响，让我们来回顾一下它对机器学习的影响。
对机器学习的启示
学习可以被描述或构建为优化问题，而大多数机器学习算法的核心都是解决优化问题。
“没有免费午餐”定理适用于优化和搜索，并应用于机器学习，特别是监督学习，它是分类和回归预测建模任务的基础。
这意味着所有机器学习算法在所有可能的预测问题上都同样有效，例如随机森林和随机预测一样好。
因此，所有学习算法都相同，因为：(1) 根据“平均”的几种定义，所有算法的平均训练集外错误分类风险都相同，(2) 因此，没有一种学习算法可以在所有 f 上比另一种算法的风险更低……
— 《监督学习的“没有免费午餐”定理》，2002 年。
这也影响了算法的评估或选择方式，例如是否通过 k 折交叉验证测试框架来选择学习算法。
……一个使用交叉验证在预设学习算法集之间进行选择的算法，其平均表现并不比不这样做的算法更好。
— 《监督学习的“没有免费午餐”定理》，2002 年。
它也影响了人们对“优秀”机器学习模型的常见启发式方法，例如避免过拟合或选择性能良好的最简单模型。
另一组例子是人们想出的所有用于监督学习的启发式方法，例如避免过拟合，偏爱更简单的模型而非更复杂的模型等。[“没有免费午餐”]说，所有这些启发式方法失败的次数和成功的次数一样多。
— 《监督学习的“没有免费午餐”定理》，2002 年。
鉴于不存在对所有可能预测问题都最优的单一机器学习算法，这促使我们需要继续开发新的学习算法，并更好地理解已开发的算法。
作为“没有免费午餐”定理的后果，我们需要开发许多不同类型的模型，以涵盖现实世界中出现的各种数据。对于每种模型，我们都可以使用许多不同的算法来训练它，这些算法在速度-准确性-复杂性之间做出不同的权衡。
— 第 24-25 页，《机器学习：概率视角》，2012 年。
它也支持了为给定预测建模问题测试一套不同机器学习算法的论点。
“没有免费午餐”定理认为，在没有关于建模问题的实质性信息的情况下，没有单一的模型能够始终优于任何其他模型。因此，很有理由尝试各种技术，然后确定要重点关注哪个模型。
— 第 25-26 页，《应用预测建模》，2013 年。
然而，与优化一样，该定理的含义基于学习算法对所解决问题的选择零知识。
在实践中，情况并非如此，并且鼓励初学者机器学习从业者审查可用数据，以便了解一些可以纳入学习算法的关于问题的信息。
我们甚至可以更进一步说，没有先验知识的学习是不可能的，而数据本身是不够的。
与此同时，“没有免费午餐”定理的实际后果是，根本没有“不带知识的学习”。数据本身是不够的。
— 第 64 页，《主算法》，2018 年。
进一步阅读
如果您想深入了解，本节提供了更多关于该主题的资源。
论文
- 学习算法之间缺乏先验区别, 1996.
- 搜索的“没有免费午餐”定理, 1995.
- 优化的“没有免费午餐”定理, 1997.
- 监督学习的“没有免费午餐”定理, 2002.
书籍
文章
总结
在本教程中，您了解了优化和搜索的“没有免费午餐”定理。
具体来说，你学到了：
- “没有免费午餐”定理表明，在某些特定约束下，所有优化算法的性能是相同的。
- 可以证明，不存在单一的最佳优化算法或机器学习算法。
- 鉴于我们只对所有可能的目标函数的一小部分感兴趣，该定理的实际意义可能有限。
你有什么问题吗？
在下面的评论中提出你的问题，我会尽力回答。
非常棒的文章！谢谢您，Jason。
我只是一名实践学生，有一个问题。
像 XGboost、LightGBM 这样的梯度提升模型怎么样？它们通常被认为比许多其他优化技术表现更好。通常，这在一系列不同的问题（函数子集）上似乎都是正确的。在这种情况下，我们可以从该定理推断出什么？
谢谢！
这表明在我们要解决的所有问题的小部分示例中，它们很可能表现出色。
NFLT 的范围要广泛得多。
什么是“没有免费午餐”定理？在 ICT 领域，它如何应用于信息系统和企业，以及信息安全和企业？
参见上面关于此主题的教程。
具体在哪里？
本教程的主题是“没有免费午餐”定理。
“没有免费午餐”定理如何应用于信息通信技术，特别是信息系统和商业，以及信息安全系统？
是我的错觉还是有些人在这里只是复制/粘贴大学作业问题作为评论？！?!? 不要作弊！！！祝贺 Jason，这篇帖子是很好的解释！
是的！
感谢您的文章！我对机器学习算法的通用性很着迷，但这个想法似乎有些不对劲……而这就是“没有免费午餐”定理。
不客气。
谢谢你
感谢您分享这篇有用的文章，Jason。
我有两个问题
1. 在 NFL 中，为什么忽略了结果的准确性（只讨论了效率）？
随机搜索的平均函数调用（对于所有可能的问题）与其他方法相同，并且随机搜索在数学上以概率 1 收敛到准确的解。但是，其他方法可能会未能找到正确的解（全局最优解）。为什么这个事实总是被忽略？
如果准确性很重要，那么提出的 NFL 证明是否正确？
2. 我们可以将基于梯度的优化方法（例如 SQP）视为黑盒优化算法（例如，通过有限差分估计梯度）。那么，我们能将其与随机蒙特卡洛采样进行比较吗？从 NFL 的角度来看，这两种搜索方法是否相同？（我问这个问题只是为了确保我对 NFL 的理解正确）。
感谢您的时间和分享您的研究成果。
1. 尝试限制随机搜索的成本（例如，在循环 1000 次时停止），那么您应该与之进行比较。如果您允许所有算法花费无限的时间（例如，使用随机初始解），您也会看到它等于您对随机搜索的描述。
2. 是的。
非常感谢。但我认为这里有些东西是错误的。
我认为我们关于搜索问题维度（即变量数量）的信息会影响 NFL 证明的普遍性。例如，一些算法是为了解决高维问题而开发的（我们可以称之为“问题相关算法”）。
一旦我们要解决一个高维问题，知道优化问题的大小（变量数量），我们就可以在我们的分析中使用它们。
因此，如果我们只比较两种算法（一种是为小规模问题开发的，一种是为高维问题开发的），整体表现可能不会相同。似乎总会有一些免费午餐（因为我们总是知道问题的大小）。
我的结论是错误的吗？
理解 NFL 的理念是，总是有成本的，而且没有一种算法总是比另一种算法更好。如果您有一个特定的问题或数据集，我有一个查找表可以立即给您答案。我的成本是零？当然不是，因为我还没有推广到所有问题。而且我还没有考虑构建查找表的成本。
非常感谢您的回复，Adrian。
你说得对，我同意您的观点。
根据我的理解，“NFL 也说对于黑盒问题，没有算法比其他算法更好”。我说：“这不属实”（这与您在回复中提出的完全不同）。
我们知道，考虑到黑盒问题的大小，与问题规模一致的算法比其他算法更好（例如，如果问题有 10000 个设计变量，那么为高维问题设计的算法比其他算法表现更好，反之亦然）。希望这能说清楚。
总之，非常感谢您的时间和回复。
那一个巨大的神经网络呢？
嗨 Sampath……更大的网络不总是最好的选择。如果你选择更大的网络，请记住以下几点
我建议在服务器上运行大型模型或长时间运行的实验。
我建议只使用您的工作站进行小型实验，并确定要运行哪些大型实验。我在这里详细讨论了这种方法
机器学习开发环境
我推荐使用 Amazon EC2 服务，因为它提供对具有大量 RAM、大量 CPU 内核和大量 GPU 内核（用于深度学习）的基于 Linux 的服务器的访问。
您可以在这些帖子中学习如何为机器学习设置 EC2 实例
如何在 Amazon Web Services 上使用 Keras 开发和评估大型深度学习模型
如何使用亚马逊云服务（Amazon Web Services）在云端训练 XGBoost 模型
您可以在此帖子中学习在服务器实例上工作时的有用命令
Amazon Web Services 上的深度学习 10 个命令行技巧
“我们甚至可以更进一步说，没有先验知识的学习是不可能的，而数据本身是不够的。”
这些话是否可以让我把“知识”改为“假设”？
这些事情引导我产生了本体论上的疑问。我们不知道世界；我们只是根据先前假设的经验来转移对世界的假设（范式）。
我猜，那些在 Othello（棋盘游戏）上训练机器，只提供完整对局的连续走子坐标（很多对局）的人，并没有通过研究最适合学习的模式来作弊（我的意思是，以某种方式将 Othello 或其棋盘编程到模型架构中），而是只是选择了一个“合理”或“可行”的模型（对于训练方法的效率也是如此）。（我指的是那些在训练后，在模型的权重中发现了某种棋盘结构的人）。（抱歉我语言不清晰；我在一篇科普文章中读到的，我对这个领域完全是新手，我甚至找不到研究文章来改进这个描述）。
感谢作者和出版商的文章！我觉得能够访问这些内容，并有机会留下这条评论，真是太棒了，更不用说有机会收到回复了……
谢谢 Juan 的帖子！虽然我们的内容不涵盖强化学习，但您可能想研究一下该领域的最新进展。这触及了您帖子中提出的许多观点，非常有趣。
https://www.youtube.com/watch?v=SupFHGbytvA&list=PL_iWQOsE6TfVYGEGiAOMaOzzv41Jfm_Ps
（我需要回复自己的评论吗？）我刚发现我在 Llm 世界模型构建的范式中读到关于 Othello 棋盘游戏的内容：l。那里提到的研究文章是
《涌现的世界表征：对合成任务训练的序列模型的探索》
Kenneth Li, Aspen K. Hopkins, David Bau, Fernanda Viégas, Hanspeter Pfister, Martin Wattenberg
在以下链接中
https://arxiv.org/abs/2210.13382?utm_campaign=The%20Batch&utm_source=hs_email&utm_medium=email&_hsenc=p2ANqtz-8Nb-a1BUHkAvW21WlcuyZuAvv0TS4IQoGggo5bTi1WwYUuEFH4RunaPClPpQPx7iBhn-BH
我在https://www.deeplearning.ai/the-batch/issue-209 的开头读到了它
感谢您让我澄清。
谢谢 Juan 为大家提供这个更新！