Advanced Structured Prediction

Editors:
Sebastian Nowozin
Microsoft Research
Cambridge, CB1 2FB, United Kingdom

Sebastian.Nowozin@microsoft.com

Peter V. Gehler
Max Planck Insitute for Intelligent Systems
72076 Tübingen, Germany

pgehler@tuebingen.mpg.de

Jeremy Jancsary
Microsoft Research
Cambridge, CB1 2FB, United Kingdom

jermyj@microsoft.com

Christoph Lampert
IST Austria
A-3400 Klosterneuburg, Austria

chl@ist.ac.at

This is a draft version of the author chapter.

The MIT Press
Cambridge, Massachusetts
London, England

1

AD3: A Fast Decoder for Structured
Prediction

André F. T. Martins
atm@priberam.pt
Priberam Labs & Instituto de Telecomunicações
Lisbon, Portugal

In this chapter, we present AD3 , a new algorithm for approximate maximum
a posteriori (MAP) decoding on factor graphs, based on the alternating directions method of multipliers. AD3 can handle many models often encounteredin natural language processing (NLP) and information retrieval (IR), suchas models with first-order logic constraints, budget and knapsack constraints,
and combinations of structured models that are hard to decode jointly. Likeother dual decomposition algorithms, AD3 has a modular architecture, where
local subproblems are solved independently, and their solutions are gathered
to compute a global update. The key characteristic of AD3 is that each local
subproblem has a quadratic regularizer, leading to faster convergence, boththeoretically and in practice. To solve these AD3 subproblems, we present anactive set method that requires only a local MAP decoder (the same requirement as subgradient-based dual decomposition), making AD3 applicable to awide range of problems. We discuss two recent applications of AD3 in NLP
problems: dependency parsing and compressive summarization.

1.1

Introduction
Graphical models enable compact representations of probability distributions, being widely used in natural language processing (NLP), computer
vision, signal processing, and computational biology (Pearl, 1988; Lauritzen,
1996; Koller and Friedman, 2009). Given a graphical model, a central prob-

2

AD3 : A Fast Decoder for Structured Prediction

lem is that of decoding the most probable (a.k.a. maximum a posteriori– MAP) configuration. Unfortunately, exact MAP decoding is intractable
for many graphical models of interest in applications, such as those involving non-local features or structural constraints. This fact has motivated asignificant research effort on approximate techniques.
In this chapter, we turn our attention to LP-MAP decoding (Schlesinger,1976), a linear relaxation that underlies recent message-passing and dual decomposition algorithms (Wainwright et al., 2005; Kolmogorov, 2006; Werner,
2007; Komodakis et al., 2007; Globerson and Jaakkola, 2008; Jojic et al.,2010).1 All these algorithms have a similar consensus-based architecture:they repeatedly perform certain “local” operations in the graph (as outlinedin Table 1.1), until some form of local agreement is achieved. The simplest
example is the projected subgradient dual decomposition (PSDD) algorithmof Komodakis et al. (2007), which has recently enjoyed great success in NLP
applications (see Rush and Collins 2012 and references therein). The major drawback of PSDD is that it is too slow to achieve consensus in large
problems, requiring O(1/2 ) iterations for an -accurate solution.
Here, we introduce an algorithm called AD3 (alternating directions dual
decomposition), which allies the modularity of dual decomposition withthe effectiveness of augmented Lagrangian optimization, via the alternating
directions method of multipliers (Glowinski and Marroco, 1975; Gabay and
Mercier, 1976). AD3 has an iteration bound of O(1/), an order of magnitude
better than the PSDD algorithm. Like PSDD, AD3 alternates between abroadcast operation, where subproblems are assigned to local workers, anda gather operation, where the local solutions are assembled by a controller,
which produces an estimate of the global solution. The key difference isthat AD3 regularizes their local subproblems toward these global estimate,which has the effect of speeding up consensus. In many cases of interest,
there are closed-form solutions or efficient procedures for solving the AD3
local subproblems (which are quadratic). For factors lacking such a solution,
we introduce an active set method which requires only a local MAP decoder(the same requirement as in PSDD). This paves the way for using AD3 with
dense or structured factors. AD3 was originally proposed in Martins et al.
(2011a) and has been successfully applied to several NLP problems (Martinset al., 2011b, 2013; Das et al., 2012; Almeida and Martins, 2013). An opensource implementation is available at http://www.ark.cs.cmu.edu/AD3.
This chapter is organized as follows. We provide background on factor
1. See Chapter ?? of this volume for further details about LP-MAP decoding, along witha generalization of the TRW-S algorithm of Wainwright et al. (2005); Kolmogorov (2006).

1.2

Factor Graphs and MAP Decoding

Algorithm
Loopy BP (Pearl, 1988)
TRW-S (Wainwright et al., 2005; Kolmogorov, 2006)
MPLP (Globerson and Jaakkola, 2008)
PSDD (Komodakis et al., 2007)
ADD (Jojic et al., 2010)
AD3 (Martins et al., 2011a)

3

Local Operation
max-marginals
max-marginals
max-marginals
MAP
marginals
QP/MAP

Table 1.1: Several approximate MAP decoders and the kind of the local operations
they need to perform at the factors to pass messages and compute beliefs. With
the exception of loopy BP, all algorithms in this table are instances of LP-MAP
decoders. In Section 1.6, we will see that the quadratic problems (QP) required byAD3 can be solved as a sequence of local MAP problems.

graphs and the MAP decoding problem in Section 1.2. In Section 1.3, we
discuss two important NLP applications, dependency parsing and summarization, along with factor graph representations. In Section 1.4, we discuss
the LP-MAP relaxation and the PSDD algorithm. In Section 1.5, we derive
AD3 and analyze its convergence properties. The AD3 subproblems are addressed in Section 1.6, where we present the active set method. Section 1.7
reports experiments using AD3 for the two NLP applications above. Finally,
related work is discussed in Section 1.8, and Section 1.9 concludes.

1.2

Factor Graphs and MAP Decoding
1.2.1

Factor Graphs

Let Y1 , . . . , YM be random variables describing a structured output, witheach Yi taking values in a finite set Yi . We follow the common assumption
in structured prediction that some of these variables have strong statisticaldependencies. In this chapter, we use factor graphs (Tanner, 1981; Kschischang et al., 2001), a convenient way of representing such dependencies that
captures directly the factorization assumptions in a model.
Definition 1.1 (Factor graph). A factor graph is a bipartite graph G :=(V, F, E), comprised of:variable nodes V := {1, . . . , M }, corresponding to the variables Y1 , . . . , YM ;factor nodes F (disjoint from V );edges E ⊆ V × F linking variable nodes to factor nodes.
We denote by F (i) := {α ∈ F | (i, α) ∈ E} the set of factors linked to4AD3 : A Fast Decoder for Structured Prediction

the ith variable, and conversely by V (α) := {i ∈ V | (i, α) ∈ E} the set ofvariables appearing in factor α. We use the short notation Yα := (Yi )i∈V (α)
to refer to tuples of random variables, which take values on the productQ
set Yα :=i∈V (α) Yi . We say that the joint probability distribution ofY1 , . . . , YM factors according to G = (V, F, E) if it can be written as!
X
X
P(Y1 = y1 , . . . , YM = yM ) ∝ exp
θi (yi ) +θα (yα ) ,
(1.1)
i∈V

α∈F

where θi (·) and θα (·) are, respectively, unary and higher-order log-potentialfunctions. These functions define “local” scores for the variable nodes and for
configurations of variables within the factor nodes. To accommodate hardconstraints (discussed in Section 1.2.3), we allow these functions to takevalues in R̄ := R ∪ {−∞}.
1.2.2

MAP Decoding

Given a probability distribution specified as in (1.1), an important task isthat of finding an assignment with maximal probability (the so-called MAP
assignment/configuration):XX
yb1 , . . . , ybM ∈ argmax
θi (yi ) +θα (yα ).
(1.2)
y1 ,...,yM

i∈V

α∈F

A solver for problem (1.2) is called a MAP decoder. In fact, this problem is
not specific to probabilistic models: other models, e.g., trained to maximize
margin, also lead to maximizations of the form above. Unfortunately, for ageneral factor graph G, this combinatorial problem is NP-hard (Koller andFriedman, 2009), so one must resort to approximations.
In this chapter, we will address a class of approximations based on linear
programming relaxations, which will be described formally in Section 1.4.
1.2.3

Dense, Hard, and Structured Factors

Along this chapter, we will consider factors of three kinds: dense factors,
hard constraint factors, and structured factors.
A dense factor is one whose log-potential function satisfies θα (yα ) > −∞for every yα ∈ Yα . To represent a dense factor computationally, we need tostore O(|Yα |) real numbers (one per factor configuration). Since |Yα | grows
exponentially with the number of variables linked to the factor, dense factors
are only tractable for small values of |V (α)|.
Hard constraint factors have special log-potential functions that are indi-1.2

Factor Graphs and MAP Decoding

XOR

5

OR

OR-OUT
BUDGET

Figure 1.1: Hard constraint factors and their marginal polytopes; the AD3
subproblems (1.20) are projections onto these polytopes. The three factors on
the left represent one-hot XOR, OR, and OR-with-output logical constraints. The
rightmost one is a budget factor, requiring at most B variables to be active.

cators of an acceptance set Sα ⊆ Yα . In other words, θα (.) is of the form:(0,
if yα ∈ Sα ,θα (yα ) :=(1.3)−∞, otherwise.
These factors ensure that any configuration not in the acceptance set will
have zero probability. This has applications in error-correcting decoding(Richardson and Urbanke, 2008), bipartite graph matching (Duchi et al.,2007), computer vision (Nowozin and Lampert, 2009), and various problems
in NLP (Sutton, 2004; Smith and Eisner, 2008; Das et al., 2012). An example
is logic factors (Martins et al., 2011b), which compute logic functions
over binary variables, serving as building blocks for expressing declarative
constraints in first-order logic. Such constraints are very useful to inject
domain knowledge into a problem (Richardson and Domingos, 2006; Changet al., 2008). Figure 1.1 shows examples of logic factors; see Martins (2012)
for how to perform computations with those factors.
Finally, structured factors have log-potential functions with an additional
layer of structure, which allows them to be represented in a compact way.
For example, they can form a chain model, or a tree, or can even have an6AD3 : A Fast Decoder for Structured Prediction*

We

learnedalesson

in

1987

about

volatility

Figure 1.2: Example of a sentence (input) and its dependency parse tree (output
to be predicted); this is a directed spanning tree where each arc (h, m) represent a
syntactic relationships between a head word h and the a modifier word m.

internal factor graph representation2 themselves, such asXXξβ (yβ ),θα (yα ) :=ξi (yi ) +i∈V (α)

(1.4)

β∈Fα

where Fα ⊆ 2V (α) . Since they have compact representations, structured
factors are able to scale to large values of |V (α)|.

1.3Factor Graphs for Natural Language Processing
Many problems in NLP can be cast as structured prediction (Smith, 2011).
In this section, we describe factor graph representations for two concrete
NLP problems: dependency parsing and compressive summarization. Later,in Section 1.7, we will show experimental results for these two tasks.
1.3.1“Turbo” Parsing

Dependency parsing is an important problem in NLP (Kübler et al., 2009).
Given a sentence with L words, to which a special root symbol ∗ isprepended, the goal is to find a directed spanning tree, where each arc
represents a syntactic function, linking a head word to a modifier word.3
For example, in Figure 1.2, three arcs depart from the head word “learned”:
one pointing to the modifier “We” (the subject), another to “lesson” (theobject), and another to “in” (which introduces a prepositional phrase).
The simplest dependency parsing models are arc-factored. In these models,
2. In the literature, structured factors are often not considered as factors on their own,
but instead as subgraphs of a larger graph that includes their internal factorization. Here,we consider structured factors explicitly, abstracting away their internal structure. This
allows to deal with combinatorial structures that are not directly represented as a graphicalmodel, such as probabilistic context-free grammars.
3. This is the definition of nonprojective dependency parsing, the one used throughout
this chapter. An formalism is projective parsing, which in addition constrains the arcs tobe nested. See Kübler et al. (2009) for more details.

1.3

Factor Graphs for Natural Language Processing

7

Figure 1.3: The parts used in our model. First-order models factor over arcs (Eisner, 1996; McDonald et al., 2005), and second-order models include also consecutive
siblings and grandparents (Carreras, 2007). Our parsers add also arbitrary siblings(not necessarily consecutive) and head bigrams, as in Martins et al. (2011b), in
addition to third-order features for grand- and tri-siblings (Koo and Collins, 2010).

one has O(L2 ) scores—one score for every possible arc linking two words—
and the goal is to pick the spanning tree maximizing the sum of thescores in its arcs. This problem can be solved efficiently with an algorithm
for finding maximal spanning trees (Chu and Liu, 1965; Edmonds, 1967;
McDonald et al., 2005). Unfortunately, arc-factored parsers perform poorly,
since they do not capture enough interactions among the dependency arcs;
and extending the model to include larger substructures (e.g. pairs of arcs)
renders the decoding problem NP-hard (McDonald and Satta, 2007).
In Martins et al. (2010b), we introduced the concept of “turbo parser,”which encapsulates several top-performing approximate dependency parsers(Smith and Eisner, 2008; Martins et al., 2009; Koo et al., 2010). The namedesignates parsers that decode factor graphs by ignoring the effects causedby the cycles of the graph.4 These parsers trade off exact decoding by theability to include scores for more complex substructures, resulting on more
expressive models and higher accuracies. Figure 1.3 shows an example of such
substructures (or parts) that constitute a recent third-order parser (Martinset al., 2013). These parts can be represented by a factor graph that mixes
dense, hard constraint, and structured factors, which we next define.
The variable nodes of the factor graph stand for the O(L2 ) possible
dependency arcs linking each pair of words, each associated with a binary
variable. The factors are the following:
A hard-constraint factor, linked to all the variables, imposing that theyjointly define a well-formed tree.
Head automata factors modeling the left and right sequences of consec4. The name stems from “turbo codes,” a class of high-performance error-correcting codes
introduced by Berrou et al. (1993) for which decoding algorithms are equivalent to running
belief propagation in a graph with loops (McEliece et al., 1998).

8

AD3 : A Fast Decoder for Structured Prediction

utive siblings, grandparents, grand-siblings, and tri-siblings. Each of thesestructured factors is a chain model that, for a given head word, assigns ascore for the sequence of modifiers and (eventually) the grandparent. These
factors have internal structure relying on horizontal and vertical Markov
assumptions.
Binary pairwise factors (also called Ising factors) for every possible pair ofsiblings. These are simple dense factors.
A structured factor modeling the sequence of heads, with scores dependingon the heads of consecutive words. This is also a chain model.
We will see in the sequel that a crucial operation to be performed at eachfactor is computing local MAP configurations. For all factors listed above,
this can be done efficiently, as described in Martins et al. (2013).
1.3.2

Compressive Summarization

Our second NLP application is compressive summarization (Almeida andMartins, 2013). We are given a collection of documents about a given topic,
and the goal is to generate a summary with less than B words, where B isa budget. Let N be the total number of sentences in the collection, where
the nth sentence has Ln words. We constrain our summary’s sentences to becompressions of the original sentences, obtained by deleting some words.5
We define one binary variable for every word of every sentence, yieldingLnvectors zn := (zn,` )`=1
. A good summary is typically a trade-off between
three important qualities: conciseness, informativeness, and grammaticality.
This can be made formal by defining the following optimization problem:
maximizeg(z) +NX

hn (zn )n=1

w.r.t. zn ∈ {0, 1}Ln , n = 1, . . . , N
s.t.

Ln
N X
X

zn,` ≤ B,(1.5)

n=1 `=1

where g(z) is a global informativeness score based on how many “concepts”6are covered by the summary z, and the hn (zn ) are local grammaticality
5. This constraint is substantially weaker than that of extractive summarizers, which form
a summary by picking full sentences. Our motivation is to make a better use of the budget,using shorter snippets to accommodate more information.
6. For simplicity, we assume concepts are word bigrams (as in Gillick et al. 2008), but otherrepresentations would be possible, such as phrases or predicate-argument structures.

1.4

LP-MAP Decoding

9

Concept tokens" Kashmir i separ atists"

Concept type

$

Talks

with Kashmir i separ atists began lastSentences$The

leaderBudgetyear ...

of moderate Kashmir i separ atists warned Thursday that ...

Figure 1.4: Components of our compressive summarizer. Factors depicted in blue
belong to the compression model, and promote grammaticality. The logic factors in
red form the coverage component. Finally, the budget factor, in green, is connectedto the word nodes; it ensures that the summary fits the word limit.

scores, computed at sentence level.
Figure 1.4 shows a factor graph representation for this task, where circles represent variables, and rectangles represent factors. We introduce abinary variable for each word in the original sentences; to handle concepts,
we distinguish between concept types (a list of word bigram types that appear frequently in the collection) and concept tokens (occurrences of thosebigrams in the text), and we introduce also binary variables for those. Notethat types and tokens are logically related: a concept type is present in thesummary if at least one concept token is present. This is captured by the
logic factors in Figure 1.4; this part of the graph takes care of the informativeness score g(z). Then, for each sentence in the collection, we introduce a
structured factor which computes a grammaticality score hn (zn ), inspired byprior work in sentence compression (Knight and Marcu, 2000). The sentence
is first parsed, yielding a dependency tree like in Figure 1.2; hn (zn ) is thendefined as a sum of penalties for the arcs deleted in the compression (seeAlmeida and Martins 2013). The internal structure of this factor is given
by a tractable tree-shaped model. Finally, we have a budget factor imposingthat at most B words can be selected, which takes care of conciseness.

1.4

LP-MAP Decoding
We now describe a class of methods for approximate MAP decoding based ona linear programming relaxation of the problem (1.2), known in the literature

10

AD3 : A Fast Decoder for Structured Prediction

as Schlesinger’s linear relaxation (Schlesinger, 1976; Werner, 2007).7
Let us start by representing the log-potential functions in (1.1) in vector
notation, θi := (θi (yi ))yi ∈Yi ∈ R̄|Yi | and θα := (θα (yα ))yα ∈Yα ∈ R̄|Yα | . We
introduce “local” probability distributions over the variables and factors,
which we represent as vectors of the same size as θi and θα :pi ∈ ∆|Yi | , ∀i ∈ V

and qα ∈ ∆|Yα | , ∀α ∈ F,

(1.6)

where ∆K := {u ∈ RK | u ≥ 0, 1 · u = 1} denotes the K-dimensional
probability simplex. We stack these distributions into vectors p and q, withPP
dimensions P := i∈V |Yi | and Q := α∈F |Yα |, respectively. If these local
probability distributions are “valid” marginal probabilities (i.e., marginals
realizable by some global probability distribution P(Y1 , . . . , YM )), then anecessary (but not sufficient) condition is that they are locally consistent. In
other words, they must satisfy the following calibration equations:Xqα (yα ) = pi (yi ),∀yi ∈ Yi , ∀(i, α) ∈ E,
(1.7)
yα ∼yiwhere the notation ∼ means that the summation is over all configurations
yα whose ith element equals yi . Equation (1.7) can be written in vector
notation as Miα qα = pi , ∀(i, α) ∈ E, where we define consistency matrices(
1, if yα ∼ yi
Miα (yi , yα ) =(1.8)
0, otherwise.
The set of locally consistent distributions forms the local polytope:()|Yα | ,
q
∈
∆
∀α
∈
F
α
L(G) = (p, q) ∈ RP +Q.
Miα qα = pi , ∀(i, α) ∈ E(1.9)

We consider the following linear program (the LP-MAP decoding problem):
X
X
LP-MAP:maximizeθ α · qα +θi · pi(1.10)α∈F
i∈V
with respect to (p, q) ∈ L(G).
If the solution (p∗ , q ∗ ) of (1.10) happens to be integral, then each p∗i andqα∗ will be at corners of the simplex, i.e., they will be indicator vectorsof local configurations yi∗ and yα∗ , in which case the output (yi∗ )i∈V isguaranteed to be a solution of the MAP decoding problem (1.2). Under
7. Chapter ?? of the current volume gives a detailed overview on what is known about
this linear relaxation, including some hardness results.

1.4

LP-MAP Decoding

11

certain conditions—for example, when the factor graph G does not havecycles—(1.10) is guaranteed to have integral solutions. In general, however,the LP-MAP decoding problem (1.10) is a relaxation of (1.2). Geometrically,
L(G) is an outer approximation of the marginal polytope, defined as the setof valid marginals (Wainwright and Jordan, 2008).
1.4.1

Dual Decomposition

While any off-the-shelf LP solver can be used for solving (1.10), specializedalgorithms have been designed to exploit the graph structure, achieving
superior performance on several benchmarks (Yanover et al., 2006). An
example is the projected subgradient dual decomposition (PSDD) algorithm,
proposed by Komodakis et al. (2007), which has old roots in optimization(Dantzig and Wolfe, 1960; Everett III, 1963; Guignard and Kim, 1987). As
we will see in Section 1.5, there is a strong affinity between PSDD and themain focus of this chapter, AD3 .
Let us first express (1.10) as a consensus problem. For each edge(i, α) ∈ E, we define a potential function θiα := (θiα (yi ))yi ∈Yi that satP
isfies α∈F (i) θiα = θi ; a trivial choice is θiα = |F (i)|−1 θi , which spreads
the unary potentials evenly across the factors. Since we have a equality constraint pi = Miα qα , (1.10) is equivalent to the following primal formulation:


X
X
θα +
 · qαLP-MAP-P:
maximizeM>iα θiαα∈Fi∈V (α)Pwith respect to p ∈ R ,qα ∈ ∆|Yα | , ∀α ∈ F,

(1.11)

subject to Miα qα = pi , ∀(i, α) ∈ E.
Note that, although the p-variables do not appear in the objective of(1.11), they play a fundamental role through the constraints in the lastline. Indeed, it is this set of constraints that complicate the optimization
problem, which would otherwise be separable into independent subproblems,
one per factor. Introducing Lagrange multipliers λiα := (λiα (yi ))yi ∈Yi forthese equality constraints, we arrive at the following dual formulation:
X
LP-MAP-D:
minimizeg(λ) :=gα (λ)(1.12)
α∈Fwith respect to λ ∈ Λ,
n
o
P
λ
=
0,
∀i
∈
V
is a linear subspace, and eachwhere Λ := λ |iαα∈F (i)12

AD3 : A Fast Decoder for Structured Predictiongα (λ) is the solution of a local subproblem:X
 · qαgα (λ) :=max θα +M>iα (θiα + λiα )qα ∈∆|Yα |=max θα (yα ) +y α ∈ Yα

(1.13)i∈V (α)X(θiα (yi ) + λiα (yi )) .

(1.14)i∈V (α)The last equality is justified by the fact that maximizing a linear objective
over the probability simplex gives the largest component of the score vector.
Note that the local subproblem (1.14) can be solved by a ComputeMAP
procedure, which receives unary potentials ξiα (yi ) := θiα (yi ) + λiα (yi ) andfactor potentials θα (yα ) (eventually structured) and returns the MAP ybα .
Problem (1.12) is often referred to as the master or controller, and each
local subproblem (1.14) as a slave or worker. The master problem (1.12)
can be solved with a projected subgradient algorithm.8 By Danskin’s rule
(Bertsekas, 1999, p. 717), a subgradient of gα is readily given by∂gα (λ)= Miα qbα ,∂λiα∀(i, α) ∈ E;

(1.15)and the projection onto Λ amounts to a centering operation. Putting thesepieces together yields Algorithm 1.1. At each iteration, the algorithm broadcasts the current Lagrange multipliers to all the factors. Each factor adjusts
its internal unary log-potentials (line 6) and invokes the ComputeMap procedure (line 7). The solutions achieved by each factor are then gathered andaveraged (line 10), and the Lagrange multipliers are updated with step sizeηt (line 11).
The two following propositions, proved in Rush and Collins (2012), establish the convergence properties of Algorithm 1.1.
Proposition 1.1 (Convergence rate). If the non-negative step size sequenceP∞(ηt )t∈N is diminishing and nonsummable (lim ηt = 0 and
t=1 ηt = ∞),∗then Algorithm 1.1 converges to the solution λ of LP-MAP-D (1.12).
Furthermore, after T = O(1/2 ) iterations, we have g(λ(T ) ) − g(λ∗ ) ≤ .
Proposition 1.2 (Certificate of optimality). If, at some iteration of Algorithm 1.1, all the local subproblems are in agreement ( i.e., if qbiα = pi afterline 10, for all i ∈ V ), then: (i) λ is a solution of LP-MAP-D (1.12); (ii) p
is binary-valued and a solution of both LP-MAP-P and MAP.
8. A slightly different formulation is presented by Sontag et al. (2011) which yields a
subgradient algorithm with no projection.

1.5

Alternating Directions Dual Decomposition (AD3 )13

Algorithm 1.1 PSDD Algorithm (Komodakis et al., 2007)
1: input: graph G, parameters θ, maximum number of iterations T , stepsizes (ηt )T
t=1
P
2: for each (i, α) ∈ E, choose θiα such thatα∈F (i) θiα = θi
3: initialize λ = 0
4: for t = 1 to T do
5:for each factor α ∈ F do
6:
set unary log-potentials ξiα := P
θiα + λiα , for i ∈ V (α)
7:set qbα := ComputeMap(θα + i∈V (α) M>iα ξiα )8:
set qbiα := Miα qbα , for i ∈ V (α)
9:end forP
10:compute average pi := |F (i)|−1 α∈F (i) qbiα for each i ∈ V
11:update λiα := λiα − ηt (qbiα − pi ) for each (i, α) ∈ E
12: end for
13: output: dual variable λ and upper bound g(λ)

Propositions 1.1–1.2 imply that, if the LP-MAP relaxation is tight, then
Algorithm 1.1 will eventually yield the exact MAP configuration alongwith a certificate of optimality. Unfortunately, in large graphs with many
overlapping factors, it has been observed that convergence can be quite
slow in practice (Martins et al., 2011b). This is not surprising, given that it
attempts to reach a consensus among all overlapping components; the larger
this number, the harder it is to achieve consensus. We describe in the next
section another LP-MAP decoder (AD3 ) with a faster convergence rate.

1.5

Alternating Directions Dual Decomposition (AD3 )AD3 obviates some of the weaknesses of PSDD by replacing the subgradientmethod with the alternating directions method of multipliers (ADMM).9
Before going into a formal derivation, let us go back to the PSDD algorithm to pinpoint the crux of their weaknesses. It resides on two aspects:
1. The dual objective function g(λ) is non-smooth. This is circumvented byusing “subgradients” rather than “gradients.” Yet, non-smooth optimization
lacks some of the good properties of its smooth counterpart. Ensuring
convergence requires diminishing step sizes, leading to slow convergence
rates such as the O(1/2 ) iteration bound stated in Proposition 1.1.
2. Consensus is promoted solely by the Lagrange multipliers (see line 6 inAlgorithm 1.1). These can be regarded as “price adjustments” that are
made at each iteration and lead to a reallocation of resources. However,
9. See Boyd et al. (2011, Section 3.1) for a historical perspective on ADMM as a faster
alternative to subgradient methods.

14

AD3 : A Fast Decoder for Structured Prediction

no “memory” exists about past allocations or adjustments, so the workers
never know how far they are from consensus. One may suspect that a smarteruse of these quantities may accelerate convergence.
The first of these aspects has been addressed by the accelerated dual
decomposition method of Jojic et al. (2010), which improves the iteration
bound to O(1/); we discuss that work further in Section 1.8. We will see thatAD3 also yields a O(1/) iteration bound with some additional advantages.
The second aspect is addressed by AD3 by broadcasting the current global
solution in addition to the Lagrange multipliers, allowing the workers toregularize their subproblems toward that solution.
1.5.1

Augmented Lagrangians, ADMM, and AD3

Augmented Lagrangian methods have a rich and long-standing history in
optimization (Hestenes, 1969; Powell, 1969; Bertsekas, 1999, Section 4.2).
Given an optimization problem with equality constraints (such as the onein (1.11)), the augmented Lagrangian function is the sum of the Lagrangianwith a quadratic constraint violation penalty. For (1.11), it is


X
X
X
θα +
 · qα −Lη (q, p, λ) =M>
λiα · piiα (θiα + λiα )α∈Fi∈V (α)

η X−
kMiα qα − pi k2 ,2(i,α)∈E(1.16)(i,α)∈E

where the scalar η > 0 controls the weight of the penalty.
The most famous augmented Lagrangian method is the method of multipliers, which alternates between maximizing the augmented Lagrangianfunction with respect to the primal variables (in our problem, a joint maximization of Lη (q, p, λ) w.r.t. q and p), followed by an update of the Lagrange multipliers. Unfortunately, the quadratic term in (1.16) couples together the variables q and p, making their joint maximization unappealing.
ADMM (Glowinski and Marroco, 1975; Gabay and Mercier, 1976) avoids
this shortcoming, by replacing this joint maximization by a single block
Gauss-Seidel-type step. This yields the following updates (where we have

1.5

Alternating Directions Dual Decomposition (AD3 )15

defined the product of simplices ∆×
F :=Broadcast:

Q

α∈F ∆

|Yα | ):q (t+1) := argmax Lη (q, p(t) , λ(t) ),(1.17)q∈∆×F

Gather:Multiplier update:p(t+1) := argmax Lη (q (t+1) , p, λ(t) ),(1.18)
p∈RP


(t+1)
(t)
(t)
λiα := λiα − η Miα qα(t) − pi , ∀(i, α) ∈ E.
(1.19)

We next analyze the broadcast and gather steps, and prove a proposition
about the multiplier update.
The maximization (1.17) can be carried out in parallel at
the factors, as in PSDD. The only difference is that, instead of a local MAP
computation, each worker needs to solve a quadratic program of the form:


X
η X
M>
(θiα + λiα ) ·qα −max θα +kMiα qα −pi k2 . (1.20)iα2qα ∈∆|Yα |Broadcast step.

i∈V (α)i∈V (α)The subproblem (1.20) differs from the linear subproblem (1.13)–(1.14)
in the PSDD algorithm by including an Euclidean penalty term, which
penalizes deviations from the global consensus. In Section 1.6, we will giveefficient procedures to solve these local subproblems.
The solution of (1.18) has a closed form. (1.18) is separable
into independent optimizations for each i ∈ V ; defining qiα := Miα qα ,

X 
η
(t+1)
:= arg minpi
λiα · pi + kqiα − pi k2
2
pi ∈R|Yi |α∈F (i)X= |F (i)|−1
qiα − η −1 λiαGather step.

α∈F (i)=−1|F (i)|

Xqiα .

(1.21)α∈F (i)

The equality in the last line is due to the following proposition:
Proposition 1.3. The sequence λ(1) , λ(2) , . . . produced by (1.17)–(1.19) isdual feasible, i.e., we have λ(t) ∈ Λ for every t, with Λ as in (1.12).
P
P
P
(t+1)
(t)
(t+1)
(t+1)
Proof. We have α∈F (i) λiα = α∈F (i) λiα −η( α∈F (i) qiα −|F (i)|pi
)=
P
P
P
(t)
(t+1)
(t+1)
(t)
− α∈F (i) (qiα − η −1 λiα )) = 0.
α∈F (i) λiα − η( α∈F (i) qiαAssembling all these pieces together leads to AD3 (Algorithm 1.2). Notice16

AD3 : A Fast Decoder for Structured Prediction

Algorithm 1.2 Alternating Directions Dual Decomposition (AD3 )input: graph G, parameters θ, penalty constant η
initialize p uniformly (i.e., pi (yi ) = 1/|Yi |, ∀i ∈ V, yi ∈ Yi )initialize λ = 0
repeatfor each factor α ∈ F do
set unary log-potentials
 ξiαP:= θiα + λiα , for i ∈ V (α) 7:set qbα := SolveQP θα + i∈V (α) M>iα ξiα , (pi )i∈V (α) , the problem (1.20)
8:
set qbiα := Miα qbα , for i ∈ V (α)
9:end forP
10:compute average pi := |F (i)|−1 α∈F (i) qbiα for each i ∈ V
11:update λiα := λiα − η (qbiα − pi ) for each (i, α) ∈ E
12: until convergence
13: output: primal variables p and q, dual variable λ, upper bound g(λ)

1:
2:
3:
4:
5:
6:

that AD3 retains the modular structure of PSDD (Algorithm 1.1). The key
difference is that AD3 also broadcasts the current global solution to theworkers, allowing them to regularize their subproblems toward that solution,
thus speeding up the consensus. This is embodied in the procedure SolveQP(line 7), which replaces ComputeMAP of Algorithm 1.1.
1.5.2

Convergence Analysis

Convergence of AD3 follows directly from the general convergence propertiesof ADMM. Unlike PSDD (Algorithm 1.1), convergence is ensured with afixed step size η, therefore no annealing is required.
Proposition 1.4 (Convergence). Let (q (t) , p(t) , λ(t) )t be the sequence of
iterates produced by Algorithm 1.2. Then the following holds:
1. The primal sequence (p(t) , q (t) )t∈N converges to a solution of the LPMAP-P (1.11); as a consequence, primal feasibility of LP-MAP-P is(t)(t)
achieved in the limit, i.e., kMiα qα − pi k → 0, ∀(i, α) ∈ E;
2. The dual sequence (λ(t) )t∈N converges to a solution of LP-MAP-D (1.12);
moreover, this sequence is always dual feasible, i.e., it is contained in Λ.
Proof. 1 and the first part of 2 are general properties of ADMM (Glowinski
and Le Tallec, 1989, Theorem 4.2). The second part of statement 2 stems
from Proposition 1.3.
The next proposition states the O(1/) iteration bound of AD3 , which is
better than the O(1/2 ) bound of PSDD.
Proposition 1.5 (Convergence rate). Let λ∗ be a solution of LP-MAPP
D (1.12), λ̄T := T1 Tt=1 λ(t) be the “averaged” Lagrange multipliers after T

1.5

Alternating Directions Dual Decomposition (AD3 )17

iterations of AD3 , and g(λ̄T ) the corresponding estimate of the dual objective(an upper bound). Then, g(λ̄T ) − g(λ∗ ) ≤  after T ≤ C/ iterations, where
C ≤

5η
5
|E| + kλ∗ k2 .
22η(1.22)

Proof. A detailed proof is presented in Martins et al. (2012), adapting a
recent result of Wang and Banerjee (2012) concerning convergence of ADMM
in a variational inequality setting.
As expected, the bound (1.22) increases with the number of overlapping
variables, quantified by the number of edges |E|, and the magnitude of the
optimal dual vector λ∗ . Note that if there is a good estimate of kλ∗ k, then
(1.22) can be used to choose a step size η that minimizes the bound.10 The
optimal stepsize is η = kλ∗ k × |E|−1/2 , which would lead to T ≤ 5−1 |E|1/2 .
1.5.3

Other Details and Extensions

Since the AD3 iterates are dual feasible, it isalso possible to check the conditions in Proposition 1.2 to obtain optimality
certificates, as in PSDD. Moreover, even when the LP-MAP relaxation is nottight, AD3 can provide stopping conditions by keeping track of primal anddual residuals (an important advantage over PSDD), as described in Boyd(t)et al. (2011). The primal residual rP is the amount by which the agreement
constraints are violated,
P
(t)
(t) 2
(i,α)∈E kMiα qα − pi k
(t)
P
rP =
∈ [0, 1].
(1.23)(i,α)∈E |Yi |Primal and dual residuals.

(t)

The dual residual rD is the amount by which a dual optimality conditionis violated,P(t)(t−1) 2k(i,α)∈E kpi − pi
(t)
P
rD =
∈ [0, 1].
(1.24)(i,α)∈E |Yi |We adopt as stopping criterion that these two residuals fall below 10−6 .
The next proposition
states that convergence may still hold, even if the local subproblems are
only solved approximately. The importance of this result will be clear in
Approximate solutions of the local subproblems.

10. Although Proposition 1.4 guarantees convergence for any choice of η, this parameter
may strongly impact the behavior of the algorithm. In our experiments, we dynamically adjust η in earlier iterations using the heuristic described in Boyd et al. (2011, Section 3.4.1).

18

AD3 : A Fast Decoder for Structured Prediction

Section 1.6.1, where we describe a general iterative algorithm for solving
the local quadratic subproblems. Essentially, Proposition 1.6 allows thesesubproblems to be solved numerically up to some accuracy without compromising global convergence, as long as the accuracy of the solutions improves
sufficiently fast over AD3 iterations.
Proposition 1.6 (Eckstein and Bertsekas, 1992). For every iteration t, let
qb(t) contain the exact solutions of (1.20), and q̃ (t) those produced by anapproximate algorithm. Then Proposition 1.4 still holds, provided that thePb(t) − q̃ (t) k < ∞.
sequence of errors is summable, i.e., ∞t=1 kqIn practice, considerable speed-ups can beachieved by caching the subproblems, following a strategy proposed for
PSDD by Koo et al. (2010). After a few iterations, many variables pi reach
(t)
(t+1)
a consensus (i.e., pi = qiα , ∀α ∈ F (i)) and enter an idle state: they areleft unchanged by the p-update (line 10), and so do the Lagrange variables(t+1)
λiα (line 11). If at iteration t all variables in a subproblem at factor α are
(t+1)
(t)
idle, then qα= qα , hence the corresponding subproblem does not need
to be solved. Typically, many variables and subproblems enter this idle state
after the first few rounds. We will show the practical benefits of caching in
the experimental section (Section 1.7.1, Figure 1.5).
Caching the subproblems.

Recall that AD3 , as just described, solves the LP-MAP relaxation, which is not only always tight. Daset al. (2012) propose to wrap AD3 into a branch-and-bound search procedure
to find the exact MAP, using the property that the optimal objective valueof LP-MAP is an upper bound of MAP, and that AD3 , along its execution,
keeps track of a sequence of feasible dual points (as guaranteed by Proposition 1.4, item 2), building tighter and tighter upper bounds. Although thisprocedure has worst-case exponential runtime, it was found empirically quite
effective in problems for which the relaxations are near-exact.
Exact decoding with branch-and-bound.

1.6

Local Subproblems in AD3
We now turn our attention to the AD3 local subproblems (1.20). In many
important cases, these QPs can be solved efficiently. Some examples are:
Ising factors (Martins et al., 2011a), which can be solved in constant time.
The logic constraint factors in Section 1.2.3, useful as building blocks
for expressing soft and hard constraints in first-order logic (Martins et al.,

1.6

Local Subproblems in AD3

19

2011a); these can be solved in linear time with respect to the number ofvariables linked to the factor.11
Budget and knapsack factors, which are important for dealing withcardinality-based potentials, or to promote diversity (Tarlow et al., 2010;
Almeida and Martins, 2013). Runtime is again linear in the size of the factor.
Parity-check factors (Barman et al., 2011), used in low-density parity checkdecoding. Runtime is O(L log L), where L is the number of parity check bits.
In fact, for hard-constraint factors, the AD3 subproblems have a nice geometric interpretation as an Euclidean projection onto the marginal polytopeof the factor (as illustrated in Figure 1.1). In this section, we complement
these results with a general active-set procedure for solving the AD3 subproblems for arbitrary factors, the only requirement being a black-box MAP
solver—the same as the PSDD algorithm. This makes AD3 applicable to awide range of problems. In particular, it makes possible to handle structured
factors (Section 1.2.3), by invoking specialized MAP decoders.12
1.6.1

Active Set Method

Our active set method is based on Nocedal and Wright (1999, Section 16.4);
it is an iterative algorithm that addresses the AD3 subproblems (1.20) bysolving a sequence of linear problems. By subtracting a constant, re-scaling,
and flipping signs, (1.20) can be written more compactly as
minimizewith respect to1
kMqα − ak2 − b · qα2qα ∈ R|Yα |subject to 1 · qα = 1,

(1.25)qα ≥ 0,where a := (ai )i∈V (α) , with ai := pi + η −1 (θiα + λiα ); b := η −1 θα ; andP
M := (Miα )i∈V (α) denotes a matrix with i |Yi | rows and |Yα | columns.
The next crucial proposition (proved in Martins et al. 2012) states thatproblem (1.25) always admits a sparse solution.
Proposition 1.7. Problem (1.25) admits a solution qα∗ ∈ R|Yα | with at most
11. This is also the asymptotic complexity for computing the MAP for those factors.
While the complexities reported by Martins et al. (2011a) have an extra logarithmic term,in all cases the runtime can drop to linear by using linear-time selection algorithms. We
refer the interested reader to Almeida and Martins (2013) for details.
12. Past work (Martins et al., 2011a) suggested another strategy (graph binarization) todeal with dense and structured factors. However, this is outperformed, in practice, by theactive set method we next present (see Martins 2012, Figure 6.3, for a comparison).

20

AD3 : A Fast Decoder for Structured Predictioni∈V (α) |Yi | − V (α) + 1 non-zero components.

P

The fact that the solution lies in a low dimensional subspace makes
active set methods appealing, since they only keep track of an active setof variables, that is, the non-zero components of qα . Proposition 1.7 tells us
Pthat such an algorithm only needs to maintain at most O( i |Yi |) elementsin the active set—note the additive, rather than multiplicative, dependency
on the number of values of the variables. Our active set method seeks to
identify the low-dimensional support of the solution qα∗ , by generating sparse(1) (2)
iterates qα , qα , . . ., while it maintains a working set W ⊆ Yα with theinequality constraints of (1.25) that are inactive along the way (i.e., thoseyα for which qα (yα ) > 0 holds strictly). Each iteration adds or removes
elements from the working set while it monotonically decreases the objectiveof Equation (1.25).13
Let τ and µ be dual variables associatedwith the equality and inequality constraints of (1.25), respectively. The
Lagrangian function is

Lagrangian and KKT conditions.

1
L(qα , τ, µ) = kMqα − ak2 − b · qα − τ (1 − 1 · qα ) − µ · qα .
2(1.26)

This gives rise to the following Karush-Kuhn-Tucker (KKT) conditions:
M> (a − Mqα ) + b = τ 1 − µ (∇qα L = 0)
1 · qα = 1, qα ≥ 0, µ ≥ 0 (Primal/dual feasibility)µ · qα = 0 (Complementary slackness).

(1.27)(1.28)(1.29)The method works at follows. At each iteration s, it first checks if the current(s)iterate qα is a subspace minimizer, i.e., if it optimizes the objective of (1.25)
in the sparse subspace defined by the working set W , {qα ∈ ∆|Yα | | qα (yα ) =0, ∀yα ∈/ W }. This check can be made by first solving a relaxation where theinequality constraints are ignored. Since in this subspace the components ofqα not in W will be zeros, one can simply delete those entries from qα andb and the corresponding columns in M; we use a horizontal bar to denote
13. Our description differs from Nocedal and Wright (1999) in which their working set
contains active constraints rather than the inactive ones. In our case, most constraints areactive for the optimal qα∗ , therefore it is appealing to store the ones that are not.

1.6

Local Subproblems in AD3

21

these truncated R|W | -vectors. The problem can be written as:
minimizewith respect to1
kM̄q̄α − ak2 − b̄ · q̄α2q̄α ∈ R|W |subject to 1 · q̄α = 1.

(1.30)The solution of this equality-constrained QP can be found by solving asystem of KKT equations:14
"
#"
# "
#
M̄> M̄ 1q̄αM̄> a + b̄=.
(1.31)1>0τ
1The solution of (1.31) will give (qbα , τb), where qbα ∈ R|Yα | is padded back(s)with zeros. If it happens that qbα = qα , then this means that the current
(s)
(s+1)
iterate qα is a subspace minimizer; otherwise a new iterate qα
will becomputed. We next discuss these two events.
(s)

Case 1: qα

is a subspace minimizer.

If this happens, then it may be(s)
the case that qα is the optimal solution of (1.25). By looking at the KKT(s)conditions (1.27)–(1.29), we have that this will happen iff M> (a − Mqα ) +b ≤ τ (s) 1. Define w := a − Mqα . The condition above is equivalent tomax b(yα ) +y α ∈ YαXwi (yi ) ≤ τ (s) .

(1.32)i∈V (α)It turns out that this maximization is precisely a local MAP decoding
problem, given a vector of unary potentials w and factor potentials b. Thus,
the maximizer ybα can be computed via the ComputeMAP procedure,
P
which we assume available. If b(ybα ) + i∈V (α) wi (ybi ) ≤ τ (s) , then the KKT
conditions are satisfied and we are done. Otherwise, ybα indicates the mostviolated condition; we will add it to the active set W , and proceed.
(s)Case 2: qα is not a subspace minimizer.

If this happens, then we compute(s+1)
a new iterate qα
by keeping searching in the same subspace. We havealready solved a relaxation in (1.30). If we have qbα (yα ) ≥ 0 for all yα ∈ W ,(s+1):= qbα and proceed.
then the relaxation is tight, so we just set qα
Otherwise, we move as much as possible in the direction of qbα while keeping
14. Note that this is a low-dimensional problem, since we are working in a sparse working
set. By caching the inverse of the matrix in the left-hand side, this system can be solvedin time O(|W |2 ) at each iteration. See Martins et al. (2012) for further details.

22

AD3 : A Fast Decoder for Structured Prediction
(s+1)

(s)

:= (1 − β)qα + β qbα —as described in Nocedal
feasibility, by defining qα
and Wright (1999), the value of β ∈ [0, 1] can be computed in closed form:)((s)
qα (yα )β = min 1,
min.
(1.33)(s)(s)
yα ∈W : qα (yα )>qbα (yα ) qα (yα ) − qbα (yα )If β < 1, this update will have the effect of making one of the constraints(s+1)
active, by zeroing out qα(yα ) for the minimizing yα above. This so-called“blocking constraint” is thus be removed from the working set W .
Algorithm 1.3 describes the complete procedure. The active set W is
initialized arbitrarily: a strategy that works well in practice is, in the firstAD3 iteration, initialize W := {ybα }, where ybα is the MAP configuration
given log-potentials a and b; and in subsequent AD3 iterations, warm-start
W with the support of the solution obtained in the previous iteration.
Each iteration of Algorithm 1.3 improves the objective of (1.25), and thealgorithm is guaranteed to stop after a finite number of steps (Nocedal andWright, 1999, Theorem 16.5). In practice, since it is run as a subroutine of
AD3 , Algorithm 1.3 does not need to be run to optimality, which is convenient in early iterations of AD3 (this is supported by Proposition 1.6). The
ability to warm-start with the solution from the previous round is very useful in practice: we have observed that, thanks to this warm-starting strategy,
very few inner iterations are typically necessary for the correct active set tobe identified. We will see some empirical evidence in Section 1.7.1.

1.7

Experiments
We next provide empirical results using AD3 for the NLP applications
described in Section 1.3. We refer the interested reader to Martins et al.
(2012) for a broader empirical evaluation in other tasks and datasets.
1.7.1

Turbo Parsing

We applied AD3 to multilingual dependency parsing, using third-ordermodels and the factor graph representation described in Section 1.3.1.15
For English, we used two datasets: English-I was derived from the Penn
Treebank (Marcus et al., 1993), converted to a dependency treebank by
applying the head rules of Yamada and Matsumoto (2003). For this dataset,
15. The resulting parser is released as free software under the name TurboParser 2.1,
and available for download at http://www.ark.cs.cmu.edu/TurboParser.

1.7

Experiments

23

Algorithm 1.3 Active Set Algorithm for Solving a General AD3 Subproblem(0)

1: input: Parameters a, b, M, starting point qα(0)
2: initialize W (0) as the support of qα
3: for s = 0, 1, 2, . . . do
4:solve the KKT system and obtain qbα and τb (Eq. 1.31)(s)
5:
if qbα = qα then6:
compute w := a − Mqbαbα via eybα = ComputeMAP(b + M> w)
7:obtain the P
tighter constraint ybα ) + i∈V (α) wi (b8:if b(yyi ) ≤ τb then9:
return solution qbα
10:
else
bα }
11:
add the most violated constraint to the active set: W (s+1) := W (s) ∪ {y12:
end if
13:
else
14:
compute the interpolation constant β as in (1.33)(s+1):= (1 − β)qα(s) + β qbα15:
set qα16:
if if β < 1 thenbα in (1.33)
17:
pick the blocking constraint ybα from the active set: W (s+1) := W (s) \ {ybα }18:remove y19:
end if20:
end if
21: end forbα
22: output: q

the resulting dependencies are all projective—i.e., all the dependency arcs
are nested (see footnote 3). English-II, on the other hand, contains nonprojective dependencies and is the dataset used in the CoNLL 2008 sharedtask (Surdeanu et al., 2008). Non-projective dependencies are particularly
appropriate for languages with a more flexible word order, such as Czech,
Dutch, and German; we report here results for those languages using the
CoNLL-X datasets (Buchholz and Marsi, 2006) with the standard splits.16
For each language, we trained linear models using various features decomposing over the parts in Figure 1.3, depending on words, part-of-speechtags, and arc direction and length. To ensure valid parse trees at test time,
we rounded fractional solutions as in Martins et al. (2009)—yet, solutions
were integral ≈ 95% of the time. Figure 1.5 shows average runtimes of AD3
and PSDD on this task, as a function of the sentence length. Clearly, AD3
scales better, even though it needs to solve more involved local subproblems.
It turns out that the caching and warm-starting procedures are crucial inachieving these runtimes, as illustrated in the right part of the figure.
Table 1.2 shows results for several languages, comparing accuracies andspeeds with those of state-of-the-art parsers, including projective parsers
16. Experiments with more languages and baselines are reported in Martins et al. (2013).

AD3 : A Fast Decoder for Structured Prediction

1000

0.20

# oracle calls (normalized)

AD3
Subgrad.
average runtime (sec.)

24

0.15

0.10

0.05

0.00
0

10

20
30
sentence length (words)

40

50

800

AD3 (full)
Subgrad. (full)

600
400
200
00

200

400

600

800 1000 1200 1400 1600 1800
# iterations

Figure 1.5: Left: averaged runtimes in the English-I dev-set as a function of thesentence length. For PSDD, we chose for each sentence the most favorable stepsize in{0.001, 0.01, 0.1, 1}. Right: number of calls to ComputeMAP for AD3 and PSDD,
as a function of the number of iterations (the number of calls is normalized by
dividing by the number of factors). In PSDD, this number would equal the numberof iterations if there was no caching (black line); in AD3 it would be even higher,
since ComputeMAP is called multiple times in the active set algorithm. Yet, bothalgorithms make significantly fewer calls. Remarkably, after just a few iterations,the number of calls made by AD3 and PSDD is comparable, as the number of active
set iterations is quickly amortized during the execution of AD3 .

such as Rush and Petrov (2012) and Zhang and McDonald (2012). For
English-I, these parsers are in advantage, since they constrain their predicted
trees to be projective and therefore easier to decode. Yet, even in this dataset,
our parser’s accuracy does not lag behind these strong competitors, being
faster than the system of Zhang and McDonald (2012) based on beam
search; but considerable slower than the highly optimized vine cascade
approach of Rush and Petrov (2012), which permits exact decoding withdynamic programming. For the other four datasets, TurboParser achieved
the best reported scores, with speeds that are the highest reported among
higher-order non-projective parsers. More details about these experiments
are presented in Martins et al. (2013).
1.7.2

Summarization

Our second task is compressive summarization, where we applied AD3 tothe factor graph in Section 1.3.2. The model was trained in a multi-task
setting, as described in Almeida and Martins (2013), leveraging datasetsfor compressive summarization (Berg-Kirkpatrick et al., 2011), manual abstracts from DUC/TAC tasks, and a dataset collected by Woodsend andLapata (2011) containing 4,481 sentence pairs from the English and Simple
English Wikipedias. Evaluation is on the non-update portion of the TAC2008 dataset, containing 48 multi-document summarization problems; eachprovides 10 related news articles as input, and asks for a summary with up
to 100 words, which is evaluated against four manually written abstracts.

1.8

Related Work

25

English-I
English-II
Dutch
German
Czech

AD3

K+ 10

M+ 11

RP12

ZM12

93.07/735
93.22/785
86.19/599
92.41/965
90.32/501

92.46/112
92.57/131
85.81/121

92.53/66
92.68/–
85.53/–
91.89/–
89.46/–

92.7–/4,460∗

93.06/220

90.8–/2,880

91.35/–

Table 1.2: Dependency parsing results for different datasets. Reported are unlabeled attachment scores ignoring punctuation (left), and parsing speeds in tokens
per second (right). K+ 10 is Koo et al. (2010); M+ 11 is Martins et al. (2011b); RP12
is Rush and Petrov (2012); ZM12 is Zhang and McDonald (2012). Our speeds include the time necessary for pruning, evaluating features, and decoding, as measured
on a Intel Core i7 processor @3.4 GHz. The others are speeds reported in the cited
papers, converted to tokens per second. The RP12 results on English I, marked withan asterisk, are not directly comparable, since a different dependency conversion
scheme was used (see Martins et al. 2013 for details).

We applied a simple rounding procedure to obtain valid summaries fromfractional LP-MAP solutions; see Almeida and Martins (2013) for details.
Table 1.3 summarizes the results. The three leftmost columns refer tostrong baselines: ICSI-1, the best performing system in the TAC-2008 evaluation (which is extractive); and two recent compressive summarizers (BergKirkpatrick et al., 2011; Woodsend and Lapata, 2012). All these systems use
off-the-shelf ILP solvers. The remaining columns show the results achievedby our implementation of a pure extractive system and a compressive summarizer, decoded with GLPK (the ILP solver used by Berg-Kirkpatrick et al.
2011) and AD3 . The ROUGE scores show that the compressive summarizers yield considerable benefits in content coverage over extractive systems,
confirming previous findings (Berg-Kirkpatrick et al., 2011). Our gains withrespect to the compressive baselines come from our multi-task training procedure. Regarding the runtimes, we see that AD3 is orders of magnitude
faster than the (exact) ILP solver, with a similar accuracy level; and it iscompetitive with the speed of an extractive summarizer. To our knowledge,
this is the first time a compressive summarizer achieves such a favorable
accuracy/speed tradeoff. Figure 1.6 shows an example summary.

1.8

Related WorkA few related methods have appeared in the literature after our earlier workin AD3 (Martins et al., 2010a, 2011a).

26

AD3 : A Fast Decoder for Structured Prediction

ICSI-1

BGK’11WL’12

Extr., ILP

Comp., ILP

Comp., AD3

11.03/–

11.71/–

11.37/–

11.16/0.265

12.40/10.394

12.30/0.406

Table 1.3: Results for compressive summarization. Shown are ROUGE-2 recall
scores (Lin, 2004) and averaged runtimes (in seconds) to solve a summarization
problem in TAC-2008. The three leftmost baselines are Gillick et al. (2008); BergKirkpatrick et al. (2011); Woodsend and Lapata (2012). The remaining columns
are our implementation of ILP-based extractive and compressive systems (decodedwith GLPK) and our compressive system decoded with AD3 .
Japan dispatched four military ships to help Russia rescue seven crew members aboard a small
submarine trapped on the seabed in the Far East. The Russian Pacific Fleet said the crew had
120 hours of oxygen reserves on board when the submarine submerged at midday Thursday (2300
GMT Wednesday) off the Kamchatka peninsula, the stretch of Far Eastern Russia facing theBering Sea. The submarine, used in rescue, research and intelligence-gathering missions, became
stuck at the bottom of the Bay of Berezovaya off Russia’s Far East coast when its propeller wascaught in a fishing net. The Russian submarine had been tending an underwater antenna mounted
to the sea floor when it became snagged on a wire helping to stabilize a ventilation cable attachedto the antenna. Rescue crews lowered a British remote-controlled underwater vehicle to a Russianmini-submarine trapped deep under the Pacific Ocean, hoping to free the vessel and its seventrapped crewmen before their air supply ran out.

Figure 1.6: Example summary from our system. Removed text is grayed out.

Meshi and Globerson (2011) also applied ADMM to LP-MAP decoding, although addressing the dual rather than the primal. Yedidia et al.
(2011) proposed a divide-and-concur algorithm for low-density parity check(LDPC) decoding, which resembles a non-convex version of AD3 . Barman
et al. (2011) proposed an algorithm analogous to AD3 for the same LDPC
decoding problem; their subproblems correspond to projections onto theparity polytope, for which they have derived an efficient algorithm. Morerecently, Fu et al. (2013) proposed a Bethe-ADMM procedure resembling
AD3 , but with a variant of ADMM that makes the subproblems become
local marginal computations.
A different strategy was proposed by Jojic et al. (2010) to overcome
the limitations of the PSDD algorithm pointed out in Section 1.5. They
also achieve a O(1/) iteration bound by smoothening the objective of(1.12) with an “entropic” perturbation (controlled by a “temperature”
parameter), and applying an accelerated gradient method (Nesterov, 2005).
An advantage is that the local subproblems become marginal computations,which are formally simpler than our QPs (1.25). However, there are two
drawbacks: first, they need to operate at near-zero temperatures, whichleads to numerical instabilities in some structured factors (the O(1/) bound1.9

Conclusions

27

requires setting the temperature to O()); second, the solution of the local
subproblems is always dense, which precludes the benefits of caching.

1.9

Conclusions
We introduced AD3 , an LP-MAP decoder based on ADMM. AD3 enjoys themodularity of dual decomposition methods, and achieves faster consensus
than subgradient algorithms, both theoretically (with its O(1/) iteration
bound) and in practice.
AD3 can handle hard constraint factors, such as those arising from statements in first-order logic and budget constraints, which are typical in NLP
and IR applications. For dense and structured factors, we introduced an active set method for solving the AD3 subproblems, which requires only a local
MAP decoder as a black-box. We have shown the effectiveness of AD3 in
two important NLP applications, dependency parsing and summarization.

Acknowledgements
I would like to thank Noah Smith, Mário Figueiredo, Eric Xing, Pedro
Aguiar, and Miguel Almeida. This work was partially supported by the
EU/FEDER programme, QREN/POR Lisboa (Portugal), under the Intelligo project (contract 2012/24803), and by a FCT grant PTDC/EEISII/2312/2012.

1.10

References
M. B. Almeida and A. F. T. Martins. Fast and robust compressive summarization
with dual decomposition and multi-task learning. In Proc. of the Annual Meetingof the Association for Computational Linguistics, 2013.
S. Barman, X. Liu, S. Draper, and B. Recht. Decomposition methods for large scale
LP decoding. In 49th Annual Allerton Conference on Communication, Control,and Computing, pages 253–260. IEEE, 2011.
T. Berg-Kirkpatrick, D. Gillick, and D. Klein. Jointly learning to extract andcompress. In Proc. of Annual Meeting of the Association for Computational
Linguistics, 2011.
C. Berrou, A. Glavieux, and P. Thitimajshima. Near Shannon limit error-correcting
coding and decoding. In Proc. of International Conference on Communications,volume 93, pages 1064–1070, 1993.
D. Bertsekas. Nonlinear Programming. Athena Scientific, 2nd edition, 1999.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein. Distributed Optimization

28

AD3 : A Fast Decoder for Structured Predictionand Statistical Learning via the Alternating Direction Method of Multipliers. Now
Publishers, 2011.
S. Buchholz and E. Marsi. CoNLL-X shared task on multilingual dependency
parsing. In International Conference on Natural Language Learning, 2006.
X. Carreras. Experiments with a higher-order projective dependency parser. In
International Conference on Natural Language Learning, 2007.
M. Chang, L. Ratinov, and D. Roth. Constraints as prior knowledge. In International Conference of Machine Learning: Workshop on Prior Knowledge for Text
and Language Processing, July 2008.
Y. J. Chu and T. H. Liu. On the shortest arborescence of a directed graph. Science
Sinica, 14:1396–1400, 1965.
G. Dantzig and P. Wolfe. Decomposition principle for linear programs. Operations
Research, 8(1):101–111, 1960.
D. Das, A. Martins, and N. Smith. An exact dual decomposition algorithm forshallow semantic parsing with constraints. In Proc. of First Joint Conference on
Lexical and Computational Semantics (*SEM), 2012.
J. Duchi, D. Tarlow, G. Elidan, and D. Koller. Using combinatorial optimization
within max-product belief propagation. Advances in Neural Information Processing Systems, 19, 2007.
J. Eckstein and D. Bertsekas. On the Douglas-Rachford splitting method andthe proximal point algorithm for maximal monotone operators. Mathematical
Programming, 55(1):293–318, 1992.
J. Edmonds. Optimum branchings. Journal of Research of the National Bureau ofStandards, 71B:233–240, 1967.
J. Eisner. Three new probabilistic models for dependency parsing: An exploration.
In Proc. of International Conference on Computational Linguistics, pages 340–
345, 1996.
H. Everett III. Generalized Lagrange multiplier method for solving problems of
optimum allocation of resources. Operations Research, 11(3):399–417, 1963.
Q. Fu, H. Wang, and A. Banerjee. Bethe-ADMM for tree decomposition based
parallel MAP inference. In Proc. of Uncertainty in Artificial Intelligence, 2013.
D. Gabay and B. Mercier. A dual algorithm for the solution of nonlinear variational
problems via finite element approximation. Computers and Mathematics with
Applications, 2(1):17–40, 1976.
D. Gillick, B. Favre, and D. Hakkani-Tur. The ICSI summarization system at TAC
2008. In Proc. of Text Understanding Conference, 2008.
A. Globerson and T. Jaakkola. Fixing max-product: Convergent message passing
algorithms for MAP LP-relaxations. Neural Information Processing Systems, 20,
2008.
R. Glowinski and P. Le Tallec. Augmented Lagrangian and operator-splitting
methods in nonlinear mechanics. Society for Industrial Mathematics, 1989.
R. Glowinski and A. Marroco. Sur l’approximation, par éléments finis d’ordre un,
et la résolution, par penalisation-dualité, d’une classe de problèmes de Dirichlet
non linéaires. Rev. Franc. Automat. Inform. Rech. Operat., 9:41–76, 1975.
M. Guignard and S. Kim. Lagrangean decomposition: a model yielding stronger
Lagrangean bounds. Mathematical programming, 39(2):215–228, 1987.
M. Hestenes. Multiplier and gradient methods. Journal of Optimization Theory1.10

References

29

and Applications, 4:302–320, 1969.
V. Jojic, S. Gould, and D. Koller. Accelerated dual decomposition for MAP
inference. In International Conference of Machine Learning, 2010.
K. Knight and D. Marcu. Statistics-based summarization—step one: Sentencecompression. In Prof. of National Conference on Artificial Intelligence, 2000.
D. Koller and N. Friedman. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009.
V. Kolmogorov. Convergent tree-reweighted message passing for energy minimization. IEEE Transactions on Pattern Analysis and Machine Intelligence, 28:1568–
1583, 2006.
N. Komodakis, N. Paragios, and G. Tziritas. MRF optimization via dual decomposition: Message-passing revisited. In Proc. of International Conference on Computer Vision, 2007.
T. Koo and M. Collins. Efficient third-order dependency parsers. In Proc. of Annual
Meeting of the Association for Computational Linguistics, pages 1–11, 2010.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. Dual decomposition
for parsing with non-projective head automata. In Proc. of Empirical Methods
for Natural Language Processing, 2010.
F. R. Kschischang, B. J. Frey, and H. A. Loeliger. Factor graphs and the sumproduct algorithm. IEEE Transactions on Information Theory, 47, 2001.
S. Kübler, R. McDonald, and J. Nivre. Dependency parsing. Morgan & Claypool
Publishers, 2009.
S. Lauritzen. Graphical Models. Clarendon Press, Oxford, 1996.
C.-Y. Lin. Rouge: A package for automatic evaluation of summaries. In S. S. MarieFrancine Moens, editor, Text Summarization Branches Out: Proceedings of the
ACL-04 Workshop, pages 74–81, Barcelona, Spain, July 2004.
M. Marcus, M. Marcinkiewicz, and B. Santorini. Building a large annotated corpus
of English: The Penn Treebank. Computational linguistics, 19(2):313–330, 1993.
A. F. T. Martins. The Geometry of Constrained Structured Prediction: Applications
to Inference and Learning of Natural Language Syntax. PhD thesis, Carnegie
Mellon University and Instituto Superior Técnico, 2012.
A. F. T. Martins, N. A. Smith, and E. P. Xing. Concise Integer Linear Programming Formulations for Dependency Parsing. In Proc. of Annual Meeting of the
Association for Computational Linguistics, 2009.
A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar, and M. A. T. Figueiredo.
Augmented Dual Decomposition for MAP Inference. In Neural Information
Processing Systems: Workshop in Optimization for Machine Learning, 2010a.
A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T. Figueiredo, and P. M. Q. Aguiar.
Turbo Parsers: Dependency Parsing by Approximate Variational Inference. In
Proc. of Empirical Methods for Natural Language Processing, 2010b.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar, N. A. Smith, and E. P.
Xing. An Augmented Lagrangian Approach to Constrained MAP Inference. In
Proc. of International Conference on Machine Learning, 2011a.
A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and M. A. T. Figueiredo. Dual
Decomposition with Many Overlapping Components. In Proc. of Empirical
Methods for Natural Language Processing, 2011b.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar, N. A. Smith, and E. P. Xing.

30

AD3 : A Fast Decoder for Structured Prediction

Alternating directions dual decomposition, 2012. Arxiv preprint arXiv:1212.6550.
A. F. T. Martins, M. B. Almeida, and N. A. Smith. Turning on the turbo: Fast
third-order non-projective turbo parsers. In Proc. of the Annual Meeting of the
Association for Computational Linguistics, 2013.
R. McDonald and G. Satta. On the complexity of non-projective data-driven
dependency parsing. In International Conference on Parsing Technologies, 2007.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. Non-projective dependency
parsing using spanning tree algorithms. In Proc. of Empirical Methods for Natural
Language Processing, 2005.
R. J. McEliece, D. J. C. MacKay, and J. F. Cheng. Turbo decoding as an instanceof Pearl’s “belief propagation” algorithm. IEEE Journal on Selected Areas inCommunications, 16(2), 1998.
O. Meshi and A. Globerson. An Alternating Direction Method for Dual MAP LP
Relaxation. In European Conference on Machine Learning and Principles andPractice of Knowledge Discovery in Databases, 2011.
Y. Nesterov. Smooth minimization of non-smooth functions. Mathematical Programming, 103(1):127–152, 2005.
J. Nocedal and S. Wright. Numerical optimization. Springer, 1st edition, 1999.
S. Nowozin and C. Lampert. Global connectivity potentials for random field models.
In IEEE Conference on Computer Vision and Pattern Recognition, pages 818–
825. IEEE, 2009.
J. Pearl. Probabilistic Reasoning in Intelligent Systems: Networks of Plausible
Inference. Morgan Kaufmann, 1988.
M. Powell. A method for nonlinear constraints in minimization problems. In
R. Fletcher, editor, Optimization, pages 283–298. Academic Press, 1969.
M. Richardson and P. Domingos. Markov logic networks. Machine Learning, 62(1):107–136, 2006.
T. Richardson and R. Urbanke. Modern coding theory. Cambridge University Press,
2008.
A. Rush and M. Collins. A Tutorial on Dual Decomposition and Lagrangian
Relaxation for Inference in Natural Language Processing. Journal of Artificial
Intelligence Research, 45:305–362, 2012.
A. M. Rush and S. Petrov. Vine pruning for efficient multi-pass dependency parsing.
In Proc. of Conference of the North American Chapter of the Association for
Computational Linguistics, 2012.
M. Schlesinger. Syntactic analysis of two-dimensional visual signals in noisy
conditions. Kibernetika, 4:113–130, 1976.
D. Smith and J. Eisner. Dependency parsing by belief propagation. In Proc. of
Empirical Methods for Natural Language Processing, 2008.
N. A. Smith. Linguistic Structure Prediction, volume 13 of Synthesis Lectures on
Human Language Technologies. Morgan and Claypool, May 2011.
D. Sontag, A. Globerson, and T. Jaakkola. Introduction to dual decomposition for
inference. In Optimization for Machine Learning. MIT Press, 2011.
M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, and J. Nivre. The CoNLL-2008
Shared Task on Joint Parsing of Syntactic and Semantic Dependencies. Proc. ofInternational Conference on Natural Language Learning, 2008.

1.10

References

31

C. Sutton. Collective segmentation and labeling of distant entities in information
extraction. Technical report, DTIC Document, 2004.
R. Tanner. A recursive approach to low complexity codes. IEEE Transactions on
Information Theory, 27(5):533–547, 1981.
D. Tarlow, I. E. Givoni, and R. S. Zemel. HOP-MAP: Efficient message passing
with high order potentials. In AISTATS, 2010.
M. Wainwright and M. Jordan. Graphical Models, Exponential Families, andVariational Inference. Now Publishers, 2008.
M. Wainwright, T. Jaakkola, and A. Willsky. MAP estimation via agreement on
trees: message-passing and linear programming. IEEE Transactions on Information Theory, 51(11):3697–3717, 2005.
H. Wang and A. Banerjee. Online Alternating Direction Method. In Proc. ofInternational Conference on Machine Learning, 2012.
T. Werner. A linear programming approach to max-sum problem: A review. IEEE
Transactions on Pattern Analysis and Machine Intelligence, 29:1165–1179, 2007.
K. Woodsend and M. Lapata. Wikisimple: Automatic simplification of wikipedia
articles. In Proc. of AAAI Conference on Artificial Intelligence, pages 927–932,
2011.
K. Woodsend and M. Lapata. Multiple aspect summarization using integer linear
programming. In Proc. of Empirical Methods in Natural Language Processing,2012.
H. Yamada and Y. Matsumoto. Statistical dependency analysis with support vector
machines. In Proc. of International Conference on Parsing Technologies, 2003.
C. Yanover, T. Meltzer, and Y. Weiss. Linear programming relaxations and belief
propagation–an empirical study. Journal of Machine Learning Research, 7:1887–
1907, 2006.
J. Yedidia, Y. Wang, and S. Draper. Divide and concur and difference-map BP
decoders for LDPC codes. IEEE Transactions on Information Theory, 57(2):786–802, 2011.
H. Zhang and R. McDonald. Generalized higher-order dependency parsing withcube pruning. In Proc. of Empirical Methods in Natural Language Processing,2012.