AD³ (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.

AD³ is one such dual decomposition algorithm:

• it handles logic factors efficiently;
• it is suitable for factor graphs with many overlapping components;
• it converges faster than other message-passing and subgradient-based dual decomposition algorithms;
• in some problems it is faster than commercial, off-the-shelf solvers;
• it can be embedded in a branch-and-bound scheme to retrieve the exact MAP.

This package contains a C++ implementation of the AD³ 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:

• It can now handle dense, sparse, and combinatorial factors, with binary or multi-valued variables. This comes in addition to the logic factors handled by AD3 v1.0. The subproblems for these factors are addressed with a new active set method, described in ref. [6] below.
• It allows user-defined factors, which are automatically handled by the AD3 algorithm. The user only needs to implement a method for computing the local MAP. Example files are included in the release as illustration.
• It now accepts input files in the UAI format. A standalone tool is included to decode the factor graphs encoded in these files.
• You can now compile AD³ as a library and included it in your project. Usage examples are provided.

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.

• The latest version of AD³ is AD3 v2.0.2 [~1.5MB,.tar.gz format]. See the README file for instructions for compilation, running, and file formatting.
• Older versions: AD3 v2.0.1 [~1.5MB,.tar.gz format], AD3 v2.0 [~2.2MB,.tar.gz format], AD3 v1.0 [~32KB,.tar.gz format].
• The factor graph file for semantic parsing used in ref. [4] below, generated by the SEMAFOR system, is available here.

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 AD³, 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.