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.