On the optimality of solutions of the max-product belief-propagation algorithm in arbitrary graphs

By Yair Weiss, William T. Freeman. IEEE Transactions on Information Theory, 2001

661 citations recorded by the source corpus.

Subfields: Computer Networks and Communications, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/3f583eca0700a808c6a802ae8e79835f111b22ce

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

In Molecular Biology

Citations in the corpus

Super-human multi-talker speech recognition: A graphical modeling approach (2010, positive): “If the algorithm does converge (meaning that all conditional estimates ^ x Cni ðx i Þ are consistent), the MAP estimate is provably optimal over all tree and single-loop sub-structures of the probability model (Weiss and Freeman, 2001).”
Decentralised coordination of low-power embedded devices using the max-sum algorithm (2008, methodology): “this approach on graphs of arbitrary topology 2 [13, 14], there exists extensive empirical evidence of their effectiveness in practical problems.”
A Comparative Study of Energy Minimization Methods for Markov Random Fields with Smoothness-Based Priors (2008, background): “However, if LBP converges and there are no ties in the minmarginals for nodes, it has a strong local minimum property that is somewhat analogous to that of graph cuts [47], [49].”
Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters (2003, background): “The probability of this solution is guaranteed to be greater than all other solutions in a large neighborhood around that solution [15].”
Image completion with structure propagation (2005, background): “For a graph with a single loop, it has been proven [Weiss and Freeman 2001] that max-product belief propagation will yield the optimal solution if it converges .”
Creating Large-Scale City Models from 3D-Point Clouds: A Robust Approach with Hybrid Representation (2012, positive): “Energy Time α -expansion 2832.9 402 min (Boykov et al., 2001) Belief propagation 3016.6 618 min (Weiss and Freeman, 2001) α -expansion with our 2853.3 3 .5 min parallelization scheme The α -expansion algorithm (Boykov et al., 2001) is used to solve each local independent optimization problem.”
Multiresolution Markov models for signal and image processing (2002, methodology): “More generally, the coarser scale variables may or may not be directly observed and may or may not be deterministic functions of the finest scale variables , and their inclusion in the representation may serve purposes such as exposing the statistical structure of the (a) (b)”
MRF Energy Minimization and Beyond via Dual Decomposition (2011, positive): “However, despite the fact that there has been a lot of work on trying to provide a better theoretical analysis of BP-based algorithms [57], [51], [50], [15], an important drawback of these methods remains that their theoretical optimality and/or convergence properties are not yet well understood…”
Dependency Parsing by Belief Propagation (2008, background): “Furthermore, on cyclic (“loopy”) graphs, BP might only converge to a local optimum (Weiss and Freedman, 2001), or it might not converge at all.”
Tree consistency and bounds on the performance of the max-product algorithm and its generalizations (2004, methodology): “Secondly, on the basis of Theorem 3, we can establish directly a result that was first proved, using alternative methods, by Weiss (2000); this result is also a corollary of the Freeman and Weiss (2001) result from above.”
A Review of Data Fusion Techniques (2013, methodology): “The data association problem is treated as an inference problem and solved by using the max-product algorithm [32].”
Learning Low-Level Vision (1999, neutral): “For every subset of nodes of the network which form a tree, if the remaining network nodes are constrained to their converged values, the values of the sub-tree's nodes found by the MAP algorithm are the global maximum over that tree's nodes (Weiss and Freeman, 2000).”