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

长风万里送秋雁

已于 2022-08-07 12:02:29 修改

阅读量722

点赞数

分类专栏：算法学习文章标签：算法

于 2022-08-07 11:59:11 首次发布

本文链接：https://blog.csdn.net/dscl_yk/article/details/126205817

版权

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

算法宝典西瓜书里绪论里提到了NFL定理，即“没有免费的午餐”，虽然道理很简单，但是证明却稍显简陋。我在拜读了Wolpert在1996年发表的论文后，将整个证明过程阐明如下：
对于某个给定问题，假设存在搜索路径为 $x_0\rightarrow x_1\rightarrow x_2\rightarrow ...\rightarrow x_m$ ，损失函数为 $f (x)$ ，并且假设算法不存在随机性，并且 $x_0\rightarrow x_1\rightarrow x_2\rightarrow ...\rightarrow x_m$ 不存在重复的搜索路径，即 $x_0,x_1,...,x_m$ 互不相等.定义搜寻过程中损失为为 $\vec{c}=$ { $f(x_0),f(x_1),...,f(x_m)$ }，搜寻范围为 $d^x_m$ ，损失函数范围为 $d^y_m$ ，记 $d_m$ 为 $d^x_m$ 和 $d^y_m$ 组成的空间，记算法为 $a$ ，搜寻次数为 $m$ ， $∣ y ∣$ 和 $∣ x ∣$ 为 $d^x_m$ 和 $d^y_m$ 的容量。
当 $m = 1$ 时,