机器学习著名定理之—No Free Lunch定理详解

引言

谈到机器学习一个非常著名的定理，那就不得不提 No Free Lunch 定理了。该定理核心思想是没有一种通用的学习算法可以在各种任务中都有很好的表现，需要对具体问题进行具体的分析。从原理出发去理解 AI 算法可以能够对 AI 相关的问题有更深刻的认识，像这种基于严格数学证明推导出的结论，尤其值得重视。翻阅了大量的相关材料力求让该定理的证明过程更加完整（需要注意的是该定理核心证明步骤中用到了一个修改版本的马尔可夫不等式），相关的材料列在文末。

No Free Lunch 定理证明

定理 1（No Free Lunch）： 假定 是一个在域 的二分类任务中任意一个机器学习算法，其损失函数为 损失。令 是一个大小为 的训练集，存在域 中的分布 ，则有：

• 存在一个函数 ，且有 。
• 对于子列 ，则概率不等式 成立。

证明：

（1）令 表示域 中大小为 的一个子集。主要的证明思路是只利用数据集 一半的数据样本点并不能给出剩下一半数据点的信息。假定 表示数据集 到标签集合 所有可能的函数集合，且 表示的是函数集合的基数，其中 ， 。对于 中每一个函数假设，令 是 中的分布：

进而可知存在函数 ，在数据分布 上则有 。（2）主要证明的关键在于即对任意的学习算法 有：

首先从 中采样出 个样本构造一个训练集，其中采样出的样本可以重复，进而可知有 中可能的样本序列。令这些样本序列分别表示为 。_ 表示的是函数 在样本序列 中的数据集合，则有：

又因为 ，所以则有：

现固定 ，令 ， ，其中 是剩余没有采样的样本数。对于每一个函数 ， 有：

所以

对于给定的 ，因为 是所有可能函数映射的基数，所以总有成对存在的 有：

进而则有：

根据马尔可夫不等式的修改版可知，给定一个随机变量 ，给定一个常数 ，进而则有：

马尔可夫不等式为：

利用马尔可夫不等可知：

No Free Lunch和先验知识

训练一个分类器的时候经常会用到一些先验知识，那 No Free Lunch 定理与先验知识有什么关系呢？考虑一个 ERM（Empirical Risk Minimization）分类器，其所有分类映射 组成了集合 。这类映射集合 缺乏先验知识，则根据 No Free Lunch 定理可知，给定一个学习算法，会在一些学习任务中学习失败，所以可以推知，该类学习算法 不是 PAC（Probably Approximately Correct）学习的。

定义1（PAC）：如果一个学习算法集合 是 PAC 学习的，存在一个计数函数 。一个学习算法对于任意的 ，任意的在域 中的分布 和任意的打标函数 ，则有该类学习算法数 ，并存在一个学习算法 ，满足以下概率公式：

根据 PAC 学习的定义和 No Free Lunch 定理可知，则有如下推论：

推论 1：令 是一个无限域集， 是所有 的函数集合，则 不是 PAC 可学习的。

证明：该推论可以利用反证法来证明。假定 是 PAC 可学习的。选取 和 。通过 PAC 的定义可知，一定存在学习算法 ，其数量为 ，对于任意在 上生成的数据分布，如果对于一些函数 ，使得 ，并且当 在采样出 个样本的数据集合 上，有：

然后由 No Free Lunch 定理可知，当 ，对于每一个学习算法，存在分布 使得：

所以出现矛盾。

那要如何防止这种失败？通过使用对特定学习任务的先验知识，可以避免 No Free Lunch 定理所预见的风险，从而避免在学习该任务时那些导致失败的分布的出现，所以可知先验知识主要通过限制学习算法类  的范围。

误差分解

令 是一个 映射，则可以 误差可以由如下公式表示：

误差分解为两部分，一个是近似误差，另一个是估计误差。

• 近似误差：近似误差是一种归纳偏差，它不取决于训练样本集的大小，而是由所由训练出的分类器的映射所决定。增大映射的范围可以减小近似误差。在可实现性假设下，近似误差为零。然而，在不可知论的情况下，近似误差可能很大。

• 估计误差：近似误差和 ERM 预测值所获得的误差之间的差值。估计误差的产生是因为经验风险（即训练误差）只是对真实风险的估计，因此最小化经验风险的预测器只是最小化真实风险的预测器的估计。这种估计的质量取决于训练分类器的训练集大小以及复杂性。

由于目标是将总损失降至最低，因此就需要面临着一种权衡，称为偏差-复杂性权衡。一方面，分类器集合 越大（模型的容量过大，自由度过高）会减少近似误差，但同时可能会增加估计误差，因为丰富的 可能会导致过度拟合。

反之，一个非常小的集合（即模型容量不够大，或者没有涵盖到真实的目标函数）会减少估计误差，但可能会增加近似误差，或者换句话说，可能会导致拟合不足。No Lunch Theorem 定理指出，没有通用的学习算法，每个学习算法都必须被指定完成某项任务，并使用有关该任务的一些先验知识。

参考文献

[1] https://www.youtube.com/watch?v=DxaK8OSnxvE&list=UUaJUsUVO8sj71H5gCVgh7sw&index=41

[2] https://www.youtube.com/watch?v=wilz_c07ImI&list=UUaJUsUVO8sj71H5gCVgh7sw&index=40

[3] https://en.wikipedia.org/wiki/No_free_lunch_theorem

[4] https://ti.arc.nasa.gov/m/profile/dhw/papers/78.pdf

更多阅读

#投 稿 通 道#

 让你的文字被更多人看到 

如何才能让更多的优质内容以更短路径到达读者群体，缩短读者寻找优质内容的成本呢？答案就是：你不认识的人。

总有一些你不认识的人，知道你想知道的东西。PaperWeekly 或许可以成为一座桥梁，促使不同背景、不同方向的学者和学术灵感相互碰撞，迸发出更多的可能性。 

PaperWeekly 鼓励高校实验室或个人，在我们的平台上分享各类优质内容，可以是最新论文解读，也可以是学术热点剖析、科研心得或竞赛经验讲解等。我们的目的只有一个，让知识真正流动起来。

📝 稿件基本要求：

• 文章确系个人原创作品，未曾在公开渠道发表，如为其他平台已发表或待发表的文章，请明确标注 

• 稿件建议以 markdown 格式撰写，文中配图以附件形式发送，要求图片清晰，无版权问题

• PaperWeekly 尊重原作者署名权，并将为每篇被采纳的原创首发稿件，提供业内具有竞争力稿酬，具体依据文章阅读量和文章质量阶梯制结算

📬 投稿通道：

• 投稿邮箱：hr@paperweekly.site 

• 来稿请备注即时联系方式（微信），以便我们在稿件选用的第一时间联系作者

• 您也可以直接添加小编微信（pwbot02）快速投稿，备注：姓名-投稿

△长按添加PaperWeekly小编

🔍

现在，在「知乎」也能找到我们了

进入知乎首页搜索「PaperWeekly」

点击「关注」订阅我们的专栏吧

·