Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
An Efficient Message-Passing Algorithm for the M-Best MAP Problem
Dhruv Batra
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.
Pages: 121-130
PS Link:
PDF Link: /papers/12/p121-batra.pdf
AUTHOR = "Dhruv Batra ",
TITLE = "An Efficient Message-Passing Algorithm for the M-Best MAP Problem",
BOOKTITLE = "Proceedings of the Twenty-Eighth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-12)",
ADDRESS = "Corvallis, Oregon",
YEAR = "2012",
PAGES = "121--130"

hosted by DSL   •   site info   •   help