Publication Type
Conference Proceeding Article
Version
acceptedVersion
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
Citation
KUMAR, Akshat and ZILBERSTEIN, Shlomo.
MAP Estimation for Graphical Models by Likelihood Maximization. (2010). Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, 6-9 December 2010, Vancouver. 1180-1188.
Available at: https://ink.library.smu.edu.sg/sis_research/2208
Copyright Owner and License
Authors
Creative Commons License
This work is licensed under a Creative Commons Attribution-NonCommercial-No Derivative Works 4.0 International License.
Additional URL
http://papers.nips.cc/paper/4165-map-estimation-for-graphical-models-by-likelihood-maximization
Included in
Artificial Intelligence and Robotics Commons, Operations Research, Systems Engineering and Industrial Engineering Commons