AF: Small: Learning and Testing Classes of Distributions

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

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.