机器学习中的“没有免费午餐”理论

在机器学习中，没有免费午餐理论（No Free Lunch Theorem, NFL）是一个重要且有趣的理论，此理论指出，若考虑所有可能的问题，那么每个学习算法的期望性能都是一样的，都等于随机猜测。本文将对这一结论进行解释。

在实际的问题中，我们能获取的数据都是有限的，因此能够拟合这些数据的函数有无数个。例如下图中，黑点表示数据，A线和B线都能够很好的拟合这几个数据点。那么，哪个曲线更好呢？

实际上，仅仅从这几个数据点来看，我们无法判断哪个更好，或者说，A和B是一样好的。然而在面对新的数据点的时候，A和B的表现就会出现不同。

如果是下图所示的情况，那么A优于B，因为A线更符合数据的规律。

A优于B（实心点为训练数据，空心点为测试数据）

但是，如果是下图所示的情况，则是B优于A，因为B线更符合数据的规律。

B优于A（实心点为训练数据，空心点为测试数据）

从这个例子可以看出，具体哪一个函数更好，取决于数据本身的规律，而这个规律，从有限的观测数据中，是不可能绝对准确地把握的。

没有免费午餐理论所证明的，正是上面这一结论：能产生所观测到的数据的规律有无穷多种，而一个函数只能很好的拟合其中某些规律，而无法很好的拟合另外一些；如果考虑所有这些可能的规律，那么任何函数都只是在进行随机猜测而已。

正如周志华老师所言：没有免费午餐定理最重要的寓意，是让我们清楚地认识到，脱离具体问题，空泛地谈论“什么学习算法更好“毫无意义，因为若考虑所有潜在的问题，则所有的算法一样好。要谈论算法的相对优劣，必须要针对具体问题；在某些问题上表现好的学习算法，在另一问题上却可能不尽如人意，学习算法自身的归纳偏好与问题是否相配，往往会起到决定性作用。

最后，在本文的例子中，通常我们会人为A更好，因为它足够简单，且拟合的足够好，这是因为我们所面临的很多问题都并不复杂，通常使用比较简单的方法就可以取得很好的效果。这也是“奥卡姆剃刀”原则所阐述的思想，即“若有多个假设与观察一致，则选最简单的那个”。

奥卡姆本尊