Skip to main content

A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles

Publication ,  Conference
Shin, J; Gelfand, AE; Chertkov, M
Published in: Advances in Neural Information Processing Systems
January 1, 2013

Max-product 'belief propagation' (BP) is a popular distributed heuristic for finding the Maximum A Posteriori (MAP) assignment in a joint probability distribution represented by a Graphical Model (GM). It was recently shown that BP converges to the correct MAP assignment for a class of loopy GMs with the following common feature: the Linear Programming (LP) relaxation to the MAP problem is tight (has no integrality gap). Unfortunately, tightness of the LP relaxation does not, in general, guarantee convergence and correctness of the BP algorithm. The failure of BP in such cases motivates reverse engineering a solution-namely, given a tight LP, can we design a 'good' BP algorithm. In this paper, we design a BP algorithm for the Maximum Weight Matching (MWM) problem over general graphs. We prove that the algorithm converges to the correct optimum if the respective LP relaxation, which may include inequalities associated with non-intersecting odd-sized cycles, is tight. The most significant part of our approach is the introduction of a novel graph transformation designed to force convergence of BP. Our theoretical result suggests an efficient BP-based heuristic for the MWM problem, which consists of making sequential, "cutting plane", modifications to the underlying GM. Our experiments show that this heuristic performs as well as traditional cutting-plane algorithms using LP solvers on MWM problems.

Duke Scholars

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2013

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Shin, J., Gelfand, A. E., & Chertkov, M. (2013). A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles. In Advances in Neural Information Processing Systems.
Shin, J., A. E. Gelfand, and M. Chertkov. “A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles.” In Advances in Neural Information Processing Systems, 2013.
Shin J, Gelfand AE, Chertkov M. A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles. In: Advances in Neural Information Processing Systems. 2013.
Shin, J., et al. “A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles.” Advances in Neural Information Processing Systems, 2013.
Shin J, Gelfand AE, Chertkov M. A graphical transformation for belief propagation: Maximum Weight Matchings and odd-sized cycles. Advances in Neural Information Processing Systems. 2013.

Published In

Advances in Neural Information Processing Systems

ISSN

1049-5258

Publication Date

January 1, 2013

Related Subject Headings

  • 4611 Machine learning
  • 1702 Cognitive Sciences
  • 1701 Psychology