Auto Byte

专注未来出行及智能汽车科技

微信扫一扫获取更多资讯

Science AI

关注人工智能与其他前沿技术、基础学科的交叉研究与融合发展

微信扫一扫获取更多资讯

籍缓、胡笳、钱天培编译

非真,亦非假—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

大数据文摘
大数据文摘

秉承“普及数据思维,传播数据文化,助⼒产业发展”的企业⽂化,我们专注于数据领域的资讯、案例、技术,形成了“媒体+教育+⼈才服务”的良性⽣态,致⼒于打造精准数据科学社区。

理论机器学习数据
相关数据
机器学习技术

机器学习是人工智能的一个分支,是一门多领域交叉学科,涉及概率论、统计学、逼近论、凸分析、计算复杂性理论等多门学科。机器学习理论主要是设计和分析一些让计算机可以自动“学习”的算法。因为学习算法中涉及了大量的统计学理论,机器学习与推断统计学联系尤为密切,也被称为统计学习理论。算法设计方面,机器学习理论关注可以实现的,行之有效的学习算法。

逻辑技术

人工智能领域用逻辑来理解智能推理问题;它可以提供用于分析编程语言的技术,也可用作分析、表征知识或编程的工具。目前人们常用的逻辑分支有命题逻辑(Propositional Logic )以及一阶逻辑(FOL)等谓词逻辑。

大数据技术技术

大数据,又称为巨量资料,指的是传统数据处理应用软件不足以处理它们的大或复杂的数据集的术语。

推荐文章
暂无评论
暂无评论~