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.
Original language | English (US) |
---|---|
Pages | 222-231 |
Number of pages | 10 |
State | Published - 2013 |
Externally published | Yes |
Event | 29th Conference on Uncertainty in Artificial Intelligence, UAI 2013 - Bellevue, WA, United States Duration: Jul 11 2013 → Jul 15 2013 |
Other
Other | 29th Conference on Uncertainty in Artificial Intelligence, UAI 2013 |
---|---|
Country/Territory | United States |
City | Bellevue, WA |
Period | 7/11/13 → 7/15/13 |
ASJC Scopus subject areas
- Artificial Intelligence