Dual Decomposition for Marginal Inference

Authors

  • Justin Domke Rochester Institute of Technology

Abstract

We present a dual decomposition approach to the tree-reweighted belief propagation objective. Each tree in the tree-reweighted bound yields one subproblem, which can be solved with the sum-product algorithm. The master problem is a simple differentiable optimization, to which a standard optimization method can be applied. Experimental results on 10x10 Ising models show the dual decomposition approach using L-BFGS is similar in settings where message-passing converges quickly, and one to two orders of magnitude faster in settings where message-passing requires many iterations, specifically high accuracy convergence, and strong interactions.

Downloads

Published

2011-08-04

How to Cite

Domke, J. (2011). Dual Decomposition for Marginal Inference. Proceedings of the AAAI Conference on Artificial Intelligence, 25(1), 1037-1042. Retrieved from https://ojs.aaai.org/index.php/AAAI/article/view/8023