AitF: Collaborative Research: Algorithms for Probabilistic Inference in the Real World

统计模型提供了一种强大的方法来量化不确定性，建模先验信念，以及描述数据中的复杂依赖关系。使用模型来回答特定问题的过程，例如根据观察到的其他随机变量的证据来推断几个随机变量的状态，称为概率推理。概率图形模型是统计模型的一种，通常用于医学诊断、理解蛋白质和基因调控网络、计算机视觉和语言理解等各种应用中。由于概率图模型在广泛的自动推理应用中发挥着核心作用，因此设计有效的概率推理算法是人工智能和机器学习中的一个基本问题。在许多这些应用中，概率推理对应于一个复杂的组合优化问题，乍一看似乎极难解决。然而，从业者在设计启发式算法以准确有效地执行现实世界推理方面取得了重大进展。该项目致力于弥合大规模机器学习系统中概率推理问题的理论与实践之间的差距。pi将识别结构属性和分析方法，以区分用于显示np硬度的现实世界实例和最坏情况的实例，并将设计具有可证明保证的高效算法，适用于大多数现实世界实例。该项目还将研究为什么像线性规划和其他凸松弛这样的启发式算法在现实世界中如此成功。作为该项目一部分开发的高效概率推理算法有可能在机器学习、统计学以及计算机视觉、社交网络和计算生物学等更多应用领域产生变革。为了帮助传播研究并促进新的合作，将组织一系列研讨会，将理论计算机科学和机器学习社区聚集在一起。此外，将开发利用机器学习向学生介绍理论计算机科学概念的本科课程。

Statistical models provide a powerful means of quantifying uncertainty, modeling prior beliefs, and describing complex dependencies in data. The process of using a model to answer specific questions, such as inferring the state of several random variables given evidence observed about others, is called probabilistic inference. Probabilistic graphical models, a type of statistical model, are often used in diverse applications such as medical diagnosis, understanding protein and gene regulatory networks, computer vision, and language understanding. On account of the central role played by probabilistic graphical models in a wide range of automated reasoning applications, designing efficient algorithms for probabilistic inference is a fundamental problem in artificial intelligence and machine learning. Probabilistic inference in many of these applications corresponds to a complex combinatorial optimization problem that at first glance appears to be extremely difficult to solve. However, practitioners have made significant strides in designing heuristic algorithms to perform real-world inference accurately and efficiently. This project focuses on bridging the gap between theory and practice for probabilistic inference problems in large-scale machine learning systems. The PIs will identify structural properties and methods of analysis that differentiate real-world instances from worst-case instances used to show NP-hardness, and will design efficient algorithms with provable guarantees that would apply to most real-world instances. The project will also study why heuristics like linear programming and other convex relaxations are so successful on real-world instances. The efficient algorithms for probabilistic inference developed as part of this project have the potential to be transformative in machine learning, statistics, and more applied areas like computer vision, social networks and computational biology. To help disseminate the research and foster new collaborations, a series of workshops will be organized bringing together the theoretical computer science and machine learning communities. Additionally, undergraduate curricula will be developed that use machine learning to introduce students to concepts in theoretical computer science.