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将对开发计算有效算法进行学习和测试各种自然概率分布的理论研究，以在极大的大域上进行。 （测试算法是算法，而不是试图准确建模未知的分布，而是测试分布是否具有感兴趣的特性的更为适中的目标。 初步结果表明，旨在利用这种类型的结构的算法可能会有显着提高效率。 （2）开发用于学习和测试复杂分布的有效算法，这些算法是由许多独立的简单随机性聚集而产生的。PI将使用PI可以开发的算法可以在数据丰富的环境中提供有用的建模工具，并且可以用作“计算基质”的“计算基础”，以在哪些大规模机器学习应用程序上可以为实用领域开发出更广泛的范围跨越范围的范围。 该赠款的其他重要重点是通过研究合作，通过研讨会的演讲，调查文章和其他出版物来培训研究生，并继续进行旨在增加对小学生理论计算机科学主题的兴趣的持续外展活动。