Lev Reyzin作者刘晓坤编译nature选自

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

在二十世纪,来自数理逻辑领域的发现革新了我们对数学基础的理解。1931 年,哥德尔证明,在任何足够建模算术运算的公理系统中,都存在不可证明的数学声明。在之后的几十年,人们发现,使用标准的数学公理也无法证明或证否连续统假设。近期,Ben-David 等人证明机器学习领域也存在这样的限制。他们发现存在这样的机器学习问题,其可解性取决于连续统假设。

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

从随机示例数据库中学习预测器(可用于进行预测的数学函数)的目标被形式化为可能近似正确(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 

理论理论基础论文Nature机器学习
相关数据
机器学习技术

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

数据压缩技术

数据压缩是指在不丢失有用信息的前提下,缩减数据量以减少存储空间,提高其传输、存储和处理效率,或按照一定的算法对数据进行重新组织,减少数据的冗余和存储的空间的一种技术方法。数据压缩包括有损压缩和无损压缩。在计算机科学和信息论中,数据压缩或者源编码是按照特定的编码机制用比未经编码少的数据位元(或者其它信息相关的单位)表示信息的过程。

数据库技术

数据库,简而言之可视为电子化的文件柜——存储电子文件的处所,用户可以对文件中的数据运行新增、截取、更新、删除等操作。 所谓“数据库”系以一定方式储存在一起、能予多个用户共享、具有尽可能小的冗余度、与应用程序彼此独立的数据集合。

神经网络技术

(人工)神经网络是一种起源于 20 世纪 50 年代的监督式机器学习模型,那时候研究者构想了「感知器(perceptron)」的想法。这一领域的研究者通常被称为「联结主义者(Connectionist)」,因为这种模型模拟了人脑的功能。神经网络模型通常是通过反向传播算法应用梯度下降训练的。目前神经网络有两大主要类型,它们都是前馈神经网络:卷积神经网络(CNN)和循环神经网络(RNN),其中 RNN 又包含长短期记忆(LSTM)、门控循环单元(GRU)等等。深度学习是一种主要应用于神经网络帮助其取得更好结果的技术。尽管神经网络主要用于监督学习,但也有一些为无监督学习设计的变体,比如自动编码器和生成对抗网络(GAN)。

在线学习技术

在计算机科学中,在线学习是一种机器学习方法。和立即对整个训练数据集进行学习的批处理学习技术相反,在线学习的数据按顺序可用,并在每个步骤使用未来数据更新最佳预测器。

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