Message-Passing Algorithms for MAP Estimation Using DC Programming

Akshat Kumar, Shlomo Zilberstein, and Marc Toussaint. Message-Passing Algorithms for MAP Estimation Using DC Programming. Proceedings of the Fifteenth International Conference on Artificial Intelligence and Statistics (AISTATS), 656-664, La Palma, Canary Islands, 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 nearoptimal solutions for standard benchmarks.

Bibtex entry:

@inproceedings{KZTaistats12,
  author	= {Akshat Kumar and Shlomo Zilberstein and Marc Toussaint},
  title		= {Message-Passing Algorithms for MAP Estimation Using DC Programming},
  booktitle     = {Proceedings of the Fifteenth International Conference on Artificial
                   Intelligence and Statistics},
  year		= {2012},
  pages		= {656-664},
  address       = {La Palma, Canary Islands},
  url		= {http://rbr.cs.umass.edu/shlomo/papers/KZTaistats12.html}
}

shlomo@cs.umass.edu