Message-Passing Algorithms for MAP Estimation Using DC Programming

Akshat Kumar, Shlomo Zilberstein, Marc Toussaint
Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, PMLR 22:656-664, 2012.

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 this Paper

BibTeX
@InProceedings{pmlr-v22-kumar12, 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}, pages = {656--664}, year = {2012}, editor = {Lawrence, Neil D. and Girolami, Mark}, volume = {22}, series = {Proceedings of Machine Learning Research}, address = {La Palma, Canary Islands}, month = {21--23 Apr}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v22/kumar12/kumar12.pdf}, url = {https://proceedings.mlr.press/v22/kumar12.html}, 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.} }
Endnote
%0 Conference Paper %T Message-Passing Algorithms for MAP Estimation Using DC Programming %A Akshat Kumar %A Shlomo Zilberstein %A Marc Toussaint %B Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2012 %E Neil D. Lawrence %E Mark Girolami %F pmlr-v22-kumar12 %I PMLR %P 656--664 %U https://proceedings.mlr.press/v22/kumar12.html %V 22 %X 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.
RIS
TY - CPAPER TI - Message-Passing Algorithms for MAP Estimation Using DC Programming AU - Akshat Kumar AU - Shlomo Zilberstein AU - Marc Toussaint BT - Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics DA - 2012/03/21 ED - Neil D. Lawrence ED - Mark Girolami ID - pmlr-v22-kumar12 PB - PMLR DP - Proceedings of Machine Learning Research VL - 22 SP - 656 EP - 664 L1 - http://proceedings.mlr.press/v22/kumar12/kumar12.pdf UR - https://proceedings.mlr.press/v22/kumar12.html AB - 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. ER -
APA
Kumar, A., Zilberstein, S. & Toussaint, M.. (2012). Message-Passing Algorithms for MAP Estimation Using DC Programming. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 22:656-664 Available from https://proceedings.mlr.press/v22/kumar12.html.

Related Material