On the optimality of tree reweighted max product message passing

V. Kolmogorov, M. Wainwright, in:, AUAI Press, 2005, pp. 316–323.

Download
No fulltext has been uploaded. References only!
Conference Paper | Published
Author
;
Abstract
Tree-reweighted max-product (TRW) message passing [9] is a modified form of the ordinary max-product algorithm for attempting to find minimal energy configurations in Markov random field with cycles. For a TRW fixed point satisfying the strong tree agreement condition, the algorithm outputs a configuration that is provably optimal. In this paper, we focus on the case of binary variables with pairwise couplings, and establish stronger properties of TRW fixed points that satisfy only the milder condition of weak tree agreement (WTA). First, we demonstrate how it is possible to identify part of the optimal solution - i.e., a provably optimal solution for a subset of nodes - without knowing a complete solution. Second, we show that for submodular functions, a WTA fixed point always yields a globally optimal solution. We establish that for binary variables, any WTA fixed point always achieves the global maximum of the linear programming relaxation underlying the TRW method.
Publishing Year
Date Published
2005-07-01
Page
316 - 323
Conference
UAI: Uncertainty in Artificial Intelligence
IST-REx-ID

Cite this

Kolmogorov V, Wainwright M. On the optimality of tree reweighted max product message passing. In: AUAI Press; 2005:316-323.
Kolmogorov, V., & Wainwright, M. (2005). On the optimality of tree reweighted max product message passing (pp. 316–323). Presented at the UAI: Uncertainty in Artificial Intelligence, AUAI Press.
Kolmogorov, Vladimir, and Martin Wainwright. “On the Optimality of Tree Reweighted Max Product Message Passing,” 316–23. AUAI Press, 2005.
V. Kolmogorov and M. Wainwright, “On the optimality of tree reweighted max product message passing,” presented at the UAI: Uncertainty in Artificial Intelligence, 2005, pp. 316–323.
Kolmogorov V, Wainwright M. 2005. On the optimality of tree reweighted max product message passing. UAI: Uncertainty in Artificial Intelligence 316–323.
Kolmogorov, Vladimir, and Martin Wainwright. On the Optimality of Tree Reweighted Max Product Message Passing. AUAI Press, 2005, pp. 316–23.

Link(s) to Main File(s)
Access Level
Restricted Closed Access

Export

Marked Publications

Open Data IST Research Explorer

Search this title in

Google Scholar