Loopy Belief Propagation for Bipartite Maximum Weight b-Matching

Published 11 March 2007

Bert Huang, Tony Jebara

Citations93

TL;DR

The weighted b-matching objective function is formulated as a probability distribution function and it is proved that belief propagation on its graphical model converges to the optimum and shows promising performance in machine learning applications.

Abstract

We formulate the weighted b-matching objective function as a probability distribution function and prove that belief propagation (BP) on its graphical model converges to the optimum. Standard BP on our graphical model cannot be computed in polynomial time, but we introduce an algebraic method to circumvent the combinatorial message updates. Empirically, the resulting algorithm is on average faster than popular combinatorial implementations, while still scaling at the same asymptotic rate of O(bn 3). Furthermore, the algorithm shows promising performance in machine learning applications. 1

Keywords

Computer Science

Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference

16,927 Citations1988Judea Pearl

The author provides a coherent explication of probability as a language for reasoning with partial belief and offers a unifying perspective on other AI approaches to uncertainty, such as the Dempster-Shafer formalism, truth maintenance systems, and nonmonotonic logic.

IEEE Transactions on Information TheoryOn the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

593 Citations2001Yaakov Weiss, William T. Freeman

It is shown that the assignment based on a fixed point of max-product is a "neighborhood maximum" of the posterior probabilities: the posterior probability of the max- product assignment is guaranteed to be greater than all other assignments in a particular large region around that assignment.

Neural ComputationCorrectness of Local Probability Propagation in Graphical Models with Loops

470 Citations2000Yair Weiss

An analytical relationship is derived between the probabilities computed using local propagation and the correct marginals and a category of graphical models with loops for which local propagation gives rise to provably optimal maximum a posteriori assignments (although the computed marginals will be incorrect).

IEEE Transactions on Information TheoryTree-based reparameterization framework for analysis of sum-product and related algorithms

238 Citations2003Martin J. Wainwright, Tommi Jaakkola +1 more

A tree-based reparameterization (TRP) framework is presented that provides a new conceptual view of a large class of algorithms for computing approximate marginals in graphs with cycles, which includes the belief propagation or sum-product algorithm as well as variations and extensions of BP.

Loopy belief propagation and Gibbs measures

190 Citations2002Sekhar Tatikonda, Michael I. Jordan

This work relates convergence of LBP to the existence of a weak limit for a sequence of Gibbs measures defined on the LBP's associated computation tree, and develops easily testable sufficient conditions for convergence.

Maximum weight matching via max-product belief propagation

103 Citations2005Mohsen Bayati, Devavrat Shah +1 more

Mixture Modeling by Affinity Propagation

95 Citations2005Brendan J. Frey, Delbert Dueck

This work describes a technique called "affinity propagation", which combines the advantages of iteratively fitting a mixture model of the data by recursively propagating affinity messages and finds that affinity propagation obtains better solutions than mixtures of Gaussians, the K-medoids algorithm, spectral clustering and hierarchical clustering.

arXiv (Cornell University)Sufficient conditions for convergence of Loopy Belief Propagation

53 Citations2012Joris M. Mooij, Hilbert J. Kappen

Novel sufficient conditions for convergence of Loopy Belief Propagation to a unique fixed point are derived and the results improve upon previously known conditions.

View PDF

ACM Journal of Experimental AlgorithmicsImplementing weighted b-matching algorithms

22 Citations2000Matthias Müller‐Hannemann, Alexander Schwartz

The experiments confirm that a fractional jump-start speeds up the algorithm, and indicate that a variant based on pairing heaps is slightly superior to a k-heap variant, and that scaling of large <i*b*-values is not necessary, whereas a delayed blossom shrinking heuristic significantly improves running times only for graphs with average degree two.

B-Matching for Spectral Clustering

14 Citations2008Tony Jebara, Vlad Shchogolev