没有免费午餐

作者: Mstarece | 来源:发表于2019-05-03 23:37 被阅读1次

好的，相信你多半可能是对这个标题产生兴趣才进来的，本文章可跟吃的没有任何关系呢，"没有免费午餐"定理(No Free Lunch，简称NFL)是Wolpert和Macerday提出的“最优化理论的发展”之一。不和吃的有关你可能会失望了，但是这是一个非常有趣的一个定理，我相信等你看完你也会觉得的。

我们先来思考一下这么一个问题，现在机器学习和深度学习在我们的生活中，已经成为了不可缺少的一部分，就单单对我们生活而言，他们的发展极大方便了我们的生活，例如你每天都要使用手机上网，互联网的存在以及它们的应用给你带来了乐趣和便利。那么既然机器学习和深度学习的成功，存不存在着一种算法，它能够在任何领域，任何情况下都表现为最佳，即有没有一种最好的算法，这样科学家们只需要努力的寻找这么一种算法就好了，但是很遗憾，事实证明，这并不存在。那么接下来，我们就来一起证明一下这个定理。接下来会涉及一点数学，每步我都会进行解释，看看数学家们是如何运用数学来完美解释的！

简单说一下机器学习，是建立一个解决问题的模型（算法)，然后通过对给定训练集的样本进行学习，通过学习不断优化自身，让其向这个问题的真实模型靠近，最后学得一个模型，使得能够在训练集之外的样本，即未见样本，对其进行预测，仍会有好的表现！

例如我们现在要训练一个模型，让它能够用来对西瓜进行分类，将西瓜分成好瓜和坏瓜，这是一个二分类问题。给的的训练集是西瓜的一些属性，例如假设决定西瓜得好坏由一下属性决定，当模型在这个数据集上进行学习，不断得优化自己，然后在未见样本下，对其进行预测，仍然有很好得表现！即我们模型的泛化能力很好，这是我们训练模型的终极目标！

首先，假设一个算法为a，而随机胡猜的算法为b，为了简单起见，假设样本空间为 $\gamma$ 和假设空间H 都是离散的。令 P(h|X,a) 表示算法a基于训练数据 X 产生假设h 的概率，再令 f 代表我们希望学习的真实目标函数。算法a的训练集外（测试集）误差，即算法a在训练集之外（测试集）的所有样本上的误差为：

$E_{ote}(a|X,f)=\sum_{h}\sum_{x\in \gamma -X}P(X)l(h(x)\neq f(x))P(h|X,a)$

其中函数 $l(\bullet )$ 为指示函数，当里面的为真，即 $h(x)\neq f(x)$ ,函数取值为1，否则为0. $P(h|X,a)$ 表示在使用算法a时，认为训练集数据X为假设h的概率。

令人生畏的长公式，不过我们来依次解读它，

首先看里面这个， $\sum_{x\in \gamma -X}P(X)l(h(x)\neq f(x))$ , 预测值h(x)与真实值f(x)一致则误差为0，不一致则误差为1，即I(h(x)≠f(x))，由于x是一个随机变量，那么这个误差值也是一个随机变量，取值为0或1，其在训练集之外的所有样本上的期望可以看作假设函数h 在训练集之外的所有样本上预测的错误率，定义为假设函数h 对训练集之外的样本 x 的误差

与此同时，在算法a 的假设空间中可能会存在多个假设函数与训练集一致，每一个假设函数的产生是有概率的，假设算法a在训练数据集X上产生某个假设h的概率为 P(h|X, a)（在使用算法a，把训练集样本X,认为是假设h的概率），那么，我们接下来要做的是定义a在“训练集之外的所有样本上的误差”，而不单单只是a产生的一个假设h的误差。

我们已经定义了假设函数h 在训练集之外的所有样本上的误差，由于假设h是算法a以概率P(h|X, a)产生的，那么我们可以定义算法a的误差为所有可能的h的误差的期望，所以按照上面的那个方式，同理，在外面嵌套一层即可，即：

$E_{ote}(a|X,f)=\sum_{h}\sum_{x\in \gamma -X}P(X)l(h(x)\neq f(x))P(h|X,a)$

接下来，考虑二分类问题，而且真实目标函数可以是任何函数 $\gamma\rightarrow \left\{ 0,1\right\}$ ，假设对所有可能的f按均匀分布对误差求和，有:

$\sum_{f}E_{ote}(a|X,f)=\sum_{f}\sum_{h}\sum_{x\in \gamma -X}P(X)l(h(x)\neq f(x))P(h|X,a)$

因为每个乘积都是独立的，所以可以把求和符号放到任意位置，

$=\sum_{x\in \gamma -X}P(X)\sum_{f}l(h(x)\neq f(x))\sum_{h}P(h|X,a)$

因为根据假设所有可能的f满足均匀分布，所以 $\sum_{f}l(h(x)\neq f(x))$ 会有一半为0，一半为1，然后任何函数取值都为0和1，样本空间有 $\vert \gamma \vert$ 个元素，令 $n= |\gamma |$ ,所以 $\sum_{f}l(h(x)\neq f(x)) = \frac{1}{2} 2^n$ ，然后 $\sum_{h}P(h|X,a) = 1$ ，因为在所有情况下概率和为1嘛。即：