No Free Lunch Theorem 没有免费午餐定理

没有免费午餐定理

定义

如果我们不对特征空间有先验假设，则所有算法的平均表现是一样的。

In computational complexity and optimization the no free lunch theorem is a result that states that for certain types of mathematical problems, the computational cost of finding a solution, averaged over all problems in the class, is the same for any solution method.
“没有免费午餐定理”（No Free Lunch Theorem）: 任何一个预测函数，如果在一些训练样本上表现好，那么必然在另一些训练样本上表现不好，表现好与表现不好的情况一样多。
D.H. Wolpert, W.G. Macready, No free lunch theorems for search, Technical Report SFI-TR-95-02-010. Santa Fe Institute, Santa Fe, NM. 1995

解释

2个存储空间

假设一台计算机上有只有两个存储单元，每个存储单元的位置上要么属于第一类，要么属于第二类。我们用○，代表第一类，用×代表第二类。假设我们知道一个存储位置为○，要预测另一个位置是○还是×

3个存储空间

没有训练样本

有一个训练样本

5*5个存储空间的时候

道理

我们认为：特征差距小的样本，更有可能是同一类。