On the optimality of tree-reweighted max-product message-passing
arXiv:1207.1395
Abstract
Tree-reweighted max-product (TRW) message passing 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.
Appears in Proceedings of the Twenty-First Conference on Uncertainty in Artificial Intelligence (UAI2005)
Cited by in corpus (6)
- Tightening LP Relaxations for MAP using Message Passing
- Lagrangian Relaxation for MAP Estimation in Graphical Models
- Node Splitting: A Scheme for Generating Upper Bounds in Bayesian Networks
- Exactness of Belief Propagation for Some Graphical Models with Loops
- MAP Estimation, Linear Programming and Belief Propagation with Convex Free Energies
- Discrete Energy Minimization, beyond Submodularity: Applications and Approximations