Turbo Parsers: Dependency Parsing by Approximate Variational Inference
André F. T. Martins∗† Noah A. Smith∗ Eric P. Xing∗∗
School of Computer Science
Carnegie Mellon University
Pittsburgh, PA 15213, USA{afm,nasmith,epxing}@cs.cmu.edu
Mário A. T. Figueiredo††
Instituto de TelecomunicaçõesInstituto Superior Técnico
Lisboa, Portugal
mtf@lx.it.pt

Pedro M. Q. Aguiar‡‡
Instituto de Sistemas e Robótica
Instituto Superior Técnico
Lisboa, Portugal
aguiar@isr.ist.utl.pt
Abstract
We present a unified view of two state-of-theart non-projective dependency parsers, both
approximate: the loopy belief propagationparser of Smith and Eisner (2008) and the relaxed linear program of Martins et al. (2009).
By representing the model assumptions witha factor graph, we shed light on the optimization problems tackled in each method. We also
propose a new aggressive online algorithm tolearn the model parameters, which makes useof the underlying variational representation.
The algorithm does not require a learning rate
parameter and provides a single framework fora wide family of convex loss functions, including CRFs and structured SVMs. Experiments
show state-of-the-art performance for 14 languages.

1

Introduction

Feature-rich discriminative models that break locality/independence assumptions can boost a parser’s
performance (McDonald et al., 2006; Huang, 2008;
Finkel et al., 2008; Smith and Eisner, 2008; Martinset al., 2009; Koo and Collins, 2010). Often, inference with such models becomes computationally intractable, causing a demand for understanding andimproving approximate parsing algorithms.
In this paper, we show a formal connection between two recently-proposed approximate inferencetechniques for non-projective dependency parsing:
loopy belief propagation (Smith and Eisner, 2008)
and linear programming relaxation (Martins et al.,2009). While those two parsers are differently motivated, we show that both correspond to inference ina factor graph, and both optimize objective functions
over local approximations of the marginal polytope.
The connection is made clear by writing the explicit
declarative optimization problem underlying Smithand Eisner (2008) and by showing the factor graphunderlying Martins et al. (2009). The success ofboth approaches parallels similar approximations inother fields, such as statistical image processing anderror-correcting coding. Throughtout, we call theseturbo parsers.1
Our contributions are not limited to dependency
parsing: we present a general method for inferencein factor graphs with hard constraints (§2), which
extends some combinatorial factors considered bySmith and Eisner (2008). After presenting a geometric view of the variational approximations underlying message-passing algorithms (§3), and closing the gap between the two aforementioned parsers(§4), we consider the problem of learning the model
parameters (§5). To this end, we propose an aggressive online algorithm that generalizes MIRA
(Crammer et al., 2006) to arbitrary loss functions.
We adopt a family of losses subsuming CRFs (Lafferty et al., 2001) and structured SVMs (Taskar etal., 2003; Tsochantaridis et al., 2004). Finally, we
present a technique for including features not attested in the training data, allowing for richer models without substantial runtime costs. Our experiments (§6) show state-of-the-art performance on dependency parsing benchmarks.
1

The name stems from “turbo codes,” a class of highperformance 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).

2

Structured Inference and Factor Graphs

Denote by X a set of input objects from which wewant to infer some hidden structure conveyed in an
output set Y. Each input x ∈ X (e.g., a sentence)is associated with a set of candidate outputs Y(x) ⊆Y (e.g., parse trees); we are interested in the casewhere Y(x) is a large structured set.
Choices about the representation of elements ofY(x) play a major role in algorithm design. In
many problems, the elements of Y(x) can be represented as discrete-valued vectors of the form y =hy1 , . . . , yI i, each yi taking values in a label set Yi .
For example, in unlabeled dependency parsing, I is
the number of candidate dependency arcs (quadratic
in the sentence length), and each Yi = {0, 1}. Of
course, the yi are highly interdependent.
Factor Graphs. Probabilistic models like CRFs
(Lafferty et al., 2001) assume a factorization of theconditional distribution of Y ,Q
Pr(Y = y | X = x) ∝C∈C ΨC (x, yC ), (1)where each C ⊆ {1, . . . , I} is a factor, C is the setof factors, each yC , hyi ii∈C denotes a partial output assignment, and each ΨC is a nonnegative potential function that depends on the output only via
its restriction to C. A factor graph (Kschischang
et al., 2001) is a convenient representation for thefactorization in Eq. 1: it is a bipartite graph Gx comprised of variable nodes {1, . . . , I} and factor nodes
C ∈ C, with an edge connecting the ith variablenode and a factor node C iff i ∈ C. Hence, the factor graph Gx makes explicit the direct dependencies
among the variables {y1 , . . . , yI }.
Factor graphs have been used for several NLP
tasks, such as dependency parsing, segmentation,and co-reference resolution (Sutton et al., 2007;
Smith and Eisner, 2008; McCallum et al., 2009).
Hard and Soft Constraint Factors. It may be
the case that valid outputs are a proper subset of
Y1 × · · · × YI —for example, in dependency parsing, the entries of the output vector y must jointly
define a spanning tree. This requires hard constraint
factors that rule out forbidden partial assignments
by mapping them to zero potential values. See Table 1 for an inventory of hard constraint factors usedin this paper. Factors that are not of this special kindare called soft factors, and have strictly positive potentials. We thus have a partition C = Chard ∪ Csoft .
We let the soft factor potentials take the formΨC (x, yC ) , exp(θ > φC (x, yC )), where θ ∈ Rd
is a vector of parameters (shared across factors) andφC (x, yC ) is a local feature vector. The conditional
distribution of Y (Eq. 1) thus becomes log-linear:Prθ (y|x) = Zx (θ)−1 exp(θ > φ(x, y)),

(2)

P
>
0
where Zx (θ) ,y0 ∈Y(x) exp(θ φ(x, y )) is thepartition function, and the features decompose as:φ(x, y) ,P

C∈Csoft φC (x, yC ).

(3)

Dependency Parsing. Smith and Eisner (2008)
proposed a factor graph representation for dependency parsing (Fig. 1). The graph has O(n2 ) variable nodes (n is the sentence length), one per candidate arc a , hh, mi linking a head h and modifier
m. Outputs are binary, with ya = 1 iff arc a belongs
to the dependency tree. There is a hard factor TREE
connected to all variables, that constrains the overallarc configurations to form a spanning tree. There is aunary soft factor per arc, whose log-potential reflects
the score of that arc. There are also O(n3 ) pairwise factors; their log-potentials reflect the scoresof sibling and grandparent arcs. These factors create loops, thus calling for approximate inference.
Without them, the model is arc-factored, and exact inference in it is well studied: finding the mostprobable parse tree takes O(n3 ) time with the ChuLiu-Edmonds algorithm (McDonald et al., 2005),2
and computing posterior marginals for all arcs takesO(n3 ) time via the matrix-tree theorem (Smith andSmith, 2007; Koo et al., 2007).
Message-passing
algorithms. In
generalfactor graphs,
both inference problems—
obtaining the most probable output (the MAP)
argmaxy∈Y(x) Prθ (y|x), and computing themarginals Prθ (Yi = yi |x)—can be addressedwith the belief propagation (BP) algorithm (Pearl,1988), which iteratively passes messages between
variables and factors reflecting their local “beliefs.”
There is a faster but more involved O(n2 ) algorithm due toTarjan (1977).
2

v1 , . . . , vn ∈ SC
where SC ⊆ {0, 1}n .
otherwise,PQvi• Message-induced distribution: ω , hmj→C ij=1,...,n• Partition function: ZC (ω) , hv1 ,...,vn i∈SC n
i=1 mi→C• Marginals: MARGi (ω) , Prω {Vi = 1|hV1 , . . . , Vn i ∈ SC }• Max-marginals: MAX - MARGi,b (ω) , maxv∈SC Prω (v|vi = b)
• Sum-prod.: mC→i = m−1• Max-prod.: mC→i = m−1
MAX - MARG i,1 (ω)/ MAX - MARG i,0 (ω)
i→C · MARG i (ω)/(1 − MARG i (ω))
i→C · P
• Local agreem. constr.: z ∈ conv SC , where z = hτi (1)in• Entropy: HC = log ZC (ω) − n
i=1 MARG i (ω) log mi→C
i=1

1 y ∈ Ytree (i.e., {a ∈ A | ya = 1} is a directed spanning tree)
TREEΨTREE (hya ia∈A ) =where A is the set of candidate arcs.
0 otherwise,• Partition function Ztree (ω) and marginals hMARGa (ω)ia∈A computed via the matrix-tree theorem, with ω , hma→TREE ia∈A
• Sum-prod.: mTREE→a = m−1
a→TREE · MARG a (ω)/(1 − MARG a (ω))• Max-prod.: mTREE→a = m−1
a→TREE · MAX - MARG a,1 (ω)/ MAX - MARG a,0 (ω), where MAX - MARG a,b (ω) , maxy∈Ytree Prω (y|ya = b)
• Local agreem. constr.: z ∈ Ztree , where
P Ztree , conv Ytree is the arborescence polytope• Entropy: Htree = log Ztree (ω) − a∈A(ω) log ma→TREE
 MARGPan1
i=1 vi = 1
XOR (“one-hot”)
ΨXOR (v1 , . . . , vn ) =0 otherwise.
“P
”−1
`
´−1
• Sum-prod.: mXOR→i =mj→XOR• Max-prod.: mXOR→i = maxj6=i mj→XOR
P j6=iP
P
P• Local agreem. constr.: i zi = 1, zi ∈ [0, 1], ∀i• HXOR = − i (mi→XOR / j mj→XOR ) log(mi→XOR / j mj→XOR )Pn1
i=1 vi ≥ 1
ORΨOR (v1 , . . . , vn ) =0 otherwise.
“”−1
Q• Sum-prod.: mOR→i = 1 − j6=i (1 + mj→OR )−1• Max-prod.: mOR→i = max{1, minj6=i m−1
j→OR }
P• Local agreem. constr.: i zi ≥ 1, zi ∈ [0, 1],∀i
Wn−1
1 vn = i=1vi
OR - WITH - OUTPUT
ΨOR - OUT (v1 , . . . , vn ) =0 otherwise.
( “
”−1
Q
(1 + mj→OR - OUT )−1i<n
1 − (1 − m−1n→
OR - OUT )j6=i,n• Sum-prod.: mOR - OUT→i =
Q
(1
+
m
)
−
1
i = n.
j→OR - OUT
j6=n
n
o
(
Q
min mn→OR - OUT j6=i,n max{1, mj→OR - OUT }, max{1, minj6=i,n m−1}i<nj→
OR - OUT• Max-prod.: mOR - OUT→i =Q
i = n.
j6=n max{1, mj→OR - OUT } min{1, maxj6=n mj→OR - OUT }

A general binary factor:

ΨC (v1 , . . . , vn ) =10

Table 1: Hard constraint factors, their potentials, messages, and entropies. The top row shows expressions for ageneral binary factor: each outgoing message is computed from incoming marginals (in the sum-product case), or
max-marginals (in the max-product case); the entropy of the factor (see §3) is computed from these marginals and thepartition function; the local agreement constraints (§4) involve the convex hull of the set SC of allowed configurations(see footnote 5). The TREE, XOR, OR and OR - WITH - OUTPUT factors allow tractable computation of all these quantities(rows 2–5). Two of these factors (TREE and XOR) had been proposed by Smith and Eisner (2008); we provide further
information (max-product messages, entropies, and local agreement constraints). Factors OR and OR - WITH - OUTPUT
are novel to the best of our knowledge. This inventory covers many cases, since the above formulae can be extended
to the case where some inputs are negated: just replace the corresponding messages by their reciprocal, vi by 1 − vi ,etc. This allows building factors NAND (an OR factor with negated inputs), IMPLY (a 2-input OR with the first input
negated), and XOR - WITH - OUTPUT (an XOR factor with the last input negated).

In sum-product BP, the messages take the form:3
Q
Mi→C (yi ) ∝ D6=C MD→i (yi )(4)PQMC→i (yi ) ∝ yC ∼yiΨC (yC ) j6=i Mj→C (yj ). (5)In max-product BP, the summation in Eq. 5 is replaced by a maximization. Upon convergence, variable and factor beliefs are computed as:Qτi (yi ) ∝(6)
C MC→i (yi )QτC (yC ) ∝ ΨC (yC ) i Mi→C (yi ).
(7)
BP is exact when the factor graph is a tree: in thesum-product case, the beliefs in Eqs. 6–7 correspondto the true marginals, and in the max-product case,maximizing each τi (yi ) yields the MAP output. In
graphs with loops, BP is an approximate method, notguaranteed to converge, nicknamed loopy BP. We
highlight a variational perspective of loopy BP in §3;
for now we consider algorithmic issues. Note thatcomputing the factor-to-variable messages for eachfactor C (Eq. 5) requires a summation/maximization
over exponentially many configurations. Fortunately, for all the hard constraint factors in rows 3–5of Table 1, this computation can be done in linear
time (and polynomial for the TREE factor)—this extends results presented in Smith and Eisner (2008).4

3

We employ the standard ∼ notation, where a summation/maximization indexed by yC ∼ yi means that it is over
all yC with the i-th component held fixed and set to yi .

4

The insight behind these speed-ups is that messages on
binary-valued potentials can be expressed as MC→i (yi ) ∝

SIB

GRAND

SIB

SIB

(h,m�,m�)
12 (h,m�,m�)2
3 (h,m�,m�)
1
3(g,h,m�)
1

ARC

(g,h)

ARC

(h,m�)
1ARC(h,m�)
2ARC(h,m�)
3

and 0 otherwise; χ(y0 ) is called the output indicator
vector. This mapping allows decoupling the feature
vector in Eq. 3 as the product of an input matrix andan output vector:X
φC (x, yC ) = F(x)χ(y), (8)φ(x, y) =C∈CsoftTREE

Figure 1: Factor graph corresponding to the dependency
parsing model of Smith and Eisner (2008) with siblingand grandparent features. Circles denote variable nodes,
and squares denote factor nodes. Note the loops createdby the inclusion of pairwise factors (GRAND and SIB).

In Table 1 we present closed-form expressions
for the factor-to-variable message ratios mC→i ,MC→i (1)/MC→i (0) in terms of their variable-tofactor counterparts mi→C , Mi→C (1)/Mi→C (0);these ratios are all that is necessary when the variables are binary. Detailed derivations are presented
in an extended version of this paper (Martins et al.,2010b).

3

Variational Representations

Let Px , {Prθ (.|x) | θ ∈ Rd } be the family of all
distributions of the form in Eq. 2. We next present
an alternative parametrization for the distributions in
Px in terms of factor marginals. We will see thateach distribution can be seen as a point in the socalled marginal polytope (Wainwright and Jordan,
2008); this will pave the way for the variational representations to be derived next.
Parts and Output Indicators. A part is a pairhC, yC i, where C is a soft factor and yC a partial
output assignment.
We let R = {hC, yC i | C ∈Q
Csoft , yC ∈ i∈C Yi } be the set of all parts. Givenan output y0 ∈ Y(x), a part hC, yC i is said to be ac0 .
tive if it locally matches the output, i.e., if yC = yC
0
Any output y ∈ Y(x) can be mapped to a |R|dimensional binary vector χ(y0 ) indicating which0parts are active, i.e., [χ(y0 )]hC,yC i = 1 if yC = yC
Pr{ΨC (YC ) = 1|Yi = yi } and MC→i (yi ) ∝maxΨC (yC )=1 Pr{YC = yC |Yi = yi }, respectively for thesum-product and max-product cases; these probabilities
Q are induced by the messages in Eq. 4: for an event A ⊆ i∈C Yi ,PQ
Pr{YC ∈ A} , yC I(yC ∈ A) i∈C Mi→C (yi ).

where F(x) is a d-by-|R| matrix whose columns
contain the part-local feature vectors φC (x, yC ).
Observe, however, that not every vector in {0, 1}|R|
corresponds necessarily to a valid output in Y(x).
Marginal Polytope. Moving to vector representations of outputs leads naturally to a geometric viewof the problem. The marginal polytope is the convex
hull5 of all the “valid” output indicator vectors:
M(Gx ) , conv{χ(y) | y ∈ Y(x)}.
Note that M(Gx ) only depends on the factor graphGx and the hard constraints (i.e., it is independent of
the parameters θ). The importance of the marginal
polytope stems from two facts: (i) each vertex ofM(Gx ) corresponds to an output in Y(x); (ii) eachpoint in M(Gx ) corresponds to a vector of marginal
probabilities that is realizable by some distribution(not necessarily in Px ) that factors according to Gx .
Variational Representations. We now describe
formally how the points in M(Gx ) are linked to the
distributions in Px . We extend the “canonical overcomplete parametrization” case, studied by Wainwright and Jordan (2008), to our scenario (common
in NLP), where arbitrary features are allowed andthe parameters are P
tied (shared by all factors). Let
H(Prθ (.|x)) , − y∈Y(x) Prθ (y|x) log Prθ (y|x)
denote the entropy of Prθ (.|x), and Eθ [.] the expectation under Prθ (.|x). The component of µ ∈M(Gx ) indexed by part hC, yC i is denoted µC (yC ).
Proposition 1. There is a map coupling each distribution Prθ (.|x) ∈ Px to a unique µ ∈ M(Gx ) suchthat Eθ [χ(Y )] = µ. Define H(µ) , H(Prθ (.|x))
if some Prθ (.|x) is coupled to µ, and H(µ) = −∞if no such Prθ (.|x) exists. Then:
1. The following variational representation for the
log-partition function (mentioned in Eq. 2) holds:
log Zx (θ) =5

max θ > F(x)µ + H(µ).
µ∈M(Gx )(9)

The convex
zk } is the set of points that can
P hull of {z1 , . . . ,Pbe written as ki=1 λi zi , where ki=1 λi = 1 and each λi ≥ 0.

al. (2001) and others, who first analyzed loopy BPfrom a variational perspective. The following two
approximations underlie loopy BP:
Parameter�space Factor�log-potentials� Marginal�polytope�
space�������

Figure 2: Dual parametrization of the distributions in
Px . Our parameter space (left) is first linearly mapped tothe space of factor log-potentials (middle). The latter ismapped to the marginal polytope M(Gx ) (right). In general only a subset of M(Gx ) is reachable from our parameter space. Any distribution in Px can be parametrized bya vector θ ∈ Rd or by a point µ ∈ M(Gx ).

2. The problem in Eq. 9 is convex and its solution
is attained at the factor marginals, i.e., there is a
maximizer µ̄ s.t. µ̄C (yC ) = Prθ (YC = yC |x)
for each C ∈ C. The gradient of the log-partition
function is ∇ log Zx (θ) = F(x)µ̄.
3. The MAP ŷ , argmaxy∈Y(x) Prθ (y|x) can beobtained by solving the linear programµ̂ , χ(ŷ) = argmax θ > F(x)µ.

(10)µ∈M(Gx )A proof of this proposition can be found in Martins et al. (2010a). Fig. 2 provides an illustration of
the dual parametrization implied by Prop. 1.

4

Approximate Inference & Turbo Parsing

We now show how the variational machinery justdescribed relates to message-passing algorithms andprovides a common framework for analyzing two recent dependency parsers. Later (§5), Prop. 1 is used
constructively for learning the model parameters.
4.1

Loopy BP as a Variational Approximation

For general factor graphs with loops, the marginal
polytope M(Gx ) cannot be compactly specified andthe entropy term H(µ) lacks a closed form, rendering exact optimizations in Eqs. 9–10 intractable. A
popular approximate algorithm for marginal inference is sum-product loopy BP, which passes messages as described in §2 and, upon convergence,computes beliefs via Eqs. 6–7. Were loopy BP exact,
these beliefs would be the true marginals and hencea point in the marginal polytope M(Gx ). However,this need not be the case, as elucidated by Yedidia et• The marginal polytope M(Gx ) is approximated by
the local polytope L(Gx ). This is an outer bound;its name derives from the fact that it only imposes
local agreement constraints ∀i, yi ∈ Yi , C ∈ C:PP
yi τi (yi ) = 1,yC ∼yi τC (yC ) = τi (yi ). (11)Namely, it is characterized by L(Gx ) , {τ ∈|R|
R+ | Eq. 11 holds ∀i, yi ∈ Yi , C ∈ C}. The
elements of L(Gx ) are called pseudo-marginals.
Clearly, the true marginals satisfy Eq. 11, andtherefore M(Gx ) ⊆ L(Gx ).
• The entropy H is replaced
PIby its Bethe approximation
H
(τ
)
,
Bethe
i=1 (1 − di )H(τ i ) +P
C∈C H(τ C ), where di = |{C | i ∈ C}| is thenumber of factors
P connected to the ith variable,
H(τ
)
,
−
yi τi (yi ) log τi (yi ) and H(τ C ) ,Pi− yC τC (yC ) log τC (yC ).
Any stationary point of sum-product BP is a local optimum of the variational problem in Eq. 9with M(Gx ) replaced by L(Gx ) and H replaced by
HBethe (Yedidia et al., 2001). Note however thatmultiple optima may exist, since HBethe is not necessarily concave, and that BP may not converge.
Table 1 shows closed form expressions for the
local agreement constraints and entropies of somehard-constraint factors, obtained by invoking Eq. 7
and observing that τC (yC ) must be zero if configuration yC is forbidden. See Martins et al. (2010b).
4.2

Two Dependency Turbo Parsers

We next present our main contribution: a formal
connection between two recent approximate dependency parsers, which at first sight appear unrelated.
Recall that (i) Smith and Eisner (2008) proposed afactor graph (Fig. 1) in which they run loopy BP,
and that (ii) Martins et al. (2009) approximate parsing as the solution of a linear program. Here, we
fill the blanks in the two approaches: we derive explicitly the variational problem addressed in (i) and
we provide the underlying factor graph in (ii). Thisputs the two approaches side-by-side as approximate
methods for marginal and MAP inference. Sinceboth rely on “local” approximations (in the sense

of Eq. 11) that ignore the loops in their graphicalmodels, we dub them turbo parsers by analogy witherror-correcting turbo decoders (see footnote 1).
Turbo Parser #1: Sum-Product Loopy BP. The
factor graph depicted in Fig. 1—call it Gx —includes
pairwise soft factors connecting sibling and grandparent arcs.6 We next characterize the local polytope
L(Gx ) and the Bethe approximation HBethe inherent
in Smith and Eisner’s loopy BP algorithm.
Let A be the set of candidate arcs, and P ⊆A2 the set of pairs of arcs that have factors. Letτ = hτ A , τ P i with τ A = hτa ia∈A and τ P =hτab iha,bi∈P . Since all variables are binary, we may
write, for each a ∈ A, τa (1) = za and τa (0) =1 − za , where za is a variable constrained to [0, 1].
Let zA , hza ia∈A ; the local agreement constraints
at the TREE factor (see Table 1) are written as zA ∈Ztree (x), where Ztree (x) is the arborescence polytope, i.e., the convex hull of all incidence vectorsof dependency trees (Martins et al., 2009). It is
straightforward to write a contingency table and obtain the following local agreement constraints at the
pairwise factors:τab (1, 1) = zab ,τab (0, 0) = 1 − za − zb + zabτab (1, 0) = za − zab , τab (0, 1) = zb − zab .
Noting that all these pseudo-marginals are constrained to the unit interval, one can get rid of all
variables τab and write everything asza ∈ [0, 1], zb ∈ [0, 1], zab ∈ [0, 1],zab ≤ za ,zab ≤ zb ,zab ≥ za + zb − 1,(12)inequalities which, along with zA ∈ Ztree (x), define the local polytope L(Gx ). As for the factor entropies, start by noting that the TREE-factor entropy
Htree can be obtained in closed form by computing
the marginals z̄A and the partition function Zx (θ)(via the matrix-tree theorem) and recalling the variational representation in Eq. 9, yielding Htree =log Zx (θ) − θ > F(x)z̄A . Some algebra allows writing the overall Bethe entropy approximation as:
X
HBethe (τ ) = Htree (zA ) −Ia;b (za , zb , zab ), (13)ha,bi∈P

where we introduced the mutual information associated with each pairwise factor, Ia;b (za , zb , zab ) =6

Smith and Eisner (2008) also proposed other variants withmore factors, which we omit for brevity.

XOR

SINGLE-PARENT
(m)

ARC
(0,m)
PATH-BUILDER
(m,k)

FLOW
(0,m,k)FLOW(n,m,k)OR

FLOW-IMPLIES-ARC(h,m,k)FLOW-DELTA
(h,k)

XOR

PATH
(m,k)

ARC
(h,m)

FLOW
(h,m,k)

ARC
(n,m)

FLOW
(h,1,k)FLOW(h,n,k)

PATH
(h,k)

Figure 3: Details of the factor graph underlying the parserof Martins et al. (2009). Dashed circles represent auxiliary variables. See text and Table 1.
τab (ya ,yb )ya ,yb τab (ya , yb ) log τa (ya )τb (yb ) . The approximatePvariational expression becomes log Zx (θ) ≈maxz

θ > F(x)z + Htree (zA ) −X

Ia;b (za , zb , zab )ha,bi∈Ps.t.

zab ≤ za , zab ≤ zb ,zab ≥ za + zb − 1, ∀ha, bi ∈ P,
zA ∈ Ztree ,(14)
whose maximizer corresponds to the beliefs returned by the Smith and Eisner’s loopy BP algorithm(if it converges).
Turbo Parser #2: LP-Relaxed MAP. We now
turn to the concise integer LP formulation of Martins et al. (2009). The formulation is exact but NPhard, and so an LP relaxation is made there by dropping the integer constraints. We next construct a factor graph G0x and show that the LP relaxation corresponds to an optimization of the form in Eq. 10, withthe marginal polytope M(G0x ) replaced by L(G0x ).
G0x includes the following auxiliary variablenodes: path variables hpij ii=0,...,n,j=1,...,n , whichindicate whether word j descends from i in the dependency tree, and flow variables hfak ia∈A,k=1,...,n ,which evaluate to 1 iff arc a “carries flow” to k,i.e., iff there is a path from the root to k that passes
through a. We need to seed these variables imposing
p0k = pkk = 1, ∀k,hfhh,mi= 0, ∀h, m;(15)i.e., any word descends from the root and from itself, and arcs leaving a word carry no flow to thatword. This can be done with unary hard constraint
factors. We then replace the TREE factor in Fig. 1 by
the factors shown in Fig. 3:• O(n) XOR factors, each connecting all arc variables of the form {hh, mi}h=0,...,n . These ensurethat each word has exactly one parent. Each factor
yields a local agreement constraint (see Table 1):Pnm ∈ {1, . . . , n}(16)h=0 zhh,mi = 1,
• O(n3 ) IMPLY factors, each expressing that if an
arc carries flow, then that arc must be active. Suchfactors are OR factors with the first input negated,
hence, the local agreement constraints are:fak ≤ za ,a ∈ A, k ∈ {1, . . . , n}.

(17)• O(n2 ) XOR - WITH - OUTPUT factors, which impose the constraint that each path variable pmk is
active if and only if exactly one incoming arc in{hh, mi}h=0,...,n carries flow to k. Such factors
are XOR factors with the last input negated, andhence their local constraints are:Pk
, m, k ∈ {1, . . . , n} (18)pmk = nh=0 fhh,miadded to indicate non-projective arcs and OR - WITH OUTPUT hard constraint factors are inserted to enW
force nhh,mi = zhh,mi ∧ min(h,m)<j<min(h,m) ¬phj .
Details are omitted for space.
In sum, although the approaches of Smith and Eisner (2008) and Martins et al. (2009) look very different, in reality both are variational approximations
emanating from Prop. 1, respectively for marginaland MAP inference. However, they operate on distinct factor graphs, respectively Figs. 1 and 3.95

Online Learning

Our learning algorithm is presented in Alg. 1. It is a
generalized online learner that tackles `2 -regularizedempirical risk minimization of the form1minθ∈Rd λ2 kθk2 + m

Pm

i=1 L(θ; xi , yi ),(21)

where each hxi , yi i is a training example, λ ≥ 0 is
the regularization constant, and L(θ; x, y) is a nonnegative convex loss. Examples include the logistic
loss used in CRFs (− log Prθ (y|x)) and the hinge
loss of structured SVMs (maxy0 ∈Y(x) θ > (φ(x, y0 )−• O(n2 ) XOR - WITH - OUTPUT factors to impose the φ(x, y)) + `(y0 , y) for some cost function `). These
constraint that words don’t consume other words’ are both special cases of the family defined in Fig. 4,
commodities; i.e., if h 6= k and k 6= 0, then there which also includes the structured perceptron’s loss
is a path from h to k iff exactly one outgoing arc (β → ∞, γ = 0) and the softmax-margin loss ofGimpel and Smith (2010; β = γ = 1).
in {hh, mi}m=1,...,n carries flow to k:
Pn
Alg. 1 is closely related to stochastic or onlinek, h, k ∈ {0, . . . , n}, k ∈/ {0, h}.
phk = m=1 fhh,migradient
descent methods, but with the key advan(19)tage of not needing a learning rate hyperparameter.
L(G0x ) is thus defined by the constraints in Eq. 12 We sketch the derivation of Alg. 1; full details canand 15–19. The approximate MAP problem, that be found in Martins et al. (2010a). On the tth round,replaces M(G0x ) by L(G0x ) in Eq. 10, thus becomes:
one example hxt , yt i is considered. We seek to solvemaxz,f ,p θ > F(x)z
(20)
s.t.
Eqs. 12 and 15–19 are satisfied.
This is exactly the LP relaxation considered by Martins et al. (2009) in their multi-commodity flow
model, for the configuration with siblings and grandparent features.7 They also considered a configuration with non-projectivity features—which fire
if an arc is non-projective.8 That configuration
can also be obtained here if variables {nhh,mi } are7

To be precise, the constraints of Martins et al. (2009) arerecovered after eliminating the path variables, via Eqs. 18–19.
8
An arc hh, mi is non-projective if there is some word in its
span not descending from h (Kahane et al., 1998).

2
minθ,ξ λm
2 kθ − θ t k + ξs.t.
L(θ; xt , yt ) ≤ ξ, ξ ≥ 0,

(23)

9Given what was just exposed, it seems appealing to try
max-product loopy BP on the factor graph of Fig. 1, or sumproduct loopy BP on the one in Fig. 3. Both attempts present serious challenges: the former requires computing messages sentby the tree factor, which requires O(n2 ) calls to the Chu-LiuEdmonds algorithm and hence O(n5 ) time. No obvious strategy seems to exist for simultaneous computation of all messages, unlike in the sum-product case. The latter is even morechallenging, as standard sum-product loopy BP has serious issues in the factor graph of Fig. 3; we construct in Martins et al.
(2010b) a simple example with a very poor Bethe approximation. This might be fixed by using other variants of sum-productBP, e.g., ones in which the entropy approximation is concave.

Lβ,γ (θ; x, y) , β1 log

P

y0 ∈Y(x)h i
exp β θ > φ(x, y0 ) − φ(x, y) + γ`(y0 , y)(22)

Figure 4: A family of loss functions including as particular cases the ones used in CRFs, structured SVMs, and thestructured perceptron. The hyperparameter β is the analogue of the inverse temperature in a Gibbs distribution, while
γ scales the cost. For any choice of β > 0 and γ ≥ 0, the resulting loss function is convex in θ, since, up to a scale
factor, it is the composition of the (convex) log-sum-exp function with an affine map.

Algorithm 1 Aggressive Online Learning
1: Input: {hxi , yi i}m
i=1 , λ, number of epochs K
2: Initialize θ 1 ← 0; set T = mK
3: for t = 1 to T do
4:
Receive instance hxt , yt i and set µt = χ(yt )5:Solve Eq. 24 to obtain µ̄t and Lβ,γ (θ t , xt , yt )6:Compute ∇Lβ,γ (θ t , xt , yt ) = F(xt )(µ̄t −µt )on
L (θ ;x ,y )17:Compute ηt = min λm, k∇Lβ,γ (θtt ;xtt ,ytt )k2β,γ8:Return θ t+1 = θ t − ηt ∇Lβ,γ (θ t ; xt , yt )9: end forPT
10: Return the averaged model θ̄ ← T1
t=1 θ t .

which trades off conservativeness (stay close to themost recent solution θ t ) and correctness (keep theloss small). Alg. 1’s lines 7–8 are the result of taking the first-order Taylor approximation of L aroundθ t , which yields the lower bound L(θ; xt , yt ) ≥L(θ t ; xt , yt ) + (θ − θ t )> ∇L(θ t ; xt , yt ), and plugging that linear approximation into the constraint of
Eq. 23, which gives a simple Euclidean projection
problem (with slack) with a closed-form solution.
The online updating requires evaluating the loss
and computing its gradient. Both quantities canbe computed using the variational expression in
Prop. 1, for any loss Lβ,γ (θ; x, y) in Fig. 4.10 Our
only assumption is that the cost function `(y0 , y)can be written as a sum over factor-local costs; letting µ = χ(y) and µ0 = χ(y0 ), this implies`(y0 , y) = p> µ0 + q for some p and q which areconstant with respect to µ0 .11 Under this assumption, Lβ,γ (θ; x, y) becomes expressible in terms of
the log-partition function of a distribution whose
log-potentials are set to β(F(x)> θ + γp). From
Eq. 9 and after some algebra, we finally obtain
Lβ,γ (θ; x, y) =10
Our description also applies to the (non-differentiable)
hinge loss case, when β → ∞, if we replace all instances of“the gradient” in the text by “a subgradient.”
11
For the Hamming cost, this holds with p = 1 − 2µ andq = 1> µ. See Taskar et al. (2006) for other examples.

1
θ > F(x)(µ0 −µ)+ H(µ0 )+γ(p> µ0 +q).
β
x)
(24)
Let µ̄ be a maximizer in Eq. 24; from the second
statement of Prop. 1 we obtain ∇Lβ,γ (θ; x, y) =F(x)(µ̄−µ). When the inference problem in Eq. 24
is intractable, approximate message-passing algorithms like loopy BP still allow us to obtain approximations of the loss Lβ,γ and its gradient.
For the hinge loss, we arrive precisely at the maxloss variant of 1-best MIRA (Crammer et al., 2006).
For the logistic loss, we arrive at a new online learning algorithm for CRFs that resembles stochastic
gradient descent but with an automatic step size that
follows from our variational representation.
maxµ0 ∈M(GUnsupported Features. As datasets grow, so dothe sets of features, creating further computational
challenges. Often only “supported” features—thoseobserved in the training data—are included, andeven those are commonly eliminated when their frequencies fall below a threshold. Important information may be lost as a result of these expedient choices. S Formally, the supported feature set
is Fsupp , m
i=1 supp φ(xi , yi ), where supp u ,{j | uj 6= 0} denotes the support of vector u. Fsupp
is a subset of the complete feature set, comprised ofthose features
output,S thatS occur in some candidate
0 ). Features
Fcomp , m
supp
φ(x
,
y
0
i
i
i=1 yi ∈Y(xi )in Fcomp \Fsupp are called unsupported.
Sha and Pereira (2003) have shown that training a
CRF-based shallow parser with the complete feature
set may improve performance (over the supportedone), at the cost of 4.6 times more features. Dependency parsing has a much higher ratio (around20 for bilexical word-word features, as estimated in
the Penn Treebank), due to the quadratic or faster
growth of the number of parts, of which only a few
are active in a legal output. We propose a simple
strategy for handling Fcomp efficiently, which canbe applied for those losses in Fig. 4 where β = ∞.
(e.g., the structured SVM and perceptron). Our procedure is the following: keep an active set F contain-

CRF (T URBO PARS . #1)
A RC -FACT.
S EC . O RD .
A RABICB ULGARIANC HINESEC ZECHDANISHD UTCHG ERMAN
JAPANESEP ORTUGUESES LOVENES PANISH
S WEDISHT URKISHE NGLISH N ON -P ROJ .
E NGLISH P ROJ .

78.28
91.02
90.58
86.18
89.58
82.91
89.34
92.90
90.64
83.03
83.83
87.81
76.86
90.15
91.23

79.12
91.78
90.87
87.72
90.08
84.31
90.58
93.22
91.00
83.17
85.07
89.01
76.28
91.08
91.94

SVM (T URBO PARS . #2)
A RC -FACT.
S EC . O RD .
79.04
90.84
91.09
86.78
89.78
82.73
89.04
93.18
90.56
83.49
84.19
88.55
74.79
90.66
91.65

79.42
92.30
91.77
88.52
90.78
84.17
91.19
93.38
91.50
84.35
85.95
88.99
76.10
91.79
92.91

|F|
6,643,191
13,018,431
28,271,086
83,264,645
7,900,061
15,652,800
49,934,403
4,256,857
16,067,150
4,603,295
11,629,964
18,374,160
6,688,373
57,615,709
55,247,093

SVM (T URBO #2)|F|+ NONPROJ ., COMPL .
|F
|
supp

2.8
2.1
2.1
2.3
2.3
2.1
2.5
2.2
2.1
2.7
2.6
2.8
2.2
2.5
2.4

80.02 (-0.14)
92.88 (+0.34) (†)
91.89 (+0.26)
88.78 (+0.44) (†)
91.50 (+0.68)
84.91 (-0.08)
91.49 (+0.32) (†)
93.42 (+0.32)
91.87 (-0.04)
85.53 (+0.80)
87.04 (+0.50) (†)
89.80 (+0.42)
76.62 (+0.62)
92.13 (+0.12)
93.26 (+0.41) (†)

Table 2: Unlabeled attachment scores, ignoring punctuation. The leftmost columns show the performance of arcfactored and second-order models for the CRF and SVM losses, after 10 epochs with 1/(λm) = 0.001 (tuned on the
English Non-Proj. dev.-set). The rightmost columns refer to a model to which non-projectivity features were added,
trained under the SVM loss, that handles the complete feature set. Shown is the total number of features instantiated,the multiplicative factor w.r.t. the number of supported features, and the accuracies (in parenthesis, we display thedifference w.r.t. a model trained with the supported features only). Entries marked with † are the highest reported in
the literature, to the best of our knowledge, beating (sometimes slightly) McDonald et al. (2006), Martins et al. (2008),
Martins et al. (2009), and, in the case of English Proj., also the third-order parser of Koo and Collins (2010), which
achieves 93.04% on that dataset (their experiments in Czech are not comparable, since the datasets are different).

ing all features that have been instantiated in Alg. 1.
At each round, run lines 4–5 as usual, using only
features in F. Since the other features have not beenused before, they have a zero weight, hence can beignored. When β = ∞, the variational problem in
Eq. 24 consists of a MAP computation and the solution corresponds to one output ŷt ∈ Y(xt ). Only theparts that are active in ŷt but not in yt , or vice-versa,
will have features that might receive a nonzero update. Those parts are reexamined for new features
and the active set F is updated accordingly.

6

Experiments

We trained non-projective dependency parsers for
14 languages, using datasets from the CoNLL-X
shared task (Buchholz and Marsi, 2006) and two
datasets for English: one from the CoNLL-2008
shared task (Surdeanu et al., 2008), which contains
non-projective arcs, and another derived from thePenn Treebank applying the standard head rules of
Yamada and Matsumoto (2003), in which all parsetrees are projective.12 We implemented Alg. 1,
12

We used the provided train/test splits for all datasets. For
English, we used the standard test partitions (section 23 of theWall Street Journal). We did not exploit the fact that somedatasets only contain projective trees and have unique roots.

which handles any loss function Lβ,γ .13 When β <∞, Turbo Parser #1 and the loopy BP algorithm ofSmith and Eisner (2008) is used; otherwise, Turbo
Parser #2 is used and the LP relaxation is solved with
CPLEX. In both cases, we employed the same pruning strategy as Martins et al. (2009).
Two different feature configurations were first
tried: an arc-factored model and a model withsecond-order features (siblings and grandparents).
We used the same arc-factored features as McDonald et al. (2005) and second-order features that conjoin words and lemmas (at most two), parts-ofspeech tags, and (if available) morphological information; this was the same set of features as in Martins et al. (2009). Table 2 shows the results obtainedin both configurations, for CRF and SVM loss functions. While in the arc-factored case performance issimilar, in second-order models there seems to be aconsistent gain when the SVM loss is used. There
are two possible reasons: first, SVMs take the costfunction into consideration; second, Turbo Parser #2
is less approximate than Turbo Parser #1, since only
the marginal polytope is approximated (the entropy
function is not involved).
13

The code is available at http://www.ark.cs.cmu.edu/

TurboParser.

βγ
A RC -F.
2 O RD .

111
10 (CRF) 1
3
5
90.15 90.41 90.38 90.53
91.08 91.85 91.89 91.51

3
5
∞
1
1
1 (SVM)
90.80 90.83 90.66
92.04 91.98 91.79

Table 3: Varying β and γ: neither the CRF nor the
SVM is optimal. Results are UAS on the English NonProjective dataset, with λ tuned with dev.-set validation.

The loopy BP algorithm managed to converge fornearly all sentences (with message damping). The
last three columns show the beneficial effect of unsupported features for the SVM case (with a more
powerful model with non-projectivity features). For
most languages, unsupported features convey helpful information, which can be used with little extra
cost (on average, 2.5 times more features are instantiated). A combination of the techniques discussed
here yields parsers that are in line with very strong
competitors—for example, the parser of Koo andCollins (2010), which is exact, third-order, and constrains the outputs to be projective, does not outperform ours on the projective English dataset.14
Finally, Table 3 shows results obtained for different settings of β and γ. Interestingly, we observethat higher scores are obtained for loss functions thatare “between” SVMs and CRFs.

7

Related Work

There has been recent work studying efficient computation of messages in combinatorial factors: bipartite matchings (Duchi et al., 2007), projective
and non-projective arborescences (Smith and Eisner, 2008), as well as high order factors with countbased potentials (Tarlow et al., 2010), among others.
Some of our combinatorial factors (OR, OR - WITH OUTPUT ) and the analogous entropy computations
were never considered, to the best of our knowledge.
Prop. 1 appears in Wainwright and Jordan (2008)
for canonical overcomplete models; we adapt it here
for models with shared features. We rely on the variational interpretation of loopy BP, due to Yedidia etal. (2001), to derive the objective being optimized
by Smith and Eisner’s loopy BP parser.
Independently of our work, Koo et al. (2010)14
This might be due to the fact that Koo and Collins (2010)
trained with the perceptron algorithm and did not use unsupported features. Experiments plugging the perceptron loss
(β → ∞, γ → 0) into Alg. 1 yielded worse performance thanwith the hinge loss.

recently proposed an efficient dual decomposition
method to solve an LP problem similar (but notequal) to the one in Eq. 20,15 with excellent parsing performance. Their parser is also an instanceof a turbo parser since it relies on a local approximation of a marginal polytope. While one can alsouse dual decomposition to address our MAP problem, the fact that our model does not decompose as
nicely as the one in Koo et al. (2010) would likely
result in slower convergence.

8

Conclusion

We presented a unified view of two recent approximate dependency parsers, by stating their underlying
factor graphs and by deriving the variational problems that they address. We introduced new hard constraint factors, along with formulae for their messages, local belief constraints, and entropies. We
provided an aggressive online algorithm for training
the models with a broad family of losses.
There are several possible directions for future
work. Recent progress in message-passing algorithms yield “convexified” Bethe approximations
that can be used for marginal inference (Wainwrightet al., 2005), and provably convergent max-productvariants that solve the relaxed LP (Globerson andJaakkola, 2008). Other parsing formalisms can behandled with the inventory of factors shown here—
among them, phrase-structure parsing.

Acknowledgments
The authors would like to thank the reviewers for theircomments, and Kevin Gimpel, David Smith, David Sontag, and Terry Koo for helpful discussions. A. M. was
supported by a grant from FCT/ICTI through the CMUPortugal Program, and also by Priberam Informática.
N. S. was supported in part by Qatar NRF NPRP-08-4851-083. E. X. was supported by AFOSR FA9550010247,
ONR N000140910758, NSF CAREER DBI-0546594,
NSF IIS-0713379, and an Alfred P. Sloan Fellowship.
M. F. and P. A. were supported by the FET programme(EU FP7), under the SIMBAD project (contract 213250).

15

The difference is that the model of Koo et al. (2010)
includes features that depend on consecutive siblings—
making it decompose into subproblems amenable to dynamic
programming—while we have factors for all pairs of siblings.

References
C. Berrou, A. Glavieux, and P. Thitimajshima. 1993.
Near Shannon limit error-correcting coding and decoding. In Proc. of ICC, volume 93, pages 1064–1070.
S. Buchholz and E. Marsi. 2006. CoNLL-X shared task
on multilingual dependency parsing. In CoNLL.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz,
and Y. Singer. 2006. Online passive-aggressive algorithms. JMLR, 7:551–585.
J. Duchi, D. Tarlow, G. Elidan, and D. Koller. 2007.
Using combinatorial optimization within max-productbelief propagation. NIPS, 19.
J. R. Finkel, A. Kleeman, and C. D. Manning. 2008. Efficient, feature-based, conditional random field parsing.
Proc. of ACL.
K. Gimpel and N. A. Smith. 2010. Softmax-margin
crfs: Training log-linear models with loss functions.
In Proc. of NAACL.
A. Globerson and T. Jaakkola. 2008. Fixing maxproduct: Convergent message passing algorithms for
MAP LP-relaxations. NIPS, 20.
L. Huang. 2008. Forest reranking: Discriminative parsing with non-local features. In Proc. of ACL.
S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudoprojectivity: a polynomially parsable non-projective
dependency grammar. In Proc. of COLING.
T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of ACL.
T. Koo, A. Globerson, X. Carreras, and M. Collins. 2007.
Structured prediction models via the matrix-tree theorem. In Proc. of EMNLP.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, and D. Sontag. 2010. Dual decomposition for parsing with nonprojective head automata. In Proc. of EMNLP.
F. R. Kschischang, B. J. Frey, and H. A. Loeliger. 2001.
Factor graphs and the sum-product algorithm. IEEE
Trans. Inf. Theory, 47(2):498–519.
J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. of ICML.
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. 2009.
Concise integer linear programming formulations for
dependency parsing. In Proc. of ACL-IJCNLP.
A. F. T. Martins, K. Gimpel, N. A. Smith, E. P. Xing,
P. M. Q. Aguiar, and M. A. T. Figueiredo. 2010a.
Learning structured classifiers with dual coordinate
descent. Technical Report CMU-ML-10-109.
A. F. T. Martins, N. A. Smith, E. P. Xing, P. M. Q. Aguiar,
and M. A. T. Figueiredo. 2010b. Turbo parsers:
Dependency parsing by approximate variational inference (extended version).

A. McCallum, K. Schultz, and S. Singh. 2009. Factorie: Probabilistic programming via imperatively defined factor graphs. In NIPS.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic.
2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of HLT-EMNLP.
R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. of CoNLL.
R. J. McEliece, D. J. C. MacKay, and J. F. Cheng. 1998.
Turbo decoding as an instance of Pearl’s “belief propagation” algorithm. IEEE Journal on Selected Areasin Communications, 16(2).
J. Pearl. 1988. Probabilistic Reasoning in Intelligent
Systems: Networks of Plausible Inference. Morgan
Kaufmann.
F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. of HLT-NAACL.
D. A. Smith and J. Eisner. 2008. Dependency parsing bybelief propagation. In Proc. of EMNLP.
D. A. Smith and N. A. Smith. 2007. Probabilistic models
of nonprojective dependency trees. In EMNLP.
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.
C. Sutton, A. McCallum, and K. Rohanimanesh. 2007.
Dynamic conditional random fields: Factorized probabilistic models for labeling and segmenting sequence
data. JMLR, 8:693–723.
R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36.
D. Tarlow, I. E. Givoni, and R. S. Zemel. 2010. HOPMAP: Efficient message passing with high order potentials. In Proc. of AISTATS.
B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin
Markov networks. In NIPS.
B. Taskar, S. Lacoste-Julien, and M. I. Jordan. 2006.
Structured prediction, dual extragradient and Bregman
projections. JMLR, 7:1627–1653.
I. Tsochantaridis, T. Hofmann, T. Joachims, and Y. Altun.
2004. Support vector machine learning for interdependent and structured output spaces. In Proc. of ICML.
M. J. Wainwright and M. I. Jordan. 2008. GraphicalModels, Exponential Families, and Variational Inference. Now Publishers.
M. J. Wainwright, T.S. Jaakkola, and A.S. Willsky. 2005.
A new class of upper bounds on the log partition function. IEEE Trans. Inf. Theory, 51(7):2313–2335.
H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc.
of IWPT.
J. S. Yedidia, W. T. Freeman, and Y. Weiss. 2001. Generalized belief propagation. In NIPS.