# Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation

Akshat Kumar and Shlomo Zilberstein.
Message-Passing Algorithms for Quadratic Programming
Formulations of MAP Estimation.
*Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence*
(UAI), 428-435, Barcelona, Spain, 2011.

## Abstract

Computing *maximum a posteriori* (MAP) estimation
in graphical models is an important
inference problem with many applications.
We present message-passing algorithms for
quadratic programming (QP) formulations of
MAP estimation for pairwise Markov random
fields. In particular, we use the concave-convex
procedure (CCCP) to obtain a locally
optimal algorithm for the *non-convex*
QP formulation. A similar technique is used
to derive a globally convergent algorithm for
the *convex* QP relaxation of MAP. We also
show that a recently developed expectation-maximization
(EM) algorithm for the QP formulation
of MAP can be derived from the
CCCP perspective. Experiments on synthetic
and real-world problems confirm that
our new approach is competitive with max-product
and its variations. Compared with
CPLEX, we achieve more than an order-of-magnitude
speedup in solving optimally the
convex QP relaxation.

### Bibtex entry:

@inproceedings{KZuai11, author = {Akshat Kumar and Shlomo Zilberstein}, title = {Message-Passing Algorithms for Quadratic Programming Formulations of {MAP} Estimation}, booktitle = {Proceedings of the Twenty-Seventh Conference on Uncertainty in Artificial Intelligence}, year = {2011}, pages = {428-435}, address = {Barcelona, Spain}, url = {http://rbr.cs.umass.edu/shlomo/papers/KZuai11.html} }shlomo@cs.umass.edu