一个无解的数学难题是如何触及机器学习的极限的? 数学统治一切

机器能学习什么？这可能是机器学习理论中最令人兴奋的问题之一。它涉及学科的极限——可学习性。另一方面，连续统假设触及了我们数学知识的极限——不可证明性。

可学习性问题

让我们从机器学习开始。为了研究可学习性问题，我们需要一个精确的数学框架来分析机器学习。为了这个目的，莱斯利·瓦利安特（Leslie Valiant）在1984年引入了可能近似正确学习模型（probably approximately correct learning ，PAC-learning）。

可能近似正确学习的想法很简单：学习者接收关于某个问题的少量信息，然后根据这些数据输出一个一般性的假设。例如，学习者可以接收照片和关于这些照片中是否有猫的信息。然后，学习者必须选择一个函数来决定给定的照片中是否包含一只猫。

可能近似正确学习模型的名字来自于这样一个事实，即我们要求学习者选择一个具有高概率的近似正确的函数。总之，如果学习者可能选择一个近似正确的函数，那么这个问题就是可能近似正确学习的。

连续统假设

康托尔的连续统问题是什么1878年，数学家康托尔（Georg Cantor）)提出一个问题：实数的所有子集是与自然数一一对应，还是与实数一一对应。这就是所谓的连续统假设。

哥德尔和科恩证明了这个问题是可从ZFC公理体系（the Zermelo-Fraenkel axioms of set theory）中判定。他们指出，既没有证据证明连续统假设，也没有证据反驳它。连续统假说是不可证明的，它的否定也是不可证明的。

可学习性与连续统假设的关系

这里似乎有两个非常不同的问题：一个是可能近似正确学习模型问题，来自于理论计算机科学，讨论机器是否可以学习某些功能。还有一个连续统问题问的是是否存在一定规模的无穷集合。这两件事有什么关系？

2019年，一组研究人员在《自然-机器智能》上发表了一篇题为《学习性可以是不可判定的》的文章：

我们描述了不能用数学标准公理证明或反驳可学习性的简单场景。我们的证明是基于一个事实，即连续统假说既不能被证明，也不能被反驳。

他们是怎么表现出来的？研究人员本·大卫对学习问题进行了极大的简化。他们称之为估计最大值问题（EMX），并给出了一个例子：

想象一个被各种各样的用户访问的网站。用X表示该网站所有潜在访问者的集合。该网站的所有者希望在上面发布广告。发布的广告将从给定的广告池中选择。广告池中的每个广告A针对特定的用户群体F(A) ⊆ X。例如，如果A是一个体育广告，则F(A)是体育爱好者的集合。目标是放置一个目标人群访问网站最频繁的广告。挑战在于事先不知道哪些访客会来访问这个网站。

这个为你的网站找到最佳广告的简单问题可以被概括为一个涉及集合族和概率分布的数学问题。给定定义域D上的子集集合F，以及在D上的一个概率分布，在F中找到具有最高概率的集合。真正困难的是我们事先不知道概率分布。

本·大卫和他的同事如何证明特定问题的“估计最大值（EMX）”可学习性独立于ZFC数学公理？

一种方法是构建集合理论的模型，即可能的数学世界，其中一个问题是估计最大值可学习的，另一个则不是。然而，这将是非常复杂的。

相反，本·大卫和他的合著者做了许多聪明的数学家以前做过的事，并使用已经确定的结果。他们利用学习和压缩之间的联系证明了估计最大值学习问题的一个非常复杂的实例等同于康托的连续体假设。

如果你能证明一个命题等同于连续统假设，那么事实上，你就证明了你的命题独立于ZFC。很容易看到，如果你的表述是正确的，那么根据等价性，连续统假设一定是正确的。如果你的表述是错误的，那么根据等价性，连续统假设一定是错误的。但是连续体假说在ZFC中既不正确也不错误，所以你的表述也必须是一样的。

数学家可计算机科学家们发现了一种巧妙的方法，将数学的基础与机器学习的基础联系起来。所有的东西都是相互联系的——可学习性的极限可能取决于我们的数学集论基础。

一个关键的声音

我们应该如何严肃对待这些结果？荷兰数学家和集合理论家K.P.哈特批判性地分析了本·大卫等人的论文。简单地说，哈特的观点是：

学习问题本质上要求学习者想出一个广义函数。如果这个广义函数足够好，那么我们就说学习者已经学会了这个问题。换句话说，这个问题是可以学习的。

然而，要求一个问题可以被机器学习是一个进一步的限制。艾伦·图灵用他著名的停机问题证明了并不是所有的函数都是可计算的。所以，要说机器可以学习问题，我们必须确保我们正在讨论的函数实际上可以由机器来处理：

所使用的函数是任意的，与任何可识别的算法无关。（K.P.哈特，《机器学习与连续体假说》）。

哈特指出，本·大卫和他的合著者已经认识到了这一点。然后他建议让问题更加精确：