Publication Type

Conference Proceeding Article

Version

publishedVersion

Publication Date

4-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.

Discipline

Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering

Research Areas

Intelligent Systems and Optimization

Publication

Proceedings of Machine Learning Research: International Conference on Artificial Intelligence and Statistics AISTATS 2012, April 21-23, La Palma, Canary Islands

Volume

22

First Page

656

Last Page

664

Publisher

JMLR

City or Country

Cambridge, MA

Copyright Owner and License

Authors

Additional URL

http://jmlr.org/proceedings/papers/v22/kumar12/kumar12.pdf

Download

Share

COinS