Exact Relaxation-Based Inference in Graphical Models (ERBI)

图模型中基于精确松弛的推理 (ERBI)

• 批准号: 323301551
• 负责人: Dr. Bogdan Savchynskyy
• 金额: --
• 依托单位: Interdisziplinäres Zentrum für Wissenschaftliches Rechnen (IWR)
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2016
• 资助国家: 德国
• 起止时间: 2015-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/323301551?language=en
• 关键词: Exact; Relaxation; Based; Inference; Graphical

Graphical models are an important and standard modeling tool in computer vision, bio-informatics, communication theory, statistical physics, signal processing, information retrieval and statisticalmachine learning. This is due to their natural ability to model complex objects consisting of a number of mutually dependent interacting components. We address an important maximum a posteriori inference problem related to graphical models which consists in finding the most probable configuration of the components' states. In general, this problem is NP-hard. However, there are efficient approximate solvers showing great results in a number of applications. At the same time, exact solvers for this problem are typically slow and memory-intensive. This prohibits their use for large problem instances. In spite of that, they are widely used in the areas such as bio-informatics, where accuracy of the obtained solutions plays a crucial role.The goal of this project is an exact, but also scalable and parallelizable method for solving the inference problem in graphical models. We base on our preliminary work which provides a proof of concept for such type of solvers. The method is based on the fact that approximate relaxation-based solvers often deliver solutions where only a small number of variables differ from the exact solution. This is used to efficiently decrease the size of the problem to be solved by standard slow exact solvers. Although our method has shown promising results in a recent benchmark study, its practical application is limited to sparse pairwise models with a small number of variable states. In this project we extent our exact inference method to the graphical models required in practice, which are dense higher order models with large variable state spaces and additional linear constraints.

图形模型是计算机视觉、生物信息学、通信理论、统计物理、信号处理、信息检索和统计机器学习中重要的标准建模工具。这是由于它们对由许多相互依赖的交互组件组成的复杂对象进行建模的天然能力。我们解决了与图形模型相关的一个重要的最大后验推理问题，该问题包括找到组件状态的最可能配置。一般来说，这个问题是np困难的。然而，有一些有效的近似求解器在许多应用中显示出很好的结果。与此同时，这个问题的精确求解器通常很慢且占用大量内存。这就禁止将它们用于大型问题实例。尽管如此，它们被广泛应用于诸如生物信息学等领域，其中获得的解决方案的准确性起着至关重要的作用。这个项目的目标是一个精确的，但也可扩展和并行的方法来解决图形模型中的推理问题。我们以我们的初步工作为基础，为这种类型的求解器提供了概念证明。该方法基于这样一个事实，即基于近似松弛的求解器通常只提供与精确解有少量变量差异的解。这是用来有效地减少问题的大小要解决的标准缓慢的精确求解。虽然我们的方法在最近的基准研究中显示出有希望的结果，但其实际应用仅限于具有少量变量状态的稀疏成对模型。在这个项目中，我们将我们的精确推理方法扩展到实践中所需的图形模型，这些模型是具有大变量状态空间和附加线性约束的密集高阶模型。

项目成果

Discrete Graphical Models - An Optimization Perspective

离散图形模型 - 优化视角

• DOI: 10.1561/0600000084
• 发表时间: 2019
• 期刊: Found. Trends Comput. Graph. Vis.
• 作者: Bogdan Savchynskyy

A Study of Lagrangean Decompositions and Dual Ascent Solvers for Graph Matching

• DOI: 10.1109/cvpr.2017.747
• 发表时间: 2016-12
• 期刊: 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)
• 作者: P. Swoboda;C. Rother;Hassan Abu Alhaija;Dagmar Kainmüller;Bogdan Savchynskyy