2012/02/14 by Kumar, Akshat, Shlomo Zilberstein, Zilberstein, Shlomo
Computer Science · #Algorithms and Data Compression #Artificial Intelligence (cs.AI) #Bayesian Modeling and Causal Inference #Cellular Automata and Applications #Computation (stat.CO) #Data Structures and Algorithms (cs.DS) #Error Correcting Code Techniques #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1202.3739
openalex publication_date 2012/02/14 · openalex created_date 2025/10/24 · openalex updated_date 2026/07/28
Computing maximum a posteriori (MAP) estimation in graphical models is an\nimportant inference problem with many applications. We present message-passing\nalgorithms for quadratic programming (QP) formulations of MAP estimation for\npairwise Markov random fields. In particular, we use the concave-convex\nprocedure (CCCP) to obtain a locally optimal algorithm for the non-convex QP\nformulation. A similar technique is used to derive a globally convergent\nalgorithm for the convex QP relaxation of MAP. We also show that a recently\ndeveloped expectation-maximization (EM) algorithm for the QP formulation of MAP\ncan be derived from the CCCP perspective. Experiments on synthetic and\nreal-world problems confirm that our new approach is competitive with\nmax-product and its variations. Compared with CPLEX, we achieve more than an\norder-of-magnitude speedup in solving optimally the convex QP relaxation.\n