👏 Hi! 我是 Yumuing，一个技术的敲钟人
👨💻 每天分享技术文章，永远做技术的朝拜者
📚 欢迎关注我的博客：Yumuing's blog
本文将解释违背了我们使用机器学习的初衷的NFL定理，它意味着单纯只能预测已有数据集的机器学习，就学了个寂寞？它是怎么在不被破解的前提下，使得问题摆脱它的影响的。
注：学习自林轩田机器学习基石国语国语
1.1 NFL 定理引入
如果提供六个数据，将它们划分成两类，标识为 $y_n = -1\,，y_n=+1$，此时，给出右边的数据，确定他的类别，此时，给出右边的数据，确定他的类别gx。由于没有统一的标准，比方说，两者的部分划分依据为整体是否为对称图形的话，此时。由于没有统一的标准，比方说，两者的部分划分依据为整体是否为对称图形的话，此时,$gx=+1$，但如果说，划分依据为每个图形最左上角方块颜色是否为黑色的话，那此时，，但如果说，划分依据为每个图形最左上角方块颜色是否为黑色的话，那此时，$gx = -1$ ，两个截然不同的答案存在对错之分吗？没有，它们都是正确的，在无监督式学习下可能会发生的。
也就是说在已有的数据之下，机器学习的结果是能够完成正确划分的，但是，一旦接受了新的数据影响下，已有的机器学习结论可能就无法正确地去进行判断。这种特性被称为没有免费午餐定理（No Free Lunch ，即 NFL 定理）。
NFL定理表明没有一个学习算法可以在任何领域总是产生最准确的学习器。不管采用何种学习算法，至少存在一个目标函数，能够使得随机猜测算法是更好的算法。平常所说的一个学习算法比另一个算法更“优越”，效果更好，只是针对特定的问题，特定的先验信息，数据的分布，训练样本的数目，代价或奖励函数等。也就是说，所有的机器学习算法都是建立在一个个假设之下的演算法的训练。
1.2 解决 NFL 问题
但这定理不就违背了我们使用机器学习的初衷了吗？单纯只能预测已有数据集的机器学习，就学了个寂寞？我们可以从下面一个例子来理解一下，它是怎么在不被破解的前提下，使得问题摆脱它的影响的。
1.2.1 数学统计例子引入
假设要计算一个装有橙色小球和绿色小球且混合均匀的瓶子里面有多少个橙色小球，由于小球数量较多，采用手工计数并不划算。此时，我们可以采用近似拟然估计的方式，也就是说，我们每次任意从已摇匀瓶子中取一个球并记录颜色，重复一百次（为方便表示，图示为重复十次），假如在前面的一百次重复记录中，有七十次是橙色球，请问罐中橙色球所占的比例最有可能是多少？，很多人都会脱口而出：70% ，这是正确的，当然，这是建立在数据足量、独立同分布且随机选取的情况下的近似概率，只能说与真实概率相似。
理论支撑详解可看：一文搞懂极大似然估计 - 知乎 zhihu.com
假设随机选取后橙色球的近似概率为 μ ，但真实概率为 ν 则绿色球近似概率为 1−μ ，真实概率为 1−ν 。并且，如果采用 Hoeffding's inequality 来进行解释的话：
$$P[|v-u|>\epsilon] \leq 2 \exp \left(-2 \epsilon^{2} N\right)$$
当 N 很大的时候，ν 与 μ 相差不会很大，它们之间的差值被限定在 ϵ 之内。我们把结论 μ=ν 称为 probably approximately correct：大致相似PAC：大致相似。
1.2.2 问题延申至机器学习
把上面的思想转换到机器学习之上，不久可以解释机器学习还是存在可行性的吗？我们假设从瓶子中随机选取的小球整体视为机器学习中用来训练的数据集，而瓶子所有小球视为训练数据集和新的预测数据集总和，其中，橙色小球代表机器学习预测失败的情况，而绿色小球代表预测成功的情况。
依据以上例子的思想，随机选取的小球中预测错误的概率（橙色小球概率）与所有小球中预测错误的概率都是 PAC 的，概率类似。此时，我们可以假设前者（训练错误概率）为 $E_{in}(h)$ ，后者（所有样本错误概率）为 $E_{out}(h)$ 。（错误概率表示 h(x) 与 f(x) 不相等的概率：h(x) 为假说公式，f(x)为目标函数）
同样，它的Hoeffding's inequality可以表示为：
$$P[|v-u|>\epsilon] \leq 2 \exp \left(-2 \epsilon^{2} N\right)P\left[\left|E_{\text {in }}(h)-E_{\text {out }}(h)\right|>\epsilon\right] \leq 2 \exp \left(-2 \epsilon^{2} N\right)$$
验证了只要当 N (样本数量)很大的时候，$E_{in}(h)=E_{out}(h)$ 也是 PAC 的。现在只是证明了，其实训练样本和验证样本下，同一个 $h(x)$ 的判断正确与否的概率是一致的，但在不同的数据集下，错误概率的大小却是不一定小的，也就是说 $g\,不一定 \approx f$。也就说，第一个例子（黑白图形）训练出来的划分依据很多，是由于样本数据不完美，存在噪声，没有尽可能囊括基本的特征，也就是存在多个 $E_{in}(h)$ 比较大的情况。
所以，我们需要通过演算法，选择最好的 h ，使得 $E_{in}(h)$ 足够小，从而使得 $E_{out}(h)$ 足够小，才能说明面对同种假设（同分布）下的新数据能够正确的预测。这还没解决 NFL 问题呢，只是提出了解决问题的一些简单前提。
不可避免的是，演算法在不合适的数据集下可能无法真正做到独立随机选取 h ，导致产生一个 $E_{in}(h)$ 与 $E_{out}(h)$ 差别较大的 h 。比如，150 人抛正负概率一致的硬币各五次，每一个人都是一个选取的数据集，150人为总体数据集，此时，可能存在某个人抛出 5 次正面朝上的概率，而这个就是不合适的数据集所产生的 $E_{in}(h) = 0$ 与 $E_{out}(h) = \frac{1}{2}$ 差别较大的 h，该数据集就被称为 Bad Sample 。
其中，M是hypothesis的个数，N是样本D的数量， 是参数。该union bound表明，当 M 有限，且N足够大的时候，Bad Sample 出现的概率就更低了，即能保证D对于所有的 h 都有$E_{in}(h)=E_{out}(h)$，满足PAC，演算法A的选择不受限制。
不同的数据集产生的 h 可以在其他的数据集进行验证错误率，只有某个数据集通过绝大部分的 h 上才是是好的数据。
这样的数据集所包含的 h 是有限个的，这才是基本囊括了机器学习所需要真正学习的内容，通过这样的数据集进行训练，此时，$E_{in}(h)=E_{out}(h)$ 从而得到一个结果为 ，$E_{in}(h) = 0$ 的 h，进而得到一个在其他数据集也能够很好地判断（泛化能力强）的结果。至此，就证明了机器学习是可行的。
但是，如上面的学习流程图右下角所示，如果 M 是无数个，例如之前介绍的 PLA 直线有无数条，是否这些推论就不成立了呢？是否机器就不能进行学习呢？后续分解。
