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

AitF：协作研究：现实世界中的概率推理算法

• 批准号: 1637585
• 负责人: Aravindan Vijayaraghavan
• 金额: $ 39.99万
• 依托单位: Northwestern University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2016
• 资助国家: 美国
• 起止时间: 2016-09-01 至 2022-08-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1637585&HistoricalAwards=false
• 关键词: AitF; Collaborative; Research; Algorithms; Probabilistic

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.

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

项目成果

Beyond Perturbation Stability: LP Recovery Guarantees for MAP Inference on Noisy Stable Instances

超越扰动稳定性：噪声稳定实例上 MAP 推理的 LP 恢复保证

• 发表时间: 2021
• 期刊: PMLR
• 作者: Lang, Hunter;Reddy, Aravind;Sontag, David;Vijayaraghavan, Aravindan
• 通讯作者: Vijayaraghavan, Aravindan

Graph cuts always find a global optimum for Potts models (with a catch)

图割总是能找到 Potts 模型的全局最优值（有一个问题）

• 发表时间: 2021
• 期刊: Proceedings of the Thirty-eighth International Conference on Machine Learning (ICML
• 作者: Lang, Hunter;Sontag, David;Vijayaraghavan, Aravindan
• 通讯作者: Vijayaraghavan, Aravindan

On Robustness to Adversarial Examples and Polynomial Optimization

• 发表时间: 2019-11
• 期刊: ArXiv
• 作者: Pranjal Awasthi;Abhratanu Dutta;Aravindan Vijayaraghavan

Clustering Semi-Random Mixtures of Gaussians

• 发表时间: 2017-11
• 作者: Pranjal Awasthi;Aravindan Vijayaraghavan

Optimality of Approximate Inference Algorithms on Stable Instances

稳定实例上近似推理算法的最优性

• 发表时间: 2018
• 期刊: Proceedings of Machine Learning Research
• 作者: Lang, Hunter;Sontag, David;Vijayaraghavan, Aravindan
• 通讯作者: Vijayaraghavan, Aravindan