Message-Passing Algorithms for Quadratic Programming Formulations of MAP Estimation
This work addresses MAP estimation, a key inference task in machine learning with applications in various domains, but it is incremental as it builds on existing QP formulations and methods like CCCP.
The authors tackled the problem of MAP estimation in graphical models by developing message-passing algorithms based on quadratic programming formulations, achieving competitive performance with max-product variants and over an order-of-magnitude speedup compared to CPLEX for convex QP relaxation.
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.