RI: Medium: Approximation Algorithms for Probabilistic Graphical Models with Constraints

该项目的目标是为概率图模型创建下一代近似推理技术和算法。概率图模型在整个科学和工程中用于解决困难的问题，包括自动推理和决策，计算生物学和遗传学，计算机视觉，数据挖掘和社交网络分析。然而，这些现实世界的问题现在是如此的大，以至于大多数现有的技术在它们的性能上是不均匀的，因为它们通常在一些问题上工作得很好，而在另一些问题上工作得不好，并且通常需要一系列的选择和定制，这些选择和定制必须在很少的指导或自动化的情况下进行。该项目汇集了独立但互补的研究流，以开发新的算法来管理包含概率和确定性关系以及基于图和上下文敏感关系的混合。该项目旨在通过开发图形模型的新近似推理技术（例如，通过利用大多数采样技术在很大程度上忽视的图形模型的丰富结构），在存在确定性约束的情况下推进概率推理的最新技术。该项目旨在通过改进用于近似推理的采样和消息传递算法，并开发利用各自优势的混合方法，为概率图形模型创建改进的框架。这些框架将用于为选择参数提供自动化指导，以优化复杂性和准确性之间的固有权衡，并为结果和准确性提供有意义的界限。该项目将利用其研究成果来改善本科和研究生教育，例如通过开发一门新的图形模型本科课程，并通过在线发布课程材料。此外，该项目将在网上发布开源代码。

The goal of this project is to create the next generation of approximate inference techniques and algorithms for probabilistic graphical models. Probabilistic graphical models are employed throughout science and engineering to solve difficult problems, including automated reasoning and decision making, computational biology and genetics, computer vision, data mining, and social network analysis. However, these real-world problems are now of such considerable size that most existing techniques are uneven in their performance in that they typically work well on some problems and not others, and often require sets of choices and customizations that must be made with little guidance or automation.This project brings together separate but complementary streams of research to develop new algorithms to manage models containing mixtures of probabilistic and deterministic relations and mixtures of graph-based and context-sensitive relationships. This project aims to advance the state of the art of probabilistic reasoning in the presence of deterministic constraints by developing new approximate inference techniques for graphical models, for instance, by exploiting the rich structure of graphical models that is largely neglected by most sampling techniques. This project aims to create improved frameworks for probabilistic graphical models by improving both sampling and message-passing algorithms for approximate inference and developing hybrid approaches that exploit the advantages of each. The frameworks will be used to provide automated guidance for selecting parameters to optimize the inherent tradeoffs between complexity and accuracy as well as provide meaningful bounds on results and accuracy. This project will use the fruits of its research to improve education, both at the undergraduate and graduate level, for instance by developing a new undergraduate course in graphical models, and by posting course materials online. In addition, the project will post open source code on the web.