没有免费午餐定理NFL

没有免费午餐定理是说：对于完全随机的问题，所有算法的平均性能相同。这意味着如果一个算法在某些问题上工作得较好，那么一定存在一些其他的问题使得该算法的性能较差。因此脱离具体的问题而空谈算法好坏没有意义

假定样本空间 $\chi$ 与假设空间 $H$ 离散，现有一个算法 $L$ ，设其经过训练数据 $X$ 的训练后得到假设空间中的一个函数 $h$ 的概率为

P(h|X,L)

再设真实的函数为 $f$ ，那么误差就是

E(L|X,f)=\sum_h\sum_{x\in \chi-X}P(x)\mathbb{I}[h(x)\neq f(x)]P(h|X,L)

其中 $\mathbb{I}$ 为示性函数

\mathbb{I}(x)= \begin{cases} 1&x=true\\ 0&x=false \end{cases}

考察二分类问题，可能的真实目标函数空间是

\{0,1\}^{|\chi|}

意为对于所有样本，都有不同的函数将它们映射到0或是1。假设所有的 $f$ 服从均匀分布，那么对于所有可能的 $f$ 误差之和为

\sum_fE(L|X,f)=\sum_f\sum_h\sum_{x\in \chi-X}P(x)\mathbb{I}[h(x)\neq f(x)]P(h|X,L)

调整求和顺序

\sum_fE(L|X,f)=\sum_{x\in \chi-X}P(x)\sum_hP(h|X,L)\sum_f\mathbb{I}[h(x)\neq f(x)]

由于 $f$ 服从均匀分布，所以对一个样本而言有一半分类正确另一半分类不正确。又因为总的函数数目为 $2^{|\chi|}$ ，所以

\sum_fE(L|X,f)=\dfrac12\cdot2^{|\chi|}\sum_{x\in \chi-X}P(x)\sum_hP(h|X,L)

对所有的 $h$ 其生成概率之和应当是归一化的，所以

\sum_fE(L|X,f)=2^{|\chi|-1}\sum_{x\in \chi-X}P(x)

所以得到分类错误与算法 $L$ 是无关的