没有免费的午餐！没有免费的午餐！没有免费的午餐！重要的事情说三遍。
【西瓜书】中对NFL（没有免费的午餐）定理进行了证明（【西瓜书式（1.1）（1.2）（1.3）】），但过于简化，本文对几个关键点进行补充，从而给出详细的证明。

NFL的证明*

（1）指示函数（用I的变体$\mathbb{I}$表示）
$$\mathbb{I}(\mathbf{x}\in A)=\{\begin{array}{l}1,\text{当x∈A}\\ 0,\text{当x∈/A}\end{array}\text{\hspace{1em}(1)}$$

（2）误差（点$\mathbf{x}$处的误差）

设点$\mathbf{x}$处的真实值为$f(\mathbf{x})$，预测值为$h(\mathbf{x})$，将预测点$\mathbf{x}$处误差记为
$$E_h(\mathbf{x})=\{\begin{array}{l}1,\text{当预测不准时}\\ 0,\text{当预测准确时}\end{array}\text{\hspace{1em}(2)}$$
记 A = { x : h ( x ) ≠ f ( x ) } A=\{\boldsymbol{x}: h(\boldsymbol{x})\neq f(\boldsymbol{x})\} A={x:h(x)=f(x)}，则由式(1)、式(2)有
$$E_h(\mathbf{x})=\mathbb{I}(h(\mathbf{x})\ne f(\mathbf{x}))\text{\hspace{1em}(3)}$$
（3）期望误差（对于固定的模型$h$，每点的期望误差）

设样本空间（sample space）为$\mathcal{X}$，训练集为$X$，$\mathbf{x}$的概率函数为$P(\mathbf{x})$，对于固定的模型$h$，求$\mathcal{X}╲X$上各点误差的平均值，记为${\overline{E}}_h$，则由式(3)有
$${\overline{E}}_h=\underset{\mathcal{X}╲X}{\mathbb{E}}(E_h(\mathbf{x}))=\sum _{\mathbf{x}\in \mathcal{X}╲X}P(\mathbf{x})\mathbb{I}(h(\mathbf{x})\ne f(\mathbf{x}))\text{\hspace{1em}(4)}$$

（4）期望误差（对于固定的算法${\mathcal{L}}_a$，每点的期望误差）

前述式(4)是基于固定的$h$的期望误差，而在已知训练集$X$条件下，算法${\mathcal{L}}_a$可产生多种$h$，设产生$h$的概率为$P(h|X,{\mathcal{L}}_a)$，则对于前述${\overline{E}}_h$再做基于$h$的平均（即求基于$h$的期望）
$$\underset{h:{\mathcal{L}}_a}{\mathbb{E}}\left({\overline{E}}_h\right)=\sum _h{\overline{E}}_{h}P(h|X,{\mathcal{L}}_a)\text{\hspace{1em}(5)}$$
而
$$\sum _{h}P(h|X,{\mathcal{L}}_a)=1\text{\hspace{1em}(6)}$$

因预报范围为$\mathcal{X}╲X$，故将其记为$E_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)$（其下标$\mathrm{ote}$指：off-training error），即
$$E_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)=\underset{h:{\mathcal{L}}_a}{\mathbb{E}}\left({\overline{E}}_h\right)\text{\hspace{1em}(7)}$$
由式(4)、式(5)、式(7)即得【西瓜书式(1.1)】

（5）现考虑二分问题所有可能的真值情况，真值函数为 f : X ↦ { 0 , 1 } f:\mathcal{X}\mapsto \{0,1\} f:X↦{0,1}，反之，任一个这类映射都有一个真值函数，所有的$f$组成一个集合$\mathcal{F}$（函数空间），该集合中元素$f$的个数为
$$|\mathcal{F}|=2^{|\mathcal{X}|}\text{\hspace{1em}(8)}$$
显然，集合$\mathcal{F}$具有对称性，即对于固定的$\mathbf{x}\in \mathcal{X}$，一定有一对$f_1,f_2\in \mathcal{F}$，使得
$$\{\begin{array}{l}{f}_1(\mathbf{x})=0\\ f_2(\mathbf{x})=1\end{array}\text{\hspace{1em}(9)}$$
即固定$\mathbf{x}$，则$|\mathcal{F}|$中的元素$f$，一半使得$f(\mathbf{x})=0$，另一半使得$f(\mathbf{x})=1$。

（6）现考虑二分问题的一个预测模型$h$。

当$h(\mathbf{x})=0$时
$$\begin{array}{rl}\sum _f\mathbb{I}(h(\mathbf{x})\ne f(\mathbf{x}))& =\sum _f\mathbb{I}(f(\mathbf{x})\ne 0)\\ & =\sum _f\mathbb{I}(f(\mathbf{x})=1)\\ & =\frac{1}{2}|\mathcal{F}|\text{（由前述的对称性）}\\ & =2^{|\mathcal{X}|-1}\text{（由式(8)）}\end{array}$$

当$h(\mathbf{x})=1$时,同样推导，即无论$h(\mathbf{x})$为0还是1，都有
$$\sum _f\mathbb{I}(h(\mathbf{x})\ne f(\mathbf{x}))=2^{|\mathcal{X}|-1}\text{\hspace{1em}(10)}$$

（7）考虑$\mathcal{F}$中，关于$f$的总误差。 即对【西瓜书式(1.1)】求关于$f$的和。
$$\begin{array}{rl}\sum _f{E}_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)& =\sum _f\sum _h\sum _{\mathbf{x}\in \mathcal{X}╲X}(\cdots )\text{（(⋯)表示省略）}\\ & =\sum _{\mathbf{x}\in \mathcal{X}╲X}\sum _h\sum _f(\cdots )\text{（交换次序）}\\ & =\sum _{\mathbf{x}\in \mathcal{X}╲X}\sum _{h}P(\mathbf{x})P(h|X,{\mathcal{L}}_a)\sum _f\mathbb{I}(h(\mathbf{x})\ne f(\mathbf{x}))\\ & =\sum _{\mathbf{x}\in \mathcal{X}╲X}\sum _{h}P(\mathbf{x})P(h|X,{\mathcal{L}}_a)2^{|\mathcal{X}|-1}\text{（由式(10)）}\\ & =2^{|\mathcal{X}|-1}\sum _{\mathbf{x}\in \mathcal{X}╲X}P(\mathbf{x})\sum _{h}P(h|X,{\mathcal{L}}_a)\\ & =2^{|\mathcal{X}|-1}\sum _{\mathbf{x}\in \mathcal{X}╲X}P(\mathbf{x})\text{（由式(6)）}\end{array}\text{\hspace{1em}(11)}$$

（8）由式(11)可知，总误差${\sum }_f{E}_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)$竟然与算法${\mathcal{L}}_a$无关，即用算法${\mathcal{L}}_b$去推导仍是相同的结果。 表明：无论聪明的算法${\mathcal{L}}_a$还是笨拙的算法${\mathcal{L}}_b$的期望性能（总误差）相同，故区分不了聪明与笨拙。 这就是“没有免费的午餐”定理（NFL）。 为什么会出现这种不可思议的情况呢？其原因：我们指望找一个算法“通吃”$\mathcal{F}$中的所有$f$，依此去求总误差，在推导中又“假设$f$是均匀分布”，（NFL）定理可以理解为：任一个算法总会在某些$f$上表现好，在某些$f$上表现差（【西瓜书图1.4】说明了这一点），平均下来各算法表现在“$f$是均匀分布”的前提下是一样的，即此时各算法的总误差是一样的。

好在“$f$是均匀分布”被现实世界所否定，即并非任意的映射 f : X ↦ { 0 , 1 } f:\mathcal{X}\mapsto \{0,1\} f:X↦{0,1}都可以作为一种真实情况而存在，有的$f$在实际中罕见，甚至根本不存在。 可以理解成：现实世界是经过“筛选”了的。
当我们放弃寻找“通吃”的算法时，即针对具体的实际问题（$f$）可以去考虑该误差的最小化（误差$E_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)$与$f$有关），这才是机器学习的任务。

（9）前述 NFL（没有免费的午餐）定理，使用的是“分类错误率”作为性能度量指标，若使用其他性能度量$\ell$，NFL（没有免费的午餐）定理仍成立。

式(2)变为
$$E_h(\mathbf{x})=\{\begin{array}{l}\alpha ,\text{当预测不正确时}\\ \beta ,\text{当预测正确时}\end{array}$$
即
$$E_h(\mathbf{x})=\{\begin{array}{l}\alpha ,\text{当f(x)=h(x)时}\\ \beta ,\text{当f(x)=h(x)时}\end{array}\text{\hspace{1em}(12)}$$
在$\mathcal{X}$上进行任意二分类（随便分），则共有$2^{|\mathcal{X}|}$个不同的二分类器 f : X ↦ { 0 , 1 } f:\mathcal{X}\mapsto \{0,1\} f:X↦{0,1}，$f$组成集合$\mathcal{F}$，不妨记为$|\mathcal{F}|=2^{|\mathcal{X}|}=n$。 显然$\mathcal{F}$中$f$具有对称性：对于固定的$\mathbf{x}$和$h$，则$\mathcal{F}$中的元素$f$，一半使得$f(\mathbf{x})=h(\mathbf{x})$，另一半使得$f(\mathbf{x})\ne h(\mathbf{x})$，各占$\frac{n}{2}$个。

由式(12)及对称性，对于固定的$\mathbf{x}$和$h$，有
$$\begin{array}{rl}\sum _f{E}_h(\mathbf{x})& =\sum _{f(\mathbf{x})\ne h(\mathbf{x})}{E}_h(\mathbf{x})+\sum _{f(\mathbf{x})=h(\mathbf{x})}{E}_h(\mathbf{x})\\ & =\sum _{f(\mathbf{x})\ne h(\mathbf{x})}\alpha +\sum _{f(\mathbf{x})=h(\mathbf{x})}\beta \\ & =\frac{n}{2}\alpha +\frac{n}{2}\beta \\ & =2^{|\mathcal{X}|-1}(\alpha +\beta )\end{array}\text{\hspace{1em}(14)}$$

采用NFL定理证明中的符号，式(11)的推导此时变为
$$\begin{array}{rl}\sum _f{E}_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)& =\sum _{\mathbf{x}\in \mathcal{X}╲X}\sum _{h}P(\mathbf{x})P(h|X,{\mathcal{L}}_a)\sum _f{E}_h(\mathbf{x})\\ & =\sum _{\mathbf{x}\in \mathcal{X}╲X}\sum _{h}P(\mathbf{x})P(h|X,{\mathcal{L}}_a)2^{|\mathcal{X}|-1}(\alpha +\beta )\text{（由式(14)）}\\ & =2^{|\mathcal{X}|-1}(\alpha +\beta )\sum _{\mathbf{x}\in \mathcal{X}╲X}P(\mathbf{x})\sum _{h}P(h|X,{\mathcal{L}}_a)\text{（由式(6)）}\\ & =2^{|\mathcal{X}|-1}(\alpha +\beta )\sum _{\mathbf{x}\in \mathcal{X}╲X}P(\mathbf{x})\end{array}\text{\hspace{1em}(15)}$$
由式(15)可知，总误差${\sum }_f{E}_{\mathrm{ote}}\left({\mathcal{L}}_a|X,f\right)$与算法${\mathcal{L}}_a$无关，定理得证。

本文为原创，您可以：

• 点赞（支持博主）
• 收藏（待以后看）
• 转发（他考研或学习，正需要）
• 评论（或讨论）
• 引用（支持原创）
• 不侵权

上一篇：1-4 机器学习中的三个空间
下一篇：2.1误差，还是有误差