不得不说，网上博客千千万，在技术方面，我承认这些博客的重要性。然而，只要和机器学习理论挂钩，似乎都讲得不清不楚，大家都是各自地抄，抄书籍，抄论文，抄别人的博客或者直接翻译，或者讲故事一样描述，几乎没什么太深入的理解，给人的感觉是“哎？似乎是这样，我好像有一点懂了”，然后就没了，其实看这样的博客简直就是在浪费时间，凡是不能一次性地搞懂一点内容，都是扯犊子。总之，看了网上的关于机器学习博客的文章，我感觉很不理解，很困惑，很迷茫。所以我就推导了一遍周志华书籍《机器学习》没有免费午餐定理(No Free Lunch Theorem)的一个简单证明过程。

一、讲故事一样的描述

        讲故事虽然并不严格，然而它还是有必要用这样的思维去描述这个定理。其用途是给别人普及，同时也方便自己记忆。

        那么，如何像讲故事一样地描述没有免费午餐定理呢？最直观的，我们吃午饭都是要付钱的，哪怕有人请客，那请你吃饭的人也帮你付了钱。但这个似乎跟机器学习并没有半吊子关系。

        在机器学习领域里面，有一个雷打不动的定理，即没有免费午餐定理。它被描述为：没有一个学习算法可以在所有情况下总是产生最准确的模型。也就是说，不管采用何种学习算法，至少存在一个模型，比随机猜测算法得到的模型要差。这个定理的最重要意义是，在脱离实际意义情况下，空泛地谈论哪种算法好毫无意义，要谈论算法优劣必须针对具体学习问题。所以，我们在比较学习算法的时候，需要针对具体的学习问题。针对这个问题，学习算法a可能更好；而针对那个问题，学习算法b可能更好。

        周志华在他的机器学习书籍里面说到，实际上在很多时候，我们只关注自己正在试图去解决的问题并它找到一个方案，而至于这个方案在其他问题上是否为好方案并不关心。例如，为了快速从A地到达B地，如果我们正考虑的A地是南京鼓楼，B地是南京新街口，那么骑自行车是一个很好的方案；如果A地是南京鼓楼，B地是北京故宫，那么骑自行车显然是一个极其糟糕的方案，但我们对此并不关心。

        总之一句话，谈论算法的相对好坏，要针对具体的学习问题。而当你的算法在某个问题取得较好的性能时，那得注意了，请你说说你为这这么好的性能付出了什么代价？

二、相对严格的描述及其证明

        这个定理之所以雷打不动，是因为它是经过严格的数学证明的。下面就顺着周志华机器学习书籍里面的内容，推导一遍其证明过程。

        首先，我们来看看原文，如下。

        看着这些公式，确实头都大了。不过不用怕，这充其量也就是高中数学的知识。求和公式、条件概率、均匀分布，这些不都很熟悉吗？我们高中就学过。只要我们把它展开，你就明白为什么会是这样的计算过程了。

        先从公式（1.1）开始理解吧。

        先看左边，表示机器学习算法的训练集外误差，可以理解为测试集误差（因为测试集是拥有标记信息的，有标记信息才能计算误差，否则不能。由于训练集外读着很别扭，所以后文直接把训练集外的样本所构成的集合当作是测试集）；

        机器学习算法能够在训练集上学习得到多个机器学习模型，而一个模型就是一个假设，多个假设便构成机器学习算法的假设空间；

         是希望学习得到的目标函数，输入一个样本，经过，那么就能够得到一个正确的标签。无论这个样本是在训练集上，还是在测试集上；

        所以，是指给定训练集和目标函数，机器学习算法的测试集误差。

        再看右边。有两个求和符号，第一个求和符号是遍历机器学习算法在训练集上所有可能的模型，第二个求和符号遍历所有测试集的样本。然后就和。把右边的两层求和公式展开，然后用另外一种方式化简，最终是可以把两个求和符号进行交换的。其中是遍历到样本的概率，是机器学习算法在训练集上产生假设的概率（记住，假设就是一个模型）。那个指示函数就不必说了，不等于就是假设预测错，等于就是假设预测正确。预测正确就不管，错了，就记录，然后加起来，最后构成测试集的误差。

        现在再来看看公式（1.2）的计算过程。在开始之前，先说一下目标函数，这里的目标函数不再是固定的目标函数，而是要考虑所有可能的目标函数，这些目标函数也构成一个集合。好了，现在再来理一理思路，有一个训练集，有一个测试集，而， 我们设计了一个机器学习算法，任务是二分类任务。所以如果训练集+测试集有个样本，那么可能的目标函数就会有种个。

        所以，要求得机器学习算法的性能，还需要在公式（1.1）的基础上外加一层求和符号，以遍历所有有可能的目标函数。

        那么，现在可以正式地推导这个过程了。具体如下

# 推导过程太长了，博客不是很方便看
# 详情见https://download.csdn.net/download/qq_36158230/20246322
# 主要思想：对求和公式展开，重组，利用概率论相关的知识化简

三、一个易于理解的例子

        看了一长串的计算过程之后，来个直观的例子，那是最舒服的。具体如下：

        给定，训练集，测试集。那么对于二分类问题：，目标函数有以下种。

        给定训练集，根据机器学习算法，得到的假设空间为； 根据机器学习算法，得到的假设空间为。方便起见，这里就等于。那么，现在我们利用公式（1.2）计算这两个算法的性能。由于测试集只有一个样例，即，故。

        对于机器学习算法，假设每个模型被选中的概率相等，那么

        而机器学习算法对应的指示函数的值为

        利用得出结论之前的公式（即公式（1.2）包含了三个求和符号的式子）计算，得到

        同理， 对于机器学习算法，假设每个模型被选中的概率相等，那么

        而机器学习算法对应的指示函数的值为

        利用得出结论之前的公式（即公式（1.2）包含了三个求和符号的式子）计算，得到

 

        经过计算发现，两个学习算法的训练集外误差竟是一样的。

        也许有人要站出来问了，你两个算法的假设空间太特殊了，万一这个例子是巧合呢？

        那好，现在令，。继续用上面的方法算一算，结果发现两个机器学习算法的训练集外误差计算结果还是一样的。但是又有人要说了，你的算法的假设还是太特殊了，万一还是巧合呢？

        好，现在令机器学习算法的假设空间为，机器学习算法的假设空间为。现在再来用上面的方法算一算。这时不变，而

 

        此时，这两个机器学习算法对应的指示函数表分别为 

        它们所对应的训练集外误差分别为

 

        这时发现它们的计算结果依然是4(通过数指示函数表中“1”的个数，然后乘以，或者累加计算也行，结果是一样的)，真是神奇啊！当然了，你也可以举其他的例子计算一遍，质疑一下这个雷打不动的机器学习定理。不过我推导了一遍计算过程，也用例子算了好几回，反正我是信了。

四、推荐阅读+观看

        1.(强推)浙大2021-机器学习_哔哩哔哩_bilibili

        2.浙江大学-研究生机器学习课程-_哔哩哔哩_bilibili

        3.参考资料第2条

五、结束语

        码字之余，难免疏漏，欢迎点评指出改正。同时，码字不易，不喜勿喷，文明交流。毕竟是个人理解，所以写的东西很有可能有所疏漏，但是希望大家能够文明交流。爱与尊重。

        花费两天找了一些资料理解这个没有免费午餐定理，再花费一天时间把我所理解的内容全部写在博客之上。确实，在理解和作笔记的过程，都是相当艰苦的。不过有了一定的理解之后，确实让人恍然大悟，感觉收获良多。一大堆写得很复杂的公式难以让人理解，实际上是由于它的跳跃性真的太大了。如果能够缩短这个跳跃间距，那么学习便不成问题了。可惜的是，论文没有那么多的篇幅给你一步一步地计算。

参考资料

        1.周志华，机器学习

        2.Ho, Yu-Chi, and David L. Pepyne. "Simple explanation of the no-free-lunch theorem and its implications." Journal of optimization theory and applications 115.3 (2002): 549-570.