Select Language

AI社区

AI技术百科

没有免费的午餐定理(No Free Lunch Theorem,简称 NFL)

我们经常听人谈论“什么算法更好”或者“A算法比B算法好”这样类似说法,其实这样的说法忽略了一个前提,那就是在解决某一个具体的问题(任务)上。为什么这么说呢,因为如果考虑所有潜在的问题,所有的学习算法都一样好。要谈论算法的相对优劣,必须要针对具体的问题和任务才有意义。

举个例子,我们有两组数据集,将它们分别切分成训练集和测试集之后,然后通过假设函数A和B分别拟合对应的两个训练集,得到结果如下:

在图(a)中的数据分布下,模型A和B都完美地拟合了所有的训练样本,但是在测试样本上的表现,模型A的拟合效果超过了模型B;在图(b)中的数据分布下,模型A和B同样完美地拟合了所有的训练样本,但是在测试样本上的表现,模型B的拟合效果超过了模型A。

上面的例子充分说明了没有哪个算法是绝对完美的,每个算法都有它适合的数据集,也就是说它适合的任务。

没有免费的午餐定理(No Free Lunch Theorem,简称 NFL)说的就是无论我们能设想到的最先进的算法还是多么笨拙的算法(比如胡乱猜测),它们的期望性能其实都是相同的。

这个结论看起来非常地“匪夷所思”,但实际上它是成立的。不过它成立的前提在所有可能出现的数据分布上。但是在实际生活中,我们很多时候只关注自己试图解决的问题,希望为它找到一个好的解决方案。举个实际生活中的场景,比如说你的家里地铁口有800m,你上班时想快速到达地铁口,这时候选择共享单车就是一个不错的方案;但如果说你想快速从北京到上海,这时候,共享单车显然不是一个好的选择。所以我们关注的就是在当前要解决的问题下(或者任务下),为它找到一个合适的解决方案。

所以说,机器学习研究的目标不是找一个通用学习算法或是绝对最好的学习算法。反之,我们的目标是理解什么样的分布与机器学习获取经验的“真实世界”相关,什么样的学习算法在我们关注的数据生成分布上效果最好。


我要发帖
机器学习术语表
2021-05-15 22:22:51加入圈子
机器学习是一门多学科交叉专业,涵盖概率论知识,统计学知识,近似理论知识和复杂算法知识,使用计算机作为工具并致力于真实实时的模拟人类学习方式,并将现有内容进行知识结构划分来有效提高学习效率。