Notice: The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates. Full accuracy metrics and methodology are described in [1].
AD3: Alternating Directions Dual Decomposition for MAP Inference in Graphical Models
Authors: André F. T. Martins, Mário A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, Eric P. Xing
JMLR 2015 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | Experiments on synthetic and real-world problems show that AD3 compares favorably with the state-of-the-art. Keywords: MAP inference, graphical models, dual decomposition, alternating directions method of multipliers. 1. Introduction... Experiments with synthetic models, as well as in protein design and dependency parsing (Section 7) testify for the success of our approach. |
| Researcher Affiliation | Collaboration | Andre F. T. Martins EMAIL Priberam Labs, Alameda D. Afonso Henriques 41, 2. , 1000 123 Lisboa, Portugal and Instituto de Telecomunica c oes, Av. Rovisco Pais 1, 1049 001 Lisboa, Portugal. Mario A. T. Figueiredo EMAIL Instituto de Telecomunica c oes, and Instituto Superior T ecnico, Universidade de Lisboa Av. Rovisco Pais 1, 1049 001 Lisboa, Portugal. Pedro M. Q. Aguiar EMAIL Instituto de Sistemas e Rob otica, and Instituto Superior T ecnico, Universidade de Lisboa Av. Rovisco Pais 1, 1049 001 Lisboa, Portugal. Noah A. Smith EMAIL Eric P. Xing EMAIL School of Computer Science, Carnegie Mellon University, 5000 Forbes Ave, Pittsburgh PA 15213 3891, USA. |
| Pseudocode | Yes | Algorithm 1 PSDD Algorithm (Komodakis et al., 2007) ... Algorithm 2 Alternating Directions Dual Decomposition (AD3) ... Algorithm 3 Active Set Algorithm for Solving a General AD3 Subproblem ... Algorithm 4 Projection onto simplex (Duchi et al., 2008) ... Algorithm 5 Projection onto A1 |
| Open Source Code | Yes | It also reports a wider set of experiments and the release of open-source code (available at http://www.ark.cs.cmu.edu/AD3), which may be useful to other researchers in the field. ... The parser is publicly available as an open-source project at http://www.ark.cs.cmu.edu/Turbo Parser. |
| Open Datasets | Yes | We compare AD3 with the MPLP implementation8 of Sontag et al. (2008) in the benchmark protein design problems9 of Yanover et al. (2006). ... We use an English data set derived from the Penn Treebank (PTB)(Marcus et al., 1993), converted to dependencies by applying the head rules of Yamada and Matsumoto (2003); |
| Dataset Splits | Yes | We use an English data set derived from the Penn Treebank (PTB)(Marcus et al., 1993), converted to dependencies by applying the head rules of Yamada and Matsumoto (2003); we follow the common procedure of training in sections 02 21 (39,832 sentences), using 22 as validation data (1,700 sentences), and testing on 23 (2,416 sentences). |
| Hardware Specification | Yes | All speeds were measured in a desktop PC with Intel Core i7 CPU 3.4 GHz and 8GB RAM. |
| Software Dependencies | No | The whole data set contains 4,462 instances, which were parsed by this exact variant of the AD3 algorithm in only 4.78 seconds, against 43.12 seconds of CPLEX, a state-of-the-art commercial ILP solver. ... We compare AD3 with the MPLP implementation8 of Sontag et al. (2008) in the benchmark protein design problems9 of Yanover et al. (2006). ... For norm-product BP, we adapted the code provided by the authors, using the trivial counting numbers cα = 1, ciα = 0, and ci = 0, (i, α) E, which leads to a concave entropy approximation. |
| Experiment Setup | Yes | For the subgradient method, the step sizes are ηt = η0/k(t), where k(t) is the number of times the dual decreased up to the tth iteration, and η0 was chosen with hindsight in {0.001, 0.01, 0.1, 10} to yield the best dual objective. For accelerated dual decomposition, the most favorable parameter ϵ {0.1, 1, 10, 100} was chosen. For norm-product BP, the temperature was set as τ = 0.001, and the dual objective is computed with zero temperature (which led to better upper bounds). AD3 uses η=0.1 for all runs. |