Stacking Dependency Parsers∗

André F. T. Martins∗† Dipanjan Das∗ 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,dipanjan,nasmith,epxing}@cs.cmu.edu

Abstract
We explore a stacked framework for learning to predict dependency structures for natural language sentences. A typical approach ingraph-based dependency parsing has been to
assume a factorized model, where local features are used but a global function is optimized (McDonald et al., 2005b). Recently
Nivre and McDonald (2008) used the output
of one dependency parser to provide features
for another. We show that this is an example
of stacked learning, in which a second predictor is trained to improve the performanceof the first. Further, we argue that this technique is a novel way of approximating rich
non-local features in the second parser, without sacrificing efficient, model-optimal prediction. Experiments on twelve languages
show that stacking transition-based and graphbased parsers improves performance over existing state-of-the-art dependency parsers.

1

Introduction

In this paper we address a representation-efficiency
tradeoff in statistical natural language processing
through the use of stacked learning (Wolpert,
1992). This tradeoff is exemplified in dependency
parsing, illustrated in Fig. 1, on which we focus inthis paper:• Exact algorithms for dependency parsing (Eisner and Satta, 1999; McDonald et al., 2005b)
are tractable only when the model makes verystrong, linguistically unsupportable independence

assumptions, such as “arc factorization” for nonprojective dependency parsing (McDonald andSatta, 2007).
• Feature-rich parsers must resort to search or
greediness, (Ratnaparkhi et al., 1994; Sagae andLavie, 2005; Hall et al., 2006), so that parsing
solutions are inexact and learned models may besubject to certain kinds of bias (Lafferty et al.,2001).
A solution that leverages the complementarystrengths of these two approaches—described in detail by McDonald and Nivre (2007)—was recently
and successfully explored by Nivre and McDonald(2008). Our contribution begins by reinterpretingand generalizing their parser combination scheme asa stacking of parsers.
We give a new theoretical motivation for stacking
parsers, in terms of extending a parsing model’s feature space. Specifically, we view stacked learning as
a way of approximating non-local features in a linear model, rather than making empirically dubious
independence (McDonald et al., 2005b) or structural
assumptions (e.g., projectivity, Eisner, 1996), using
search approximations (Sagae and Lavie, 2005; Hallet al., 2006; McDonald and Pereira, 2006), solving a(generally NP-hard) integer linear program (Riedel
and Clarke, 2006), or adding latent variables (Titov
and Henderson, 2007). Notably, we introduce theuse of very rich non-local approximate features in
one parser, through the output of another parser.
Related approaches are the belief propagation algorithm of Smith and Eisner (2008), and the “tradingof structure for features” explored by Liang et al.

learning via the EM algorithm – none of which have
2.1 Dependency
Parsingpreviously
been
to have exact
learning
via
the known
EM algorithm– nonenon-projectiveof which have
implementations.
previously
been
known
to
have
exact
non-projective
Dependency syntax is a lightweight syntactic repWe then switch
to modelsthat accountfor where
implementations.
resentation
thatfocus
modelsa sentence
as a graphnon-local
information,in particular
arity
and
neighWethenswitchfocus
tomodelsthat
account
for arethe words are vertices and syntactic relationships$
Figure 1: A projective dependency graph.
bouring
parse
decisions.
Forsystemsthat
modelarnon-local
particular arity
andtoneighdirectedinformation,edges (arcs)inconnecting
heads
their arguity
constraints
wegive a reduction
from thatthe HamiltoFigure 1: A projective dependency graph.
bouring
parse
decisions.
Forsystemsmodel arments
andmodifiers.
niangraph problem
suggestingthat fromthe parsing
probity constraints
we givea reduction
the HamiltoDependency
parsingisoften
viewedcomputalem
intractable
this case.thatFor
nianisgraphprobleminsuggestingtheneighbouringparsing probtionallyasastructured
prediction
problem:for eachparse
we inextend
the work
McDonald
lem isdecisions,intractable
this case.
Forofneighbouring
input
sentencex,withnwords,
exponentially
andPereira(2006)weandshow thethatworkmodeling
vertical many$parse
decisions,extendof McDonald
candidate dependency
trees intractabley ∈ Y(x) are
possible inneighbourhoods
makes
addiand Pereira (2006)
and parsing
show thatmodelinginverticalFigure 2: Non-projective dependency graph.
principle.
We
denote
each
tree
by
its
set
of vertices
tiontomodelinghorizontal
neighbourhoods.
A
conneighbourhoods makes parsing intractable in addiFigure Figure
1: A projective
dependency
parse (top),graph.
and a non- sequence
2: Non-projective
dependencyof thesearcs,
results
is thatitisunlikelythat
anddirected
y
=
(V
,
A
).
A
legal
y
y
tion to modeling horizontal neighbourhoods.
A con-depenprojective
dependency
parse(bottom)fortwoEnglishexact
non-projective
dependency
parsingistractable
those that assume each dependency decision is indency tree
has nresults+ 1 vertices,
corresponding
tosequenceof theseis that iteachis unlikely
that
sentences; examples from McDonald and Satta (2007).
anywordmodelplus
assumptions
weakerthanthose madedependent modulo the global structural constraint foronea“wall”
symbol,$,assumedtobethethose that assume each dependency decision is in- exact non-projective dependency parsing is tractablethat dependency graphs must be trees. Such mod- by the edge-factored
root assumptionsof themodels.
sentence.
a valid
any model
weakerInthan
thosedependency
madedependent modulo the global structural constraint forhidden
els are commonly referred to as edge-factored since(2008).
tree,
eachvertexexcepttheroot
has
exactly
one parby theRelatededge-factored
that dependency graphs must be trees. Such mod- 1.1
Work models.
their paper
parametersfactorto individualThisfocuseson relative
dependency
parsing,edges
which ent. In the projective case, arcs cannot cross whenels
arereferred2001;
to as edge-factored
has beenWork
extensive work on data-driven deofbecome
the commonly
graph(Paskin,
McDonald
etsinceal.,hastheirwidelyused relativein relation
extraction(Cu- There
1.1
Relateddepictedon one side of the sentence; in the nonparametersfactortoindividualedges
pendency
parsingfor both projective parsing (Eis2005a).
Edge-factoredmodelshave
many
computalotta
and graph
Sorensen,2004),
machinetranslation
projective
case,
this constraintis
not imposed
There
has
been
extensive
work onand
data-drivende- (seeofthe(Paskin,
2001;
McDonald
etal.,Matsumoto,tionalbenefits,
mostnotablythat inference
for(Wangnon- ner, 1996; Paskin, 2001; Yamada
(Ding
and
Palmer,2005),
questionanswering
Fig. Nivre1). parsing
pendency
for both2004;
projective
parsing
2005a).
Edge-factoredmany
computaand Scholz,
McDonald
et (Eisal.,projective
dependency models
graphs havecan beachieved
in 2003;et tionalal., 2007),
and
many
other
NLP
applications.
ner,
1996;
Paskin,2001;
YamadaandMatsumoto,benefits,
mostnotablythatinferencefornonandnon-projective
parsingsystems(Nivrepolynomial time (McDonald et al., 2005b). The pri- 2005a)
2.1.1 Graph-based vs. transition-based models
Weprojective
show thatdependency
stacking methods
outperformthe ap2003;
Nivre2005;
and Scholz,
et al.,
graphsbe achievedin andNilsson,Hall and2004;Nóvák,McDonald
2005; McDonmary problem
in treatingeach candependency
as inMost
recentworkondependency
parsing
can beproximate“second-order”
parserof
McDonald
and2005a)
non-projective
parsing systems(Nivrepolynomialal., 2005b).
The pri- ald
et al.,and2005b).
These approaches
can oftenbedependent istime
that(McDonald
it is not aetrealistic
assumption.
categorizedasgraph-basedortransition-based.
In
Pereira(2006)
ontwelvelanguages
and
can
be
used
and Nilsson,
Hall categories.
and Nóvák,In2005;
McDonmaryproblemin treatingeach
as in- classified
into 2005;
two broadthe first
catNon-local
information,such
as dependency
arity (or valency)
parsing,
dependency
treesarebescoredwithinapproximation
to aachieve
bettertore- egory
aldgraph-based
et areal., those
2005b).
Thesethatapproaches
can
often
dependent
is that dependencies,
it is notrealistic
methods
employ approximate
and thatneighbouring
can evenbeassumption.
crucialbyfactoring
the
tree
into
its
arcs,
and
parsingissults.
These
resultsaresimilarinspiritto(Nivreandclassified
into
two
broad
categories.
In
the
first
catNon-local
information,
such
as
arity
(or
valency)obtaining high parsing accuracies (Klein and Man- inference, typically through the use of linear time
performedbysearchingforthehighestscoring
tree
McDonald,2008),
butwithfollowing
conegory are thosemethods
that employ
anddependencies,
can2006).
be novelcrucialto shift-reduceparsingalgorithms(Yamadaapproximate
and Matning,neighbouring
2002;
McDonald
andthePereira,
How(Eisner,
1996;
McDonald
et al.,
2005b).
inference,
typically
throughtheuseof NivrelinearTransitiontime
obtaininghighparsing accuracies(Kleinthis
andcanMantributions:
2003;
Nivre
and Scholz,
2004;
and
ever, in thedata-driven
parsing setting
be sumoto,
Inmodelthesecondcategoryarethosebased 2005).
parsers
the sequence
decisionspartially
advertedby incorporatingrich2006).
featureHowrep- Nilsson,shift-reduceparsingalgorithms(Yamadaof
andMat- ofning,
2002;
McDonald
and Pereira,• aever,stacking
employexhaustive
inference
algorithms,
usuresentations
over
the inputparsing(McDonald
et al.,
sumoto,
2003;
Nivre
and
Scholz,previous
2004; Nivre
and andin theinterpretation,
data-driven
setting
this2005a).
can be thata shift-reduceparser,given
decisionsallybymakingstrongindependence
assumptions,
as
The
goal
of
this
work
is
to
furtherourcurrent• apartiallyricher featureincludes non-local
featuresIn thesecondareby
thoseadvertedsetbythat
incorporatingrich feature
rep- Nilsson,
current2005).
state, andparsing
is category
performed
greedilytheemploycase fortheedge-factoredmodelstransition(Paskin, 2001;
understanding
theinputcomputationalofnon- isthat
exhaustive
algorithms,(shownhereovertoofimprove
performance),
andresentations
the(McDonaldnature
et al.,
2005a).
choosing
highest inference
scoringoutusuof eachetal.,2005a;
McDonaldetal.,2005b).
projective
parsingalgorithms
forfurther
both learning
and McDonald
allybymakingstrongindependence
assumptions,
as
The
goal
of
this
work
is
to
our
current
successive parsing state or by searching for the best
• a variety of stacking architectures.
there
also been(Ratnaparkhi
proposals
for exhausinference withinsetting.
We start
by Recently
is sequence
the caseforedge-factoredmodels(Paskin,understanding
ofthe
thedata-driven
computational
natureof nonofhavetransitions
et 2001;
al., 1994;
tive
methods
thatweakentheedge-factored
assumpinvestigating
andextendingtheedge-factored
model
Using
stacking
withalgorithms
rich features,
we obtain
et al.,Matsumoto,2005a; McDonald
al., 2005b).
projective
parsingfor bothlearningresultsand McDonald
Yamada and2003; etNivre
et al., 2004;
includingbothmethodsfor(McDonof McDonald
al. data-driven(2005b).
Insetting.
particular,
wewhileapRecently
thereLavie,
haveapproximate
also
been
proposals
exhauscompetitive
withetNivre
and McDonald(2008)
inference
withinthe
We startby tion,Sagae and
2005;
Hall
et al., 2006).
ald
andPereira,
2006)
and
exact
methods
through
inpealtothe
MatrixTree
Theoremformulti-digraphs
thatweakentheedge-factored
assumpinvestigating
theparsingedge-factored
preserving
the andfastextending
quadratic
time modelof arc- tive methods
Bothapproaches
mostcommonlyuse
linearmodlinear
programming(Riedel and
Clarke,2006)
to McDonald
designpolynomial-timealgorithms
for calculattion,
includingbothapproximate
methods(McDonof
et treeal. (2005b).
In particular,
we ap- teger
factoredspanning
algorithms.
els
to assign scores
to arcs(Hirakawa,or decisions,so that a
branch-and-bound2006).
ing bothpartition
andedge expecta- or
and Pereira,2006)algorithms
and exact
methods
through
inpealto thethe
MatrixTree function
Theoremfor multi-digraphs
The
paper
is organized
as follows.
We discuss re- aldscoreisadot-productofafeaturevectorf and ations
over polynomial-time
all possible dependency
graphsfor
forcalculata given
For linear
grammarbased models
thereandhas Clarke,
been limited
teger
programming(Riedel2006)
todesignalgorithms
lated prior work on dependency parsing and stacking learned weight vector w.
sentence. To motivate these algorithms, we show work on empirical systems for non-projective parsing
both model
the partition
functionandedgeanalysis
expecta- or branch-and-bound algorithms (Hirakawa, 2006).
in §2.
given
§3. A
novel
In sum, notablethese twolines ofinclude
researchdifferent
that Ourthey can beisused
in in
many
importantlearningof ing systems,
exceptions
theusework
tions overall possible
dependency
for a given
For grammar based models there has been limited
stacking
in linearmodelsisincluding
given ingraphs§4. Experiments
achieve
tractability.
Transitionand inference
problems
min-risk
decod- of approximations
Wang and Harperto(2004).
Theoreticalstudiesof
To motivate
these algorithms, we show work on empirical systems for non-projective parsaresentence.
presented§5.
includethe work ofsolve
Neuhausand Bökerof(1997)
ing,
trainingingloballynormalized log-linear mod- note
based
approaches
a sequence
local probthat they can be used in many important learning ing systems, notable exceptions include the workels, syntactic language modeling, and unsupervised showing
the recognition
problema mini- guarlems inthat
sequence,sacrificing
globalfor
optimality
inference problems
includingWork
min-risk decod- of Wang and Harper (2004). Theoretical studies of
2 andBackgroundand Related
antees and possibly expressive power (Abney et al.,ing, training globally normalized log-linear mod- note include the work of Neuhaus and Böker (1997)
Weels,
briefly
review
work modeling,on the NLP
of depen- showing1999). that
Graph-based
methods
perform
global insyntactic
languageandtask
unsupervised
the recognition
problem
for a mini-dency parsing and the machine learning framework
known as stacked learning.

ference using score factorizations that correspondto strong independence assumptions (discussed in§2.1.2). Recently, Nivre and McDonald (2008) proposed combining a graph-based and a transitionbased parser and have shown a significant improvement for several languages by letting one of theparsers “guide” the other. Our stacked formalism(to be described in §3) generalizes this approach.
2.1.2 Arc factorization
In the successful graph-based method of McDonald et al. (2005b), an arc factorization independence
assumption is used to ensure tractability. This assumption forbids any feature that depends on two
or more arcs, permitting only “arc-factored” features(i.e. features that depend only on a single candidate
arc a ∈ Ay and on the input sequence x). This induces a decomposition of the feature vector f (x, y)as:Xf (x, y) =fa (x).
a∈Ay

Parsing amounts to solving arg maxy∈Y(x)w> f (x, y), where w is a weight vector. Witha projectivity constraint and arc factorization, theparsing problem can be solved in cubic time bydynamic programming (Eisner, 1996), and with aweaker “tree” constraint (permitting nonprojective
parses) and arc factorization, a quadratic-timealgorithm exists (Chu and Liu, 1965; Edmonds,
1967), as shown by McDonald et al. (2005b). In
the projective case, the arc-factored assumption canbe weakened in certain ways while maintaining
polynomial parser runtime (Eisner and Satta, 1999),
but not in the nonprojective case (McDonald andSatta, 2007), where finding the highest-scoring tree
becomes NP-hard.
McDonald and Pereira (2006) adopted an approximation based on O(n3 ) projective parsing followedby rearrangement to permit crossing arcs, achieving
higher performance. In §3 we adopt a frameworkthat maintains O(n2 ) runtime (still exploiting the
Chu-Liu-Edmonds algorithm) while approximating
non arc-factored features.
2.2

Stacked Learning

Stacked generalization was first proposed by
Wolpert (1992) and Breiman (1996) for regression.
The idea is to include two “levels” of predictors. The
first level, “level 0,” includes one or more predictors
g1 , . . . , gK : Rd → R; each receives input x ∈ Rd

and outputs a prediction gk (x). The second level,“level 1,” consists of a single function h : Rd+K →R that takes as input hx, g1 (x), . . . gK (x)i and outputs a final prediction ŷ = h(x, g1 (x), . . . gK (x)).
The predictor, then, combines an ensemble (the gk )with a meta-predictor (h).
Training is done as follows: the training data are
split into L partitions, and L instances of the level
0 predictor are trained in a “leave-one-out” basis.
Then, an augmented dataset is formed by letting
each instance output predictions for the partition thatwas left out. Finally, each level 0 predictor is trainedusing the original dataset, and the level 1 predictor
is trained on the augmented dataset, simulating thetest-time setting when h is applied to a new instancex concatenated with hgk (x)ik .
This framework has also been applied to classification, for example with structured data. Some applications (including here) use only one classifier atlevel 0; recent work includes sequence labeling (Cohen and de Carvalho, 2005) and inference in conditional random fields (Kou and Cohen, 2007). Stacking is also intuitively related to transformation-basedlearning (Brill, 1993).

3

Stacked Dependency Parsing

We next describe how to use stacked learning for
efficient, rich-featured dependency parsing.
3.1

Architecture

The architecture consists of two levels. At level 0
we include a single dependency parser. At runtime,
this “level 0 parser” g processes an input sentence x
and outputs the set of predicted edges that make up
its estimation of the dependency tree, ŷ0 = g(x). At
level 1, we apply a dependency parser—in this work,
always a graph-based dependency parser—that uses
basic factored features plus new ones from the edges
predicted by the level 0 parser. The final parser predicts parse trees as h(x, g(x)), so that the total runtime is additive in calculating h(·) and g(·).
The stacking framework is agnostic about theform of g and h and the methods used to learn themfrom data. In this work we use two well-known,
publicly available dependency parsers, MSTParser(McDonald et al., 2005b),1 which implements ex1

http://sourceforge.net/projects/mstparser

act first-order arc-factored nonprojective parsing(§2.1.2) and approximate second-order nonprojective parsing, and MaltParser (Nivre et al., 2006),
which is a state-of-the-art transition-based parser.2
We do not alter the training algorithms used in priorwork for learning these two parsers from data. Using the existing parsers as starting points, we will
combine them in a variety of ways.
3.2

Training

Regardless of our choices for the specific parsers andlearning algorithms at level 0 and level 1, training isdone as sketched in §2.2. Let D be a set of training
examples {hxi , yi i}i .
1. Split training data D into L partitions
D1 , . . . , DL .
2. Train L instances of the level 0 parser in the following way: the l-th instance, g l , is trained on
D−l = D \ Dl . Then use g l to output predictions for the (unseen) partition Dl . At the end,Sl
an augmented dataset D̃ = L
l=1 D̃ is built, sothat D̃ = {hxi , g(xi ), yi i}i .
3. Train the level 0 parser g on the original training
data D.
4. Train the level 1 parser h on the augmented training data D̃.
The runtime of this algorithm is O(LT0 +T1 ), where
T0 and T1 are the individual runtimes required fortraining level 0 and level 1 alone, respectively.

4

Two Views of Stacked Parsing

We next describe two motivations for stacking
parsers: as a way of augmenting the features of agraph-based dependency parser or as a way to approximate higher-order models.
4.1

Adding Input Features

Suppose that the level 1 classifier is an arc-factored
graph-based parser. The feature vectors will take theform3
f (x, y) = f1 (x, y) ^ f2 (x, ŷ0 , y)=X

f1,a (x) ^ f2,a (x, g(x)),

a∈Ay2

http://w3.msi.vxu.se/∼jha/maltparser

3

We use ^ to denote vector concatenation.

P

where f1 (x, y) =a∈Ay f1,a (x) are regular arc-factored features, and f2 (x, ŷ0 , y) =Pa∈Ay f2,a (x, g(x)) are the stacked features. An
example of a stacked feature is a binary feature
f2,a (x, g(x)) that fires if and only if the arc a waspredicted by g, i.e., if a ∈ Ag(x) ; such a feature wasused by Nivre and McDonald (2008).
It is difficult in general to decide whether the inclusion of such a feature yields a better parser, sincefeatures strongly correlate with each other. However, a popular heuristic for feature selection consists of measuring the information gain provided byeach individual feature. In this case, we may obtaina closed-form expression for the information gainthat f2,a (x, g(x)) provides about the existence or notof the arc a in the actual dependency tree y. Let A
and A0 be binary random variables associated withthe events a ∈ Ay and a0 ∈ Ag(x) , respectively. We
have:
I(A; A0 ) =X

p(a, a0 ) log2a,a0 ∈{0,1}= H(A0 ) −X

p(a, a0 )p(a)p(a0 )p(a)H(A0 |A = a).

a∈{0,1}

Assuming, for simplicity, that at level 0 the probability of false positives equals the probability offalse negatives (i.e., Perr , p(a0 = 0|a = 1) =p(a0 = 1|a = 0)), and that the probability oftrue positives equals the probability of true negatives(1 − Perr = p(a0 = 0|a = 0) = p(a0 = 1|a = 1)),the expression above reduces to:I(A; A0 ) = H(A0 ) + Perr log2 Perr
+ (1 − Perr ) log2 (1 − Perr )= H(A0 ) − Herr ,where Herr denotes the entropy of the probability oferror on each arc’s prediction by the level 0 classifier. If Perr ≤ 0.5 (i.e. if the level 0 classifier isbetter than random), then the information gain provided by this simple stacked feature increases with(a) the accuracy of the level 0 classifier, and (b) the
entropy H(A0 ) of the distribution associated with its
arc predictions.
4.2

Approximating Non-factored Features

Another way of interpreting the stacking framework
is as a means to approximate a higher order model,such as one that is not arc-factored, by using stacked
features that make use of the predicted structurearound a candidate arc. Consider a second-ordermodel where the features decompose by arc and byarc pair:f (x, y) =XX

fa (x) ^1

a1 ∈Ayfa1 ,a2 (x) .

a2 ∈AyExact parsing under such model, with arbitrary
second-order features, is intractable (McDonald andSatta, 2007). Let us now consider a stacked modelin which the level 0 predictor outputs a parse ŷ. At
level 1, we use arc-factored features that may be
written asf̃ (x, y) =XX

fa (x) ^1

a1 ∈Ay=≤

a2 ∈Aŷ∆s(x, y) = w̃> f̃ (x, y) − w> f (x, y) ,where w̃ and w stand respectively for the parameters
learned for the stacked model and those that would
be learned for the (intractable) exact second ordermodel. We can bound ∆s(x, y) by spliting it into
two terms: ∆s(x, y) =>(w̃ − w) f̃ (x, y) + w (f̃ (x, y) − f (x, y))≤w> (f̃ (x, y) − f (x, y))
X

w2> 

a1 ∈Ayfa1 ,a2 (x) ;this model differs from the previous one only by replacing Ay by Aŷ in the index set of the second summation. Since ŷ is given, this makes the latter modelarc-factored, and therefore, tractable. We can now
view f̃ (x, y) as an approximation of f (x, y); indeed,
we can bound the score approximation error,>

where k.k1 and k.k∞ denote the `1 -norm and supnorm, respectively, and the last inequality holds
when the features are binary (so that kf̃ (x, y)k∞ ≤1). The proper way to bound the term kw̃ − wk1
depends on the training algorithm. As for the decoding error term, it can bounded for a given weightvector w, sentence x, candidate tree y, and level 0
prediction ŷ. Decomposing the weighted vector as
w = w1 ^ w2 , w2 being the sub-vector associated with the second-order features, we have respectively: ∆sdec (x, y) =

X


X

X

fa1 ,a2 (x) −a2 ∈Aŷfa1 ,a2 (x)a2 ∈Ayw2> fa1 ,a2 (x)X

a1 ∈Ay a2 ∈Aŷ ∆Ay≤

X|Aŷ ∆Ay | ·a1 ∈Ay=X

2L(y, ŷ) ·a1 ∈Aymax

w2> fa1 ,a2 (x)max

w2> fa1 ,a2 (x) ,a2 ∈Aŷ ∆Ay

a2 ∈Aŷ ∆Aywhere Aŷ ∆Ay , (Aŷ − Ay ) ∪ (Ay − Aŷ ) denotes
the symmetric difference of the sets Aŷ and Ay ,which has cardinality 2L(y, ŷ), i.e., twice the Hamming distance between the sequences of heads thatcharacterize y and the predicted parse ŷ. Using
Hölder’s inequality, we have bothw2> fa1 ,a2 (x)≤ kw2 k1 · kfa1 ,a2 (x)k∞and w2> fa1 ,a2 (x)≤ kw2 k∞ · kfa1 ,a2 (x)k1 .

>>(w̃ − w) f̃ (x, y) + w (f̃ (x, y) − f (x, y)) ;
|

{z

} |

,∆str (x,y){z},∆sdec (x,y)

where we introduced the terms ∆str and ∆sdec thatreflect the portion of the score approximation errorthat are due to training error (i.e., different parameterizations of the exact and approximate models) anddecoding error (same parameterizations, but different feature vectors). Using Hölder’s inequality, theformer term can be bounded as:∆str (x, y) =(w̃ − w)> f̃ (x, y)≤ kw̃ − wk1 · kf̃ (x, y)k∞
≤ kw̃ − wk1 ;Assuming that all features are binary valued, we
have that kfa1 ,a2 (x)k∞ ≤ 1 and that kfa1 ,a2 (x)k1 ≤Nf,2 , where Nf,2 denotes the maximum number ofactive second order features for any possible pair ofarcs (a1 , a2 ). Therefore:∆sdec (x, y) ≤ 2nL(y, ŷ) min{kw2 k1 , Nf,2 ·kw2 k∞ },where n is the sentence length. Although this boundcan be loose, it suggests (intuitively) that the scoreapproximation degrades as the predicted tree ŷ gets
farther away from the true tree y (in Hamming distance). It also degrades with the magnitude ofweights associated with the second-order features,

Name
PredEdge

Description
Indicates whether the candidate edge
was present, and what was its label.
Sibling
Lemma, POS, link label, distance anddirection of attachment of the previous
and and next predicted siblings
GrandParents Lemma, POS, link label, distance anddirection of attachment of the grandparent of the current modifier
PredHead
Predicted head of the candidate modifier(if PredEdge=0)
AllChildren Sequence of POS and link labels of all
the predicted children of the candidate
head
Table 1: Feature sets derived from the level 0 parser.

SubsetA
B
C
D
E

Description
PredEdge
PredEdge+Sibling
PredEdge+Sibling+GrandParents
PredEdge+Sibling+GrandParents+PredHead
PredEdge+Sibling+GrandParents+PredHead+
AllChildren

Table 2: Combinations of features enumerated in Table 1
used for stacking. A is a replication of (Nivre and McDonald, 2008), except for the modifications described infootnote 4.

which suggests that a separate regularization of thefirst-order and stacked features might be beneficial
in a stacking framework.
As a side note, if we set each component of
the weight vector to one, we obtain a boundon the `1 -norm of the feature vector difference,f̃ (x, y) − f (x, y) ≤ 2nL(y, ŷ)Nf,2 .
1

5

Experiments

In the following experiments we demonstrate the effectiveness of stacking parsers. As noted in §3.1, we
make use of two component parsers, the graph-based
MSTParser and the transition-based MaltParser.
5.1

Implementation and Experimental Details

The publicly available version of MSTParser performs parsing and labeling jointly. We adapted thissystem to first perform unlabeled parsing, then label the arcs using a log-linear classifier with accessto the full unlabeled parse (McDonald et al., 2005a;

McDonald et al., 2005b; McDonald and Pereira,2006). In stacking experiments, the arc labels fromthe level 0 parser are also used as a feature.4
In the following subsections, we refer to our modification of the MSTParser as MST 1O (the arcfactored version) and MST 2O (the second-order
arc-pair-factored version). All our experiments use
the non-projective version of this parser. We refer tothe MaltParser as Malt.
We report experiments on twelve languages fromthe CoNLL-X shared task (Buchholz and Marsi,2006).5 All experiments are evaluated using thelabeled attachment score (LAS), using the default
settings.6 Statistical significance is measured using Dan Bikel’s randomized parsing evaluation comparator with 10,000 iterations.7 The additional features used in the level 1 parser are enumerated inTable 1 and their various subsets are depicted in Table 2. The PredEdge features are exactly the six features used by Nivre and McDonald (2008) in their
MSTMalt parser; therefore, feature set A is a replication of this parser except for modifications noted
in footnote 4. In all our experiments, the number ofpartitions used to create D̃ is L = 2.
5.2

Experiment: MST 2O + MST 2O

Our first experiment stacks the highly accurate
MST 2O parser with itself. At level 0, the parser
uses only the standard features (§5.1), and at level 1,
these are augmented by various subsets of featuresof x along with the output of the level 0 parser, g(x)(Table 2). The results are shown in Table 3. While
we see improvements over the single-parser baseline4

We made other modifications to MSTParser, implementing many of the successes described by (McDonald et al.,2006). Our version of the code is publicly available at http://www.ark.cs.cmu.edu/MSTParserStacked. The
modifications included an approximation to lemmas for datasets
without lemmas (three-character prefixes), and replacing morphology/word and morphology/lemma features with morphology/POS features.
5
The CoNLL-X shared task actually involves thirteen languages; our experiments do not include Czech (the largest
dataset), due to time constraints. Therefore, the average resultsplotted in the last rows of Tables 3, 4, and 5 are not directlycomparable with previously published averages over thirteen
languages.
6

http://nextens.uvt.nl/∼conll/software.html
http://www.cis.upenn.edu/∼dbikel/software.
html
7

Arabic
Bulgarian
ChineseDanishDutch
GermanJapanese
Portuguese
SloveneSpanishSwedishTurkishAverage

,A
,B
,C
,D
,E
T 2O MST 2O MST 2O MST 2O MST 2O
2O
S
T
S
M
M
+
+
+
+
+
67.88 66.91 67.41 67.68 67.37 68.02
87.31 87.39 87.03 87.61 87.57 87.55
87.57 87.16 87.24 87.48 87.42 87.48
85.27 85.39 85.61 85.57 85.43 85.57
79.99 79.79 79.79 79.83 80.17 80.13
87.44 86.92 87.32 87.32 87.26 87.04
90.93 91.41 91.21 91.35 91.11 91.19
87.12 87.26 86.88 87.02 87.04 86.98
74.02 74.30 74.30 74.00 74.14 73.94
82.43 82.17 82.35 82.81 82.53 82.75
82.87 82.99 82.95 82.51 83.01 82.69
60.11 59.47 59.25 59.47 59.45 59.31
81.08 80.93 80.94 81.05 81.04 81.05

Table 3: Results of stacking MST 2O with itself at both level 0 and level 1. Column 2 enumerates LAS for MST 2O .
Columns 3–6 enumerate results for four different stacked feature subsets. Bold indicates best results for a particularlanguage.

for nine languages, the improvements are small (lessthan 0.5%). One of the biggest concerns about thismodel is the fact that it stacks two predictors thatare very similar in nature: both are graph-based andshare the features f1,a (x). It has been pointed out by
Breiman (1996), among others, that the success ofensemble methods like stacked learning strongly depends on how uncorrelated the individual decisions
made by each predictor are from the others’ decisions.8 This experiment provides further evidence
for the claim.
5.3

Experiment: Malt + MST 2O

We next use MaltParser at level 0 and the secondorder arc-pair-factored MST 2O at level 1. Thisextends the experiments of Nivre and McDonald(2008), replicated in our feature subset A.
Table 4 enumerates the results. Note that thebest-performing stacked configuration for each andevery language outperforms MST 2O , corroborating results reported by Nivre and McDonald (2008).
The best performing stacked configuration outperforms Malt as well, except for Japanese and Turkish. Further, our non-arc-factored features largely
outperform subset A, except on Bulgarian, Chinese,

and Japanese. On average, the best feature configuration is E, which is statistically significant overMalt and MST 2O with p < 0.0001, and over feature subset A with p < 0.01.
5.4

Experiment: Malt + MST 1O

Finally, we consider stacking MaltParser with thefirst-order, arc-factored MSTParser. We view thisapproach as perhaps the most promising, since it isan exact parsing method with the quadratic runtime
complexity of MST 1O .
Table 5 enumerates the results. For all twelve
languages, some stacked configuration outperforms
MST 1O and also, surprisingly, MST 2O , the second order model. This provides empirical evidence that using rich features from MaltParser atlevel 0, a stacked level 1 first-order MSTParser canoutperform the second-order MSTParser.9 In only
two cases (Japanese and Turkish), the MaltParser
slightly outperforms the stacked parser.
On average, feature configuration D performs
the best, and is statistically significant over Malt,
MST 1O , and MST 2O with p < 0.0001, and overfeature subset A with p < 0.05. Encouragingly, thisconfiguration is barely outperformed by configura-

8This claim has a parallel in the cotraining method (Blumand Mitchell, 1998), whose performance is bounded by the degree of independence between the two feature sets.

9

Recall that MST 2O uses approximate search, as opposed
to stacking, which uses approximate features.

Arabic
Bulgarian
ChineseDanishDutch
GermanJapanese
Portuguese
SloveneSpanishSwedishTurkishAverage

,A
,D
,E
,B
,C
2O
2O
2O
2O
2O
T
T
T
T
T
S
S
S
S
S
M
M
M
M
M
2O
t
t + alt + alt + alt + alt +Mal
MST MalM
M
M
M
66.71 67.88 68.56 69.12 68.64 68.34 68.92
87.41 87.31 88.99 88.89 88.89 88.93 88.91
86.92 87.57 88.41 88.31 88.29 88.13 88.41
84.77 85.27 86.45 86.67 86.79 86.13 86.71
78.59 79.99 80.75 81.47 81.47 81.51 81.29
85.82 87.44 88.16 88.50 88.56 88.68 88.38
91.65 90.93 91.63 91.43 91.59 91.61 91.49
87.60 87.12 88.00 88.24 88.30 88.18 88.22
70.30 74.02 76.62 76.00 76.60 76.18 76.72
81.29 82.43 83.09 83.73 83.47 83.21 83.43
84.58 82.87 84.92 84.60 84.80 85.16 84.88
65.68 60.11 64.35 64.51 64.51 65.07 65.21
80.94 81.08 82.52 82.58 82.65 82.59 82.71

Table 4: Results of stacking Malt and MST 2O at level 0 and level 1, respectively. Columns 2–4 enumerate LAS for
Malt, MST 2O and Malt + MST 2O as in Nivre and McDonald (2008). Columns 5–8 enumerate results for four otherstacked feature configurations. Bold indicates best result for a language.

5.5

Disagreement as a Confidence Measure

In pipelines or semisupervised settings, it is useful when a parser can provide a confidence measure
alongside its predicted parse tree. Because stacked
predictors use ensembles with observable outputs,
differences among those outputs may be used to estimate confidence in the final output. In stacked dependency parsing, this can be done (for example) bymeasuring the Hamming distance between the outputs of the level 0 and 1 parsers, L(g(x), h(x)). Indeed, the bound derived in §4.2 suggests that thesecond-order approximation degrades for candidate
parses y that are Hamming-far from g(x); therefore,
if L(g(x), h(x)) is large, the best score s(x, h(x))
may well be “biased” due to misleading neighboring information provided by the level 0 parser.
We illustrate this point with an empirical analysisof the level 0/1 disagreement for the set of experiments described in §5.3; namely, we compare the1

Level 0Level 1
Level 0 (Overall)
Level 1 (Overall)

0.95

Sentence Averaged Accuracytion A of Malt + MST 2O (see Table 4), the difference being statistically insignificant (p > 0.05).
This shows that stacking M alt with the exact, arcfactored MST 1O bridges the difference between theindividual MST 1O and MST 2O models, by approximating higher order features, but maintaining an
O(n2 ) runtime and finding the model-optimal parse.

0.9
0.85
0.8
0.75
0.7
0.65

0

2

4

6

8

10

L(g(x),h(x))

Figure 2: Accuracy as a function of token disagreement
between level 0 and level 1. The x-axis is the Hamming
distance L(g(x), h(x)), i.e., the number of tokens wherelevel 0 and level 1 disagree. The y-axis is the accuracy
averaged over sentences that have the specified Hamming
distance, both for level 0 and level 1.

Arabic
Bulgarian
ChineseDanishDutch
GermanJapanese
Portuguese
SloveneSpanishSwedishTurkishAverage

,A
,E
,B
,C
,D
1O
1O
1O
1O
1O
T
T
T
T
T
S
S
S
S
S
M
M
M
M
M
1O
2O
t
t + alt + alt + alt + alt +Mal
MST MST Mal
M
M
M
M
66.71 66.81 67.88 68.40 68.50 68.20 68.42 68.68
87.41 86.65 87.31 88.55 88.67 88.75 88.71 88.79
86.92 86.60 87.57 87.67 87.73 87.83 87.67 87.61
84.77 84.87 85.27 86.59 86.27 86.21 86.35 86.15
78.59 78.95 79.99 80.53 81.51 80.71 81.61 81.37
85.82 86.26 87.44 88.18 88.30 88.20 88.36 88.42
91.65 91.01 90.93 91.55 91.53 91.51 91.43 91.57
87.60 86.28 87.12 88.16 88.26 88.46 88.26 88.36
70.30 73.96 74.02 75.84 75.64 75.42 75.96 75.64
81.29 81.07 82.43 82.61 83.13 83.13 83.09 82.99
84.58 81.88 82.87 84.86 84.62 84.64 84.82 84.76
65.68 59.63 60.11 64.49 64.97 64.47 64.63 64.61
80.94 80.33 81.08 82.28 82.42 82.29 82.44 82.41

Table 5: Results of stacking Malt and MST 1O at level 0 and level 1, respectively. Columns 2–4 enumerate LAS for
Malt, MST 1O and MST 2O . Columns 5–9 enumerate results for five different stacked feature configurations. Bold
indicates the best result for a language.

level 0 and level 1 predictions under the best overall
configuration (configuration E of M alt + M ST2O ).
Figure 2 depicts accuracy as a function of level 0level 1 disagreement (in number of tokens), averaged over all datasets.
We can see that performance degrades steeply
when the disagreement between levels 0 and 1 increases in the range 0–4, and then behaves more irregularly but keeping the same trend. This suggeststhat the Hamming distance L(g(x), h(x)) is informative about parser performance and may be used
as a confidence measure.

6

Conclusion

In this work, we made use of stacked learning to improve dependency parsing. We considered an architecture with two layers, where the output of a standard parser in the first level provides new features
for a parser in the subsequent level. During learning,
the second parser learns to correct mistakes made by
the first one. The novelty of our approach is in the
exploitation of higher-order predicted edges to simulate non-local features in the second parser. We provided a novel interpretation of stacking as featureapproximation, and our experimental results show
rich-featured stacked parsers outperforming stateof-the-art single-layer and ensemble parsers. No-

tably, using a simple arc-factored parser at level 1,
we obtain an exact O(n2 ) stacked parser that outperforms earlier approximate methods (McDonald andPereira, 2006).

Acknowledgments
The authors thank the anonymous reviewers forhelpful comments, Vitor Carvalho, William Cohen,
and David Smith for interesting discussions, andRyan McDonald and Joakim Nivre for providing
us their code and preprocessed datasets. A.M. was
supported by a grant from FCT through the CMUPortugal Program and the Information and Communications Technologies Institute (ICTI) at CMU.
N.S. was supported by NSF IIS-0713265 and an
IBM faculty award. E.X. was supported by NSF
DBI-0546594, DBI-0640543, and IIS-0713379.

References
S. P. Abney, D. A. McAllester, and F. Pereira. 1999. Relating probabilistic grammars and automata. In Proceedings of ACL.
A. Blum and T. Mitchell. 1998. Combining labeled
and unlabeled data with co-training. In Proceedingsof COLT.
L. Breiman. 1996. Stacked regressions. Machine Learning, 24:49.

E. Brill. 1993. A Corpus-Based Approach to Language
Learning. Ph.D. thesis, University of Pennsylvania.
S. Buchholz and E. Marsi. 2006. CoNLL-X shared task
on multilingual dependency parsing. In Proceedingsof CoNLL.
Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396–
1400.
W. W. Cohen and V. Rocha de Carvalho. 2005. Stacked
sequential learning. In Proceedings of IJCAI.
A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proceedings of ACL.
Y. Ding and M. Palmer. 2005. Machine translation using
probabilistic synchronous dependency insertion grammar. In Proceedings of ACL.
J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–
240.
J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head automaton grammars. In Proceedings of ACL.
J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of
COLING.
J. Hall, J. Nivre, and J. Nilsson. 2006. Discriminativeclassifiers for deterministic dependency parsing. In
Proceedings of ACL.
Z. Kou and W. W. Cohen. 2007. Stacked graphical models for efficient inference in Markov random fields. In
Proceedings of SDM.
J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proceedingsof ICML.
P. Liang, H. Daumé, and D. Klein. 2008. Structure compilation: trading structure for features. In Proceedingsof ICML.
R. McDonald and J. Nivre. 2007. Characterizing theerrors of data-driven dependency parsing models. In
Proceedings of EMNLP-CoNLL.
R. T. McDonald and F. C. N. Pereira. 2006. Online learning of approximate dependency parsing algorithms. In
Proceedings of EACL.
R. McDonald and G. Satta. 2007. On the complexityof non-projective data-driven dependency parsing. In
Proceedings of IWPT.
R. McDonald, K. Crammer, and F. Pereira. 2005a. Online large-margin training of dependency parsers. In
Proceedings of ACL.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005b. Non-projective dependency parsing using spanning tree algorithms. In Proceedings of HLTEMNLP.

R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proceedings CoNLL.
J. Nivre and R. McDonald. 2008. Integrating graphbased and transition-based dependency parsers. In
Proceedings of ACL-HLT.
J. Nivre, J. Hall, and J. Nilsson. 2004. Memory-based
dependency parsing. In Proceedings of CoNLL.
J. Nivre, J. Hall, J. Nilsson, G. Eryiǧit, and S. Marinov.
2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of
CoNLL.
A. Ratnaparkhi, S. Roukos, and R. T. Ward. 1994. A
maximum entropy model for parsing. In Proceedingsof ICSLP.
S. Riedel and J. Clarke. 2006. Incremental integer linear
programming for non-projective dependency parsing.
In Proceedings of EMNLP.
K. Sagae and A. Lavie. 2005. A classifier-based parser
with linear run-time complexity. In Proceedings of
IWPT.
D. A. Smith and J. Eisner. 2008. Dependency parsing bybelief propagation. In Proceedings of EMNLP.
I. Titov and J. Henderson. 2007. A latent variable modelfor generative dependency parsing. In Proceedings of
IWPT.
M. Wang, N. A. Smith, and T. Mitamura. 2007. What is
the Jeopardy model? A quasi-synchronous grammar
for QA. In Proceedings of EMNLP-CoNLL.
D. Wolpert. 1992. Stacked generalization. Neural Networks, 5(2):241–260.
H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proceedings of IWPT.