An Augmented Lagrangian Approach to Constrained MAP Inference

André F. T. Martins†‡
afm@cs.cmu.edu
Mário A. T. Figueiredo‡
mario.figueiredo@lx.it.pt
Pedro M. Q. Aguiar]
aguiar@isr.ist.utl.pt
Noah A. Smith†nasmith@cs.cmu.edu
Eric P. Xing†
epxing@cs.cmu.edu†
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA, USA‡
Instituto de Telecomunicações / ] Instituto de Sistemas e Robótica, Instituto Superior Técnico, Lisboa, Portugal

Abstract
We propose a new algorithm for approximate
MAP inference on factor graphs, by combining augmented Lagrangian optimization withthe dual decomposition method. Each slave
subproblem is given a quadratic penalty,
which pushes toward faster consensus than inprevious subgradient approaches. Our algorithm is provably convergent, parallelizable,
and suitable for fine decompositions of thegraph. We show how it can efficiently handle problems with (possibly global) structural
constraints via simple sort operations. Experiments on synthetic and real-world data
show that our approach compares favorablywith the state-of-the-art.

1. Introduction
Graphical models enable compact representations ofprobability distributions, being widely used in computer vision, natural language processing (NLP), andcomputational biology (Koller & Friedman, 2009). A
prevalent problem is the one of inferring the most probable configuration, the so-called maximum a posteriori(MAP). Unfortunately, this problem is intractable, except for a limited class of models. This fact precludes
computing the MAP exactly in many important models involving non-local features or requiring structural
constraints to ensure valid predictions.
A significant body of research has thus been placed on
approximate MAP inference, e.g., via linear programming relaxations (Schlesinger, 1976). Several messagepassing algorithms have been proposed that exploit
Appearing in Proceedings of the 28 th International Conference on Machine Learning, Bellevue, WA, USA, 2011.
Copyright 2011 by the author(s)/owner(s).

the graph structure in these relaxations (Wainwrightet al., 2005; Kolmogorov, 2006; Werner, 2007; Globerson & Jaakkola, 2008; Ravikumar et al., 2010). In thesame line, Komodakis et al. (2007) proposed a method
based on the classical dual decomposition technique(DD; Dantzig & Wolfe 1960; Everett III 1963; Shor
1985), which breaks the original problem into a setof smaller (slave) subproblems, splits the shared variables, and tackles the Lagrange dual with the subgradient algorithm. Initially applied in computer vision,
DD has also been shown effective in NLP (Koo et al.,2010). The drawback is that the subgradient algorithm
is very slow to converge when the number of slaves islarge. This led Jojic et al. (2010) to propose an accelerated gradient method by smoothing the objective.
In this paper, we ally the simplicity of DD withthe effectiveness of augmented Lagrangian methods,
which have a long-standing history in optimization(Hestenes, 1969; Powell, 1969; Glowinski & Marroco,
1975; Gabay & Mercier, 1976; Boyd et al., 2011). The
result is a novel algorithm for approximate MAP inference: DD-ADMM (Dual Decomposition with the Alternating Direction Method of Multipliers). Rather
than placing all efforts in attempting progress inthe dual, DD-ADMM looks for a saddle point of
the Lagrangian function, which is augmented with aquadratic term to penalize slave disagreements. Keyfeatures of DD-ADMM are:• It is suitable for heavy parallelization (many slaves);• it is provably convergent, even when each slave subproblem is only solved approximately;• consensus among slaves is fast, by virtue of thequadratic penalty term, hence it exhibits faster convergence in the primal than competing methods;• in addition to providing an optimality certificate forthe exact MAP, it also provides guarantees that the
LP-relaxed solution has been found.

An Augmented Lagrangian Approach to Constrained MAP Inference

After providing the necessary background (Sect. 2)
and introducing and analyzing DD-ADMM (Sect. 3),
we turn to the slave subproblems (Sect. 4). Of particular concern to us are problems with structural constraints, which arise commonly in NLP, vision, andother structured prediction tasks. We show that, forseveral important constraints, each slave can be solved
exactly and efficiently via sort operations. Experiments with pairwise MRFs and dependency parsing(Sect. 5) testify to the success of our approach.

2. Background2.1. Problem Formulation
Let X , (X1 , . . . , XN ) ∈ X be a vector of discreterandom variables, where each Xi ∈ Xi , with Xi a finite set. We assume that X has a Gibbs distribution
associated with a factor graph G (Kschischang et al.,2001), composed of a set of variable nodes {1, . . . , N }and a set of factor nodes A, with each a ∈ A linked toa subset of variables N(a) ⊆ {1, . . . , N }:PPNPθ,φ (x) ∝ exp
i=1 θi (xi ) +a∈A φa (xa ) . (1)Above, xa stands for the subvector indexed by the elements of N(a), and θi (.) and φa (.) are, respectively,
unary and higher-order log-potential functions. To accommodate hard constraints, we allow these functions
to take values in R ∪ {−∞}. For simplicity, we writeθ i , (θi (xi ))xi ∈Xi and φa , (φa (xa ))xa ∈Xa .
We are interested in the task of finding the most probable assignment (the MAP), x̂ , arg maxx∈X Pθ,φ (x).
This (in general NP-hard) combinatorial problem canbe transformed into a linear program (LP) by introducing marginal variables µ , (µi )ni=1 and ν ,(ν a )a∈A , constrained to the marginal polytope of G,
i.e., the set of realizable marginals (Wainwright & Jordan, 2008). Denoting this set by M(G), this yields
P >
P >
OPT ,
max
(2)
i θ i µi +a φa ν a ,(µ,ν)∈M(G)which always admits an integer solution. Unfortunately, M(G) often lacks a concise representation,
which renders (2) intractable. A common workaroundis to replace M(G) by the outer bound L(G) ⊇ M(G)—the so-called local polytope, defined as
1> µi = 1, ∀i ∧
L(G) = (µ, ν) Hia ν a = µi , ∀a, i ∈ N(a) ∧,ν a ≥ 0, ∀a(3)where Hia (xi , xa ) = 1 if [xa ]i = xi , and 0 otherwise.
This yields the following LP relaxation of (2):P >P >OPT0 ,max(4)i θ i µi +a φa ν a ,(µ,ν)∈L(G)which will be our main focus throughout. Obviously,
OPT0 ≥ OPT, since L(G) ⊇ M(G).
2.2. Dual Decomposition
Several message passing algorithms (Wainwright et al.,2005; Kolmogorov, 2006; Globerson & Jaakkola, 2008)
are derived via some reformulation of (4) followed bydualization. The DD method (Komodakis et al., 2007)
reformulates (4) by adding new variables ν ai (for eachfactor a and i ∈ N(a)) that are local “replicas” ofthe marginals µi . Letting N(i) , {a|i ∈ N(a)} anddi = |N(i)| (the degree of node i), (4) is rewritten asP P>−1 > a(5)maxai∈N(a) di θ i ν i + φa ν a
ν,µ

s.t.

(ν aN(a) , ν a ) ∈ M(Ga ),ν ai = µi ,∀a∀a, i ∈ N(a),where Ga is the subgraph of G comprised only offactor a and the variables in N(a), M(Ga ) is thecorresponding marginal polytope, and we denoteν aN(a) , (ν ai )i∈N(a) . (Note that by definition, L(G) ={(µ, ν) | (µNa , ν a ) ∈ M(Ga ), ∀a ∈ A}.) Problem (5)would be completely separable (over the factors) if itwere not the “coupling” constraints ν ai = µi . Introducing Lagrange multipliers λai for these constraints,
the dual problem (master ) becomes



P
a
min L(λ) , a sa d−1i θ i + λi i∈N(a) , φa
λ

P
a
(6)
s.t.
λ∈Λ, λa∈N(i) λi = 0, ∀i ,where each sa corresponds to a slave subproblemX>asa (ω aN(a) , φa ) , amaxω>(7)i ν i + φa ν a .
(ν N(a) ,ν a )i∈N(a)∈M(Ga )

Note that the slaves (7) are MAP problems of the samekind as (2), but local to each factor a. Denote by(ν̂ aN(a) , ν̂ a ) = map(ω aN(a) , φa ) the maximizer of (7).
The master problem (6) can be addressed elegantlywith a projected subgradient algorithm: note that a
subgradient ∇λai L(λ) is readily available upon solving
the ath slave, via ∇λai L(λ) = ν̂ ai . These slaves canbe handled in parallel and then have their solutions
gathered for computing a projection onto Λ, which issimply a centering operation. This results in Alg. 1.
Alg. 1 inherits the properties of subgradient algorithms, hence it converges to the optimal value of
OPT0 in (4) if the stepsize sequence (ηt )t∈T is diminishing and nonsummable (Bertsekas et al., 1999). In
practice, convergence can be quite slow if the numberof slaves is large. This is because it may be hard toreach a consensus on variables with many replicas.

An Augmented Lagrangian Approach to Constrained MAP Inference

Algorithm 1 DD-Subgradient

Algorithm 2 DD-ADMM

1: input: factor graph G, parameters θ, φ, number of
iterations T , stepsize sequence (ηt )Tt=1
2: Initialize λ = 0
3: for t = 1 to T do
4:for each factor a ∈ A doa5:
Set ω ai = d−1i θ i + λi , for i ∈ N(a)a6:Compute (ν̂ N(a) , ν̂ a ) = map ω aN(a) , φa7:
end forP
8:
Compute average µi = di −1 a:i∈N(a) ν̂ ai
9:Update λai ← λai − ηt (ν̂ ai − µi )10: end for
11: output: λ

1: input: factor graph G, parameters θ, φ, number of
iterations T , sequence (ηt )Tt=1 , parameter τ
2: Initialize µ uniformly, λ = 0
3: for t = 1 to T do
4:for each factor a ∈ A doa5:
Set ω ai = d−1i θ i + λi + ηt µi , for i ∈ N(a)a6:
Update (ν N(a) , ν a ) ← quadηt ω aN(a) , φa7:
end forP
8:Update µi ← di −1 a:i∈N(a) ν ai − ηt−1 λai
9:Update λai ← λai − τ ηt (ν ai − µi )10: end for
11: output: µ, ν, λ3. Augmented Lagrangian Methodneeds to solve a QP of the form

In this section we introduce a faster method, DDADMM, which replaces the MAP computation ateach factor a by a (usually simple) quadratic problem (QP); this method penalizes disagreements amongslaves more aggressively than the subgradient method.

ηt Xkν ai − ηt−1 ω ai k2 − φ>a ν a . (12)(ν a,ν a )∈M(Ga ) 2N(a)Given an optimization problem with equality constraints, the augmented Lagrangian (AL) function is
the Lagrangian augmented with a quadratic constraint
violation penalty. For the constraint problem (5), it is

X X

a > a
ν i + φ>d−1
Aη (µ, ν, λ) ,a νai θ i + λia−i∈N(a)

η>λai µi −2
a i∈N(a)XXXXkν ai − µi k2 ,(8)

a i∈N(a)where η controls the weight of the penalty. Applied
to our problem, a traditional AL method (Hestenes,
1969; Powell, 1969) would alternate between the joint
maximization of Aη (µ, ν, λ) w.r.t. µ and ν, and an update of the Lagrange multipliers λ. Unfortunately, thequadratic term in (8) breaks the separability, making
the joint maximization w.r.t. µ and ν unappealing.
We bypass this problem by using the alternating direction method of multipliers (ADMM; Gabay & Mercier
1976; Glowinski & Marroco 1975), in which the joint
maximization is replaced by a single Gauss-Seidel step.
This yields the following updates:
ν (t) ← argmax Aηt (µ(t−1) , ν, λ(t−1) ),

(9)

min

i∈N(a)The resulting algorithm is DD-ADMM (Alg. 2). Let
quadηt(ω N(a) , φa ) denote the solution of (12); as ηt →0, quadηt (ω N(a) , φa ) approaches map(ω N(a) , φa ),hence Alg. 2 approaches Alg. 1. However, DD-ADMM
converges without the need of decreasing ηt :Proposition 1 Let (µ(t) , ν (t) , λ(t) )t be the sequenceof iterates√produced by Alg. 2 with a fixed ηt = η and0 < τ ≤ ( 5 + 1)/2 ' 1.61. Then the following holds:
1. Primal feasibility of (5) is achieved in the limit,a(t)(t)
i.e., kν i − µi k → 0, ∀a ∈ A, i ∈ N(a);2. (µ(t) , ν (t) ) converges to an optimal solution of (4);3. λ(t) converges to an optimal solution of (6);4. λ(t) is always dual feasible; hence the objective of(6) evaluated at λ(t) approaches OPT0 from above.
Proof: 1, 2, and 3 are general properties of ADMM algorithms (Glowinski & Le Tallec, 1989, Thm. 4.2). All
necessary conditions are met: problem (5) is convex
and the coupling constraint can be written in the form
(ν aN(a) )a∈A = M µ where M has full column rank. To
show 4, use induction: λ(0) = 0 ∈ Λ; if λ(t−1) ∈ Λ,Pa(t−1)
i.e., a∈N(i) λi= 0, ∀i, then, after line 9,νµ(t) ← argmax Aηt (µ, ν (t) , λ(t−1) ),
(10)
µ


a(t)
a(t−1)a(t)(t)λ i ← λi− τ ηt ν i − µi , ∀a, i ∈ N(a). (11)


X

a(t)

λi

a∈N(i)=λi− τ ηt a∈N(i)= (1 − τ )Crucially, the maximization w.r.t. µ (10) has a closed
form, while that w.r.t. ν (9) can be carried out inparallel at each factor, as in Alg. 1. The only differenceis that, instead of computing the MAP, each slave now

a(t−1)

X


X

a(t)

νi

(t)

− di µi a∈N(i)

Xa(t−1)λi= 0 ⇒ λ(t) ∈ Λ.

a∈N(i)

Prop. 1 reveals yet another important feature of DDADMM: after a sufficient decrease of the residual term,

An Augmented Lagrangian Approach to Constrained MAP Inference

P P
say a i∈N(a) kν ai − µi k2 < , we have at hand a feasible primal-dual pair. If, in addition, the dualitygap (difference between (4) and (6)) is < δ, then weare in possession of an (, δ)-optimality certificate forthe LP relaxation. Such a certificate is not readily
available in Alg. 1, unless the relaxation is tight.
The next proposition, based on results of Eckstein& Bertsekas (1992), states that convergence may still
hold if (12) is solved approximately.
Proposition 2 Let ηt = η be fixed and τ = 1. Con(t)sider the sequence of residuals r (t) , (ra )a∈A , where
a(t)

(t)

ra(t) , k(ν N(a) , ν (t)a ) − quadηt(ω N(a) , φa )k.
P∞
Then, Prop. 1 still holds provided t=1 kr (t) k < ∞.

4. Solving the Slave Subproblems
We next show how to efficiently solve (12). Several
cases admit closed-form solutions: binary pairwise factors, some factors expressing hard constraints, and factors linked to multi-valued variables, once binarized.
In all cases, the asymptotic computational cost is thesame as that of MAP computations, up to a logarithmic factor. Detailed proofs of the following facts areincluded as supplementary material.
4.1. Binary pairwise factors
If factor a is binary and pairwise (|N(a)| = 2), problem(12) can be re-written as the minimization of 21 (z1 −c1 )2 + 12 (z2 − c2 )2 − c12 z12 , w.r.t. (z1 , z2 , z12 ) ∈ [0, 1]3 ,under the constraints z12 ≤ z1 , z12 ≤ z2 , and z12 ≥z1 +z2 −1, where c1 , c2 and c12 are functions of ω ai andφa . Considering c12 ≥ 0, without loss of generality (ifc12 < 0, we recover this case by redefining c01 = c1 +c12 ,0
c02 = 1 − c2 , c012 = −c12 , z20 = 1 − z2 , z12= z1 − z12 ),the lower bound constraints z12 ≥ z1 + z2 − 1 andz12 ≥ 0 are always innactive and can be ignored. By
inspecting the KKT conditions we obtain the following∗
closed-form solution: z12= min{z1∗ , z2∗ } and
if c1 > c2 + c12 ([c1 ]U , [c2 + c12 ]U )([c1 + c12 ]U , [c2 ]U )if c2 > c1 + c12∗ ∗(z1 , z2 ) =
([(c
+
c
+
c
)/2]
,

1
2
12
U


[(c1 + c2 + c12 )/2]U ) otherwise,
where [x]U = min{max{x, 0}, 1} denotes the projection (clipping) onto the unit interval.
4.2. Hard constraint factors
Many applications, e.g., in error-correcting coding(Richardson & Urbanke, 2008) and NLP (Smith & Eisner, 2008; Martins et al., 2010; Tarlow et al., 2010)

involve hard constraint factors—these are factors withindicator log-potential functions: φa (xa ) = 0, if xa ∈Sa , and −∞ otherwise, where Sa is an acceptance set.
For binary variables, these factors impose logical constraints; e.g.,• the one-hot xor factor,
Pn for which Sxor{(x1 , . . . , xn ) ∈ {0, 1}n | i=1 xi = 1},=• the or W
factor, for which Sor = {(x1 , . . . , xn ) ∈n{0, 1}n | i=1 xi = 1},• the or-with-output factor,
Wn−1 for which Sor-out ={(x1 , . . . , xn ) ∈ {0, 1}n | i=1 xi = xn }.
Variants of these factors (e.g., with negated inputs/outputs) allow computing a wide range of otherlogical functions. It can be shown that the marginal
polytope of a hard factor with binary variables andacceptance set Sa is defined by z ∈ conv Sa , wherez , (µ1 (1), . . . , µn (1)) and conv denotes the convex
hull. Letting c , (ωai (1) + 1 − ωai (0))i∈N(a) , problem(12) is that of minimizing kz − ck2 s.t. z ∈ conv Sa ,which is a Euclidean projection onto a polyhedron:• conv Sxor is the probability simplex; the projection
is efficiently obtained via a sort (Duchi et al., 2008).
• conv Sor is a “faulty” hypercube with a vertex removed, and conv Sor-out is a pyramid whose base is a
hypercube with a vertex removed; both projections
can be efficiently computed with sort operations.
The algorithms and proofs of correctness are provided
as supplementary material. In all cases, complexity isO(|N(a)| log |N(a)|) and can be improved to O(|N(a)|)
using a technique similar to Duchi et al. (2008).
4.3. Larger slaves and multi-valued variables
For general factors, a closed-form solution of problem(12) is not readily available. One possible strategy (exploiting Prop. 2) is to use an inexact algorithm that
becomes sufficiently accurate as Alg. 2 proceeds; thiscan be achieved by warm-starting with the solution obtained in the previous iteration. This strategy can be
useful for handling coarser decompositions, in which
each factor is a subgraph such as a chain or a tree.
However, unlike the map problem in DD-subgradient,in which dynamic programming can be used to compute an exact solution for these special structures, that
does not seem possible in quad.
Yet, there is an alternative strategy for handling multivalued variables, which is to binarize the graph andmake use of the results established in Sect. 4.2 for hardconstraint factors. We illustrate this procedure for
pairwise MRFs (but the idea carries over when higher
order potentials are used): let X1 , . . . , XN be the variables of the original graph, and E ⊆ {1, . . . , N }2 beAn Augmented Lagrangian Approach to Constrained MAP Inference

Figure 1. Results for 30 × 30 random Ising models with several edge couplings. We plot the dual objectives and the best
primal feasible solution at each iteration. For DD-subgradient, we set ηt = η0 /t, with η0 yielding the maximum dual
improvement in 10 iterations, with halving steps (those iterations are not plotted). For DD-Acc we plot the most favorable ∈ {0.1, 1, 10, 100}. For DD-ADMM, we set η = 5.0 and τ = 1.0. All decompositions are edge-based.

the set of edges. Let M = |E| be the number of edges
and L = |Xi |, ∀i the number of labels. Then:• For each node i, define binary variables Uik for eachpossible k ∈ {1, . . . , L} of Xi . Link these variablesPLto a xor factor, imposing k=1 µi (k) = 1, ∀i.
• For each edge (i, j) ∈ E, define binary variables
Uijkk0 for each value pair (k, k 0 ) ∈ {1, . . . , L}2 . Link
variables {Uijkk0 }L
k0 =1 and ¬Uik to a xor factor, foreach k ∈ {1, . . . , L}; and link variables {Uijkk0 }L
k=1
and ¬Ujk0 to a xor factor for each k 0 ∈ {1, . . . , L}.
PL
These impose constraints µi (k) = k0 =1 µij (k, k 0 ),Pl∀k, and µj (k 0 ) = k=1 µij (k, k 0 ), ∀k 0 .
The constraints above define a local polytope whichis equivalent to the one of the original graph, hence
problem (4) is the same for both graphs. This processincreases the number of factors to N + 2M L, where
each is a xor of size L or L + 1. However, solving
quad for each of these factors only costs O(L log L)(see Sect. 4.2), hence the overall cost per iteration of
Alg. 2 is O(M L2 log L) if the graph is connected. Up
to a log factor, this is the same as message-passing
algorithms or DD-subgradient when run in the originalgraph, which have O(M L2 ) cost per iteration.

5. Experiments
We compare DD-ADMM (Alg. 2) with four other approximate MAP inference algorithms:• Star-MSD (Sontag et al., 2011), an acceleration of
the max-sum diffusion algorithm (Kovalevsky & Koval, 1975; Werner, 2007) based on star updates;• Generalized MPLP (Globerson & Jaakkola, 2008);• DD-subgradient (Komodakis et al. 2007, Alg. 1);• DD-Acc (accelerated DD, Jojic et al. 2010).

All these algorithms address problem (4) with thesame cost per iteration: the first two use messagepassing, performing block coordinate descent in thedual; DD-Acc uses a smoothed dual objective byadding an entropic term to each subproblem, and thenapplies optimal first-order methods (Nesterov, 1983),
yielding O(1/) complexity. The primal and dual objectives are the same for all algorithms.
5.1. Binary Pairwise MRFs
Fig. 1 shows typical plots for an Ising model (binary
pairwise MRF) on a random grid, with single node logpotentials chosen as θi (1)−θi (0) ∼ U[−1, 1] and mixededge couplings in U[−ρ, ρ], where ρ ∈ {0.5, 1, 1.5, 2}.
Decompositions are edge-based for all methods. For
MPLP and Star-MSD, primal feasible solutions (x̂i )N
i=1
were obtained by decoding the single node messages, as
in Globerson & Jaakkola (2008); for the DD methods
we use x̂i = argmaxxi µi (xi ).
We observe that DD-subgradient is the slowest, taking
a long time to find a “good” primal feasible solution,
arguably due to the large number of slave subproblems. Surprisingly, DD-Acc is also not competitivein this setting, as it consumes many iterations before
it reaches a near-optimal region.1 MPLP performs
slightly better than Star-MSD and both are comparable to DD-ADMM in terms of convergence of thedual objective. However, DD-ADMM outperforms allcompetitors at obtaining a “good” feasible primal solution in early iterations (it retrieved the true MAP
in all cases, in ≤ 200 iterations). We conjecture that
this rapid progress in the primal is due to the penalty
term in the AL (8), which is very effective at pushing1

It is conceivable that the early iterations of DD-Acc
could make faster progress by annealing . Here we havejust used the variant described by Jojic et al. (2010).

{ryantm,pereira}@cis.upenn.edu
Kiril Ribarov
Jan Hajič
Institute of Formal and Applied Linguistics
Charles
University
An Augmented Lagrangian Approachto Constrained
MAP Inference{ribarov,hajic}@ufal.ms.mff.cuni.cz

Dual Objective

2025
2020

MPLP
Abstract
DD−AccDD−ADMM
Dual Opt.

root

We formalize weighted dependency parsing as searching for maximum spanning2015
trees (MSTs) in directed graphs. Using
this representation, the parsing algorithm
2010of Eisner (1996) is sufficient for search2005
ing over all projective trees in O(n3 ) time.
More surprisingly, the representation is
0
200
400
600
800
1000
extended naturally to non-projective parsNumber of Iterations
ing using Chu-Liu-Edmonds (Chu andLiu,random
1965; Edmonds,
1967)with
MST alFigure 2. Results for a 20 × 20
Potts model2 ) parsing al8-valued nodes and coupling gorithm,
factor ρyielding= 10. anWeO(nplotthegorithm. We evaluate these methods
dual objectives, and the value of the true dual optimum.
on the Prague Dependency Treebank usFor DD-Acc,  = 1.0; for DD-ADMM, η = 0.5, τ = 1.0.
ing online large-margin learning techniques (Crammer et al., 2003; McDonald
et al.,
2005)relaxedand showLP.
that MST parsing
for a feasible primal solutionof theincreases efficiency and accuracy for languages with non-projective dependencies.

John

hit

the

ball

with

the

bat

Figure 1: An example dependency tree.
SIB

SIB

SIB

(h,m�,m�)
12 (h,m�,m�)2
3 (h,m�,m�)
Dependency
representations,which
link1words
to
3
GRAND
their arguments,
have
a
long
history(Hudson,1984).
(g,h,m�)1
Figure 1 shows a dependency tree for the sentenceJohn hit the ball with the bat. We restrict ourselvesto dependency tree
analyses,ARC
in which ARC
each word deARC
ARC(h,m�)(h,m�)
3 word or apends on(g,h)
exactly(h,m�)
one1parent,
eitheranother2dummy root symbol as shown in the figure. The tree
in Figure 1 is projective, meaning that if we put thewords in their linear order, preceded by the root, theedges can be drawn above the TREE
words without crossings, or, equivalently, a word and its descendants
formXORa contiguous substring of
the sentence.
OR
SINGLE-PARENT

FLOW-IMPLIES-ARC(h,m,k)(m)
In English, projective
trees are sufficient
to analyze most sentence types. In fact, the largest sourceof English dependency trees is automatically gener5.2. Multi-valued Pairwise MRFs
ARC
FLOW
ARC
ARCthe Penn Treebank
ated from(Marcuset al.,(h,m)1993)(h,m,k)(n,m)(0,m)
To assess the effectivenessof
DD-ADMMinthenonandisbyconvention
exclusively
projective.
How1 Introduction
ever,
there are certain examplesFLOW-DELTA
in which a nonbinary case, we evaluated it against DD-Acc and
PATH-BUILDER
XOR
(h,k)
(m,k) tree is preferable. Consider
parsingpairwise
has seen MRF)
a surge of inter- projective
the sentence
MPLP in a Potts modelDependency(multi-valued
est lately for applications such as relation extrac- John saw a dog yesterday which was a Yorkshire Terwith single node log-potentials chosen as θi (xi ) ∼tion (Culotta and Sorensen, 2004), machine trans- rier. Here the relative clause which was a Yorkshire
U[−1, 1] and edge log-potentials
θij (x∼ genera- Terrier and the object it modifies (the dog) are sepi , xj )synonym
lation (Ding and as
Palmer,2005),
U[−10, 10] if xi = xj and0 otherwise.
For DD-Acc
FLOWis no
FLOW
PATHTheretion (Shinyama
et al., 2002),
and lexical resource arated
an adverb.
way PATH
to draw the
FLOWby FLOW(m,k) (h,1,k) (h,n,k)(0,m,k) (n,m,k)(Snow
et al., 2004). as
The primary dependency
tree forthis sentence in the (h,k)
plane withand MPLP, we used theaugmentation
same edge
decomposition
using dependency
structures instead of no crossing edges, as illustrated in Figure 2. In lanbefore, since they can reasons
handleformulti-valued
variables;
Figure
Top:witha moredependency
parse
tree,
more informative
phraseinstructures
is 3.
guagesflexible wordorder
than where
English,each arc
for DD-ADMM we binarized
the graphlexicalized
as describedthat they are more efficient to learn and parse (h,whilesuch asGerman,Dutchanda Czech,
non-projectivem) linksa headword
h tomodifier
word m. Middle:
Sect. 4.3. Fig. 2 shows thebest dual solutions obtained
still encoding much of the predicate-argument tree-based
infor- dependencies
are morefrequent. Rich
factor graphcorresponding
toinflection
a second-orderat each iteration for themation
threeneededalgorithms.
We observein applications.
systems
reduce model
reliance withon wordorder andto express
dependency
parsingsibling
grandparent

that MPLP decreases the objective very rapidly in the
beginning and then slows down. DD-Acc manages toconverge faster, but it is relatively slow to take off.
DD-ADMM has the best features of both methods.

features, including a tree hard constraint factor. Bottom:
the flow-based factor graph is an alternative representation
for the same model, in which extra flow and path variables
are added, and the tree factor is replaced by smaller xor,or and or-out. See Martins et al. (2010) for details.

5.3. Dependency Parsing
A third set of experiments aims at assessing the ability of DD-ADMM for handling problems with heavily
constrained outputs. The task is non-projective dependency parsing of natural language sentences, to which
DD approaches have recently been applied (Koo et al.,2010). Fig. 3 depicts an example of a sentence (theinput) and its dependency tree (the output to be predicted). Second-order models are state-of-the-art forthis task: they include scores for each possible arc andfor certain pairs of arcs (e.g., siblings and grandparents); the goal is to find a directed spanning tree maximizing the overall score.
We experimented with two factor graphs that represent this problem (see Fig. 3). Both models have hardconstraints on top of a binary pairwise MRF whose
nodes represent arc candidates and whose edges link
pairs of arcs which bear a sibling or grandparent rela-tionship. The “tree” model has a tree hard constraint
factor connected to all nodes enforcing the overall assignment to be a directed spanning tree (Smith & Eisner, 2008). Unfortunately, handling this factor poses
difficulties for all methods except DD-subgradient.2
2

Further information about the combinatorial tree factor can be found in Martins et al. (2010) and references
therein. Briefly, solving the map subproblem (necessaryfor DD-subgradient) corresponds to finding a maximum
weighted arborescence, which can be done in O(n2 ) time,
where n is the number of words in the sentence (Tarjan,
1977). Computing all posterior marginals (necessary for
DD-Acc) can be done in O(n3 ) time invoking the matrixtree theorem (Smith & Smith, 2007; Koo et al., 2007; McDonald & Satta, 2007). Unfortunately, this procedure suffers from severe numerical problems in the low-temperature
setting, which prevents its use in DD-Acc where the temperature must be set as O(/(n log n)). Finally, no efficientalgorithm is currently known for the simultaneous computation of all max-marginals in the tree factor (which

An Augmented Lagrangian Approach to Constrained MAP InferenceThis is illustrated in Fig. 4, which shows that DDsubgradient converges slowly, even with the more favorable tree-based factor graph (both for synthetic andreal-world data). For this problem, MPLP and StarMSD also have poor performance, while DD-ADMM
manages to converge to a near-optimal solution very
fast (note the sharp decrease in relative error on thebottom plot, compared with DD-subgradient). This
has an impact in final accuracy: setting a maximumof 1000 iterations for all algorithms gave DD-ADMM
an advantage of > 1.5% in unlabeled attachment score(fraction of words with the correct head attached), in
the Penn Treebank dataset.

6. Related Work and Final Remarks
DD-subgradient was first proposed for image segmentation using pairwise (Komodakis et al., 2007) andhigher order factor graphs (Komodakis & Paragios,2009). It was recently adopted for NLP (Koo et al.,2010), with only a few slave subproblems handled withdynamic programming or combinatorial algorithms.
Johnson et al. (2007) proposed smoothing the objective by adding an entropic term to each subproblem,with the goal of enabling gradient-based optimization;
each subproblem becomes that of computing marginals
at a particular temperature. Jojic et al. (2010) combined this with optimal first order methods to accelerate DD to O(1/) complexity. This rate, however, relies on the ability to compute low-temperature
marginals with arbitrary precision, which poses problems for some of the hard constraint factors considered in this paper. In contrast, DD-ADMM uses exact
solutions of the corresponding slave subproblems, efficiently computed using sort operations (see Sect. 4.2).
We point out that replacing the quadratic penalty of
the AL (8) by an entropic one would not lead to thesame subproblems as in Jojic et al. (2010): it would
lead to the problem of minimizing non-strictly conwould be necessary for MPLP and Star-MSD); or for computing an Euclidean projection onto the arborescence polytope (which would be necessary for DD-ADMM).

Synthetic

Dual Objective

40
Star−MSD
MPLP
DD−Subgrad
DD−Subgrad (tree)
DD−ADMM

35
30
25
20
15
1

2

10

Average Relative Error

The “flow” model imposes the same global constraint
by adding extra variables and several xor, or andor-out factors (Martins et al., 2010). The two models have the same expressive power, and differ fromthe one in Koo et al. (2010), which combines a tree
constraint with factors that emulate head automata(instead of all pairs of arcs) and has fewer slaves. In
our case, both factor graphs yield O(n3 ) slaves (n isthe number of words in the sentence), degrading theperformance of standard DD methods.

10
10
10
10
10
10

3

10
Number of Iterations
Penn Treebank

10

0
−1
−2
−3
−4
−5

Star−MSD
MPLP
DD−Subgrad
DD−Subgrad (tree)
DD−ADMM
1

10

10Number of Iterations

2

3

10

Figure 4. Dependency parsing with 2nd-order models. For
DD-subgradient, we consider both tree-based and flowbased factor graphs, and η0 as in Fig. 1. DD-ADMM(η = 0.05, τ = 1.5), MPLP, and Star-MSD ran only on theflow-based factor graph (see footnote 2). DD-Acc is notshown due to numerical problems when computing some
low-temperature marginals. Top: synthetic 10-word sentences; we randomly generated (unary) arc log-potentials
from N(0, 1) and (pairwise) grandparent and sibling logpotentials from N(0, 0.1). Bottom: §23 of the Penn Treebank; the plot shows relative errors per iteration w.r.t. thedual optimum, averaged over the 2,399 test sentences.

vex free energies with different counting numbers. Although extensions of ADMM to Bregman penalties
have been considered in the literature, convergence has
been shown only for quadratic penalties.
Quadratic problems were also recently considered in asequential algorithm (Ravikumar et al., 2010); however, that algorithm tackles the primal formulationand only pairwise models are considered. A similar
cyclic projection can be adopted in DD-ADMM to approximately solve quad for larger slaves.
DD-ADMM is dual decomposable, hence the slaves canbe solved in parallel, making it suitable for multi-corearchitectures with obvious speed-ups. A significant
amount of computation can be saved by caching andwarm-starting the subproblems, which tend to become
more and more similar across later iterations.
In the future, we plan to experiment with larger slaves,by using approximate ADMM steps as enabled by
Prop. 2. The encouraging results of DD-ADMM forsolving LP relaxations suggest that it can also be useful for tightening these relaxations towards the true
MAP, as the MPLP algorithm in Sontag et al. (2008).

An Augmented Lagrangian Approach to Constrained MAP Inference

Acknowledgments
A. M. was supported by a FCT/ICTI grant through the
CMU-Portugal Program, and also by Priberam. This work
was partially supported by the FET programme (EU FP7),
under the SIMBAD project (contract 213250), and by a
FCT grant PTDC/EEA-TEL/72572/2006. N. S. was supported by NSF CAREER IIS-1054319. E. X. was supported by AFOSR FA9550010247, ONR N000140910758,
NSF CAREER DBI-0546594, NSF IIS-0713379, and an Alfred P. Sloan Fellowship.

References
Bertsekas, D., Hager, W., and Mangasarian, O. Nonlinear
programming. Athena Scientific, 1999.
Bertsekas, D.P., Nedic, A., and Ozdaglar, A.E. Convex
analysis and optimization. Athena Scientific, 2003.
Boyd, S., Parikh, N., Chu, E., Peleato, B., and Eckstein, J.
Distributed Optimization and Statistical Learning via theAlternating Direction Method of Multipliers (to appear).
Now Publishers, 2011.
Boyle, J.P. and Dykstra, R.L. A method for finding projections onto the intersections of convex sets in Hilbert
spaces. In Advances in order restricted statistical inference, pp. 28–47. Springer Verlag, 1986.
Dantzig, G. and Wolfe, P. Decomposition principle for linear programs. Operations Research, 8(1):101–111, 1960.
Duchi, J., Shalev-Shwartz, S., Singer, Y., and Chandra, T.
Efficient projections onto the L1-ball for learning in highdimensions. In ICML, 2008.
Eckstein, J. and Bertsekas, D. On the Douglas-Rachford
splitting method and the proximal point algorithm for
maximal monotone operators. Mathematical Programming, 55(1):293–318, 1992.
Everett III, H. Generalized Lagrange multiplier method
for solving problems of optimum allocation of resources.
Operations Research, 11(3):399–417, 1963.
Gabay, D. and Mercier, B. A dual algorithm for the solution of nonlinear variational problems via finite element
approximation. Computers and Mathematics with Applications, 2(1):17–40, 1976.
Globerson, A. and Jaakkola, T. Fixing max-product:
Convergent message passing algorithms for MAP LPrelaxations. NIPS, 20, 2008.
Glowinski, R. and Le Tallec, P. Augmented Lagrangianand operator-splitting methods in nonlinear mechanics.
Society for Industrial Mathematics, 1989.
Glowinski, R. and Marroco, A. Sur l’approximation,
par éléments finis d’ordre un, et la résolution, parpenalisation-dualité, d’une classe de problèmes deDirichlet non linéaires. Rev. Franc. Automat. Inform.
Rech. Operat., 9:41–76, 1975.
Hestenes, M. Multiplier and gradient methods. Jour. Optim. Theory and Applic., 4:302–320, 1969.
Johnson, J.K., Malioutov, D.M., and Willsky, A.S. Lagrangian relaxation for MAP estimation in graphicalmodels. In 45th Annual Allerton Conference on Communication, Control and Computing, 2007.
Jojic, V., Gould, S., and Koller, D. Accelerated dual decomposition for MAP inference. In ICML, 2010.
Koller, D. and Friedman, N. Probabilistic Graphical Models: Principles and Techniques. The MIT Press, 2009.
Kolmogorov, V. Convergent tree-reweighted message passing for energy minimization. IEEE Trans. Pattern Analysis and Machine Intelligence, 28:1568–1583, 2006.

Komodakis, N. and Paragios, N. Beyond pairwise energies:
Efficient optimization for higher-order MRFs. In CVPR,
2009.
Komodakis, N., Paragios, N., and Tziritas, G. MRF optimization via dual decomposition: Message-passing revisited. In ICCV, 2007.
Koo, T., Globerson, A., Carreras, X., and Collins, M.
Structured prediction models via the matrix-tree theorem. In EMNLP, 2007.
Koo, T., Rush, A. M., Collins, M., Jaakkola, T., andSontag, D. Dual decomposition for parsing with nonprojective head automata. In EMNLP, 2010.
Kovalevsky, V.A. and Koval, V.K. A diffusion algorithm
for decreasing energy of max-sum labeling problem.
Glushkov Institute of Cybernetics, Kiev, USSR, 1975.
Kschischang, F. R., Frey, B. J., and Loeliger, H. A. Factor
graphs and the sum-product algorithm. IEEE Trans.
Information Theory, 47, 2001.
Martins, A., Smith, N., Xing, E., Figueiredo, M., andAguiar, P. Turbo parsers: Dependency parsing by approximate variational inference. In EMNLP, 2010.
McDonald, R. and Satta, G. On the complexity of nonprojective data-driven dependency parsing. In IWPT,
2007.
Nesterov, Y. A method of solving a convex programming
problem with convergence rate O(1/k2 ). Soviet Math.
Doklady, 27:372–376, 1983.
Powell, M. A method for nonlinear constraints in minimization problems. In Fletcher, R. (ed.), Optimization,
pp. 283–298. Academic Press, 1969.
Ravikumar, P., Agarwal, A., and Wainwright, M. Messagepassing for graph-structured linear programs: Proximal
methods and rounding schemes. JMLR, 11:1043–1080,
2010.
Richardson, T.J. and Urbanke, R.L. Modern coding theory.
Cambridge Univ Pr, 2008.
Schlesinger, M. Syntactic analysis of two-dimensional visual signals in noisy conditions. Kibernetika, 4:113–130,
1976.
Shor, N. Minimization methods for non-differentiable functions. Springer, 1985.
Smith, D. and Eisner, J. Dependency parsing by belief
propagation. In EMNLP, 2008.
Smith, D. and Smith, N. Probabilistic models of nonprojective dependency trees. In EMNLP-CoNLL, 2007.
Sontag, D., Meltzer, T., Globerson, A., Weiss, Y., andJaakkola, T. Tightening LP relaxations for MAP using
message-passing. In UAI, 2008.
Sontag, D., Globerson, A., and Jaakkola, T. Introduction
to dual decomposition for inference. In Optimization for
Machine Learning. MIT Press, 2011.
Tarjan, R.E. Finding optimum branchings. Networks, 7(1):25–36, 1977.
Tarlow, D., Givoni, I. E., and Zemel, R. S. HOP-MAP:
Efficient message passing with high order potentials. In
AISTATS, 2010.
Wainwright, M. and Jordan, M. Graphical Models, Exponential Families, and Variational Inference. Now Publishers, 2008.
Wainwright, M., Jaakkola, T., and Willsky, A. MAP estimation via agreement on trees: message-passing andlinear programming. IEEE Trans. Information Theory,51(11):3697–3717, 2005.
Werner, T. A linear programming approach to max-sum
problem: A review. IEEE Trans. Pattern Analysis andMachine Intelligence, 29:1165–1179, 2007.