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

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

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

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

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

A优于B(实心点为训练数据,空心点为测试数据)

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

B优于A(实心点为训练数据,空心点为测试数据)

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

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

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

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

奥卡姆本尊

  • 发表于:
  • 原文链接:http://kuaibao.qq.com/s/20171227A0ZO6100?refer=cp_1026

扫码关注云+社区