科学研究 / 科研进展

学习数据和概率分布的等价性及其应用

George Barmpalias, Nan Fang and Frank Stephan (2018): Equivalences between learning of data and probability distributions, and their applications. Information and Computation 262: 123-140

背景:在很多领域,学习理论都十分重要,比如人工智能(如机器学习)、心理学和认知科学(如语言学习)等。形式学习理论的两个主要体系包括算法学习(Gold创建于1960年)和计算学习(以20世纪70年代 Vapnik创建的统计学习理论为基础,后以20世纪80年代 Valiant创建的PAC学习理论重新呈现)。传统意义上,方法算法学习更靠近归纳推理领域,并且主要研究针对有老师(监督学习时)帮助回答假设和猜想情况下的“有限学习”。此外,通常方法算法是从样例中学习,不涉及概率情况(特殊情况除外);计算学习本质上是和统计学相关的,研究随机抽取拟学习概念样本的学习情况。近来,P. Vitanyi和N. Chater建议结合算法学习和算法信息两方面的理论来研究数据分布学习(而非研究数据本身)。在《概率识别算法有难点》一文中 [L. Bienvenu,S. Figueira,B. Monin和A. Shen, 概率识别算法有难点. 计算机与系统科学杂志,95:98-108,2018] ,作者对此进行了进一步研究,研究结果显示,在该框架内,概率分布学习呈可判定性和不可判定性的结果,这与经典算法学习理论中的结构化数据(或语言)学习有相似之处。

重要突破:我们的研究表明,从某种意义上来说,这两种方法基本上是等效的。换言之,从一类语言的学习者可以有效地构建一个相关概率分布类语言学习者;反之亦然,从一个概率分布指标集学习者,可以复原学习者指标集分布情况对应的语言类别。这两种不同学习任务之间的深层联系,提供了许多应用可能,并进一步拓展了与经典算法学习理论中数据有限学习类似的分布学习理论。此外它还提供了一种统一的方法,能将结果从一个设置下转化到另一种设置中,避免了Vitanyi和Chater以及Bienvenu等人方法需要特定论据。