Uncertainty in Artificial Intelligence
First Name   Last Name   Password   Forgot Password   Log in!
    Proceedings   Proceeding details   Article details         Authors         Search    
Bethe-ADMM for Tree Decomposition based Parallel MAP Inference
Qiang Fu, Huahua Wang, Arindam Banerjee
Abstract:
We consider the problem of maximum a posteriori (MAP) inference in discrete graphical models. We present a parallel MAP inference algorithm called Bethe-ADMM based on two ideas: tree-decomposition of the graph and the alternating direction method of multipliers (ADMM). However, unlike the standard ADMM, we use an inexact ADMM augmented with a Bethe-divergence based proximal function, which makes each subproblem in ADMM easy to solve in parallel using the sum-product algorithm. We rigorously prove global convergence of Bethe-ADMM. The proposed algorithm is extensively evaluated on both synthetic and real datasets to illustrate its effectiveness. Further, the parallel Bethe-ADMM is shown to scale almost linearly with increasing number of cores.
Keywords:
Pages: 222-231
PS Link:
PDF Link: /papers/13/p222-fu.pdf
BibTex:
@INPROCEEDINGS{Fu13,
AUTHOR = "Qiang Fu and Huahua Wang and Arindam Banerjee",
TITLE = "Bethe-ADMM for Tree Decomposition based Parallel MAP Inference",
BOOKTITLE = "Proceedings of the Twenty-Ninth Conference Annual Conference on Uncertainty in Artificial Intelligence (UAI-13)",
PUBLISHER = "AUAI Press",
ADDRESS = "Corvallis, Oregon",
YEAR = "2013",
PAGES = "222--231"
}


hosted by DSL   •   site info   •   help