BIGDATA: F: Testing High Dimensional Distributions without the Curse of Dimensionality

科学家们开发了解释他们观察结果的模型描述。但是，需要多少观察来验证模型的有效性？当模型是概率性的时，由此产生的问题是：需要从一个分布中抽取多少样本来检验它是否具有某种属性？可以说，这个问题是科学思想的基础，近年来，计算机科学文献中有大量的工作试图接近测试分布特性所需的精确样本和时间复杂性。数据通常是高维的--例如，患者的医疗记录有许多条目。然而，高维分布数据是出了名的难以处理。 这个项目将找到新的方法来克服处理高维数据的困难，通过隔离在实践中发生的数据的属性，帮助简化分布测试问题。这个项目的更广泛的影响包括推进计算机科学，统计学和学习的接口。我们的方法将在包括370多万患者的医疗数据集上进行测试，并将测试用于改善医疗结果的常见模型的准确性。该项目的更广泛影响还包括参与小学生的计算机科学活动，麻省理工学院PRIMES与高中生的数学研究，以及参与促进妇女参与研究的活动。目前分布性质测试的工作主要集中在一维分布的性质，如均匀性，单调性，对数分布，和其他人，只有少数结果测试高维分布的性质。不幸的是，测试高维分布的性质很快就会遇到指数样本复杂度的下限。该项目的目标是开发新的分析框架，以克服这些下限。通常情况下，下界构造了高度复杂的分布，这些分布不具有属性，但很难与具有属性的分布区分开来。我们的论点是，这种丰富的结构可能不存在于许多实际的利益设置。我们研究的首要问题是：是否有合理的假设，人们可以对未知的分布下，高维测试问题更容易处理？本研究将（1）探索如何使用图形模型的表达语言来限制高维分布的相关结构，以便更快地进行测试;（2）开发分析框架，允许从单个或恒定数量的样本中测试组合结构（如社交网络）的生成模型;这听起来像是一种矛盾修饰法，但只要对生成组合结构的模型做适当的假设，就有可能实现。(1)将揭示贝叶斯网络及其在医疗决策中的应用，以及计算生物学和遗传学的重要联系，而（2）将与社交网络建模有关。

Scientists develop descriptions of models that explain their observations. But how many observations are needed to verify the validity of a model? When the model is probabilistic, the resulting question is this: How many samples from a distribution are needed to test whether it has a certain property? Arguably this problem lies at the foundations of scientific thought, and recent years have seen a tremendous body of work in the Computer Science literature trying to close in on the precise sample and time complexity needed to test distribution properties. Often data is high dimensional -- for example, medical records for patients have many entries. However, high dimensional distribution data is notoriously hard to deal with. This project will find new ways of overcoming the difficulties of dealing with high dimensional data, by isolating properties of data occurring in practice that aid in simplifying the distribution testing problems.The broader impact of this project includes advancing the interface of Computer Science, Statistics and Learning. Our methods will be tested on a healthcare dataset, including over 3.7 million patients, and will test the accuracy of common models used to improve healthcare outcomes. Broader impact of this project also includes engagement in Computer Science activities for elementary school children, MIT PRIMES mathematical research with high school students, and participation in activities for promoting women in research. Current work on distribution property testing has focused on properties of single-dimensional distributions such as uniformity, monotonicity, log-concavity, and others, with only a few results on testing properties of high-dimensional distributions. Unfortunately, testing properties of high-dimensional distributions quickly runs into exponential sample complexity lower bounds. The goal of the project is to develop new analysis frameworks for overcoming these lower bounds. Typically the lower bounds construct highly-complex distributions that do not possess a property but are really hard to distinguish from those that do. Our thesis is that such rich structure may not be present in many practical settings of interest. The overarching question of our research then is this: are there reasonable assumptions that one could make about the unknown distribution under which high-dimensional testing problems are more tractable? This research will (1) explore how the expressive language of graphical models can be used to restrict the correlation structure of high-dimensional distributions in ways that can be leveraged for faster testing; and (2) develop analysis frameworks that allow testing generating models of combinatorial structures, such as social networks, from a single or a constant number of samples; this sounds like an oxymoron but it will be made possible with adequate assumptions about the model generating the combinatorial structure. (1) will reveal important connections to Bayesian networks and their use in healthcare decision making, as well as to computational biology and phylogenetics, while (2) will have connections to social network modeling.