An important algorithmic challenge in Markov random fields
(MRF) is efficient computation of the most likely configuration or mode. Although easily solvable for tree-structured graphs, the mode-finding problem for general MRFs is intractable. However, message-passing algorithms, such as the max-product and sum-product algorithm, are widely used to compute approximate solutions. In this talk, we begin by showing how the ordinary max-product algorithm can be very misleading, by converging rapidly to sub-optimal solutions.
We then discuss the class of tree-reweighted max-product algorithms, their associated correctness guarantees, and links to linear programming (LP) relaxation, as well as connections to other distributed algorithms. Finally, we describe dual-certificate methods for establishing optimality of message-passing and/or LP relaxation, and use it to establish high-probability performance guarantees for error-correction based on sparse random graphs.
Based on joint works with Costis Daskalakis, Alex Dimakis, Richard Karp, Vladimir Kolmogorov, Tommi Jaakkola, Alan Willsky.
Copyright. All Rights Reserved.