纽约大学：无免费午餐定理、科尔莫哥洛夫复杂度以及归纳偏差在机器学习中的作用

​

监督学习中的“不存在免费午餐定理”指出，没有一个学习器可以解决所有问题，也没有一个学习器可以在学习问题的统一分布上平均达到完全相同的准确性。因此，这些定理经常被引用来支持个别问题需要特别定制归纳偏见的观点。虽然几乎所有均匀采样的数据集复杂度很高，但真实世界的问题会不成比例地生成低复杂度的数据，我们认为神经网络模型也有这种偏好，可以用Kolmogorov复杂度加以形式化。值得注意的是，我们展示了针对特定领域的网络结构，例如计算机视觉，可以压缩各种看似不相关的领域的数据集。我们的实验表明，预训练甚至随机初始化的语言模型都倾向于生成低复杂度的序列。尽管不存在免费午餐定理似乎表明需要专门的学习器来解决个别问题，但我们解释了在有限的机器学习模型集内自动实现对人类干预的任务的趋势，例如在标记数据稀缺或丰富时选择合适大小模型的任务。这些观察结果证明了深度学习中将看似不相关的问题统一到越来越少的机器学习模型集中的趋势。

总结：

本文主要介绍了无免费午餐定理、科尔莫哥洛夫复杂度以及归纳偏差在机器学习中的作用。无免费午餐定理表明，对于所有可能的学习问题和算法，其期望表现是相同的，没有一种通用的学习算法能够在所有问题上表现优异。科尔莫哥洛夫复杂度则是用来衡量信息的复杂程度，它提供了一种衡量学习算法效率的方法。而归纳偏差则是指在学习过程中所引入的关于数据分布的先验偏好，它能够帮助机器学习算法在大量数据中进行学习，提高模型的泛化能力。最后文章还介绍了一些机器学习中使用的归纳偏差方法以及如何在设计机器学习算法时考虑归纳偏差的影响。

标题：The No Free Lunch Theorem, Kolmogorov Complexity, and the Role of Inductive Biases in Machine Learning

作者：Micah Goldblum, Marc Finzi, Keefer Rowan, Andrew Gordon Wilson

​Read More