机器学习中的「哥德尔定理」

机器学习关注设计和分析算法，其中算法可以利用数据学习并提升性能。下面的例子说明了这个想法的力量：虽然似乎不可能通过显示编程来让计算机识别图像中的目标，但机器学习系统经过标记图像的训练后可以实时识别目标。

从随机示例数据库中学习预测器（可用于进行预测的数学函数）的目标被形式化为可能近似正确（PAC）的学习模型。在此模型中，目标是训练预测器以匹配标记数据的某些真实函数。另一种称为在线学习的模型让学习器在拿到数据时立即做出预测。例如，捕获交易系统在不断变化的市场中执行交易的任务。另一种被称为多臂 bandits 的模型可以模拟临床试验，其中实验者观察到的医疗结果取决于其自己的选择。

这些只是机器学习中使用的许多模型的几个例子。在每种情况下，模型的基本目标是和最佳预测器（例如神经网络或决策树）一样或几乎一样地执行一系列函数。对于给定的模型和函数族，如果可以在一些合理的约束下实现该目标，则称该函数族在该模型中是可学习的。

机器学习理论通常能够将关于特定函数族的可学习性的问题转化为涉及分析衡量函数复杂性的某些方面的各种维度概念的问题。例如，用于分析 PAC 学习的适当概念称为 Vapnik-Chervonenkis（VC）维度。并且一般而言，与复杂性相关的可学习性结果有时被称为 Occam-razor 定理。这些维度概念恰好足够简单，不会为任何不可证明性留下空间。但 Ben-David 及其同事表明，机器学习并不总能逃脱这种命运。他们引入了一种称为估计最大值（EMX）的学习模型，并发现一系列函数，这些函数在 EMX 中的可学习性在标准数学中无法证明。

Ben-David 等人描述了 EMX 问题的一个例子：对访问网站最频繁的用户进行定向广告推荐，其中将访问网站的用户是不能事先知道的。作者将 EMX 形式化为学习器从给定函数族寻找函数的能力的问题，该函数的目标分布的期望值尽可能大。EMX 和 PAC 模型很像，但其中细微不同的学习标准意外地将其联系到了连续统假设，并带来了不可证明性。

作者的证明涉及机器学习和数据压缩之间的漂亮联系，该结果于 1980 年被首次发现。简单来说，如果由来自一个函数族的一个函数所标记的训练样本总是可以被压缩，该函数族必然在某种意义上拥有低的复杂度，并因此是可学习的。作者引入了单调压缩，这是一种压缩变体，并表明其适合特征化 EMX 中特定函数族的可学习性。

Ben-David 和其同事随后证明执行单调压缩的弱形式的能力和某些无穷集合的大小有关。作者最终使用的集合是单位区间，也就是 0 和 1 之间的实数集。他们的结果表明：当且仅当连续统假设为真时，单位区间的有限子集存在单调压缩方案，并因此在 EMX 中可学习。然而，连续统假设已知是不可证明的。

由于 EMX 是机器学习的一种新模型，我们目前仍不知道其对开发现实世界算法的用途。因此这些结果可能并没有实际意义上的重要性。但我们现在知道在引入新的学习模型时应该小心。此外，我们可能需要再次审视过去研究的许多微妙之处，即使在已建立的学习模型中也是如此。

原文链接： https://www.nature.com/articles/d41586-019-00012-4