Concise Integer Linear Programming Formulations
for Dependency Parsing∗

André F. T. Martins∗† Noah A. Smith∗ Eric P. Xing∗
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA†
Instituto de Telecomunicações, Instituto Superior Técnico, Lisboa, Portugal{afm,nasmith,epxing}@cs.cmu.edu
Abstract

We formulate the problem of nonprojective dependency parsing as apolynomial-sized integer linear program. Our formulation is able to handle
non-local output features in an efficientmanner; not only is it compatible withprior knowledge encoded as hard constraints, it can also learn soft constraints
from data. In particular, our model is able
to learn correlations among neighboringarcs (siblings and grandparents), word
valency, and tendencies toward nearlyprojective parses. The model parameters
are learned in a max-margin framework
by employing a linear programming
relaxation. We evaluate the performanceof our parser on data in several natural
languages, achieving improvements overexisting state-of-the-art methods.

1

Introduction

Much attention has recently been devoted to integer linear programming (ILP) formulations of
NLP problems, with interesting results in applications like semantic role labeling (Roth and Yih,
2005; Punyakanok et al., 2004), dependency parsing (Riedel and Clarke, 2006), word alignment
for machine translation (Lacoste-Julien et al.,2006), summarization (Clarke and Lapata, 2008),
and coreference resolution (Denis and Baldridge,2007), among others. In general, the rationale forthe development of ILP formulations is to incorporate non-local features or global constraints, which
are often difficult to handle with traditional algorithms. ILP formulations focus more on the modeling of problems, rather than algorithm design.
While solving an ILP is NP-hard in general, fastsolvers are available today that make it a practicalsolution for many NLP problems.
This paper presents new, concise ILP formulations for projective and non-projective depen-dency parsing. We believe that our formulations can pave the way for efficient exploitation of
global features and constraints in parsing applications, leading to more powerful models. Riedel
and Clarke (2006) cast dependency parsing as
an ILP, but efficient formulations remain an open
problem. Our formulations offer the following
comparative advantages:• The numbers of variables and constraints arepolynomial in the sentence length, as opposed torequiring exponentially many constraints, eliminating the need for incremental procedures likethe cutting-plane algorithm;• LP relaxations permit fast online discriminative
training of the constrained model;• Soft constraints may be automatically learned
from data. In particular, our formulations handle higher-order arc interactions (like siblingsand grandparents), model word valency, and canlearn to favor nearly-projective parses.
We evaluate the performance of the new parsers
on standard parsing tasks in seven languages. The
techniques that we present are also compatible
with scenarios where expert knowledge is available, for example in the form of hard or soft firstorder logic constraints (Richardson and Domingos, 2006; Chang et al., 2008).

2

Dependency Parsing

2.1

Preliminaries

A dependency tree is a lightweight syntactic representation that attempts to capture functional relationships between words. Lately, this formalism
has been used as an alternative to phrase-based
parsing for a variety of tasks, ranging from machine translation (Ding and Palmer, 2005) to relation extraction (Culotta and Sorensen, 2004) andquestion answering (Wang et al., 2007).
Let us first describe formally the set of legal dependency parse trees. Consider a sentence x =hw0 , . . . , wn i, where wi denotes the word at the ith position, and w0 = $ is a wall symbol. We form
the (complete1 ) directed graph D = hV, Ai, withvertices in V = {0, . . . , n} (the i-th vertex corresponding to the i-th word) and arcs in A = V 2 .
Using terminology from graph theory, we say thatB ⊆ A is an r-arborescence2 of the directed
graph D if hV, Bi is a (directed) tree rooted at r.
We define the set of legal dependency parse treesof x (denoted Y(x)) as the set of 0-arborescencesof D, i.e., we admit each arborescence as a potential dependency tree.
Let y ∈ Y(x) be a legal dependency tree forx; if the arc a = hi, ji ∈ y, we refer to i as theparent of j (denoted i = π(j)) and j as a child ofi. We also say that a is projective (in the sense of
Kahane et al., 1998) if any vertex k in the span of
a is reachable from i (in other words, if for any ksatisfying min(i, j) < k < max(i, j), there is adirected path in y from i to k). A dependency tree
is called projective if it only contains projective
arcs. Fig. 1 illustrates this concept.3
The formulation to be introduced in §3 makes
use of the notion of the incidence vector associated with a dependency tree y ∈ Y(x). This isthe binary vector z , hza ia∈A with each component defined as za = I(a ∈ y) (here, I(.) denotes
the indicator function). Considering simultaneously all incidence vectors of legal dependency
trees and taking the convex hull, we obtain a polyhedron that we call the arborescence polytope,
denoted by Z(x). Each vertex of Z(x) can be
identified with a dependency tree in Y(x). The
Minkowski-Weyl theorem (Rockafellar, 1970) ensures that Z(x) has a representation of the form
Z(x) = {z ∈ R|A| | Az ≤ b}, for some p-by-|A|matrix A and some vector b in Rp . However, it is
not easy to obtain a compact representation (wherep grows polynomially with the number of wordsn). In §3, we will provide a compact representation of an outer polytope Z̄(x) ⊇ Z(x) whose
integer vertices correspond to dependency trees.
Hence, the problem of finding the dependency treethat maximizes some linear function of the inci1
The general case where A ⊆ V 2 is also of interest; itarises whenever a constraint or a lexicon forbids some arcs
from appearing in dependency tree. It may also arise as aconsequence of a first-stage pruning step where some candidate arcs are eliminated; this will be further discussed in §4.
2
Or “directed spanning tree with designated root r.”
3
In this paper, we consider unlabeled dependency parsing,where only the backbone structure (i.e., the arcs without thelabels depicted in Fig. 1) is to be predicted.

learning via the E
previously
beenlearning via
the kE
implementations.
previously been
We then switch
implementations
non-local
informa
We thenswitc$
Figure 1: A projective dependency graph.
bouring
parse
dec
non-local inform
ity
constraints
Figure 1: A projective dependency graph.
bouring parsewedeniangraph proble
ity constraints
w
lem
intractabl
nianisgraph
probl
parse
lem isdecisions,intractab
andPereira
(2006
$
parse
decisions,neighbourhoods
and Pereira (200Figure 2: Non-projective dependency graph.
tion
to modelingneighbourhoods
Figure Figure
1: A projective
dependency
parse(top),
andanon2: Non-projective dependency graph.
sequence of thesprojective dependency parse (bottom) for two English sen- tion to modeling
non-project
thosethat assume
each dependency
tences;examplesfrom McDonald
and Sattadecision(2007). is in- exact
sequence of thedependent modulo the global structural constraint for any model ass
those that assume each dependency decision is in- exact non-projecthat dependency graphs must be trees. Such mod- by the edge-facto
dependent
modulothestructural
constraint
dence
vectors
can becastglobalasILP. A similar
idea for any model as
els arecommonlyreferredto an
as edge-factored
sinceby the edge-facto
thatdependency
graphsmustbetrees.
Such
modwastheirappliedto wordalignment
Lacoste-Julien
parametersfactorrelative tobyindividualedges 1.1 Related Wo
elsreferred2001;
to as edge-factored
has beenWeof arethe commonlygraphwhere(Paskin,
McDonald
etsinceal.,ar- Thereet al.
(2006),
permutations(rather than
1.1 Related
theirparametersfactorrelativetoindividualedges pendency
parsing
2005a). Edge-factoredmodels have many
computaborescences)were the combinatorial
structure
beTherehas Paskin
been
of
thebenefits,graph most(Paskin,
2001;
McDonald
etnonal., ner,
1996;
tionalnotablythatinferencefor
ing2005a).
requiring
representation.
pendency
parsinEdge-factoredmodelshave
many
computaprojective dependency graphs can be achieved in 2003; Nivre andLetting
X denotetheset ofpossible sentences,ner, 1996;
tionalbenefits,
notably
thatfor nonS
and Paski
nonpolynomial
timemost(McDonaldetal.,inference
2005b). The
pri- 2005a)
Y(x).
Given
a be
labeleddatasetdefine
Y
,
x∈X
2003;
Nivre
and
projective
dependency
graphscanachieved
inandNilsson,200
mary problem in treating each dependency as
inm , weL polynomial
,
hhx
,
y
i,
.
.
.
,
hx
,
y
ii
∈
(X
×
Y)
1
1
m
m
2005a)
andnontime(McDonaldetal.,2005b).
The
pridependent is that it is not a realistic assumption. ald et al., 2005b
aimmary
to learna parser,
i.e.,
aeach
functionh : valency)
Xas→in-Y classified
and Nilsson,
problemin treating
into 200tw
Non-local
information,such
as dependency
arity (orald et areal., those
2005bmis X
thatoutputs
it is nota realistic
thatdependentgivenx∈
a legaldependency
andneighbouring
dependencies,
can beassumption.
crucialparseto egoryclassified intotw
Non-local
information,such
as arity(orandvalency)y ∈Y(x). highTheparsing
fact that
thereareexponentiallytypicaobtainingaccuracies(KleinMan- inference,egory are thoseandneighbouring
can2006).
be crucial
to shift-reduceparsning,candidates
2002; McDonald
Pereira,Howmany
in dependencies,
Y(x)andmakes
dependency
parsinference,
typicahighparsing accuracies(Kleinthis
andcanMan2003;N
ever,in thedata-driven
parsingproblem.
setting
be sumoto,ingobtaining
a structured
classification
2005).
shift-reduceparspartially
advertedby incorporatingrich2006).
featureHowrep- Nilsson,
ning,
2002;
McDonald
and Pereira,
employexha
resentations
over
the inputparsing(McDonald
et al.,
sumoto,2003;
N
2.2ever,Arc
Factorization
andLocalityin thedata-driven
setting
this2005a).
can be thatally
by makingst
The goalof thiswork
is to further
ourcurrent
Nilsson,2005).
partially
advertedbyincorporatingrich
featurerepThere has been much recent work on dependency
theemploycase forexhedunderstandingof thetheinputcomputational
non- isthat
resentations
over(McDonaldnature
et al., of
2005a).
parsing
using
graph-based,transition-based,
and McDonald et al.,projective
parsingalgorithms
forboth
learning
andThe goal of this work is to further our current ally by making s
hybridmethods;
see data-driven
Nivre and setting.
McDonald(2008)
there
inference
withinWe start
by Recentlyis the casefor haed
understandingofthe
the computational
natureof nonforprojective
an overview.
Typicalgraph-based
methods
tive
methods
investigating
andextendingtheedge-factored
model
al.
parsing algorithms for both learning and McDonald etthat
considerlinearclassifiersof theform
includingof McDonald
et theal. data-driven(2005b).
Insetting.
particular,
we apRecently
therebohinference
withinWe startby tion,ald
andPereira,
2
peal
to
the
MatrixTree
Theoremformulti-digraphs
tive
methods
tha
investigating and extending the edge-factoredmodel
hw (x)= argmaxy∈Yw> f (x,fory),calculat-(1) teger linear progr
to McDonald
designpolynomial-timealgorithmsofet al. (2005b).
In particular,
we ap- tion, including b
or branch-and-bo
ing
both
the
partitionfunctionandedge
expectaand Pereira, 2peal tothey)
MatrixTree Theorem
for multi-digraphs
where
fover
(x,
is a vectorof features
andw
is the aldFor
tions
all
possibledependency
graphsforagiven
grammarteger linear
progb
todesignpolynomial-timealgorithms
forcalculatcorresponding
One wants
hw to work on empirica
sentence. To weightmotivatevector.
these algorithms,
we show
ing both the partition function and edge expecta- or branch-and-bo
have
expected
the important
typical loss
func- ing systems, notthatsmallthey canbe usedloss;
in many
learning
tions over all possible dependency
graphs for a given
For grammar b
0
problems
including
min-risk
decodtionandis inference
the Hammingloss,`(y ; y), |{hi,ji ∈ of Wang and Har
sentence.
To
motivatethesealgorithms,
we
show
work
on empiricing,
training
globally
normalized
log-linear
mod- note include the w
y 0 that: hi,theyji ∈/cany}|.
Tractability
usuallylearning
ensuredbe usedin many isimportanting systems, noels,
syntactic
language modeling,
and unsupervisedthat thebyandstrongfactorization
like theone showing
inference
problemsassumptions,
including min-risk
decodof Wang and Ha
underlying
the globallyarc-factoredmodellog-linear(Eisner, mod1996; note include theing, training
normalized
McDonaldetal.,2005),
which
forbidsanyfeatureels, syntactic language modeling, and unsupervised showing that ththat depends on two or more arcs. This induces adecomposition of the feature vector f (x, y) as:f (x, y) =Pa∈y fa (x).

(2)

Under this decomposition, each arc receives ascore; parsing amounts to choosing the configuration that maximizes the overall score, which, asshown by McDonald et al. (2005), is an instanceof the maximal arborescence problem. Combinatorial algorithms (Chu and Liu, 1965; Edmonds,
1967) can solve this problem in cubic time.4 If
the dependency parse trees are restricted to be
projective, cubic-time algorithms are available via
dynamic programming (Eisner, 1996). While in
the projective case, the arc-factored assumption
can be weakened in certain ways while maintaining polynomial parser runtime (Eisner and Satta,
1999), the same does not happen in the nonprojective case, where finding the highest-scoring tree
becomes NP-hard (McDonald and Satta, 2007).
Approximate algorithms have been employed tohandle models that are not arc-factored (althoughfeatures are still fairly local): McDonald andPereira (2006) adopted an approximation basedon O(n3 ) projective parsing followed by a hillclimbing algorithm to rearrange arcs, and Smithand Eisner (2008) proposed an algorithm based on
loopy belief propagation.

3

Dependency Parsing as an ILP

Our approach will build a graph-based parser
without the drawback of a restriction to local features. By formulating inference as an ILP, nonlocal features can be easily accommodated in ourmodel; furthermore, by using a relaxation technique we can still make learning tractable. The impact of LP-relaxed inference in the learning problem was studied elsewhere (Martins et al., 2009).
A linear program (LP) is an optimization problem of the formminx∈Rds.t.

c> xAx ≤ b.

(3)

If the problem is feasible, the optimum is attained
at a vertex of the polyhedron that defines the constraint space. If we add the constraint x ∈ Zd , thenthe above is called an integer linear program(ILP). For some special parameter settings—e.g.,when b is an integer vector and A is totally unimodular5 —all vertices of the constraining polyhedron are integer points; in these cases, the integer
constraint may be suppressed and (3) is guaranteed to have integer solutions (Schrijver, 2003).
Of course, this need not happen: solving a general ILP is an NP-complete problem. Despite this4

There is also a quadratic algorithm due to Tarjan (1977).
A matrix is called totally unimodular if the determinantsof each square submatrix belong to {0, 1, −1}.
5fact, fast solvers are available today that make thisa practical solution for many problems. Their performance depends on the dimensions and degreeof sparsity of the constraint matrix A.
Riedel and Clarke (2006) proposed an ILP formulation for dependency parsing which refines
the arc-factored model by imposing linguisticallymotivated “hard” constraints that forbid some arc
configurations. Their formulation includes an exponential number of constraints—one for eachpossible cycle. Since it is intractable to throwin all constraints at once, they propose a cuttingplane algorithm, where the cycle constraints are
only invoked when violated by the current solution. The resulting algorithm is still slow, and an
arc-factored model is used as a surrogate during
training (i.e., the hard constraints are only used attest time), which implies a discrepancy between
the model that is optimized and the one that is actually going to be used.
Here, we propose ILP formulations that eliminate the need for cycle constraints; in fact, theyrequire only a polynomial number of constraints.
Not only does our model allow expert knowledge
to be injected in the form of constraints, it is also
capable of learning soft versions of those constraints from data; indeed, it can handle featuresthat are not arc-factored (correlating, for example, siblings and grandparents, modeling valency,
or preferring nearly projective parses). While, as
pointed out by McDonald and Satta (2007), theinclusion of these features makes inference NPhard, by relaxing the integer constraints we obtainapproximate algorithms that are very efficient andcompetitive with state-of-the-art methods. In thispaper, we focus on unlabeled dependency parsing,for clarity of exposition. If it is extended to labeledparsing (a straightforward extension), our formulation fully subsumes that of Riedel and Clarke(2006), since it allows using the same hard constraints and features while keeping the ILP polynomial in size.
3.1

The Arborescence Polytope

We start by describing our constraint space. Ourformulations rely on a concise polyhedral representation of the set of candidate dependency parsetrees, as sketched in §2.1. This will be accomplished by drawing an analogy with a network
flow problem.
Let D = hV, Ai be the complete directed graphassociated with a sentence x ∈ X , as stated in§2. A subgraph y = hV, Bi is a legal dependency
tree (i.e., y ∈ Y(x)) if and only if the following
conditions are met:

• Flow is zero on disabled arcs:
φa ≤ nza , a ∈ A(8)• Each arc indicator lies in the unit interval:
1. Each vertex in V \ {0} must have exactly one
incoming arc in B,
2. 0 has no incoming arcs in B,

For each vertex v ∈ V , let δ − (v) , {hi, ji ∈A | j = v} denote its set of incoming arcs, andδ + (v) , {hi, ji ∈ A | i = v} denote its set ofoutgoing arcs. The two first conditions can be easily expressed by linear constraints on the incidence
vector z:a∈δ − (j) za = 1,Pa∈δ − (0)j ∈ V \ {0}za = 0• Root sends flow n:a∈δ + (0) φa = n(6)• Each node consumes one unit of flow:a∈δ − (j)Xa∈δ + (j)(10)

Furthermore, the integer points of Z̄(x) are precisely the incidence vectors of dependency treesin Y(x); these are obtained by replacing Eq. 9 byza ∈ B, a ∈ A.
3.2

Note that conditions 1-2-3 are equivalent to 1-230 , in the sense that both define the same set Y(x).
However, as we will see, the latter set of conditions is more convenient. Connectedness of graphs
can be imposed via flow constraints (by requiring that, for any v ∈ V \ {0}, there is a directed
path in B connecting 0 to v). We adapt the single
commodity flow formulation for the (undirected)
minimum spanning tree problem, due to Magnantiand Wolsey (1994), that requires O(n2 ) variables
and constraints. Under this model, the root node
must send one unit of flow to every other node.
By making use of extra variables, φ , hφa ia∈A ,to denote the flow of commodities through eacharc, we are led to the following constraints in addition to Eqs. 4–5 (we denote U , [0, 1], andB , {0, 1} = U ∩ Z):

φa −⊇ Z(x).

(11)(5)

30 . B is connected.

XZ̄(x) , {z ∈ R|A| | (z, φ) satisfy (4–9)}(4)

Condition 3 is somewhat harder to express. Rather
than adding exponentially many constraints, one
for each potential cycle (like Riedel and Clarke,
2006), we equivalently replace condition 3 byP

(9)These constraints project an outer bound of the arborescence polytope, i.e.,

3. B does not contain cycles.

Pza ∈ U, a ∈ A.

φa = 1, j ∈ V \ {0} (7)Arc-Factored Model

Given our polyhedral representation of (an outerbound of) the arborescence polytope, we can
now formulate dependency parsing with an arcfactored model as an ILP. By storing the arclocal feature vectors into the columns of a matrix
F(x) , [fa (x)]a∈A , and defining the score vector s , F(x)> w (each entry is an arc score) the
inference problem can be written as
max w> f (x, y) =y∈Y(x)maxz∈Z(x)= maxz,φw> F(x)z
s> z
"

s.t.

z
A
φ
z∈B

#

≤b

(12)
where A is a sparse constraint matrix (with O(|A|)
non-zero elements), and b is the constraint vector; A and b encode the constraints (4–9). Thisis an ILP with O(|A|) variables and constraints(hence, quadratic in n); if we drop the integer
constraint the problem becomes the LP relaxation.
As is, this formulation is no more attractive thansolving the problem with the existing combinatorial algorithms discussed in §2.2; however, we can
now start adding non-local features to build a more
powerful model.
3.3

Sibling and Grandparent Features

To cope with higher-order features of the form
fa1 ,...,aK (x) (i.e., features whose values depend on
the simultaneous inclusion of arcs a1 , . . . , aK ona candidate dependency tree), we employ a linearization trick (Boros and Hammer, 2002), defining extra variables za1 ...aK , za1 ∧ . . . ∧ zaK . This
logical relation can be expressed by the following
O(K) agreement constraints:6
za1 ...aK≤ za i ,za1 ...aKPK≥

i=1 zai − K + 1.

grand

(13)

if hi, ji and hi, ki areconsecutive siblings,
 0 otherwise,

first childzij,

1 if j is the first child of i,
0 otherwise.

Suppose (without loss of generality) that i < j <k ≤ n. We could naively compose the constraints(14) with additional linear constraints that encode
the logical relationnext sibl
sibl
zijk= zijk
∧

grand

zijk

≤ zjk ,

Vj<l<k ¬zil ,but this would yield a constraint matrix with
O(n4 ) non-zero elements. Instead, we define auxiliary variables βjk and γij :(1, if ∃l s.t. π(l) = π(j) < j < l < k0, otherwise,(

1, if ∃k s.t. i < k < j and hi, ki ∈ y0, otherwise.

βjk =
γij =

(16)

sibl
zijk
≤ zik ,

next sibl = z sibl ∧ (¬β ) and
Then, we have that zijk
jk
ijk
first child = z ∧ (¬γ ), which can be encoded via
zij
ij
ij

grand

≥ zij +zjk −1(15)
for all triples hi, j, ki ∈ Rgrand . Let R , A ∪Rsibl ∪ Rgrand ; by redefining z , hzr ir∈R andF(x) , [fr (x)]r∈R , we may express our inference
problem as in Eq. 12, with O(|A| · |V |) variables
and constraints.
Notice that the strategy just described to handle sibling features is not fully compatible withthe features proposed by Eisner (1996) for projective parsing, as the latter correlate only consecutive siblings and are also able to place special features on the first child of a given word.
The ability to handle such “ordered” features is
intimately associated with Eisner’s dynamic programming parsing algorithm and with the Markovian assumptions made explicitly by his generative model. We next show how similar features6≤ zij ,



 1

(

sibl
zijk
≥ zij + zik − 1(14)
for all triples hi, j, ki ∈ Rsibl , andzijk

next siblzijk,

i = 1, . . . , K

As shown by McDonald and Pereira (2006) and
Carreras (2007), the inclusion of features that
correlate sibling and grandparent arcs may behighly beneficial, even if doing so requires resorting to approximate algorithms.7 Define Rsibl ,{hi, j, ki | hi, ji ∈ A, hi, ki ∈ A} and Rgrand ,{hi, j, ki | hi, ji ∈ A, hj, ki ∈ A}. To include
such features in our formulation, we need to add
extra variables zsibl , hzr ir∈Rsibl and zgrand ,hzr ir∈Rgrand that indicate the presence of siblingand grandparent arcs. Observe that these indicator variables are conjunctions of arc indicator varisibl = z ∧ z and z grand = z ∧ z .
ables, i.e., zijk
ij
ij
ik
jk
ijk
Hence, these features can be handled in our formulation by adding the following O(|A| · |V |) variables and constraints:
sibl
zijk
≤ zij ,

can be incorporated in our model by adding “dynamic” constraints to our ILP. Define:zijk

Actually, any logical condition can be encoded with linear constraints involving binary variables; see e.g. Clarke andLapata (2008) for an overview.
7
By sibling features we mean features that depend on
pairs of sibling arcs (i.e., of the form hi, ji and hi, ki); by
grandparent features we mean features that depend on pairsof grandparent arcs (of the form hi, ji and hj, ki).

next sibl ≤ z sibl
first child ≤ z
zijk
zij
ij
ijk
next
sibl
first child ≤ 1 − γ≤ 1 − βjk
zij
zijk
ij
next sibl ≥ z sibl − βfirst child ≥ z − γ
zijk
z
ij
ij
jk
ij
ijk

The following “dynamic” constraints encode thelogical relations for the auxiliary variables (16):βj(j+1) = 0βj(k+1) ≥ β
jk
X
sibl
βj(k+1) ≥zijk

γi(i+1) = 0
γi(j+1) ≥ γij
γi(j+1) ≥ ziji<jβj(k+1) ≤ βjk +

X

sibl
zijk
γi(j+1) ≤ γij + zij

i<jAuxiliary variables and constraints are defined
analogously for the case n ≥ i > j > k. This
results in a sparser constraint matrix, with onlyO(n3 ) non-zero elements.
3.4

Valency Features

A crucial fact about dependency grammars is thatwords have preferences about the number and arrangement of arguments and modifiers they accept. Therefore, it is desirable to include features

that indicate, for a candidate arborescence, howmany outgoing arcs depart from each vertex; deP
note these quantities by vi ,a∈δ + (i) za , foreach i ∈ V . We call vi the valency of the ith verval , I(v = k)tex. We add valency indicators ziki
for i ∈ V and k = 0, . . . , n − 1. This way, we areable to penalize candidate dependency trees thatassign unusual valencies to some of their vertices,by specifying a individual cost for each possible
value of valency. The following O(|V |2 ) constraints encode the agreement between valency indicators and the other variables:• All variables lie in the unit interval:

Pn−1

Now, define indicators znp , hza ia∈A , whereval =k=0 kzikPn−1 valzk=0 ik
val
zik

3.5

P

a∈δ + (i) za ,

i∈V

(17)

i∈V

≥ 0,

i ∈ V, k ∈ {0, . . . , n − 1}

For most languages, dependency parse trees tend
to be nearly projective (cf. Buchholz and Marsi,2006). We wish to make our model capable oflearning to prefer “nearly” projective parses whenever that behavior is observed in the data.
The multicommodity directed flow model of
Magnanti and Wolsey (1994) is a refinement of themodel described in §3.1 which offers a compact
and elegant way to indicate nonprojective arcs, requiring O(n3 ) variables and constraints. In thismodel, every node k 6= 0 defines a commodity:
one unit of commodity k originates at the root
node and must be delivered to node k; the variable φkij denotes the flow of commodity k in arc
hi, ji. We first replace (4–9) by (18–22):• The root sends one unit of commodity to each
node:
φka −

a∈δ − (0)X

φka = −1, k ∈ V \ {0} (18)a∈δ + (0)• Any node consumes its own commodity and noother:Xa∈δ − (j)

φka −

X

(22)

We next define auxiliary variables ψjk that indicate if there is a path from j to k. Since each vertex except the root has only one incoming arc, thefollowing linear equalities are enough to describe
these new variables:ψjk =ka∈δ − (j) φa ,P

ψ0k = 1,j, k ∈ V \ {0}k ∈ V \ {0}.

(23)

np

zanp , I(a ∈ y and a is nonprojective).

= 1,

Projectivity FeaturesXφka ∈ U, a ∈ A, k ∈ Vza ∈ U,φka = δjk , j, k ∈ V \ {0} (19)a∈δ + (j)From the definition of projective arcs in §2.1, we
np
have that za = 1 if and only if the arc is active(za = 1) and there is some vertex k in the span ofa = hi, ji such that ψik = 0. We are led to thefollowing O(|A| · |V |) constraints for hi, ji ∈ A:
zij

np

≤ zij

np
zij
np
zij

≥ zij − ψik ,≤ −min(i, j) ≤ k ≤ max(i, j)

Pmax(i,j)−1

k=min(i,j)+1 ψik + |j − i| − 1

There are other ways to introduce nonprojectivity indicators and alternative definitions of “nonprojective arc.” For example, by using dynamic
constraints of the same kind as those in §3.3,
we can indicate arcs that “cross” other arcs with
O(n3 ) variables and constraints, and a cubic number of non-zero elements in the constraint matrix(omitted for space).
3.6

Projective Parsing

It would be straightforward to adapt the constraints in §3.5 to allow only projective parse trees:np
simply force za = 0 for any a ∈ A. But there are
more efficient ways of accomplish this. While it isdifficult to impose projectivity constraints or cycle
constraints individually, there is a simpler way of
imposing both. Consider 3 (or 30 ) from §3.1.
Proposition 1 Replace condition 3 (or 30 ) with

where δjk , I(j = k) is the Kronecker delta.
• Disabled arcs do not carry any flow:φka ≤ za , a ∈ A, k ∈ V

(20)


0
0

 i ≤ π(k) ≤ j ,• There are exactly n enabled arcs:
Pa∈A za = n

300 . If hi, ji ∈ B, then, for any k = 1, . . . , nsuch that k 6= j, the parent of k must satisfy(defining i0 , min(i, j) and j 0 , max(i, j)):(21)

if i0 < k < j 0 ,π(k) < i0 ∨ π(k) > j 0 , if k < i0 or k > j 0
or k = i.

Then, Y(x) will be redefined as the set of projective dependency parse trees.
We omit the proof for space. Conditions 1, 2, and300 can be encoded with O(n2 ) constraints.

4

Experiments

We report experiments on seven languages, six(Danish, Dutch, Portuguese, Slovene, Swedishand Turkish) from the CoNLL-X shared task
(Buchholz and Marsi, 2006), and one (English)
from the CoNLL-2008 shared task (Surdeanu etal., 2008).8 All experiments are evaluated using
the unlabeled attachment score (UAS), using thedefault settings.9 We used the same arc-factored
features as McDonald et al. (2005) (included in the
MSTParser toolkit10 ); for the higher-order models
described in §3.3–3.5, we employed simple higher
order features that look at the word, part-of-speechtag, and (if available) morphological informationof the words being correlated through the indicator variables. For scalability (and noting that someof the models require O(|V | · |A|) constraints andvariables, which, when A = V 2 , grows cubicallywith the number of words), we first prune the basegraph by running a simple algorithm that ranks the
k-best candidate parents for each word in the sentence (we set k = 10); this reduces the number ofcandidate arcs to |A| = kn.11 This strategy is similar to the one employed by Carreras et al. (2008)
to prune the search space of the actual parser. The
ranker is a local model trained using a max-margin
criterion; it is arc-factored and not subject to any
structural constraints, so it is very fast.
The actual parser was trained via the online
structured passive-aggressive algorithm of Crammer et al. (2006); it differs from the 1-best MIRA
algorithm of McDonald et al. (2005) by solving a sequence of loss-augmented inference problems.12 The number of iterations was set to 10.
The results are summarized in Table 1; for thesake of comparison, we reproduced three strong
8
We used the provided train/test splits except for English,
for which we tested on the development partition. For training, sentences longer than 80 words were discarded. For testing, all sentences were kept (the longest one has length 118).
91011

http://nextens.uvt.nl/∼conll/software.html
http://sourceforge.net/projects/mstparser

Note that, unlike reranking approaches, there are still exponentially many candidate parse trees after pruning. The
oracle constrained to pick parents from these lists achieves> 98% in every case.
12
The loss-augmented inference problem can also be expressed as an LP for Hamming loss functions that factor overarcs; we refer to Martins et al. (2009) for further details.

baselines, all of them state-of-the-art parsers basedon non-arc-factored models: the second ordermodel of McDonald and Pereira (2006), the hybrid model of Nivre and McDonald (2008), which
combines a (labeled) transition-based and a graphbased parser, and a refinement of the latter, due
to Martins et al. (2008), which attempts to approximate non-local features.13 We did not reproduce the model of Riedel and Clarke (2006) since
the latter is tailored for labeled dependency parsing; however, experiments reported in that paperfor Dutch (and extended to other languages in the
CoNLL-X task) suggest that their model performs
worse than our three baselines.
By looking at the middle four columns, we cansee that adding non-arc-factored features makes
the models more accurate, for all languages. With
the exception of Portuguese, the best results areachieved with the full set of features. We canalso observe that, for some languages, the valencyfeatures do not seem to help. Merely modelingthe number of dependents of a word may not be
as valuable as knowing what kinds of dependents
they are (for example, distinguishing among arguments and adjuncts).
Comparing with the baselines, we observe that
our full model outperforms that of McDonald andPereira (2006), and is in line with the most accurate dependency parsers (Nivre and McDonald,
2008; Martins et al., 2008), obtained by combining transition-based and graph-based parsers.14
Notice that our model, compared with these hybrid parsers, has the advantage of not requiring an
ensemble configuration (eliminating, for example,
the need to tune two parsers). Unlike the ensembles, it directly handles non-local output featuresby optimizing a single global objective. Perhaps
more importantly, it makes it possible to exploit
expert knowledge through the form of hard global
constraints. Although not pursued here, the samekind of constraints employed by Riedel and Clarke(2006) can straightforwardly fit into our model,
after extending it to perform labeled dependency
parsing. We believe that a careful design of fea13

Unlike our model, the hybrid models used here as baselines make use of the dependency labels at training time; indeed, the transition-based parser is trained to predict a labeled dependency parse tree, and the graph-based parser use
these predicted labels as input features. Our model ignores
this information at training time; therefore, this comparison
is slightly unfair to us.
14
See also Zhang and Clark (2008) for a different approachthat combines transition-based and graph-based methods.

8
X0

DANISHD UTCHP ORTUGUESES LOVENE
S WEDISHT URKISHE NGLISH

]

T
AC

OR

ED
A
GR

ND

P.
Y
NC

U
. (F

LL

)
L
RE

8]
6]
E
J
F
,
L/
CP0
DS
AL
LL
RO
IB
M0
+P
FU
[M
[N
+V
[M
AR
+S
90.60 91.30 91.54 89.80 91.06 90.98 91.18 91.04 (-0.14)
84.11 84.19 84.79 83.55 84.65 84.93 85.57 85.41 (-0.16)
91.40 91.81 92.11 90.66 92.11 92.01 91.42 91.44 (+0.02)
83.67 85.09 85.13 83.93 85.13 85.45 85.61 85.41 (-0.20)
89.05 90.54 90.50 89.09 90.50 90.34 90.60 90.52 (-0.08)
75.30 75.68 76.36 75.16 76.20 76.08 76.34 76.32 (-0.02)
90.85
–
–
90.15 91.13 91.12 91.16 91.14 (-0.02)

AX

ED

Table 1: Results for nonprojective dependency parsing (unlabeled attachment scores). The three baselines are the second ordermodel of McDonald and Pereira (2006) and the hybrid models of Nivre and McDonald (2008) and Martins et al. (2008). The
four middle columns show the performance of our model using exact (ILP) inference at test time, for increasing sets of features(see §3.2–§3.5). The rightmost column shows the results obtained with the full set of features using relaxed LP inference
followed by projection onto the feasible set. Differences are with respect to exact inference for the same set of features. Bold
indicates the best result for a language. As for overall performance, both the exact and relaxed full model outperform the arcfactored model and the second order model of McDonald and Pereira (2006) with statistical significance (p < 0.01) according
to Dan Bikel’s randomized method (http://www.cis.upenn.edu/∼dbikel/software.html).

tures and constraints can lead to further improvements on accuracy.
We now turn to a different issue: scalability. In
previous work (Martins et al., 2009), we showedthat training the model via LP-relaxed inference(as we do here) makes it learn to avoid fractional solutions; as a consequence, ILP solvers
will converge faster to the optimum (on average).
Yet, it is known from worst case complexity theory that solving a general ILP is NP-hard; hence,these solvers may not scale well with the sentence
length. Merely considering the LP-relaxed versionof the problem at test time is unsatisfactory, as it
may lead to a fractional solution (i.e., a solution
whose components indexed by arcs, z̃ = hza ia∈A ,are not all integer), which does not correspond to avalid dependency tree. We propose the following
approximate algorithm to obtain an actual parse:
first, solve the LP relaxation (which can be donein polynomial time with interior-point methods);
then, if the solution is fractional, project it onto thefeasible set Y(x). Fortunately, the Euclidean projection can be computed in a straightforward way
by finding a maximal arborescence in the directed
graph whose weights are defined by z̃ (we omit
the proof for space); as we saw in §2.2, the ChuLiu-Edmonds algorithm can do this in polynomial
time. The overall parsing runtime becomes polynomial with respect to the length of the sentence.
The last column of Table 1 compares the accuracy of this approximate method with the exact one. We observe that there is not a substantial
drop in accuracy; on the other hand, we observed
a considerable speed-up with respect to exact inference, particularly for long sentences. The av-

erage runtime (across all languages) is 0.632 seconds per sentence, which is in line with existinghigher-order parsers and is much faster than theruntimes reported by Riedel and Clarke (2006).

5

Conclusions

We presented new dependency parsers based on
concise ILP formulations. We have shown how
non-local output features can be incorporated,while keeping only a polynomial number of constraints. These features can act as soft constraints
whose penalty values are automatically learned
from data; in addition, our model is also compatible with expert knowledge in the form of hard constraints. Learning through a max-margin framework is made effective by the means of a LPrelaxation. Experimental results on seven languages show that our rich-featured parsers outperform arc-factored and approximate higher-orderparsers, and are in line with stacked parsers, having with respect to the latter the advantage of not
requiring an ensemble configuration.

Acknowledgments
The authors thank the reviewers for their comments. Martins was supported by a grant from
FCT/ICTI through the CMU-Portugal Program,and also by Priberam Informática. Smith was
supported by NSF IIS-0836431 and an IBM Faculty Award. Xing was supported by NSF DBI0546594, DBI-0640543, IIS-0713379, and an Alfred Sloan Foundation Fellowship in Computer
Science.

References
E. Boros and P.L. Hammer. 2002. Pseudo-Boolean optimization. Discrete Applied Mathematics, 123(1–3):155–225.
S. Buchholz and E. Marsi. 2006. CoNLL-X sharedtask on multilingual dependency parsing. In Proc.
of CoNLL.
X. Carreras, M. Collins, and T. Koo. 2008. TAG,
dynamic programming, and the perceptron for efficient, feature-rich parsing. In Proc. of CoNLL.
X. Carreras. 2007. Experiments with a higher-orderprojective dependency parser. In Proc. of CoNLL.
M. Chang, L. Ratinov, and D. Roth. 2008. Constraints
as prior knowledge. In ICML Workshop on Prior
Knowledge for Text and Language Processing.
Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396–
1400.
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.
A. Culotta and J. Sorensen. 2004. Dependency tree
kernels for relation extraction. In Proc. of ACL.
P. Denis and J. Baldridge. 2007. Joint determinationof anaphoricity and coreference resolution using integer programming. In Proc. of HLT-NAACL.
Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion
grammar. In Proc. of ACL.
J. Edmonds. 1967. Optimum branchings. Journalof Research of the National Bureau of Standards,
71B:233–240.
J. Eisner and G. Satta. 1999. Efficient parsing forbilexical context-free grammars and head automaton
grammars. In Proc. of ACL.
J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. of COLING.
S. Kahane, A. Nasr, and O. Rambow. 1998. Pseudoprojectivity: a polynomially parsable non-projective
dependency grammar. In Proc. of COLING-ACL.
S. Lacoste-Julien, B. Taskar, D. Klein, and M. I. Jordan. 2006. Word alignment via quadratic assignment. In Proc. of HLT-NAACL.
T. L. Magnanti and L. A. Wolsey. 1994. Optimal
Trees. Technical Report 290-94, Massachusetts Institute of Technology, Operations Research Center.
A. F. T. Martins, D. Das, N. A. Smith, and E. P. Xing.
2008. Stacking dependency parsers. In Proc. of
EMNLP.
A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009.
Polyhedral outer approximations with application tonatural language parsing. In Proc. of ICML.
R. T. McDonald and F. C. N. Pereira. 2006. Online
learning of approximate dependency parsing algorithms. In Proc. of EACL.

R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of IWPT.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajič.
2005. Non-projective dependency parsing using
spanning tree algorithms. In Proc. of HLT-EMNLP.
J. Nivre and R. McDonald. 2008. Integrating graphbased and transition-based dependency parsers. In
Proc. of ACL-HLT.
V. Punyakanok, D. Roth, W. Yih, and D. Zimak. 2004.
Semantic role labeling via integer linear programming inference. In Proc. of COLING.
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 Proc. of EMNLP.
R. T. Rockafellar. 1970. Convex Analysis. Princeton
University Press.
D. Roth and W. T. Yih. 2005. Integer linear programming inference for conditional random fields. In
ICML.
A. Schrijver. 2003. Combinatorial Optimization:
Polyhedra and Efficiency, volume 24 of Algorithms
and Combinatorics. Springer.
D. A. Smith and J. Eisner. 2008. Dependency parsing
by belief propagation. In Proc. of EMNLP.
M. Surdeanu, R. Johansson, A. Meyers, L. Màrquez,and J. Nivre. 2008. The conll-2008 shared task
on joint parsing of syntactic and semantic dependencies. Proc. of CoNLL.
R. E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36.
M. Wang, N. A. Smith, and T. Mitamura. 2007. Whatis the Jeopardy model? A quasi-synchronous grammar for QA. In Proceedings of EMNLP-CoNLL.
Y. Zhang and S. Clark.
2008.
A tale oftwo parsers: investigating and combining graphbased and transition-based dependency parsing using beam-search. In Proc. of EMNLP.