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

科学家开发了解释他们观察到的模型的描述。但是，需要多少观测才能验证模型的有效性呢？当模型是概率模型时，由此产生的问题是：需要来自分布的多少样本来测试它是否具有某种性质？可以说，这个问题存在于科学思想的基础上，近年来，计算机科学文献中有大量工作试图接近测试分布特性所需的精确样本和时间复杂性。数据通常是高维的--例如，患者的医疗记录有许多条目。然而，众所周知，高维分布数据很难处理。这个项目将找到新的方法来克服处理高维数据的困难，通过隔离在实践中出现的有助于简化分布测试问题的数据的属性。该项目的更广泛影响包括推进计算机科学、统计和学习的接口。我们的方法将在包括370多万患者的医疗数据集上进行测试，并将测试用于改善医疗结果的常见模型的准确性。该项目的更广泛影响还包括参与小学生的计算机科学活动，麻省理工学院向高中生推广数学研究，以及参与促进妇女参与研究的活动。目前对分布性质的检验主要集中在一维分布的一致性、单调性、对数凹性等性质上，对高维分布性质的检验结果很少。不幸的是，测试高维分布的性质很快就会遇到指数样本复杂性下限。该项目的目标是开发新的分析框架，以克服这些下限。通常，下界构造了高度复杂的分布，这些分布没有性质，但实际上很难与具有性质的分布区分开来。我们的论点是，如此丰富的结构可能并不存在于许多感兴趣的实际环境中。那么，我们研究的首要问题是：人们是否可以对未知分布做出合理的假设，在这种分布下，高维测试问题更容易处理？这项研究将(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.