Dual Decomposition with Many Overlapping Components
André F. T. Martins∗† Noah A. Smith∗ Pedro M. Q. Aguiar‡ Mário A. T. Figueiredo†∗
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA‡
Instituto de Sistemas e Robótica, Instituto Superior Técnico, Lisboa, Portugal†
Instituto de Telecomunicações, Instituto Superior Técnico, Lisboa, Portugal{afm,nasmith}@cs.cmu.edu, aguiar@isr.ist.utl.pt, mtf@lx.it.pt
Abstract
Dual decomposition has been recently proposed as a way of combining complementary models, with a boost in predictive power.
However, in cases where lightweight decompositions are not readily available (e.g., due tothe presence of rich features or logical constraints), the original subgradient algorithm
is inefficient. We sidestep that difficulty byadopting an augmented Lagrangian methodthat accelerates model consensus by regularizing towards the averaged votes. We show
how first-order logical constraints can be handled efficiently, even though the corresponding subproblems are no longer combinatorial,
and report experiments in dependency parsing, with state-of-the-art results.

1

Introduction

The last years have witnessed increasingly accurate
models for syntax, semantics, and machine translation (Chiang, 2007; Finkel et al., 2008; Petrov andKlein, 2008; Smith and Eisner, 2008; Martins etal., 2009a; Johansson and Nugues, 2008; Koo et al.,2010). The predictive power of such models stems
from their ability to break locality assumptions. The
resulting combinatorial explosion typically demands
some form of approximate decoding, such as sampling, heuristic search, or variational inference.
In this paper, we focus on parsers built from linear programming relaxations, the so-called “turbo
parsers” (Martins et al., 2009a; Martins et al., 2010).
Rush et al. (2010) applied dual decomposition asa way of combining models which alone permit
efficient decoding, but whose combination is intractable. This results in a relaxation of the original problem that is elegantly solved with the subgradient algorithm. While this technique has provenquite effective in parsing (Koo et al., 2010; Auli
and Lopez, 2011) as well as machine translation(Rush and Collins, 2011), we show here that its

success is strongly tied to the ability of finding a“good” decomposition, i.e., one involving few overlapping components (or slaves). With many components, the subgradient algorithm exhibits extremely
slow convergence (cf. Fig. 2). Unfortunately, alightweight decomposition is not always at hand, either because the problem does not factor in a naturalway, or because one would like to incorporate features that cannot be easily absorbed in few tractablecomponents. Examples include features generated
by statements in first-order logic, features that violate Markov assumptions, or history features such as
the ones employed in transition-based parsers.
To tackle the kind of problems above, we adopt
DD-ADMM (Alg. 1), a recently proposed algorithm
that accelerates dual decomposition (Martins et al.,2011). DD-ADMM retains the modularity of thesubgradient-based method, but it speeds up consensus by regularizing each slave subproblem towards
the averaged votes obtained in the previous round(cf. Eq. 14). While this yields more involved subproblems (with a quadratic term), we show that exact solutions can still be efficiently computed for
all cases of interest, by using sort operations. As
a result, we obtain parsers that can handle very richfeatures, do not require specifying a decomposition,and can be heavily parallelized. We demonstrate thesuccess of the approach by presenting experiments
in dependency parsing with state-of-the-art results.

2

Background

2.1

Structured Prediction

Let x ∈ X be an input object (e.g., a sentence), fromwhich we want to predict a structured output y ∈Y (e.g., a parse tree). The output set Y is assumed
too large for exhaustive search to be tractable. We
assume to have a model that assigns a score f (y) toeach candidate output, based on which we predict
yb = arg max f (y).
y∈Y

(1)

Designing the model must obey certain practicalconsiderations. If efficiency is the major concern,
a simple model is usually chosen so that Eq. 1 canbe solved efficiently, at the cost of limited expressive
power. If we care more about accuracy, a model withricher features and more involved score functions
may be designed. Decoding, however, will be more
expensive, and approximations are often necessary.
A typical source of intractability comes from the
combinatorial explosion inherent in the compositionof two or more tractable models (Bar-Hillel et al.,1964; Tromble and Eisner, 2006). Recently, Rushet al. (2010) have proposed a dual decomposition
framework to address NLP problems in which theglobal score decomposes as f (y) = f1 (z1 )+f2 (z2 ),where z1 and z2 are two overlapping “views” of theoutput, so that Eq. 1 becomes:
maximizew.r.t.
s.t.

f1 (z1 ) + f2 (z2 )z1 ∈ Y1 , z2 ∈ Y2
z1 ∼ z2 .

(2)Above, the notation z1 ∼ z2 means that z1 andz2 “agree on their overlaps,” and an isomorphism
Y ' {hz1 , z2 i ∈ Y1 × Y2 | z1 ∼ z2 } is assumed. We
next formalize these notions and proceed to compositions of an arbitrary number of models. Of special
interest is the unexplored setting where this number
is very large and each component very simple.
2.2

Decomposition into Parts

A crucial step in the design of structured predictors
is that of decomposing outputs into parts (Taskar etal., 2003). We assume the following setup:
Basic parts. We let R be a set of basic parts, suchthat each element y ∈ Y can be identified with asubset of R. The exact meaning of a “basic part”
is problem dependent. For example, in dependency
parsing, R can be the set of all possible dependency
arcs (see Fig. 1); in phrase-based parsing, it can be
the set of possible spans; in sequence labeling, it canbe the set of possible labels at each position. Our
only assumption is that we can “read out” y fromthe basic parts it contains. For convenience, we represent y as a binary vector, y = hy(r)ir∈R , wherey(r) = 1 if part r belongs to y, and 0 otherwise.
Decomposition. We generalize the decomposition
in Eq. 2 by considering sets Y1 , . . . , YS for S ≥ 2.

Figure 1: Parts used by our parser. Arcs are the basic parts: any dependency tree can be “read out” fromthe arcs it contains. Consecutive siblings and grandparent parts introduce horizontal and vertical Markovization(McDonald et al., 2006; Carreras, 2007). We break thehorizontal Markov assumption via all siblings parts andthe vertical one through parts which indicate a directed
path between two words. Inspired by transition-basedparsers, we also adopt head bigram parts, which look at
the heads attached to consecutive words. Finally, we follow Martins et al. (2009a) and have parts which indicate
if an arc is non-projective (i.e., if it spans words that do
not descend from its head).

Each Ys is associated with its own set of parts Rs , inthe same sense as above; we represent the elementsof Ys as binary vectors zs = hzs (r)ir∈Rs . Examples
are vectors indicating a tree structure, a sequence,or an assignment of variables to a factor, in whichcase it may happen that only some binary vectors
are legal. Some parts in Rs are basic, while others
are not. We denote by R̄s = Rs ∩ R the subset ofthe ones that are. In addition, we assume that:S• R1 , . . . , RS jointly cover R, i.e., R ⊆ Ss=1 Rs ;• Only basic parts may overlap, i.e., Rs ∩ Rt ⊆R, ∀s, t ∈ {1, . . . , S};• Each zs ∈ Ys is completely defined by its entries
indexed by elements of R̄s , from which we canguess the ones in Rs \ R̄s . This implies that eachy ∈ Y has a unique decomposition hz1 , . . . , zS i.
Fig. 1 shows several parts used in dependency parsing models; in phrase-based parsing, these could bespans and production rules anchored in the surface
string; in sequence labeling, they can be unigram,bigram, and trigram labels.1
1

There is a lot of flexibility about how to decompose themodel into S components: each set Rs can correspond to a sin-Global consistency. We want to be able to readout y ∈ Y by “gluing” together the components
hz1 , . . . , zS i. This is only meaningful if they are“globally consistent,” a notion which we make precise. Two components zs ∈ Ys and zt ∈ Yt are said
to be consistent (denoted zs ∼ zt ) if they agree on
their overlaps, i.e., if zs (r) = zt (r), ∀r ∈ Rs ∩ Rt .
A complete assignment hz1 , . . . , zS i is globally consistent if all pairs of components are consistent. Thisis equivalent to the existence of a witness vector
hu(r)ir∈R such that zs (r) = u(r), ∀s, r ∈ R̄s .
With this setup, assuming
PS that the score function
decomposes as f (z) = s=1 fs (zs ), the decoding
problem (which extends Eq. 2 for S ≥ 2) becomes:
P :maximizew.r.t.
s.t.

PS

s=1 fs (zs )zs ∈ Ys , ∀shu(r)ir∈R ∈ R|R| ,zs (r) = u(r), ∀s, r ∈ R̄s .

(3)

We call the equality constraints expressed in the lastline the “agreement constraints.” It is these constraints that complicate the problem, which would
otherwise be exactly separable into S subproblems.
The dual decomposition method (Komodakis et al.,2007; Rush et al., 2010) builds an approximation by
dualizing out these constraints, as we describe next.
2.3

Dual Decomposition

We describe dual decomposition in a slightly different manner than Rush et al. (2010): we will firstbuild a relaxation of P (called P 0 ), in which the entire approximation is enclosed. Then, we dualize P 0 ,yielding problem D. In the second step, the duality
gap is zero, i.e., P 0 and D are equivalent.2
Relaxation. For each s ∈ {1, . . . , S} we consider
the convex hull of Ys ,
(
Zs =

)
X
zs ∈Ysp(zs )zsp(zs ) ≥ 0,X

p(zs ) = 1 .

zs ∈Ys(4)
gle factor in a factor graph (Smith and Eisner, 2008), or to aentire subgraph enclosing several factors (Koo et al., 2010), oreven to a formula in Markov logic (Richardson and Domingos,
2006). In these examples, the basic parts may correspond toindividual variable-value pairs.
2
Instead of following the path P → P 0 → D, Rush et al.
(2010) go straight from P to D via a Lagrangian relaxation.
The two formulations are equivalent for linear score functions.

We have that Ys = Zs ∩ Z|Rs | ; hence, problem P(Eq. 3) is equivalent to one in which each Ys is replaced by Zs and the z-variables are constrained to
be integer. By dropping the integer constraints, we
obtain the following relaxed problem:
P0 :maximizew.r.t.
s.t.

PS

s=1 fs (zs )zs ∈ Zs , ∀shu(r)ir∈R ∈ R|R| ,zs (r) = u(r), ∀s, r ∈ R̄s .

(5)

If the score functions fs are convex, P 0 becomes aconvex program (unlike P , which is discrete); beinga relaxation, it provides an upper bound of P .
Lagrangian. Introducing a Lagrange multiplierλs (r) for each agreement constraint in Eq. 5, one
obtains the Lagrangian functionPP
L(z, u, λ) = Ss=1 fs (zs ) + r∈R̄s λs (r)zs (r)

P
P
− r∈R
s:r∈R̄s λs (r) u(r), (6)and the dual problem (the master)D:

minimizew.r.t.
s.t.

PS

s=1 gs (λs )λ=P hλ1 , . . . , λS i
s:r∈R̄s λs (r) = 0, ∀r ∈ R,

(7)

where the gs (λs ) are the solution values of the following subproblems (the slaves):
maximizew.r.t.

fs (zs ) +zs ∈ Z s .

Pr∈R̄s λs (r)zs (r)(8)

We assume that strong duality holds (w.r.t. Eqs. 5–7), hence we have P ≤ P 0 = D.3
Solving the dual. Why is the dual formulation D(Eqs. 7–8) more appealing than P 0 (Eq. 5)? The answer is that the components 1, . . . , S are now decoupled, which makes things easier provided eachslave subproblem (Eq. 8) can be solved efficiently.
In fact, this is always a concern in the mind of
the model’s designer when she chooses a decomposition (the framework that we describe in §3,
in some sense, alleviates her from this concern).
If the score
Pfunctions are linear, i.e., of the formfs (zs ) =r∈Rs θs (r)zs (r) for some vector θs =hθs (r)ir∈Rs , then Eq. 8 becomes a linear program,for which a solution exists at a vertex of Zs (which
3This is guaranteed if the score functions fs are linear.

in turn is an element of Ys ). Depending on the structure of the problem, Eq. 8 may be solved by brute
force, dynamic programming, or specialized combinatorial algorithms (Rush et al., 2010; Koo et al.,2010; Rush and Collins, 2011).
Applying the projected subgradient method (Komodakis et al., 2007; Rush et al., 2010) to the master problem (Eq. 7) yields a remarkably simple algorithm, which at each round t solves the subproblems
in Eq. 8 for s = 1, . . . , S, and then gathers thesesolutions (call them zst+1 ) to compute an “averaged”
vote for each basic part,
1 P
t+1
ut+1 (r) = δ(r)(9)
s:r∈R̄s zs (r),where δ(r) = |{s : r ∈ Rs }| is the number of components which contain part r. An update of the Lagrange variables follows,
t
t+1
t+1
λt+1
(r)), (10)s (r) = λs (r) − ηt (zs (r) − u

where ηt is a stepsize. Intuitively, the algorithm
pushes for a consensus among the slaves (Eq. 9),
via an adjustment of the Lagrange multipliers whichtakes into consideration deviations from the average (Eq. 10). The subgradient method is guaranteed to converge to the solution of D (Eq. 7), forsuitably chosen stepsizes (Shor, 1985; Bertsekas etal., 1999); it also provides a certificate of optimality in case the relaxation is tight (i.e., P = D) andthe exact solution has been found. However, convergence is slow when S is large (as we will show
in the experimental section), and no certificates areavailable when there is a relaxation gap (P < P 0 ).
In the next section, we describe the DD-ADMM algorithm (Martins et al., 2011), which does not havethese drawbacks and shares a similar simplicity.

3

Alternating Directions Method

There are two reasons why subgradient-based dual
decomposition is not completely satisfying:• it may take a long time to reach a consensus;• it puts all its resources in solving the dual problem
D, and does not attempt to make progress in the
primal P 0 , which is closer to our main concern.4
Our main concern is P ; however solving P 0 is often auseful step towards that goal, either because a good rounding
scheme exists, or because one may build tighter relaxations toapproach P (Sontag et al., 2008; Rush and Collins, 2011).
4

Taking a look back at the relaxed primal problem
P 0 (Eq. 5), we see that any primal feasible solution
must satisfy the agreement constraints. This suggests that penalizing violations of these constraints
could speed up consensus.
Augmented Lagrangian. By adding a penalty
term to Eq. 6, we obtain the augmented Lagrangianfunction (Hestenes, 1969; Powell, 1969):
SAρ (z, u, λ) = L(z, u, λ) −ρX X
(zs (r) − u(r))2 ,
2 s=1
r∈R̄s

(11)

where the parameter ρ ≥ 0 controls the intensityof the penalty. Augmented Lagrangian methods
are well-known in the optimization community (see,e.g., Bertsekas et al. (1999), §4.2). They alternate
updates to the λ-variables, while seeking to maximize Aρ with respect to z and u. In our case, however, this joint maximization poses difficulties, since
the penalty term couples the two variables. The alternating directions method of multipliers (ADMM),
coined by Gabay and Mercier (1976) and Glowinski
and Marroco (1975), sidesteps this issue by performing alternate maximizations,z t+1 = arg max Aρ (z, ut , λt ),(12)

ut+1 = arg max Aρ (z t+1 , u, λt ),

(13)

z

u

followed by an update of the Lagrange multipliers
as in Eq. 10. Recently, ADMM has attracted interest, being applied in a variety of problems; see therecent book by Boyd et al. (2011) for an overview.
As derived in the App. A, the u-updates in Eq. 13
have a closed form, which is precisely the averaging operation performed by the subgradient method(Eq. 9). We are left with the problem of computing the z-updates. Like in the subgradient approach,the maximization in Eq. 12 can be separated into S
independent slave subproblems, which now take theform:Pmaximize fs (zs ) + r∈R̄s λs (r)zs (r)P− ρ2 r∈R̄s (zs (r) − ut (r))2(14)
w.r.t.
zs ∈ Zs (x).
Comparing Eq. 8 and Eq. 14, we observe that the
only difference is the presence in the latter of aquadratic term which regularizes towards the previous averaged votes ut (r). Because of this term,
the solution of Eq. 14 for linear score functions may
not be at a vertex (in contrast to the subgradientmethod). We devote §4 to describing exact and efficient ways of solving the problem in Eq. 14 for important, widely used slaves. Before going into details, we mention another advantage of ADMM overthe subgradient algorithm: it knows when to stop.
Primal and dual residuals. Recall that the subgradient method provides optimality certificateswhen the relaxation is tight (P = P 0 ) and an exact solution of P has been found. While this is goodenough when tight relaxations are frequent, as in thesettings explored by Rush et al. (2010), Koo et al.
(2010), and Rush and Collins (2011), it is hard toknow when to stop when a relaxation gap exists.
We would like to have similar guarantees concerning the relaxed primal P 0 .5 A general weakness of
subgradient algorithms is that they do not have thiscapacity, and so are usually stopped by specifying amaximum number of iterations. In contrast, ADMM
allows to keep track of primal and dual residuals(Boyd et al., 2011). This allows providing certificates not only for the exact solution of P (when therelaxation is tight), but also to terminate when a near
optimal solution of the relaxed problem P 0 has beenfound. The primal residual rPt measures the amountby which the agreement constraints are violated:
PS P(z t (r) − ut (r))2tPR̄s srP = s=1 r∈;(15)r∈R δ(r)t is the amount by which a dual
the dual residual rD
optimality condition is violated (see Boyd et al.
(2011), p.18, for details). It is computed via:P
δ(r)(ut (r) − ut−1 (r))2trD = r∈R P,(16)
r∈R δ(r)Our stopping criterion is thus that these two residuals are below a threshold, e.g., 1 × 10−3 . The complete algorithm is depicted as Alg. 1. As stated in
5This problem is more important than it may look. Problems
with many slaves tend to be less exact, hence relaxation gaps
are frequent. Also, when decoding is embedded in training, it isuseful to obtain the fractional solution of the relaxed primal P(rather than an approximate integer solution). See Kulesza andPereira (2007) and Martins et al. (2009b) for details.

Algorithm 1 ADMM-based Dual Decomposition
1: input: score functions hfs (.)iS
s=1 , parameters ρ, η,

thresholds P and D .
2: initialize t ← 1
3: initialize u1 (r) ← 0.5 and λ1s (r) ← 0, ∀s, ∀r ∈ R̄s
4: repeat5:
for each s = 1, . . . , S do
6:make a zs -update, yielding zst+1 (Eq. 14)
7:
end for8:
make a u-update, yielding ut+1 (Eq. 9)
9:make a λ-update, yielding λt+1 (Eq. 10)
10:
t←t+1
t+1
t+1
11: until rP< P and rD< D (Eqs. 15–16)
12: output: relaxed primal and dual solutions u, z, λMartins et al. (2011), convergence to the solution of
P 0 is guaranteed with a fixed stepsize ηt = τ ρ, withτ ∈ [1, 1.618] (Glowinski and Le Tallec, 1989, Thm.
4.2). In our experiments, we set τ = 1.5, and adapt
ρ as described in (Boyd et al., 2011, p.20).6

4

Solving the Subproblems

In this section, we address the slave subproblems of
DD-ADMM (Eq. 14). We show how these subproblems can be solved efficiently for several important
cases that arise in NLP applications. Throughout,
we assume that the score functions
Pfs are linear, i.e.,they can be written as fs (zs ) = r∈Rs θs (r)zs (r).
This is the case whenever a linear model is used, in1
which case θs (r) = δ(r)w · φ(x, r), where w is aweight vector and φ(x, r) is a feature vector. It isalso the scenario studied in previous work in dual
decomposition (Rush et al., 2010). Under this assumption, and discarding constant terms, the slave
subproblem in Eq. 14 becomes:max

zs ∈ZsX
r∈Rs \R̄sθs (r)zs (r) −ρ X(zs (r) − as (r))2 .
2
r∈R̄s

(17)

where as (r) = ut (r)+ρ−1 (θs (r)+λts (r)). Since Zs
is a polytope, Eq. 17 is a quadratic program, which
can be solved with a general purpose solver. However, that does not exploit the structure of Zs and isinefficient when |Rs | is large. We next show that for
many cases, a closed-form solution is available and6

Briefly, we initialize ρ = 0.03 and then increase/decreaseρ by a factor of 2 whenever the primal residual becomes > 10times larger/smaller than the dual residual.

can be computed in O(|Rs |) time, up to log factors.7
Pairwise Factors. This is the case where RPAIR ={r1 , r2 , r12 }, where r1 and r2 are basic parts andr12 is their conjunction, i.e., we have YPAIR ={hz1 , z2 , z12 i | z12 = z1 ∧ z2 }. This factor is useful to make conjunctions of variables participate in
the score function (see e.g. the grandparent, sibling,and head bigram parts in Fig. 1). The convex hullof YPAIR is the polytope ZPAIR = {hz1 , z2 , z12 i ∈[0, 1]3 | z12 ≤ z1 , z12 ≤ z2 , z12 ≥ z1 + z2 − 1}, asshown by Martins et al. (2010). In this case, problem(17) can be written as
max θ12 z12 − ρ2 [(z1 − a1 )2 + (z2 − a2 )2 ]w.r.t. hz1 , z2 , z12 i ∈ [0, 1]3s.t.
z12 ≤ z1 , z12 ≤ z2 , z12 ≥ z1 + z2 − 1(18)

and has a closed form solution (see App. B).
Uniqueness Quantification and XOR. Many
problems involve constraining variables to take asingle value: for example, in dependency parsing,a modifier can only take one head. This can be
expressed as the statement ∃!y : Q(y) in first-orderlogic,8 or as a one-hot XOR factor in a factor
graph (Smith and Eisner, 2008; Martins et al.,2010). In this case, RXOR = {r1P
, . . . , rn }, andn
YXOR = {hz1 , . . . , zn i ∈ {0, 1}n |i=1 zi = 1}.
The convex
hull
of
Y
is
Z
=
{hz
XOR
XOR
1 , . . . , zn i ∈Pnn[0, 1] |i=1 zi = 1}. Assume for the sake ofsimplicity that all parts in RXOR are basic.9 Up to a
constant, the slave subproblem becomes:Pnminimize 21 i=1 (zi − ai )2nw.r.t.
hz
P1n, . . . , zn i ∈ [0, 1]
s.t.
i zi = 1.

(19)This is the problem of projecting onto the probability simplex, which can be done in O(n log n) time
via a sort operation (see App. C).10
7
This matches the asymptotic time that would be necessary
to solve the corresponding problems in the subgradient method,
for which algorithms are straightforward to derive. The point isthat with ADMM fewer instances of these subproblems need tobe solved, due to faster convergence of the master problem.
8
The symbol ∃! means “there is one and only one.”
9
A similar derivation can be made otherwise.
10
Also common is the need for constraining existence of “atmost one” element. This can be reduced to uniqueness quantification by adding a dummy NULL label.

Existential Quantification and OR. Sometimes,
only existence is required, not necessarily uniqueness. This can be expressed with disjunctions, existential quantifiers in first-order logic (∃y : Q(y)),
or as a OR factor. In this case, ROR =W {r1 , . . . , rn },YOR = {hz1 , . . . , zn i ∈ {0, 1}n | ni=1 zi = 1},
and the P
convex hull is ZOR = {hz1 , . . . , zn i ∈n[0, 1]n |i=1 zi ≥ 1} (see Tab. 1 in Martins et al.
(2010)). The slave subproblem becomes:Pnminimize 12 i=1 (zi − ai )2
w.r.t.
hz1 , . . . , zn i ∈ [0, 1]nPns.t.
i zi ≥ 1.

(20)

We derive a procedure in App. D to compute thisprojection in O(n log n) runtime, also with a sort.
Negations. The two cases above can be extended
to allow some of their inputs to be negated. By achange of variables in Eqs. 19–20 it is possible toreuse the same black box that solves those problems.
The procedure is as follows:
1. For i = 1, . . . , n, set a0i = 1−ai if the ith variable
is negated, and a0i = ai otherwise.
2. Obtain hz10 , . . . , zn0 i as the solution of Eqs. 19 or
20 providing ha01 , . . . , a0n i as input.
3. For i = 1, . . . , n, set zi = 1−zi0 if the ith variable
is negated, and zi = zi0 otherwise.
The ability to handle negated variables adds agreat degree of flexibility. From De Morgan’slaws, we can V
now handle conjunctions and implications(since ni=1 Qi (x) ⇒ R(x) is equivalent toWn
i=1 ¬Qi (x) ∨ R(x)).
Logical Variable Assignments. All previous examples involve taking a group of existing variables
and defining a constraint. Alternatively, we may
want to define a new variable which is the result ofan operation involving other variables. For example, R(x) := ∃!y : Q(x, y). This corresponds to the
XOR - WITH - OUTPUT factor in Martins et al. (2010).
Interestingly, this can be expressed as a XOR whereR(x) is negated (i.e., either ¬R(x) holds or exactly
one y satisfies Q(x, y), but not both).
A more difficult problem is that of the OR - WITH OUTPUT factor, expressed by the formula R(x) :=∃y : Q(x, y). We have ROR - OUT = {r0 , . . . , rn },and YOR - OUT = {hz0 , . . . , zn i ∈ {0, 1}n | z0 =TreeAll siblings
Grandp.
Head Bigram
Consec. Sibl.

Nonproj. Arc∃!h : arc(h, m), m 6= 0
flow(h, m, k) ⇒ arc(h, m)path(m, d) := ∃!h : flow(h, m, d), m 6= 0path(h, d) := ∃!m : flow(h, m, d)path(0, m) := TRUE, flow(h, m, m) := TRUEsibl(h, m, s) := arc(h, m) ∧ arc(h, s)
grand(g, h, m) := arc(g, h) ∧ arc(h, m)bigram(b, h, m) := arc(b, m − 1) ∧ arc(h, m), m 6= 0
lastsibl(h, m, m) := arc(h, m)∃!m ∈ [h, k] : lastsibl(h, m, k)lastsibl(h, m, k) := lastsibl(h, m, k + 1)
⊕ nextsibl(h, m, k + 1)
arc(h, m) := ∃!s ∈ [h, m] : nextsibl(h, s, m)
nonproj(h, m) := arc(h, m) ∧ ∃k ∈ [h, m] : ¬path(h, k)# SlavesO(n)O(n3 )O(n2 )O(n2 )

RuntimeO(n log n)O(1)O(n log n)O(n log n)O(n3 )O(n3 )O(n3 )

O(1)
O(1)
O(1)

O(n2 )

O(n log n)O(n3 )O(n2 )O(n2 )O(1)O(n log n)O(n log n)

Description
Each non-root word has a head
Only active arcs may carry flow
Paths and flows are consistent(see Martins et al. (2010))
By definition
By definition
By definition
Head automaton model(see supplementary material)

By definition

Table 1: First-order logic formulae underlying our dependency parser. The basic parts are the predicate variablesarc(h, m) (indicating an arc linking head h to modifier m), path(a, d) (indicating a directed path from ancestor
a to descendant d), nextsibl(h, m, s) (indicating that hh, mi and hh, si are consecutive siblings), nonproj(h, m)(indicating that hh, mi is a non-projective arc), as well as the auxiliary variables flow(h, m, d) (indicating that arc
hh, mi carries flow to d), and lastsibl(h, m, k) (indicating that, up to position k, the last seen modifier of h occurredat position m). The non-basic parts are the pairwise factors sibl(h, m, s), grand(g, h, m), and bigram(b, h, m); as
well as each logical formula. Columns 3–4 indicate the number of parts of each kind, and the time complexity forsolving each subproblem. For a sentence of length n, there are O(n3 ) parts and the total complexity is O(n3 log n).

Wn

i=1 zi }. The convex hull of YOR - OUT is the follown
ing
Pn set: ZOR - OUT = {hz0 , . . . , zn i ∈ [0, 1] | z0 ≥i=1 zi , z0 ≤ zi , ∀i = 1, . . . , n} (Martins et al.,2010, Tab.1). The slave subproblem is:

minimizew.r.t.
s.t.

1
2

Pn

2
i=0 (zi − ai )hz0 , . .P
. , zn i ∈ [0, 1]nnz0 ≥ i=1 zi ; z0 ≤ zi , ∀i = 1, . . . , n.
(21)

The problem in Eq. 21 is more involved than theones in Eqs. 19–20. Yet, there is still an efficient
procedure with runtime O(n log n) (see App. E).
By using the result above for negated variables, weare now endowed with a procedure for many othercases, such that AND - WITH - OUTPUT and formulas with universal quantifiers (e.g., R(x) := ∀y :Q(x, y)). Up to a log-factor, the runtimes will belinear in the number of predicates.
Larger Slaves. The only disadvantage of DDADMM in comparison with the subgradient algorithm is that there is not an obvious way of solving
the subproblem in Eq. 14 exactly for large combinatorial factors, such as the TREE constraint in dependency parsing, or a sequence model. Hence, ourmethod seems to be more suitable for decompositions which involve “simple slaves,” even if their
number is large. However, this does not rule out thepossibility of using this method otherwise. Ecksteinand Bertsekas (1992) show that the ADMM algorithm may still converge when the z-updates are inexact. Hence the method may still work if the slaves
are solved numerically up to some accuracy. We defer this to future investigation.

5

Experiments: Dependency Parsing

We used 14 datasets with non-projective dependencies from the CoNLL-2006 and CoNLL-2008
shared tasks (Buchholz and Marsi, 2006; Surdeanu
et al., 2008). We also used a projective English
dataset derived from the Penn Treebank by applying
the standard head rules of Yamada and Matsumoto(2003).11 We did not force the parser to output projective trees or unique roots for any of the datasets;
everything is learned from the data. We trained byrunning 10 iterations of the cost-augmented MIRA
algorithm (Crammer et al., 2006) with LP-relaxed
decoding, as in Martins et al. (2009b). Following common practice (Charniak and Johnson, 2005;
Carreras et al., 2008), we employed a coarse-to-fineprocedure to prune away unlikely candidate arcs, as
described by Koo and Collins (2010). To ensure
valid parse trees at test time, we rounded fractional11

As usual, we train on sections §02–21, use §22 as validation
data, and test on §23. We ran SVMTool (Giménez and Marquez,2004) to obtain automatic part-of-speech tags for §22–23.

solutions as described in Martins et al. (2009a) (yet,solutions were integral most of the time).
The parts used in our full model are the ones
depicted in Fig. 1. Note that a subgradient-based
method could handle some of those parts efficiently(arcs, consecutive siblings, grandparents, and headbigrams) by composing arc-factored models, head
automata, and a sequence labeler. However, nolightweight decomposition seems possible for incorporating parts for all siblings, directed paths, andnon-projective arcs. Tab. 1 shows the first-orderlogical formulae that encode the constraints in ourmodel. Each formula gives rise to a subproblem
which is efficiently solvable (see §4). By ablatingsome of rows of Tab. 1 we recover known methods:• Resorting to the tree and consecutive sibling formulae gives one of the models in Koo et al.
(2010), with the same linear relaxation (a proofof this fact is included in App. F);• Resorting to tree, all siblings, grandparent, andnon-projective arcs, recovers a multi-commodity
flow configuration proposed by Martins et al.
(2009a); the relaxation is also the same.12
The experimental results are shown in Tab. 2.
For comparison, we include the best published results for each dataset (at the best of our knowledge),among transition-based parsers (Nivre et al., 2006;
Huang and Sagae, 2010), graph-based parsers (McDonald et al., 2006; Koo and Collins, 2010), hybrid
methods (Nivre and McDonald, 2008; Martins et al.,2008), and turbo parsers (Martins et al., 2010; Kooet al., 2010). Our full model achieved the best reported scores for 7 datasets. The last two columns
show a consistent improvement (with the exceptionsof Chinese and Arabic) when using the full set offeatures over a second order model with grandparent
and consecutive siblings, which is our reproductionof the model of Koo et al. (2010).13
12

Although Martins et al. (2009a) also incorporated consecutive siblings in one of their configurations, our constraints aretighter than theirs. See App. F.
13Note however that the actual results of Koo et al. (2010)
are higher than our reproduction, as can be seen in the second
column. The differences are due to the features that were used
and on the way the models were trained. The cause is not searcherror: exact decoding with an ILP solver (CPLEX) revealed nosignificant difference with respect to our G+CS column. We
leave further analysis for future work.

ArabicBulgar.
ChineseCzech
EnglishDanishDutch
GermanJapane.
Portug.
SloveneSpanishSwedishTurkishPTB §23

Best known UAS
80.18 [Ma08]
92.88 [Ma10]
91.89 [Ma10]
88.78 [Ma10]
92.57 [Ko10]
91.78 [Ko10]85.81 [Ko10]
91.49 [Ma10]
93.42 [Ma10]
93.03 [Ko10]
86.21 [Ko10]
87.04 [Ma10]
91.36 [Ko10]
77.55 [Ko10]
93.04 [KC10]

G+CS
81.12
93.04
91.05
88.80
92.45
91.70
84.77
91.29
93.62
92.05
86.09
85.99
89.94
76.24
92.19

Full
81.10 (-0.02)
93.50 (+0.46)
90.62 (-0.43)
89.46 (+0.66)
92.68 (+0.23)
91.86 (+0.16)
85.53 (+0.76)
91.89 (+0.60)
93.72 (+0.10)
92.29 (+0.24)
86.95 (+0.86)
86.74 (+0.75)
90.16 (+0.22)
76.64 (+0.40)
92.53 (+0.34)

Table 2: Unlabeled attachment scores, excluding punctuation. In the second column, [Ma08] denotes Martinset al. (2008), [KC10] is Koo and Collins (2010), [Ma10]
is Martins et al. (2010), and [Ko10] is Koo et al. (2010).
In columns 3–4, “Full” is our full model, and “G+CS” isour reproduction of the model of Koo et al. (2010), i.e.,the same as “Full” but with all features ablated exceptedfor grandparents and consecutive siblings.

PTB §22
PTB §23

AF
91.02
91.36

+G+CS
92.13
92.19

+AS
92.32
92.41

+NP
92.36
92.50

Full
92.41
92.53

Table 3: Feature ablation experiments. AF is an arcfactored model; +G+CS adds grandparent and consecutive siblings; +AS adds all-siblings; +NP adds nonprojective arcs; Full adds the bigram and directed paths.

Feature ablation and error analysis. We conducted a simple ablation study by training several
models on the English PTB with different sets offeatures. Tab. 3 shows the results. As expected, performance keeps increasing as we use models withgreater expressive power. We show some concrete
examples in App. G of sentences that the full model
parsed correctly, unlike less expressive models.
Convergence speed and optimality. Fig. 2 compares the performance of DD-ADMM and the subgradient algorithms in the validation section of thePTB.14 For the second order model, the subgradient14
The learning rate in the subgradient method was set as ηt =
η0 /(1+Nincr (t)), as in Koo et al. (2010), where Nincr (t) is thenumber of dual increases up to the tth iteration, and η0 is chosen
to maximize dual decrease after 20 iterations (in a per sentencebasis). Those preliminary iterations are not plotted in Fig. 2.

Runtime and caching strategies. Despite its suitability to problems with many overlapping components, our parser is still 1.6 times slower than Koo
et al. (2010) (0.34 against 0.21 sec./sent. in PTB§23), and is far beyond the speed of transition-basedparsers (e.g., Huang and Sagae (2010) take 0.04
sec./sent. on the same data, although accuracy islower, 92.1%). Our implementation, however, is not
fully optimized. We next describe how considerable
speed-ups are achieved by caching the subproblems,
following a strategy similar to Koo et al. (2010).
Fig. 3 illustrates the point. After a few iterations,many variables u(r) see a consensus being achieved(i.e., ut (r) = zst+1 (r), ∀s) and enter an idle state:
they are left unchanged by the u-update in Eq. 9,
and so do the Lagrange variables λt+1
s (r) (Eq. 10).
If by iteration t all variables in a subproblem s are
idle, then zst+1 (r) = zst (r), hence the subproblem
does not need to be resolved.15 Fig. 3 shows that
15

Even if not all variables are idle in s, caching may still be
useful: note that the z-updates in Eq. 14 tend to be sparse for the
subproblems described in §4 (these are Euclidean projections
onto polytopes with 0/1 vertices, which tend to hit corners). Another trick that may accelerate the algorithm is warm-starting:since many subproblems involve a sort operation, storing thesorted indexes may speedup the next round.

Full ADMM% active msgs
% active subproblems% active vars

100
% active

80
60
40
20
0

200

400

600
Iterations

800

1000

Figure 3: Fraction of active variables, subproblems andmessages along DD-ADMM iterations (full model). The
number of active messages denotes the total number ofvariables (active or not) that participate in an active factor.
Elapsed Times
101
Time CPLEX (sec.)

method has more slaves than in Koo et al. (2010):
it has a slave imposing the TREE constraint (whose
subproblems consists on finding a minimum spanning tree) and several for the all-sibling parts, yielding an average number of 310.5 and a maximumof 4310 slaves. These numbers are still manageable, and we observe that a “good” UAS is achieved
relatively quickly. The ADMM method has many
more slaves due to the multicommodity flow constraints (average 1870.8, maximum 65446), yet it
attains optimality sooner, as can be observed in theright plot. For the full model, the subgradient-based
method becomes extremely slow, and the UAS scoreseverely degrades (after 1000 iterations it is 2%
less than the one obtained with the ADMM-based
method, with very few instances having been solved
to optimality). The reason is the number of slaves:in this configuration and dataset the average numberof slaves per instance is 3327.4, and the largest number is 113207. On the contrary, the ADMM method
keeps a robust performance, with a large fraction of
optimality certificates in early iterations.

100
10-1
10-2
10-3
10-3

10-2

10-1
100
Time ADMM (sec.)

101

Figure 4: Runtimes of DD-ADMM and CPLEX on PTB§22 (each point is a sentence). Average runtimes are
0.362 (DD-ADMM) and 0.565 sec./sent. (CPLEX).

many variables and subproblems are left untouched
after the first few rounds.
Finally, Fig. 4 compares the runtimes of our implementation of DD-ADMM with those achieved bya state-of-the-art LP solver, CPLEX, in its best performing configuration: the simplex algorithm applied to the dual LP. We observe that DD-ADMM
is faster in some regimes but slower in others. For
short sentences (< 15 words), DD-ADMM tends tobe faster. For longer sentences, CPLEX is quite effective as it uses good heuristics for the pivot steps
in the simplex algorithm; however, we observed thatit sometimes gets trapped on large problems. Notealso that DD-ADMM is not fully optimized, and that
it is much more amenable to parallelization than thesimplex algorithm, since it is composed of many independent slaves. This suggests potentially significant speed-ups in multi-core environments.

6

Related Work

Riedel and Clarke (2006) first formulated dependency parsing as an integer program, along withlogical constraints. The multicommodity flow for-

Accuracy

ADMM Full
Subgrad Full
ADMM Sec Ord
Subgrad Sec Ord
200

400
600
Iterations

Stopping Criteria

100

800

1000

Certificates (%)

UAS (%)

92
91
90
89
88
87
86
850

80

ADMM Full (Tol<0.001)
ADMM Full (Exact)
Subgrad Full (Exact)
ADMM Sec Ord (Tol<0.001)
ADMM Sec Ord (Exact)
Subgrad Sec Ord (Exact)

60
40
20
00

200

400
600
Iterations

800

1000

Figure 2: UAS including punctuation (left) and fraction of optimality certificates (right) accross iterations of thesubgradient and DD-ADMM algorithms, in PTB §22. “Full” is our full model; “Sec Ord” is a second-order modelwith grandparents and all siblings, for which the subgradient method uses a coarser decomposition with a TREE factor.
Since subgradient and DD-ADMM are solving the same problems, the solid lines (as the dashed ones) would meet in
the limit, however subgradient converges very slowly for the full model. The right plot shows optimality certificatesfor both methods, indicating that an exact solution of P has been found; for DD-ADMM we also plot the fraction of
instances that converged to an accurate solution of P 0 (primal and dual residuals < 10−3 ) and hence can be stopped.

mulation was introduced by Martins et al. (2009a),along with some of the parts considered here. Koo
et al. (2010) proposed a subgradient-based dual decomposition method that elegantly combines head
automata with maximum spanning tree algorithms;
these parsers, as well as the loopy belief propagation
method of Smith and Eisner (2008), are all instancesof turbo parsers (Martins et al., 2010).
DD-ADMM has been proposed and theoreticallyanalyzed by Martins et al. (2011) for problems representable as factor graphs. The general ADMM
method has a long-standing history in optimization(Hestenes, 1969; Powell, 1969; Glowinski and Marroco, 1975; Gabay and Mercier, 1976; Boyd et al.,2011). Other methods have been recently proposedto accelerate dual decomposition, such as Jojic et al.
(2010) and Meshi and Globerson (2011) (the latter
applying ADMM in the dual rather than the primal).
While our paper shows limitations of the subgradient method when there are many overlapping
components, this method may still be advantageousover ADMM in problems that are nicely decomposable, since it often allows reusing existing combinatorial machinery. Yet, the scenario we consider here is realistic in NLP, where we often haveto deal with not-lightly-decomposable constrained
problems (e.g., exploiting linguistic knowledge).

7

Conclusion

We have introduced new feature-rich turbo parsers.
Since exact decoding is intractable, we solve an LP
relaxation through a recently proposed consensus al-

gorithm, DD-ADMM, which is suitable for problems with many overlapping components. We study
the empirical runtime and convergence properties of
DD-ADMM, complementing the theoretical treatment in Martins et al. (2011). DD-ADMM compares favourably against the subgradient method inseveral aspects: it is faster to reach a consensus, it
has better stopping conditions, and it works betterin non-lightweight decompositions. While its slave
subproblems are more involved, we derived closedform solutions for many cases of interest, such as
first-order logic formulas and combinatorial factors.
DD-ADMM may be useful in other frameworks
involving logical constraints, such as the models
for compositional semantics presented by Lianget al. (2011). Non-logical constraints may also
yield efficient subproblems, e.g., the length constraints in summarization and compression (Clarkeand Lapata, 2008; Martins and Smith, 2009; BergKirkpatrick et al., 2011). Finally, DD-ADMM canbe adapted to tighten its relaxations towards exact
decoding, as in Sontag et al. (2008) and Rush andCollins (2011). We defer this for future work.

Acknowledgments
We thank all reviewers for their comments, Eric Xing forhelpful discussions, and Terry Koo and Sasha Rush foranswering questions about their parser and for providing
code. A. M. was supported by a FCT/ICTI grant throughthe CMU-Portugal Program, and by Priberam. This
work was partially supported by the FET programme(EU FP7), under the SIMBAD project (contract 213250).
N. S. was supported by NSF CAREER IIS-1054319.

References
M. Auli and A. Lopez. 2011. A Comparison of Loopy
Belief Propagation and Dual Decomposition for Integrated CCG Supertagging and Parsing. In Proc. of
ACL.
Y. Bar-Hillel, M. Perles, and E. Shamir. 1964. On formal properties of simple phrase structure grammars.
Language and Information: Selected Essays on their
Theory and Application, pages 116–150.
Taylor Berg-Kirkpatrick, Dan Gillick, and Dan Klein.
2011. Jointly learning to extract and compress. In
Proc. of ACL.
D. Bertsekas, W. Hager, and O. Mangasarian. 1999.
Nonlinear programming. Athena Scientific.
D.P. Bertsekas, A. Nedic, and A.E. Ozdaglar. 2003. Convex analysis and optimization. Athena Scientific.
S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein.
2011. Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers. Now Publishers (to appear).
J.P. Boyle and R.L. Dykstra. 1986. A method for finding projections onto the intersections of convex sets in
Hilbert spaces. In Advances in order restricted statistical inference, pages 28–47. Springer Verlag.
S. Buchholz and E. Marsi. 2006. CoNLL-X shared task
on multilingual dependency parsing. In CoNLL.
X. Carreras, M. Collins, and T. Koo. 2008. TAG, Dynamic Programming, and the Perceptron for Efficient,Feature-rich Parsing. In CONLL.
X. Carreras. 2007. Experiments with a higher-order projective dependency parser. In CoNLL.
E. Charniak and M. Johnson. 2005. Coarse-to-fine nbest parsing and MaxEnt discriminative reranking. In
Proc. ACL, pages 173–180. Association for Computational Linguistics Morristown, NJ, USA.
D. Chiang. 2007. Hierarchical phrase-based translation.
computational linguistics, 33(2):201–228.
J. Clarke and M. Lapata. 2008. Global Inference for Sentence Compression An Integer Linear Programming
Approach. JAIR, 31:399–429.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz, and
Y. Singer. 2006. Online Passive-Aggressive Algorithms. JMLR, 7:551–585.
J. Duchi, S. Shalev-Shwartz, Y. Singer, and T. Chandra.
2008. Efficient projections onto the L1-ball for learning in high dimensions. In ICML.
J. Eckstein and D. Bertsekas. 1992. On the DouglasRachford splitting method and the proximal point algorithm for maximal monotone operators. Mathematical Programming, 55(1):293–318.
J. R. Finkel, A. Kleeman, and C. D. Manning. 2008. Efficient, feature-based, conditional random field parsing.
Proceedings of ACL-08: HLT, pages 959–967.

D. Gabay and B. Mercier. 1976. A dual algorithm forthe solution of nonlinear variational problems via finite
element approximation. Computers and Mathematics
with Applications, 2(1):17–40.
J. Giménez and L. Marquez. 2004. Svmtool: A general pos tagger generator based on support vector machines. In Proc. of LREC.
R. Glowinski and P. Le Tallec. 1989. Augmented Lagrangian and operator-splitting methods in nonlinear
mechanics. Society for Industrial Mathematics.
R. Glowinski and A. Marroco.
1975.
Sur
l’approximation, par éléments finis d’ordre un, et larésolution, par penalisation-dualité, d’une classe deproblèmes de Dirichlet non linéaires. Rev. Franc. Automat. Inform. Rech. Operat., 9:41–76.
M. Hestenes. 1969. Multiplier and gradient methods.
Jour. Optim. Theory and Applic., 4:302–320.
L. Huang and K. Sagae. 2010. Dynamic programming
for linear-time incremental parsing. In Proc. of ACL,
pages 1077–1086.
R. Johansson and P. Nugues. 2008. Dependency-based
Semantic Role Labeling of PropBank. In EMNLP.
V. Jojic, S. Gould, and D. Koller. 2010. Accelerated dual
decomposition for MAP inference. In ICML.
N. Komodakis, N. Paragios, and G. Tziritas. 2007.
MRF optimization via dual decomposition: Messagepassing revisited. In ICCV.
T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL, pages 1–11.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with nonprojective head automata. In EMNLP.
A. Kulesza and F. Pereira. 2007. Structured Learningwith Approximate Inference. NIPS.
P. Liang, M.I. Jordan, and D. Klein. 2011. Learning
dependency-based compositional semantics. In Proc.
Association for Computational Linguistics (ACL).
A. F. T. Martins and N. A. Smith. 2009. Summarization
with a joint model for sentence extraction and compression. In NAACL-HLT Workshop on Integer Linear
Programming for NLP.
A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing.
2008. Stacking dependency parsers. In EMNLP.
A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009a.
Concise integer linear programming formulations for
dependency parsing. In ACL-IJCNLP.
A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009b.
Polyhedral outer approximations with application tonatural language parsing. In ICML.
A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T.
Figueiredo, and P. M. Q. Aguiar. 2010. Turbo parsers:
Dependency parsing by approximate variational inference. In EMNLP.

A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar,
N. A. Smith, and E. P. Xing. 2011. An Augmented
Lagrangian Approach to Constrained MAP Inference.
In ICML.
R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In CoNLL.
O. Meshi and A. Globerson. 2011. An Alternating Direction Method for Dual MAP LP Relaxation. In ECML
PKDD.
J. Nivre and R. McDonald. 2008. Integrating graphbased and transition-based dependency parsers. In
ACL-HLT.
J. Nivre, J. Hall, J. Nilsson, G. Eryiǧit, and S. Marinov.
2006. Labeled pseudo-projective dependency parsing
with support vector machines. In Procs. of CoNLL.
S. Petrov and D. Klein. 2008. Sparse multi-scale grammars for discriminative latent variable parsing. In
Proc. of EMNLP.
M. Powell. 1969. A method for nonlinear constraints inminimization problems. In R. Fletcher, editor, Optimization, pages 283–298. Academic Press.
M. Richardson and P. Domingos. 2006. Markov logic
networks. Machine Learning, 62(1):107–136.
S. Riedel and J. Clarke. 2006. Incremental integer linear
programming for non-projective dependency parsing.
In EMNLP.
A. M. Rush and M. Collins. 2011. Exact decoding ofsyntactic translation models through lagrangian relaxation. In ACL.
A. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010.
On dual decomposition and linear programming relaxations for natural language processing. In EMNLP.
N. Shor.
1985.
Minimization methods for nondifferentiable functions. Springer.
D. Smith and J. Eisner. 2008. Dependency parsing bybelief propagation. In EMNLP.
D. Sontag, T. Meltzer, A. Globerson, Y. Weiss, andT Jaakkola. 2008. Tightening LP relaxations for MAP
using message-passing. In UAI.
M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez, andJ. Nivre. 2008. The CoNLL-2008 shared task on
joint parsing of syntactic and semantic dependencies.
CoNLL.
B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin
Markov networks. In NIPS.
R.W. Tromble and J. Eisner. 2006. A fast finite-state
relaxation method for enforcing global constraints on
sequence decoding. In Proc. of NAACL, pages 423–
430.
M. Wainwright and M. Jordan. 2008. Graphical Models,Exponential Families, and Variational Inference. Now
Publishers.

H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In
IWPT.