免费午餐定理（NFL）的绝妙比喻

最近ChatGPT很火，我也玩了一下，效果看起来很好，回答像模像样，很有点百科词条的味道。至于为什么是“看起来”，玩过都知道，有些内容显然是ChatGPT在一本正经地瞎说。很多人在问ChatGPT会不会干掉谷歌，学界近期也出了几篇用大语言模型（LLM）做信息检索的论文，思路是用LLM“生成”文档ID，不知道是巧合还是呼应。

我做了些调查，想用LLM平替搜素引擎现在看来还不现实，可靠性姑且不论，响应成本太高，经济账首先就算不下来。本来文章都快写完了，结果今天出来一条新闻，说必应要整合ChatGPT击败谷歌，好嘛，说好的打人不打脸呢。

本着得不到就毁掉的心情，是时候谈一谈这条叫NFL的定理（No Free Lunch Theorem，没有免费午餐定理）。NFL是一条网红的定理，机器学习中引用很多，达到了滥用的地步。定理的结论简单但劲爆，“由于对所有可能函数的相互补偿，优化算法的性能是等价的”。这段话很拗口，拗口的地方在于用词很诡异，“可能函数”是什么？“互相补充”又是咋回事？而且不同教材用词还不同，这里我们聊的是机器学习下的NFL定理，干脆统一都叫“问题”。“问题”究竟是什么，怎样做到相互补偿，不急，这是后文的重点。这里我们只需要知道，这句结论用人话来说，就是在座各位都是垃圾。

1.表世界

首先介绍一下NFL定理。NFL定理最早出现在1997年Wolpert发表的论文《No Free Lunch Theorems for Optimization》，顾名思义，原始论文说的是优化算法没有最强，后来有人把它套用到了机器学习领域，于是学习算法也没有了最强。如果读懂了这条结论，就会发现非常反直觉，根据NFL定理，大红大紫的ChatGPT也好，其它刷榜顶会的什么模型也好，总会在一些问题上表现不如随机瞎猜。这就是“没有免费午餐”的意思。

总觉得“没有免费午餐”有点词不达意，可能是这句进口谚语在我们的语境中意思发生了微妙的变化，要我起名字，这条定理应该改叫“不如白嫖定理”。

NFL定理的表层逻辑解释起来不复杂，需要用到机器学习中一个叫“归纳偏置”的术语。归纳偏置是说学习算法总会包含一些显性或者隐性的假设，简单来说就是算法总会有“执念”，如果我们把模型的学习过程看作是拟合问题的数据分布，那么当这些执念和数据分布大致相符的时候，模型拟合会如丝顺滑，如果八字不合，那模型自然就成了魔怔人。

ChatGPT也不例外，她也会有执念，也会和某些问题八字不合，表现自然就不如随机瞎猜。一般对NFL定理的介绍到这里也就差不多了，但其实漏了一个非常关键的假设条件，这也最终成为了NFL定理被滥用的原因。

2.里世界

很多教材对NFL定理的介绍，大致可以归纳为定理证明了机器学习不能脱离具体问题、具体任务去说模型的性能好坏。我过去对于定理的理解，也基本停留在“机器学习没有最好的模型，只有最合适的模型”的层面。

这些理解不能算错，不过，这是“推论”，不够原教旨。NFL定理给出的直接结论其实是“从全局来看，所有算法的总误差相等”。下面我们就深入到这个层面重新审视NFL定理。

前面说的“相互补偿”就隐含在这个结论里面。既然全局总误差相等，那在某个局部问题算法误差很小，那必然得在另外某个局部问题上误差很大，这就是相互补偿。这边加一分那边就得减一分，说白了就是零和。

逻辑捋清楚了，可是这么一看，NFL定理就更反直觉了。ChatGPT力压随机瞎猜的例子随处可见，按说也得有相当体量的反例才能“相互补偿”。可是，在哪呢？另外还有个延伸问题也十分有趣，不少人问说既然有NFL定理，研究新模型的意义究竟在哪？

这就要说到那条NFL定理非常关键的假设条件：问题是均匀分布。

均匀分布是关键。不过，这就得先说清楚“问题”究竟是什么，然后才好理解这玩意为啥还能“均匀分布”。按我们惯常的理解，机器学习中的问题约等于学习任务，譬如说有监督学习任务，就是给一套数据集，要求做分类或者做回归。

NFL定理在证明过程中，对问题进行了简化。原始论文一共16页，估计没谁愿意去看，周志华老师在西瓜书中提供了简版证明，在这版证明里面，“问题”是一个映射函数，起个名字叫f，将输入x映射成0或者1。

熟悉机器学习的同学，一看就知道这就是个二分类任务，这个映射函数f就是真值函数，模型要做的，就是通过数据学一个函数，起个名字叫h，让函数h的分布尽可能拟合函数f，也就是尽可能让预测值贴近真值。

接着进入证明的关键部分。推导还是其次，这里我们最需要关注的是前面提到的总误差是怎么算出来的，只有搞清楚总误差怎么算，才能真正理解NFL定理怎样让所有算法总误差相等。

不复杂，拢共两步，首先计算特定真值函数f下的误差（引自西瓜书）：

别看式子里面有的没的好像很多内容，核心就是数一下有多少预测值不等于真值，也就得到了一个真值函数下的误差和。接着更简单，把全部真值函数下的误差和加总，就得到了总误差（引自西瓜书）：

好了，推导过程我就不放了，知道大家都害怕。上面两步的数学式子不难理解，无非就是加完再乘，乘完再加，难理解的是公式背后的意义。

就数学来说，映射可以做排列组合，譬如f(a)和f(b)的结果，就可能有(1,0)、(1,1)、(0,0)、(0,1)一共4种，至于均匀分布，指的就是出现这4种结果的概率是相等的。但是，f可是真值函数，描述的是客观事实，NFL定理难道描述的是薛定谔的世界观，同样一件事，是真是假的概率是50对50？

这里，我想到一个绝妙的比喻。

3.绝妙的比喻

如果我们不把函数f看作是真值函数，而是女孩子的喜好函数，事情就合理多了。

假设a是送礼物，b是看电影，而f返回的结果分别是喜欢（表示为1）、讨厌（表示为0），那么，出现(1,0)、(1,1)、(0,0)、(0,1)这4种情况，实在是合理至极，再加上一个“均匀分布”强设定也是可以的，意思无非就是假设全世界喜欢看电影和讨厌看电影的女孩子各占一半。这点很关键：不一定合乎事实，但合乎逻辑。

那么，学习算法是什么呢？是学习追求女孩子。这里我们暂且放下追求女孩子到底是靠真心还是靠技巧的争论，假设追求女孩子就是“投其所好”，用机器学习的语言来说，就是学习一个函数h，让h的输出尽可能拟合f。

最后聊一聊NFL定理反直觉的部分。现在我们介绍一位名叫“ChatGPT”公子，这位公子有执念，就是喜欢浪漫，追求女孩子一定都要送礼物和请看电影。对于(1,1)类型的女孩子，也就是喜欢礼物和看电影的女孩子，ChatGPT毫无疑问就是情圣，对于(1,0)和(0,1)类型的女孩子，ChatGPT恐怕要被发好人卡，至于(0,0)类型的女孩子，那ChatGPT的表现肯定糟糕透顶，还不如随机瞎猜了。

那么，总误差是什么呢？就是追遍全世界的女孩子，一共收到多少张好人卡。NFL定理给出了结论：甭管用什么方法，只要是均匀分布，收卡的数量都是一样的。

不过，现实世界各种f真的都遵循均匀分布吗？