# MAP Estimation for Graphical Models by Likelihood Maximization

Akshat Kumar and Shlomo Zilberstein.
MAP Estimation for Graphical Models by Likelihood Maximization.
*Proceedings of the Twenty-Fourth Neural Information Processing Systems Conference*
(NIPS), 1180-1188, Vancouver, British Columbia, Canada, 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 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.
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.

### Bibtex entry:

@inproceedings{KZnips10, author = {Akshat Kumar and Shlomo Zilberstein}, title = {{MAP} Estimation for Graphical Models by Likelihood Maximization}, booktitle = {Proceedings of the Twenty-Fourth Neural Information Processing Systems Conference}, year = {2010}, pages = {1180-1188}, address = {Vancouver, British Columbia, Canada}, url = {http://rbr.cs.umass.edu/shlomo/papers/KZnips10.html} }shlomo@cs.umass.edu