Conference Proceeding Article
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.
Artificial Intelligence and Robotics | Operations Research, Systems Engineering and Industrial Engineering
Intelligent Systems and Optimization
Advances in Neural Information Processing Systems 23: 24th Annual Conference on Neural Information Processing Systems 2010, 6-9 December 2010, Vancouver
Neural Information Processing Systems
City or Country
La Jolla, CA
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. Research Collection School Of Information Systems.
Available at: https://ink.library.smu.edu.sg/sis_research/2208
Copyright Owner and License
Creative Commons License
This work is licensed under a Creative Commons Attribution-Noncommercial-No Derivative Works 4.0 License.