无免费午餐定理 (NFL) 指出

定理 (Wolpert and Macready 1997)让$A$是关于二元分类任务的任何学习算法 $0−1$域损失$\chi$. 让$m$是任何小于的数 $|X |/2$，表示训练集大小。那么，存在一个分布$D$超过$X \times \{0, 1\}$这样：

1. 存在一个函数$f : X \rightarrow \{0, 1\}$和$L_D(f) = 0$.
2. 至少有概率$1/7$在选择$S \sim D^m$, 我们有$L_D(A(S)) \geq 1/8$.

在哪里$L_D$是预测规则的误差。

我知道 ML 社区中的一些人发现 NFL 定理的相关性值得怀疑，因为它似乎假设所有假设的类别都是均匀分布的$H = \{ f \text{ such that } f : X \rightarrow \{0, 1\} \}$，特别是它包括对抗性问题类。

那么NFL提出的问题有多严重？或者你能把一个结构有多合理$H$在你得到免费午餐之前？

你能描述一下所需的复杂性吗$H$没有免费的午餐需要举行吗？或者你什么时候有免费午餐？