Tree consistency and bounds on the performance of the max-product algorithm and its generalizations

By Martin J. Wainwright, Tommi S. Jaakkola, Alan S. Willsky. 2004

143 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics, Computer Networks and Communications

How researchers see this paper

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

In Artificial Intelligence

In Computational Theory and Mathematics

In Computer Networks and Communications

Citations in the corpus

Deep Coordination Graphs (2019, background): “We compare DCG’s performance with that of other MARL Q -learning algorithms in a challenging family of predator-prey tasks that require coordinated actions.”
Bounded approximate decentralised coordination via the max-sum algorithm (2009, unknown): “See [34] for details.”
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].”
Convergent Tree-Reweighted Message Passing for Energy Minimization (2006, background): “E(x | θ) = E(x | θ̄) for all x ∈ X ) then θ is called a reparameterization of θ̄ [5,25,26,30,32] (in [25] this notion was called equivalent transformations).”
Minimizing Nonsubmodular Functions with Graph Cuts-A Review (2007, background): “The term repameterization was introduced in the machine learning community [13], [34] (an alternative term for this is equivalent transformations [25], [36]).”
Exploiting Agent and Type Independence in Collaborative Graphical Bayesian Games (2011, methodology): “es are sent either in parallel or sequentially with a ﬁ xed or random ordering. When run on an acyclic factor graph (i.e., a tree), it is guaranteed to converge to an optimal ﬁxed point (Pearl, 1988; Wainwright et al., 2004). In cyclic factor graphs, such as those deﬁned in Sec. 3 .4, there are no g”
Collaborative Multiagent Reinforcement Learning by Payoff Propagation (2006, methodology): “For trees the messages converge to a fixed point within a finite number of steps (Pearl, 1988; Wainwright et al., 2004).”
Comparison of graph cuts with belief propagation for stereo, using identical MRF parameters (2003, unknown): “Upper bounds on the difference between the probability of the true MAP solution and the approximate solution returned by Belief Propagation are shown in [13].”
A Linear Programming Approach to Max-Sum Problem: A Review (2007, background): “Importantly, it is noted [26], [27] that message passing can be alternatively viewed as reparameterizations of the problem.”