NFL定理

NFL定理 #

“No Free Lunch Theorem”, 简称 NFL 定理, 是由 David Wolpert 和 William Macready 于 1997 年提出的, 它对机器学习的局限性提供了深刻的洞见.

NFL 定理告诉我们, 不同算法的期望性能是相同的. 具体而言, 考虑离散的样本空间 $\mathcal{X}$ 和假设空间 $\mathcal{H}$ , 如果想要学习的真实目标函数为 $f$ , 那么对于给定模型 $\mathfrak{L}$ , 其训练集外误差为 $$ E_{ote}\left(\mathfrak{L}|X,f\right) =\sum_{h}\sum_{x\in \mathcal{X}-X}P\left(x\right)\mathbb{I}\left(h\left(x\right)\neq f\left(x\right)\right)P\left(h\mid X,\mathfrak{L}\right) $$ 假定 $f$ 服从均匀分布, 那么对误差项求和, 有 $$ \begin{aligned} \sum_{f}E_{ote}\left(\mathfrak{L}|X,f\right)
& =\sum_{f}\sum_{h}\sum_{x\in \mathcal{X}-X}P\left(x\right)\mathbb{I}\left(h\left(x\right)\neq f\left(x\right)\right)P\left(h\mid X,\mathfrak{L}\right) \\ &=\sum_{x\in{\cal X}-X}P(x)\sum_{h}P(h\mid X,{\mathfrak{L}})\sum_{f}\mathbb{I}(h(x)\neq f(x)) \\ &=\sum_{x\in{\cal X}-X}P\left(x\right)\sum_{h}P\left(h|X,{\mathfrak{L}}\right)\frac{1}{2}2\left|X\right| \\ &=\frac{1}{2}2^{\left|\mathcal{X}\right|}\sum_{x\in\mathcal{X}-X}P\left(x\right)\sum_{h}P\left(h\mid X,\mathfrak{L}\right) \\ &=2^{|\mathcal{X}|-1}\sum\limits_{x\in\mathcal{X}-X}P(x) \cdot 1 \end{aligned} $$ 可以发现总误差 (平均误差) 与算法 $\mathfrak{L}$ 没有关系.