| Autor: |
Martins, Andre F.T., Figeuiredo, Mario A. T., Aguiar, Pedro M.Q., Smith, Noah A., Xing, Eric P |
| Rok vydání: |
2018 |
| Předmět: |
|
| DOI: |
10.1184/r1/6475457.v1 |
| Popis: |
We propose AD3 , a new algorithm for approximate maximum a posteriori (MAP) inference on factor graphs based on the alternating directions method of multipliers. Like dual decomposition algorithms, AD3 uses worker nodes to iteratively solve local subproblems and a controller node to combine these local solutions into a global update. The key characteristic of AD3 is that each local subproblem has a quadratic regularizer, leading to a faster consensus than subgradient-based dual decomposition, both theoretically and in practice. We provide closed-form solutions for these AD3 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 AD3 applicable to a wide range of problems. Experiments on synthetic and realworld problems show that AD3 compares favorably with the state-of-the-art. |
| Databáze: |
OpenAIRE |
| Externí odkaz: |
|
