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.