Exact MAP-Inference by Confining Combinatorial Search with LP Relaxation
This provides an incremental improvement for researchers and practitioners in machine learning and AI by making exact MAP-inference more computationally feasible in specific domains.
The paper tackles the NP-hard MAP-inference problem in graphical models by proposing a family of LP relaxations that decompose it into an easy LP-tight part and a difficult combinatorial part, enabling exact solutions with significantly reduced computational time in applications where the difficult part is small.
We consider the MAP-inference problem for graphical models, which is a valued constraint satisfaction problem defined on real numbers with a natural summation operation. We propose a family of relaxations (different from the famous Sherali-Adams hierarchy), which naturally define lower bounds for its optimum. This family always contains a tight relaxation and we give an algorithm able to find it and therefore, solve the initial non-relaxed NP-hard problem. The relaxations we consider decompose the original problem into two non-overlapping parts: an easy LP-tight part and a difficult one. For the latter part a combinatorial solver must be used. As we show in our experiments, in a number of applications the second, difficult part constitutes only a small fraction of the whole problem. This property allows to significantly reduce the computational time of the combinatorial solver and therefore solve problems which were out of reach before.