本站内容均来自兴趣收集,如不慎侵害的您的相关权益,请留言告知,我们将尽快删除.谢谢.
引言
谈到机器学习一个非常着名的定理，那就不得不提 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
Be First to Comment