AD3 (Alternating Directions Dual Decomposition)

This page provides a link to AD3 (pronounced AD-cubed), a free approximate MAP decoder developed by André Martins.
It is based on joint work with Noah Smith, Mário Figueiredo, Eric Xing, Pedro Aguiar, Dipanjan Das.

Background

It is often convenient in NLP and other fields to use factor graph representations with special factors representing hard constraints: we may have first-order logic constraints that render zero probability to the output configurations that violate those constraints. Unfortunately, computing the MAP in an undirected graphical model is in general NP-hard. Among the most popular approximate decoders are those based on LP relaxations (hereafter, LP-MAP decoding), which underlie several recently proposed message-passing and dual decomposition algorithms.

AD3 is one such dual decomposition algorithm:

For the reasons above, AD3 is suitable for dealing with declarative constraints, which are convenient in NLP for expressing rich prior knowledge.

This package contains a C++ implementation of the AD3 described in the papers [1, 2, 3] below.

News

We released AD3 v2.0 on September 9th, 2012! This version introduces a number of new features:

Download

To run this software, you need a standard C++ compiler. The code is self-contained. AD3 v2.0 uses Eigen, which is included in the release (current version is Eigen 3.1.1). It has been tested on Linux, but it should run in other platforms with minor adaptations.

For questions, bug fixes and comments, please e-mail afm [at] cs.cmu.edu.

To contribute to AD3, you can fork the following github repository: http://github.com/andre-martins/AD3.

To receive announcements about updates to AD3, join the ARK-tools mailing list.

Further Reading

If this code is used, please cite the paper [2] below. The main technical ideas behind this software appear in the following papers and thesis:


[1]  André F. T. Martins, Noah A. Smith, Eric P. Xing, Pedro M. Q. Aguiar, and Mário A. T. Figueiredo.
Augmented Dual Decomposition for MAP Inference.
NIPS Workshop in Optimization for Machine Learning, Whistler, Canada, December 2010.
[2]  André F. T. Martins, Mário A. T. Figueiredo, Pedro M. Q. Aguiar, Noah A. Smith, and Eric P. Xing.
An Augmented Lagrangian Approach to Constrained MAP Inference.
International Conference on Machine Learning (ICML'11), Bellevue, Washington, USA, June 2011.
[3]  André F. T. Martins, Noah A. Smith, Mário A. T. Figueiredo, Pedro M. Q. Aguiar.
Dual Decomposition With Many Overlapping Components.
Empirical Methods in Natural Language Processing (EMNLP'11), Edinburgh, UK, July 2011.
[4]  Dipanjan Das, André F. T. Martins, and Noah A. Smith.
An Exact Dual Decomposition Algorithm for Shallow Semantic Parsing with Constraints.
Proceedings of *SEM 2012.
[5]  André F. T. Martins.
The Geometry of Constrained Structured Prediction: Applications to Natural Language Syntax.
PhD thesis, Carnegie Mellon University and Instituto Superior Técnico, 2012. To appear.

Acknowledgments

A. M. was supported by a FCT/ICTI grant through the CMU-Portugal Program, and by Priberam. This work was partially supported by the FET programme (EU FP7), under the SIMBAD project (contract 213250), and by National Science Foundation grant IIS-1054319.