一个证明题

周志华《机器学习》第一章中，有一个关于“没有免费的午餐”定理的题目，题目是这样的：

假设样本空间和假设空间都是离散的，令为算法基于训练数据产生假设的概率，令代表真实目标函数。考查二分类问题，可以是任何函数，函数空间为，假设是均匀分布（即不管是什么，都有一半的对的预测与不一致）。现在采用作为分类器的性能度量，考虑的“训练集外误差”：

试证明“没有免费午餐定理”成立。

分析与解答

题目未给定的具体形式，但在二分类问题中，无非就4种情况。记，，，，它们都是常数。将的训练集外误差对所有按均匀分布求和为：

上面最后一个等式是因为是均匀分布，因此如果给定了和，不管是0还是1，都有一半的会是，一半的会是。

又因为，可将上式继续化简：

上式中，第一部分 显然与无关，第二部分则不然，需要再附加条件才可以使整个式子与无关，在周志华的书中，并没有加这个限制，可能是默认隐含了（因为加入这个条件很合理）。

特殊化情形

再来看在书正文中的例子，该例子将特殊化为二分类的错误率，即取，对应到本文的设定中，有，，将它们代入后得：

因此，它与无关。对于任意的和，它们的样本外误差的期望其实是相等的。这就是“没有免费的午餐”定理（No Free Lunch Theorem，NFL）。