Convergent message passing algorithms - a unifying view
arXiv:1205.2625
Abstract
Message-passing algorithms have emerged as powerful techniques for approximate inference in graphical models. When these algorithms converge, they can be shown to find local (or sometimes even global) optima of variational formulations to the inference problem. But many of the most popular algorithms are not guaranteed to converge. This has lead to recent interest in convergent message-passing algorithms. In this paper, we present a unified view of convergent message-passing algorithms. We present a simple derivation of an abstract algorithm, tree-consistency bound optimization (TCBO) that is provably convergent in both its sum and max product forms. We then show that many of the existing convergent algorithms are instances of our TCBO algorithm, and obtain novel convergent algorithms "for free" by exchanging maximizations and summations in existing algorithms. In particular, we show that Wainwright's non-convergent sum-product algorithm for tree based variational bounds, is actually convergent with the right update order for the case where trees are monotonic chains.
Appears in Proceedings of the Twenty-Fifth Conference on Uncertainty in Artificial Intelligence (UAI2009)
References in corpus (3)
Cited by in corpus (23)
- Learning Graphical Model Parameters with Approximate Marginal Inference
- Learning Deep Structured Models
- A new look at reweighted message passing
- Variational Algorithms for Marginal MAP
- Efficient MRF Energy Minimization via Adaptive Diminishing Smoothing
- Decomposition Bounds for Marginal MAP
- Message-Passing Algorithms for Quadratic Minimization
- Joint Structured Models for Extraction from Overlapping Sources
- Tightening Fractional Covering Upper Bounds on the Partition Function for High-Order Region Graphs
- Performing Bayesian Risk Aggregation using Discrete Approximation Algorithms with Graph Factorization
- A Graphical Transformation for Belief Propagation: Maximum Weight Matchings and Odd-Sized Cycles
- Generalized Belief Propagation on Tree Robust Structured Region Graphs
- Approximated Structured Prediction for Learning Large Scale Graphical Models
- Norm-Product Belief Propagation: Primal-Dual Message-Passing for Approximate Inference
- Efficient Message Passing for 0-1 ILPs with Binary Decision Diagrams
- Relaxed Marginal Consistency for Differentially Private Query Answering
- Concavity of reweighted Kikuchi approximation
- Fundamental Linear Algebra Problem of Gaussian Inference
- On Coordinate Minimization of Convex Piecewise-Affine Functions
- Diffusion Methods for Classification with Pairwise Relationships
- Tree-based iterated local search for Markov random fields with applications in image analysis
- Best-Choice Edge Grafting for Efficient Structure Learning of Markov Random Fields
- End-to-end Training of CNN-CRF via Differentiable Dual-Decomposition