Message-Passing Algorithms for MAP Estimation Using DC Programming
Abstract
We address the problem of finding the most likely assignment or MAP estimation in a Markov random field. We analyze the linear programming formulation of MAP through the lens of difference of convex functions (DC) programming, and use the concave-convex procedure (CCCP) to develop efficient message-passing solvers. The resulting algorithms are guaranteed to converge to a global optimum of the well-studied local polytope, an outer bound on the MAP marginal polytope. To tighten the outer bound, we show how to combine it with the mean-field based inner bound and, again, solve it using CCCP. We also identify a useful relationship between the DC formulations and some recently proposed algorithms based on Bregman divergence. Experimentally, this hybrid approach produces optimal solutions for a range of hard OR problems and near-optimal solutions for standard benchmarks.
Cite
Text
Kumar et al. "Message-Passing Algorithms for MAP Estimation Using DC Programming." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.Markdown
[Kumar et al. "Message-Passing Algorithms for MAP Estimation Using DC Programming." Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, 2012.](https://mlanthology.org/aistats/2012/kumar2012aistats-messagepassing/)BibTeX
@inproceedings{kumar2012aistats-messagepassing,
title = {{Message-Passing Algorithms for MAP Estimation Using DC Programming}},
author = {Kumar, Akshat and Zilberstein, Shlomo and Toussaint, Marc},
booktitle = {Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics},
year = {2012},
pages = {656-664},
volume = {22},
url = {https://mlanthology.org/aistats/2012/kumar2012aistats-messagepassing/}
}