Dual Decomposition for Marginal Inference
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.
Cite
Text
Domke. "Dual Decomposition for Marginal Inference." AAAI Conference on Artificial Intelligence, 2011. doi:10.1609/AAAI.V25I1.8023Markdown
[Domke. "Dual Decomposition for Marginal Inference." AAAI Conference on Artificial Intelligence, 2011.](https://mlanthology.org/aaai/2011/domke2011aaai-dual/) doi:10.1609/AAAI.V25I1.8023BibTeX
@inproceedings{domke2011aaai-dual,
title = {{Dual Decomposition for Marginal Inference}},
author = {Domke, Justin},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2011},
pages = {1037-1042},
doi = {10.1609/AAAI.V25I1.8023},
url = {https://mlanthology.org/aaai/2011/domke2011aaai-dual/}
}