Exact Relaxation-Based Inference in Graphical Models (ERBI)

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

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.