UMass Machine Learning and Friends Lunch | Main / MAP Estimation For Graphical Models By Likelihood Maximization

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. In this talk, I will present an alternative approach, which transforms the MAP problem into that of likelihood maximization in a mixture of simple Bayes nets. I will show how this problem can be solved by using the well known Expectation-Maximization (EM) algorithm. EM 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. Experiments on the real-world protein design dataset show that EM's convergence rate is significantly higher than the previous LP relaxation based approach MPLP. EM also achieves a solution quality within 95% of optimal for most instances.