AD3 (approximate MAP decoder with Alternating Direction Dual Decomposition) Copyright (C) 2012 Andre Martins Priberam Labs, Lisbon, Portugal & Instituto de Telecomunicacoes, Instituto Superior Tecnico, Lisbon, Portugal All Rights Reserved.
This program is free software: you can redistribute it and/or modify it under the terms of the GNU Lesser General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.
This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License for more details.
You should have received a copy of the GNU Lesser General Public License along with this program. If not, see http://www.gnu.org/licenses/.
AD3 (Alternating Directions Dual Decomposition) is an LP-MAP decoder for undirected constrained factor graphs. In other words, it is an approximate MAP decoder that retrieves the solution of an LP relaxation of the original problem. It applies the ADMM method which is described in refs. [1,3,4,5,6] below.
The input is a factor graph, which may contain both soft factors, associated with log-potentials, and hard constraint factors, associated with a logic function. Factors can be dense, sparse, or combinatorial. Specialized factors can be implemented by the practicioner (see below for instructions and examples).
The output is the LP-MAP assignment, with a posterior value for each variable. If all variables are integer, the relaxation is tight and the solution is the true MAP. Otherwise, some entries can be in the unit interval. External tools can be used to obtain a valid solution using rounding heuristics. Optionally, a flag can be set that applies a branch-and-bound procedure and retrieves the true MAP (but it can be slow if the relaxation has many fractional components).
AD3 v2.0 can handle dense, sparse, and combinatorial factors, with binary or multi-valued variables. This comes in addition to the PAIR and logic factors (XOR, OR, OR-with-output, and ATMOSTONE) already handled by AD3 v1.0. The subproblems for these factors are addressed with the active set method described in ref. [6] below.
AD3 v2.0 allows the practicioner to implement her own specialized factor, which will be automatically handled by the AD3 algorithm. The practicioner only needs to implement a method for computing the local MAP for that factor. We include example files to illustrate how this can be done for sequential factors, tree factors and head automaton factors (used in dependency parsing).
AD3 v2.0 can now process input UAI files (see http://www.cs.huji.ac.il/project/PASCAL/fileFormat.php), in addition to the FG files already processed by AD3 v1.0. A standalone tool is included to decode the factor graphs encoded in these files.
AD3 v2.0 can also be compiled as a library (libad3), whose methods can be called from an external program. See below for usage examples.
Running AD3 v2.0 requires a standard C++ compiler. The code is self-contained. The only dependency is Eigen (http://eigen.tuxfamily.org/), 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.
This tarball contains a folder called ad3_v2, which we will refer to as the "root" folder. Underneath it, there are the following files and folders:
ad3_multi.cpp Source file for the standalone application.
ad3/ Folder containing the source and header files for AD3.
data/ Folder containing some example input files.
examples/ Folder containing some example implementations that use libad3.
Eigen/ Folder containing the Eigen header files (downloaded from http://eigen.tuxfamily.org/)
Makefile Makefile for generating all the executables and library files.
LICENSE Text of the GNU Lesser General Public License, Version 3.
README This file.
The Python wrapper can be downloaded and installed via:
pip setup.py install
To install the C++ binary and library from source, AD3 v2.1 can be downloaded from http://github.com/andre-martins/AD3/archive/2.1.tar.gz. To compile the code, cd the root folder and type:
make
This will create an executable file ad3_multi in the root folder, a static library libad3 in the ad3 folder, and several executables in the example folders. To test, type:
./ad3_multi
which should produce the following output:
Usage: ad3_multi --format=[ad3(*)|uai] --file_graphs=[IN] \
--file_posteriors=[OUT] --algorithm=[ad3(*)|psdd|mplp] \
(--max_iterations=[NUM] --eta=[NUM] --adapt_eta=[true(*)|false] \
--residual_threshold=[NUM] --convert_to_binary=[true|false(*)] \
--exact=[true|false(*)])Then, type:
> ./ad3_multi --format=uai --file_graphs=data/30markers.uai \
--file_posteriors=posteriors.out | tail -4It should print something like:
Solution value after 37 iterations (AD3) = -1005.47
Took 0.296 sec.
Solution is integer.
Elapsed time: 0.296 sec.and a file named "posteriors.out" should be created in the root folder.
The following flags can be set:
Usage: ad3_multi --format=[ad3(*)|uai] --file_graphs=[IN] \
--file_posteriors=[OUT] --algorithm=[ad3(*)|psdd|mplp] \
(--max_iterations=[NUM] --eta=[NUM] --adapt_eta=[true(*)|false] \
--residual_threshold=[NUM] --convert_to_binary=[true|false(*)] \
--exact=[true|false(*)])--file_graphs=[IN] Specifies the path to the input file, containing the structure of the factor graphs and their log-potentials.
--format=[ad3(*)|uai] Specifies the format of the input file. Default is "ad3" which is described below. An alternative for factor graphs with dense factors, is the "uai" format, which is described at http://www.cs.huji.ac.il/project/PASCAL/fileFormat.php.
--file_posteriors=[OUT] Specifies the path to the output file, containing the LP-MAP or MAP solution. See below for an description of the format of this file.
--algorithm=[ad3(*)|psdd|mplp] Decoding algorithm. Default is AD3, other choices are the projected subgradient algorithm and generalized MPLP.
--max_iterations=[NUM] Maximum number of iterations, for any of the algorithms above. Default is 1000.
--eta=[NUM] Value of the penalty constant in AD3, or the initial stepsize in the projected subgradient algorithm. In AD3, if adapt_eta is true, this is the initial penalty, otherwise every iteration will apply this amount of penalty. Default is 0.1.
--adapt_eta=[true(*)|false] If true, adapt eta using the strategy described in ref. [2] below. Default is true.
--residual_threshold=[NUM] Threshold for the primal and dual residuals in AD3. The algorithm will be stopped if both residuals are below this threshold. Default is 1e-6.
--exact=[true|false(*)] If true, apply a branch-and-bound procedure for obtaining the exact MAP (note: this can be quite slow if the relaxation is "too fractional"). Default is false.
--convert_to_binary=[true|false(*)] If true, convert a factor graph with multi-valued variables to one which only containts binary variables and hard constraints. This is an alternative to the active set method, but it is usually much slower. Default is false.
NOTE: for factor graphs with dense factors and multi-valued variables, we recommend using the (more standard) UAI file format instead. However, the AD3 file format is recommended for factor graphs with hard constraint logic factors. They also allow specifying multiple factor graphs in a single file.
IMPORTANT NOTE: AD3 files contain log-potentials, while UAI file contain potentials.
AD3 files are in ASCII format and contain the following information:
[BLOCK DESCRIBING FACTOR GRAPH 1]
[BLOCK DESCRIBING FACTOR GRAPH 2]
...
[BLOCK DESCRIBING FACTOR GRAPH K]That is, each block is a description of a single factor graph, and blocks are separated by empty lines.
Each block should be of the following format:
[NUMBER OF VARIABLES]
[NUMBER OF FACTORS]
Log-potential of variable 1
Log-potential of variable 2
...
Log-potential of variable N
[LINE DESCRIBING FACTOR 1]
[LINE DESCRIBING FACTOR 2]
...
[LINE DESCRIBING FACTOR M]The line describing each factor should have the following fields, separated by whitespaces: [FACTOR TYPE] [FACTOR DEGREE] [INDEX OF VAR 1] ... [INDEX OF VAR L] ([FACTOR LOG-POTENTIAL])
The meaning of these fields is the following: [FACTOR TYPE] can be one of XOR, OR, OROUT, ATMOSTONE, or PAIR. [FACTOR DEGREE] is the number of variables linked to the factor (always 2 for PAIR factors). [INDEX OF VAR i] contains one-based indices of the variables. For the logic factors (i.e., all the above except PAIR) a dash used as a prefix means that the variable is negated. [FACTOR POTENTIAL] is optional and should be included iff FACTOR TYPE is "PAIR", in which case it contains a score for the configuration where both input variables are TRUE (the other three configurations receive a score of zero).
Some examples:
"XOR 3 15 1417 -1419"
A XOR factor linked to three variables (15, 1417 and 1419) where the
last variable is negated. This is actually equivalent to
XOR-with-output. The feasible configurations are (TRUE, FALSE, TRUE),
(FALSE, TRUE, TRUE) and (FALSE, FALSE, FALSE).
"ATMOSTONE 3 15 1417 1419"
A ATMOSTONE factor linked to three variables (15, 1417 and 1419). The
feasible configurations are (TRUE, FALSE, FALSE), (FALSE, TRUE, FALSE),
(FALSE, FALSE, TRUE) and (FALSE, FALSE, FALSE).
"OR 2 1 2"
A OR factor linked to two variables (1 and 2). All configurations are
feasible except (FALSE, FALSE).
"OROUT 3 10 20 30"
A OR-with-output factor with two inputs (10 and 20) and one output (30).
If either 10 or 20 are TRUE, 30 must be TRUE; otherwise 30 must be FALSE.
"OROUT 3 -10 -20 -30"
A OR-with-output factor with two negated inputs (10 and 20) and one
negated output (30). This is actually equivalent to a AND-with-output.
If both 10 or 20 are TRUE, 30 must be TRUE; otherwise 30 must be FALSE.
"PAIR 2 25 26 0.048103"
A PAIR factor connecting variables 25 and 26. The potential function
evaluates to 0.048103 if both variables are TRUE, and to 0 otherwise.Some examples of input files:
1) Example of input file (example1.fg) for a constrained factor graph consisting of three variables connected by a OR factor:
3
1
0.75
1.25
-0.5
OR 3 1 2 3In this case the probability distribution is
P(y1,y2,y3) = 0, if y1 = y2 = y3 = 0
1/Z exp(0.75*y1 + 1.25*y2 - 0.5*y3), otherwise.2) Example of input file (example2.fg) that in addition have the two first variables connected by a PAIR factor:
3
2
0.75
1.25
-0.5
OR 3 1 2 3
PAIR 2 1 2 -1.05In this case the probability distribution is
P(y1,y2,y3) =
0, if y1 = y2 = y3 = 0
1/Z exp(0.75*y1 + 1.25*y2 - 0.5*y3 - 1.05*y1*y2), otherwise.3) Example of input file (coref.fg) for a toy coreference task with transitivity constraints and some constraints requiring that each entity cluster has at least a noun (all expressable as OR factors). Here the LP-MAP is fractional, but the branch and bound procedure (flag --exact=true) is able to retrieve the true MAP.
4) Example of input file (parsing_excerpt.fg) for dependency parsing in Slovene, taken from ref. [4] below. This is for a single sentence, and the LP-MAP is integer.
5) Input file used in ref. [5] below, for FrameNet semantic parsing. Contains several factor graphs, one per predicate in the dev-set, with various constraints regarding the kind of roles and their spans associated with the predicate frame. (Thanks to Dipanjan Das for generating this file.)
The output file contains one floating point number per line, and as many lines as the number of binary variables (or states of multi-valued variables) plus the number of factor log-potential values (e.g., a PAIR factor has one log-potential value, a DENSE factor with 5 variables and 3 states each has 3^5 log-potential values). The values in each line contain the LP-MAP value for each variable, by order of index, followed by the LP-MAP values for each factor configuration, by order of appearance.
NOTE: Internally, multi-valued variables are treated as arrays of binary variables, one per state.
To use AD3 in your C++ project, either copy the source/header files in the ad3 folder, or link statically with libad3. You can look at the makefiles in the example folders.
As a simple example, the following code will create a fully connected Potts model with 3 variables with 5 states each, and will run AD3 on it. Other simple examples are in the example folders, including one for non-projective dependency parsing with head automata, one for co-reference resolution, and another for decoding Potts grids.
int main(int argc, char **argv) { // Create the factor graph. AD3::FactorGraph factor_graph;
// Create 3 multi-valued variables with 5 states each. std::vector<AD3::MultiVariable*> multi_variables(3); for (int i = 0; i < 3; ++i) { multi_variables[i] = factor_graph.CreateMultiVariable(5);
// Set uniform log-potentials.
for (int k = 0; k < 5; ++k) {
score = 0.0;
multi_variables[i]->SetLogPotential(k, score);
}}
// Set the factor log-potentials.
vector
// Create 3 factors connecting all the variables pairs. vector<AD3::MultiVariable*> multi_variables_local(2); multi_variables_local[0] = multi_variables[0]; multi_variables_local[1] = multi_variables[1]; factor_graph.CreateFactorDense(multi_variables_local, additional_log_potentials); multi_variables_local[0] = multi_variables[0]; multi_variables_local[1] = multi_variables[2]; factor_graph.CreateFactorDense(multi_variables_local, additional_log_potentials); multi_variables_local[0] = multi_variables[1]; multi_variables_local[1] = multi_variables[2]; factor_graph.CreateFactorDense(multi_variables_local, additional_log_potentials);
vector
// Run AD3. factor_graph.SetEtaAD3(0.1); factor_graph.AdaptEtaAD3(true); factor_graph.SetMaxIterationsAD3(1000); factor_graph.SolveLPMAPWithAD3(&posteriors, &additional_posteriors, &value);
return 0; }
To contribute to AD3, you can fork the following github repository:
http://github.com/andre-martins/AD3.
If this code is used, please cite the paper [3] below.
[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] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. "Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers." Foundations and Trends in Machine Learning, Michael Jordan, Editor in Chief, 3(1):1–122, 2011.
[3] 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.
[4] 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.
[5] 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.
[6] André F. T. Martins. "The Geometry of Constrained Structured Prediction: Applications to Natural Language Syntax." PhD thesis, Carnegie Mellon University and Instituto Superior Tecnico, 2012.
If you find any bugs or have questions, please email André Martins (afm@cs.cmu.edu).
1.0 - First public release (2012-06-01) 2.0 - Second public release (2012-09-08) 2.1 - Incremental release for Python wrapper functionality (2017-07-31)