Exact Relaxation-Based Inference in Graphical Models (ERBI)

• Applicant: Dr. Bogdan Savchynskyy
• Subject Area: Image and Language Processing, Computer Graphics and Visualisation, Human Computer Interaction, Ubiquitous and Wearable Computing
• Term: from 2016 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 323301551

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.

• DFG Programme: Research Grants