“没有免费的午餐定理”

没有免费午餐定理(No Free Lunch，简称NFL)是wolpert和Macerday提出的“最优化理论的发展”之一。

引言

最优化理论的发展之一是wolpert和Macerday提出了没有免费的午餐定理(No Free Lunch，简称NFL)。该定理的结论是，由于对所有可能函数的相互补偿，最优化算法的性能是等价的。该定理暗指，没有其它任何算法能够比搜索空间的线性列举或者纯随机搜索算法更优。该定理只是定义在有限的搜索空间，对无限搜索空间结论是否成立尚不清楚。

NFL定理

1）对所有可能的的目标函数求平均，得到的所有学习算法的“非训练集误差”的期望值相同；
2）对任意固定的训练集，对所有的目标函数求平均，得到的所有学习算法的“非训练集误差”的期望值也相同；
3）对所有的先验知识求平均，得到的所有学习算法的“非训练集误差”的期望值也相同；
4）对任意固定的训练集，对所有的先验知识求平均，得到的所有学习算法的的“非训练集误差”的期望值也相同。
NFL定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。

NFL理论详情

首先，假设一个算法为a，而随机胡猜的算法为b，为了简单起见，假设样本空间为和假设空间为H都是离散的。令P(h|X,a)表示算法a基于训练数据X产生假设h的概率，再令f代表希望的真实目标函数。a的训练集外误差，即a在训练集之外的所有样本上的误差为

其中是指示函数，若为真则取值1，否则取值0.
考虑二分类问题，且真实目标函数可以是任何函数 ↦{0,1},函数空间为 (指样本空间中元素个数，对所有可能的f按均匀分布对误差求和
可以看到总误差竟与算法无关。得证无论算法多好在没有实际背景情况下都不优于随机胡猜。
所以，NFL定理最重要意义是，在脱离实际意义情况下，空泛地谈论哪种算法好毫无意义，要谈论算法优劣必须针对具体学习问题。