We found a match
Your institution may have access to this item. Find your institution then sign in to continue.
- Title
AD³: Alternating Directions Dual Decomposition for MAP Inference in Graphical Models.
- Authors
Martins, André F. T.; Figueiredo, Mário A. T.; Aguiar, Pedro M. Q.; Smith, Noah A.; Xing, Eric P.
- Abstract
We present AD³, a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs, based on the alternating directions method of multipliers. Like other dual decomposition algorithms, AD³ has a modular architecture, where local subproblems are solved independently, and their solutions are gathered to compute a global update. The key characteristic of AD³ is that each local subproblem has a quadratic regularizer, leading to faster convergence, both theoretically and in practice. We provide closed-form solutions for these AD³ subproblems for binary pairwise factors and factors imposing first-order logic constraints. For arbitrary factors (large or combinatorial), we introduce an active set method which requires only an oracle for computing a local MAP configuration, making AD³ applicable to a wide range of problems. Experiments on synthetic and real-world problems show that AD³ compares favorably with the state-of-the-art.
- Subjects
MATHEMATICAL decomposition; GRAPHICAL modeling (Statistics); ALGORITHMS; APPROXIMATION theory; STOCHASTIC convergence
- Publication
Journal of Machine Learning Research, 2015, Vol 16, p495
- ISSN
1532-4435
- Publication type
Article