NSF-BSF: AF: Small: Identifying Functional Structure in Data

用于无监督学习任务的算法在科学、工程、医学研究等领域不断使用。因此，这些问题的优化过程中的进展具有非常广泛的采用潜力。该奖项的主要研究主题之一是无监督学习方法，用于在由于实际或伦理原因而无法进行受控实验的情况下确定因果关系。目前，推断因果关系的理论有些脆弱，因为它依赖于数学建模中不切实际的准确性，对于大系统来说，依赖于不切实际的样本量。因此，科学家没有非常可靠的方法来向公众提供关于“假设”情景的建议。这项研究旨在提供并表征具有以下目标的因果识别算法的性能：(A)在比当前理论所做的假设更弱的假设下工作的算法(特别是在模型与现实的保真度方面)，但仍提供有用的保证；(B)在比当前理论所做的更强的结构性假设下工作的算法，因此可以使用更小的样本大小。一个相关的研究主题涉及优化问题的逼近算法和不可逼近界，例如数据聚类和混合模型的学习。研究人员将在计算理论的这些和相关领域培训学生和博士后。因果推理问题将通过有向概率图形模型的框架来解决。现有的因果识别算法使用简单的参数大小来操作，因为对于N元图形模型，复杂性参数(和样本复杂性)在N中是指数的。相比之下，用于聚类、用于学习产品分布的混合或用于主题模型的所有算法方法都将维度(即，变量的数目N)视为不应该出现在指数中的参数，或者在最坏的情况下以多对数的形式出现。这个项目的目标是提供具有这种复杂性的算法；然而，这不仅仅是一个算法问题。现有的关于因果关系识别何时可能的描述是在假设一个人能够获得关于N个变量的联合分布的全部知识的前提下提出的。因此，一个相关的统计但不是算法的目标是获得图形模型的特征，其中因果推理只能从相对于N小的变量集的联合分布来实现。这类模型的候选类别来自混合模型，从乘积的混合开始，扩展到马尔可夫模型的混合。另一个问题涉及图形模型，在这些模型中，因果关系识别是不可能的，但与数据一致的因果关系范围很小。在这种情况下，限制因果关系的算法是完全识别的适当替代；提供这样的保证是这项工作的另一个目标。最后，研究将集中于欧几里德成本平方的聚类：在不可逼近阈值上，以及通过线性规划放松或其他方法改善近似系数。这一奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Algorithms for unsupervised learning tasks are in constant use in science, engineering, medical research, etc. Progress in optimization procedures for these problems has therefore the potential for very wide adoption. One of the primary research topics of this award is unsupervised learning methods for determining causal effect in scenarios where one cannot, for practical or ethical reasons, perform controlled experiments. At present, the theory for deducing causal effects is somewhat brittle, since it relies upon unrealistic accuracy in the mathematical modeling, and, for large systems, upon unrealistic sample sizes. Scientists therefore do not have very reliable ways of advising the public about "what-if" scenarios. This research aims to provide, and characterize the performance of, causal-identification algorithms with the following goals: (a) Algorithms that work under weaker assumptions than current theory makes (in particular regarding the fidelity of the model to reality), yet deliver still-useful guarantees; (b) Algorithms that work under stronger structural assumptions than current theory makes and can use smaller sample sizes as a result. A related research topic concerns approximation algorithms, and inapproximability bounds, for optimization problems such as data clustering and learning of mixture models. The investigator will train students and postdocs in these and related areas of the theory of computation.Causal-inference problems will be addressed through the framework of directed probabilistic graphical models. Existing causal-identification algorithms operate with a naive parameter size because, for N-variate graphical models, the complexity parameter (and sample complexity) is exponential in N. By contrast all algorithmic methods for clustering, for learning mixtures of product distributions, or for topic models regard the dimension (i.e., the number of variables N) as a parameter that should not appear, or at worst appear poly-logarithmically, in the exponent. This project aims to provide algorithms with such complexity; however, this is not only an algorithmic question. The existing characterization of when causal identification is even possible is stated under the assumption that one has access to full knowledge of the joint distribution on the N variables. Therefore a related, statistical but not algorithmic goal is to obtain a characterization of graphical models in which causal inference is possible only from the joint distributions of sets of variables of size small relative to N. A candidate class of such models comes from mixture models, beginning with mixtures of products and extending to mixtures of Markov models. Another question concerns graphical models in which causal identification is not possible, yet the range of causal effects consistent with the data is small. In such cases, an algorithm which bounds the causal effect is an adequate replacement for full identification; providing such guarantees is another goal of this work. Finally, research will focus on clustering with squared Euclidean costs: both on the inapproximability threshold and in improving approximation factors through linear programming relaxations or other methods.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.