Convergent Propagation Algorithms via Oriented Trees
By Amir Globerson, Tommi S. Jaakkola. 2007
39 citations recorded by the source corpus.
Inference problems in graphical models are often approximated by casting them as constrained optimization problems. Message passing algorithms, such as belief propagation, have previously been suggested as methods for solving these optimization problems. However, there are few convergence guarantees for such algorithms, and the algorithms are therefore not guaranteed to solve the corresponding optimization problem. Here we present an oriented tree decomposition algorithm that is guaranteed to converge to the global optimum of the Tree-Reweighted (TRW) variational problem. Our algorithm performs local updates in the convex dual of the TRW problem - an unconstrained generalized geometric program. Primal updates, also local, correspond to oriented reparametrization operations that leave the distribution intact.
Subfields: Probabilistic & Bayesian Methods
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Probabilistic & Bayesian Methods
- David A. Sontag
- David M. Blei
- Simon Lacoste-Julien
- Tommi S. Jaakkola
- Martin J. Wainwright
- Michael I. Jordan
- Rahul G. Krishnan
- Jeremy Jancsary
Citations in the corpus
- Barrier Frank-Wolfe for Marginal Inference (2015, methodology): “Fast combinatorial solvers for the TRW objective exist, including Tree-Reweighted Belief Propagation (TRBP) (Wainwright et al., 2005), convergent message-passing based on geometric programming (Globerson and Jaakkola, 2007), and dual decomposition (Jancsary and Matz, 2011).”
- Graphical Models, Exponential Families, and Variational Inference (2008, methodology): “As an alternative, Globerson and Jaakkola [93] proposed a related messagepassing algorithm based on oriented trees that is guaranteed to converge, but appears to do so more slowly than damped TRW-message passing.”
- Convergent Decomposition Solvers for Tree-reweighted Free Energies (2011, background): “Globerson and Jaakkola (2007) provide a convergent algorithm for tree-reweighted free energies that solves an unconstrained geometric program.”
- Fixing Max-Product: Convergent Message Passing Algorithms for MAP LP-Relaxations (2007, methodology): “In [3] we use such an approach to optimize a variational bound on the partition function.”