Timezone: »

MAP Estimation for Graphical Models by Likelihood Maximization
Akshat Kumar · Shlomo Zilberstein

Mon Dec 06 12:00 AM -- 12:00 AM (PST) @
Computing a {\em 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.

Author Information

Akshat Kumar (University of Massachusetts, Amherst)
Shlomo Zilberstein (Univ of Mass)

More from the Same Authors