AF: Small: Learning and Testing Classes of Distributions

AF：小：学习和测试分布类

• 批准号: 1319788
• 负责人: Rocco Servedio
• 金额: $ 47.19万
• 依托单位: Columbia University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2013
• 资助国家: 美国
• 起止时间: 2013-06-01 至 2016-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1319788&HistoricalAwards=false
• 关键词: AF; Small; Learning; Testing; Classes

A long and successful line of research in machine learning deals with algorithms that learn from "labeled" data, where a target function is assumed to provide a label for each data point. A major focus of theoretical work has been to develop efficient algorithms for learning different classes of target functions. Recent years have witnessed a data explosion across many domains of science and society, but much of this newly available data consists simply of example points (DNA sequences, sensor readings, smartphone user locations, etc) without any labels. A natural model of such scenarios is that data points are generated according to some unknown probability distribution (typically over an extremely large domain). The goal of the proposed work is to study the learnability of different classes of probability distributions given access to samples drawn from the distributions. This is closely analogous to the framework of learning from labeled data sketched above, but with probability distributions playing the role of functions as the objects to be learned.In this project, the PI will perform theoretical research on developing computationally efficient algorithms for learning and testing various natural types of probability distributions over extremely large domains. (Testing algorithms are algorithms which, instead of trying to accurately model an unknown distribution, have the more modest goal of testing whether or not the distribution has some property of interest.) Specific problems the PI will address include: (1) Developing efficient algorithms to learn and test univariate probability distributions that satisfy various natural kinds of "shape constraints" on the underlying probability density function. Preliminary results suggest that dramatic improvements in efficiency may be possible for algorithms that are designed to exploit this type of structure. (2) Developing efficient algorithms for learning and testing complex distributions that result from the aggregation of many independent simple sources of randomness.The algorithms that the PI will work to develop can provide useful modelling tools in data-rich environments and may serve as a "computational substrate" on which large-scale machine learning applications can be developed for real-world problems spanning a broad range of application areas. Other important focuses of the grant are to train graduate students through research collaboration, disseminate research results through seminar talks, survey articles and other publications, and to continue ongoing outreach activities aimed at increasing interest in theoretical computer science topics in elementary school students.

在机器学习领域，有一个漫长而成功的研究路线涉及从“标记”数据中学习的算法，其中假设目标函数为每个数据点提供标签。 理论工作的一个主要焦点是开发有效的算法来学习不同类别的目标函数。 近年来，科学和社会的许多领域都出现了数据爆炸式增长，但这些新获得的数据中，大部分都是简单的示例点（DNA序列、传感器读数、智能手机用户位置等），没有任何标签。 这种场景的一个自然模型是，数据点是根据某种未知的概率分布（通常在一个非常大的域上）生成的。 所提出的工作的目标是研究的可学习性的不同类别的概率分布给定的访问从分布中提取的样本。 这与上述基于标记数据的学习框架非常相似，但学习对象是函数的概率分布。在本项目中，PI将对开发计算效率高的算法进行理论研究，以学习和测试超大范围内的各种自然类型的概率分布。（测试算法是这样的算法，它不是试图精确地建模一个未知的分布，而是有一个更温和的目标，即测试该分布是否具有某些感兴趣的属性。PI将解决的具体问题包括：（1）开发有效的算法来学习和测试单变量概率分布，这些概率分布满足底层概率密度函数的各种自然类型的“形状约束”。 初步结果表明，效率的显着提高可能是设计用于利用这种类型的结构的算法。 (2)开发有效的算法，用于学习和测试由许多独立的简单随机性来源聚合而成的复杂分布。PI将致力于开发的算法可以在数据丰富的环境中提供有用的建模工具，并可以作为“计算基底”，在此基础上可以开发大规模机器学习应用程序，以解决跨越广泛应用领域的现实问题。 赠款的其他重点是通过研究合作培训研究生，通过研讨会演讲，调查文章和其他出版物传播研究成果，并继续开展旨在提高小学生对理论计算机科学主题兴趣的外联活动。