非真，亦非假—20世纪数学悖论入侵机器学习

20世纪30年代，奥地利数学家Kurt Gödel向世人证明， 集合论中的“连续统假设(continuum hypothesis)”既无法被证明，也无法被证伪。

一个彻头彻尾的悖论。

自此，这一悖论如乌云般笼罩于数学界，并给数学的根基带了革命性的改变。

而今，这一朵乌云出人意料地降临到了机器学习界，或将“颠覆”机器学习理论。

这一研究的最新结果已被发表于1月7日的Nature Machine Intelligence。

那么，什么是“连续统假设(continuum hypothesis)”？这一假设对机器学习而言又意味着什么呢?

近日，几位研究机器学习问题的数学家表示， “可学习性”问题——即算法能否从有限的数据中提取模式——与被称为连续统假设(continuum hypothesis)的悖论有关。 数学家Gödel曾表示，使用标准数学语言不能证明该假设是真是假。

“对我们来说，这是一个惊喜，”该论文的作者之一、以色列理工学院(Technio)的Amir Yehudayoff说，虽然有许多技术数学问题被同样认为“不可判定”，但他之前并没有想到这种现象会出现在机器学习中一个相对简单的问题上。

英国斯旺西大学( Swansea University, UK)的计算机科学家John Tucker说，这篇论文是“ 关于我们知识局限性的重量级结果 ”， 对数学和机器学习都具有基础性意义。

并非所有无限集合都是大小相等的

研究人员通常根据算法是否可以被推广应用来定义可学习性。比如，算法会回答“是或否”类型的问题，例如“这张图是否是只猫？”。通过有限数量的数据进行训练，然后应用于猜测新数据的答案。

Yehudayoff和他的合作者在研究可学习性和“压缩”之间的联系时得出了结论，这意味着找到一种方法，来总结较小数据集中大量数据的显着特征。 作者发现，信息被有效压缩的能力可以被归结为集合理论中的一个问题——对象的数学集合，例如温氏图中的集合。特别是对于涉及包含无限多个对象的不同大小的集合。

集合论的创始人Georg Cantor在19世纪70年代证明，并非所有的无限集都是大小相等的：特别值得一提是，整数的集合比所有实数的集合“小”，也称为连续统(continuum)。（实数包括无理数，有理数和整数。）Cantor还推测不可能存在“中间”大小的集合，即大于整数但小于连续统的集合。但他无法证明这种连续统假设，许多追随他的数学家和逻辑学家也未能证明。

他们的努力是徒劳的。

Gödel 1940年的成果（最终由美国数学家 Paul Cohen于20世纪60年代完成）表明，连续统假设不能从标准公理被证明为真或假——这一结论在集合理论上被认为是真的，并通常被认为是所有数学的基础。

Gödel 和Cohen关于连续统假设的研究表明，可以存在兼容标准数学的并行数学宇宙，其中一个连续统假设被添加到标准公理并因此被宣布为真，而另一个则被宣布为假。

可学习性的不稳定性

在最新的论文中，Yehudayoff和他的合作者将可学习性定义为通过采样少量数据点来预测较大数据集的能力。与Cantor问题的联系是，选择较小的采样集合的方式有无限种，但这个无限集合有多大却是未知的。

论文作者继续表明，如果连续统假设为真，那么一个小样本就足以进行外推。但如果它为假，那么将需要无限的样本。通过这种方式，他们表明可学习性问题等同于连续统假设。因此，可学习性问题也处于不稳定状态，只有通过选择公理宇宙才能解决。

Yehudayoff说，这一结果也有助于更好地理解可学习性。“如果你想了解‘学习’，压缩和泛化之间的联系非常重要。”

伦敦大学学院的计算机科学家Peter O’Hearn说，研究人员发现了许多类似的“不可判定”问题。特别是，继Gödel的工作之后，共同创立算法理论的Alan Turing发现了一类任何计算机程序都无法保证能在任何有限的步骤中解答的问题。

但这种不可判定性是“罕见的”，而且更令人惊讶的是，O'Hearn补充说：它指出了 Gödel 的发现对任何数学语言都存在内在不完整性。这些发现可能对机器学习理论很重要，尽管“不确定它会在实际应用中产生多大影响”。

相关报道： https://www.nature.com/articles/d41586-019-00083-3