An Efficient Message-Passing Algorithm for the M-Best MAP Problem
This addresses the need for multiple high-probability solutions in probabilistic models, offering a faster method for applications like computer vision or natural language processing, though it is incremental as it builds on existing LP formulations.
The paper tackles the M-Best MAP problem by proposing an efficient message-passing algorithm that solves a Linear Programming formulation, achieving orders of magnitude faster performance than generic LP-solvers.
Much effort has been directed at algorithms for obtaining the highest probability configuration in a probabilistic random field model known as the maximum a posteriori (MAP) inference problem. In many situations, one could benefit from having not just a single solution, but the top M most probable solutions known as the M-Best MAP problem. In this paper, we propose an efficient message-passing based algorithm for solving the M-Best MAP problem. Specifically, our algorithm solves the recently proposed Linear Programming (LP) formulation of M-Best MAP [7], while being orders of magnitude faster than a generic LP-solver. Our approach relies on studying a particular partial Lagrangian relaxation of the M-Best MAP LP which exposes a natural combinatorial structure of the problem that we exploit.