Publication Type

Conference Proceeding Article

Version

Postprint

Publication Date

12-2010

Abstract

Computing a maximum a posteriori (MAP) assignment in graphical models is a crucial inference problem for many practical applications. Several provably convergent approaches have been successfully developed using linear programming (LP) relaxation of the MAP problem. We present an alternative approach, which transforms the MAP problem into that of inference in a finite mixture of simple Bayes nets. We then derive the Expectation Maximization (EM) algorithm for this mixture that also monotonically increases a lower bound on the MAP assignment until convergence. The update equations for the EM algorithm are remarkably simple, both conceptually and computationally, and can be implemented using a graph-based message passing paradigm similar to max-product computation. We experiment on the real-world protein design dataset and show that EM's convergence rate is significantly higher than the previous LP relaxation based approach MPLP. EM achieves a solution quality within 95% of optimal for most instances and is often an order-of-magnitude faster than MPLP.

Discipline

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

Research Areas

Intelligent Systems and Optimization

Publication

Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, 6-9 December 2010, Vancouver

First Page

1180

Last Page

1188

ISBN

9781617823800

Publisher

Neural Information Processing Systems

City or Country

La Jolla, CA

Copyright Owner and License

Authors

Creative Commons License

Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.

Additional URL

http://papers.nips.cc/paper/4165-map-estimation-for-graphical-models-by-likelihood-maximization

Download

Share

COinS