AD3 (Alternating Directions Dual Decomposition) (original) (raw)
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:
- 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. 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:
- 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 AD3 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 AD3 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 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.