Turning on the Turbo: Fast Third-Order Non-Projective Turbo Parsers
André F. T. Martins∗†

Miguel B. Almeida∗†

Noah A. Smith#∗

Priberam Labs, Alameda D. Afonso Henriques, 41, 2o , 1000-123 Lisboa, Portugal
Instituto de Telecomunicações, Instituto Superior Técnico, 1049-001 Lisboa, Portugal#
School of Computer Science, Carnegie Mellon University, Pittsburgh, PA 15213, USA{atm,mba}@priberam.pt,
nasmith@cs.cmu.edu†

Abstract
We present fast, accurate, direct nonprojective dependency parsers with thirdorder features. Our approach uses AD3 ,an accelerated dual decomposition algorithm which we extend to handle specialized head automata and sequential headbigram models. Experiments in fourteen
languages yield parsing speeds competitive to projective parsers, with state-ofthe-art accuracies for the largest datasets(English, Czech, and German).

1

Introduction

Dependency parsing has become a prominent approach to syntax in the last few years, with increasingly fast and accurate models being devised(Kübler et al., 2009; Huang and Sagae, 2010;
Zhang and Nivre, 2011; Rush and Petrov, 2012).
In projective parsing, the arcs in the dependency
tree are constrained to be nested, and the problemof finding the best tree can be addressed with dynamic programming. This results in cubic-time
decoders for arc-factored and sibling second-ordermodels (Eisner, 1996; McDonald and Pereira,2006), and quartic-time for grandparent models(Carreras, 2007) and third-order models (Koo andCollins, 2010). Recently, Rush and Petrov (2012)trained third-order parsers with vine pruning cascades, achieving runtimes only a small factor
slower than first-order systems. Third-order features have also been included in transition systems(Zhang and Nivre, 2011) and graph-based parsers
with cube-pruning (Zhang and McDonald, 2012).
Unfortunately, non-projective dependency
parsers (appropriate for languages with a more
flexible word order, such as Czech, Dutch, andGerman) lag behind these recent advances. The
main obstacle is that non-projective parsing is
NP-hard beyond arc-factored models (McDonald

and Satta, 2007). Approximate parsers have therefore been introduced, based on belief propagation(Smith and Eisner, 2008), dual decomposition(Koo et al., 2010), or multi-commodity flows(Martins et al., 2009, 2011). These are all instances of turbo parsers, as shown by Martins etal. (2010): the underlying approximations comefrom the fact that they run global inference infactor graphs ignoring loop effects. While thisline of research has led to accuracy gains, none ofthese parsers use third-order contexts, and their
speeds are well behind those of projective parsers.
This paper bridges the gap above by presenting
the following contributions:• We apply the third-order feature models of Koo
and Collins (2010) to non-projective parsing.
• This extension is non-trivial since exact dynamic programming is not applicable. Instead,
we adapt AD3 , the dual decomposition algorithm proposed by Martins et al. (2011), to handle third-order features, by introducing specialized head automata.
• We make our parser substantially faster than the
many-components approach of Martins et al.
(2011). While AD3 requires solving quadratic
subproblems as an intermediate step, recent results (Martins et al., 2012) show that they can beaddressed with the same oracles used in the subgradient method (Koo et al., 2010). This enables
AD3 to exploit combinatorial subproblems likethe the head automata above.
Along with this paper, we provide a free distribution of our parsers, including training code.1

2

Dependency Parsing with AD3Dual decomposition is a class of optimization
techniques that tackle the dual of combinatorial
1
Released as TurboParser 2.1, and publicly available at
http://www.ark.cs.cmu.edu/TurboParser.

Figure 1: Parts considered in this paper. Firstorder models factor over arcs (Eisner, 1996; McDonald et al., 2005), and second-order models include also consecutive siblings and grandparents(Carreras, 2007). Our parsers add also arbitrary
siblings (not necessarily consecutive) and head bigrams, as in Martins et al. (2011), in addition
to third-order features for grand- and tri-siblings(Koo and Collins, 2010).
problems in a modular and extensible manner (Komodakis et al., 2007; Rush et al., 2010). In thispaper, we employ alternating directions dual decomposition (AD3 ; Martins et al., 2011). Like
the subgradient algorithm of Rush et al. (2010),
AD3 splits the original problem into local subproblems, and seeks an agreement on the overlapping variables. The difference is that the AD3
subproblems have an additional quadratic term toaccelerate consensus. Recent analysis (Martins etal., 2012) has shown that: (i) AD3 converges ata faster rate,2 and (ii) the quadratic subproblems
can be solved using the same combinatorial machinery that is used in the subgradient algorithm.
This opens the door for larger subproblems (suchas the combination of trees and head automata in
Koo et al., 2010) instead of a many-components
approach (Martins et al., 2011), while still enjoying faster convergence.
2.1

Our Setup

Given a sentence with L words, to which weprepend a root symbol $, let A := {hh, mi | h ∈{0, . . . , L}, m ∈ {1, . . . , L}, h 6= m} be theset of possible dependency arcs. We parameterize a dependency tree via an indicator vector
u := hua ia∈A , where ua is 1 if the arc a is in thetree, and 0 otherwise, and we denote by Y ⊆ R|A|
the set of such vectors that are indicators of well2
Concretely, AD3 needs O(1/) iterations to converge toa -accurate solution, while subgradient needs O(1/2 ).

formed trees. Let {As }Ss=1 be a cover of A, where
each As ⊆ A. We assume that the score
PS of a parsetree u ∈ Y decomposes as f (u) := s=1 fs (z s ),where each z s := hzs,a ia∈As is a “partial view” ofu, and each local score function fs comes from afeature-based linear model.
Past work in dependency parsing considered either (i) a few “large” components, such as trees
and head automata (Smith and Eisner, 2008; Kooet al., 2010), or (ii) many “small” components,
coming from a multi-commodity flow formulation(Martins et al., 2009, 2011). Let Ys ⊆ R|As | denote the set of feasible realizations of z s , i.e., thosethat are partial views of an actual
Q parse tree. A tuple of views hz 1 , . . . , z S i ∈ Ss=1 Ys is said to be
globally consistent if zs,a = zs0 ,a holds for every
a, s and s0 such that a ∈ As ∩As0 . We assume eachparse u ∈ Y corresponds uniquely to a globallyconsistent tuple of views, and vice-versa. Following Martins et al. (2011), the problem of obtaining
the best-scored tree can be written as follows:PS
maximize
s=1 fs (z s )w.r.t. u ∈ R|A| , z s ∈ Ys , ∀ss.t. zs,a = ua , ∀s, ∀a ∈ As ,(1)

where the equality constraint ensures that the partial views “glue” together to form a coherent parsetree.3
2.2

Dual Decomposition and AD3Dual decomposition methods dualize out theequality constraint in Eq. 1 by introducing Lagrange multipliers λs,a . In doing so, they solve a
relaxation where the combinatorial sets Ys are replaced by their convex hulls Zs := conv(Ys ).4 Allthat is necessary is the following assumption:
Assumption 1 (Local-Max Oracle). Every s ∈{1, . . . , S} has an oracle that solves efficiently any
instance of the following subproblem:Pmaximize fs (z s ) + a∈As λs,a zs,aw.r.t. z s ∈ Ys .

(2)

Typically, Assumption 1 is met whenever the maximization of fs over Ys is tractable, since the objective in Eq. 2 just adds a linear function to fs .
Q
Note that any tuple hz 1 , . . . , z S i ∈ S
s=1 Ys satisfying
the equality constraints will be globally consistent; this fact,
due the assumptions above, will imply u ∈ Y.
P
4Let ∆|Ys | := {α ∈ R|Ys | | α ≥ 0, ys ∈Ys αys = 1}
be the probability simplex. The convex hull of Ys is the setP
conv(Ys ) := { ys ∈Ys αys y s | α ∈ ∆|Ys | }. Its members
represent marginal probabilities over the arcs in As .
3• z-updates, which decouple over s = 1, . . . , S,and solve a penalized version of Eq. 2:
P(t)z (t+1):= arg max fs (z s ) + a∈As λs,a zs,as
z s ∈Zs

− ρ2

P

(t)

2
a∈As (zs,a − ua ) .

(3)

Above, ρ is a constant and the quadratic term
penalizes deviations from the current global solution (stored in u(t) ).5 We will see (Prop. 2)that this problem can be solved iteratively using
only the Local-Max Oracle (Eq. 2).
• u-updates, a simple averaging operation:
P
(t+1)
1
u(t+1):= |{s : a∈Aas : a∈As zs,a .
}|
s

(4)

• λ-updates, where the Lagrange multipliers areadjusted to penalize disagreements:(t+1)
λ(t+1):= λ(t)− u(t+1)).
s,as,a − ρ(zs,aa(5)

In sum, the only difference between AD3 andthe subgradient method is in the z-updates, whichin AD3 require solving a quadratic problem.
While closed-form solutions have been developed
for some specialized components (Martins et al.,2011), this problem is in general more difficult
than the one arising in the subgradient algorithm.
However, the following result, proved in Martinset al. (2012), allows to expand the scope of AD3
to any problem which satisfies Assumption 1.
Proposition 2. The problem in Eq. 3 admits asolution z ∗s which is spanned by a sparse basis
W ⊆ Ys with cardinality at most |W| ≤ O(|As |).
In other words, there is a distribution
α with supP
port in W such that z ∗s = ys ∈W αys y s .6
Prop. 2 has motivated an active set algorithm(Martins et al., 2012) that maintains an estimateof W by iteratively adding and removing elements
computed through the oracle in Eq. 2.7 Typically,
very few iterations are necessary and great speedups are achieved by warm-starting W with the active set computed in the previous AD3 iteration.
This has a huge impact in practice and is crucial toobtain the fast runtimes in §4 (see Fig. 2).
5In our experiments (§4), we set ρ = 0.05.
Note that |Ys | = O(2|As | ) in general. What Prop. 2
tells us is that the solution of Eq. 3 can be represented as a
distribution over Ys with a very sparse support.
7
The algorithm is a specialization of Nocedal and Wright(1999), §16.4, which effectively exploits the sparse representation of z ∗s . For details, see Martins et al. (2012).
6

average runtime (sec.)

The AD3 algorithm (Martins et al., 2011) alternates among the following iterative updates:

0.20

Subgrad.
AD3
0.10

0.00
0

10

20
30
sentence length (words)

40

50

Figure 2: Comparison between AD3 and subgradient. We show averaged runtimes in PTB §22 asa function of the sentence length. For subgradient, we chose for each sentence the most favorable
stepsize in {0.001, 0.01, 0.1, 1}.

3

Solving the Subproblems

We next describe the actual components used in
our third-order parsers.
Tree component. We use an arc-factored scorefunction(McDonald et al., 2005): f TREE (z) =PL
m=1 σARC (π(m), m), where π(m) is the parentof the mth word according to the parse tree z,
and σARC (h, m) is the score of an individual arc.
The parse tree that maximizes this function can befound in time O(L3 ) via the Chu-Liu-Edmonds’
algorithm (Chu and Liu, 1965; Edmonds, 1967).8Grand-sibling head automata. Let Ain
h anddenoterespectively
the
sets
of
incomingandAouthoutgoing candidate arcs for the hth word, where
the latter subdivides into arcs pointing to the right,out
Aouth,→ , and to the left, Ah,← . Define the sets
out
GSIB
out
GSIB
in
Ah,→ = Ah ∪Ah,→ and Ah,← = Ainh ∪Ah,← . We
describe right-side grand-sibling head automata;their left-side counterparts are analogous. For
each head word h in the parse tree z, define
g := π(h), and let hm0 , m1 , . . . , mp+1 i be the sequence of right modifiers of h, with m0 = STARTand mp+1 = END. Then, we have the following
grand-sibling component:
Pp+1
GSIB
GSIB ) =fh,→(z|Ah,→
k=1 σSIB (h, mk−1 , mk )
σGP (g, h, mk ) + σGSIB (g, h, mk−1 , mk ) ,where we use the shorthand z|B to denote thesubvector of z indexed by the arcs in B ⊆ A.
Note that this score function absorbs grandparent
and consecutive sibling scores, in addition to the
GSIB
grand-sibling scores.9 For each h, fh,→can be8
In fact, there is an asymptotically faster O(L2 ) algorithm(Tarjan, 1977). Moreover, if the set of possible arcs is reduced
to a subset B ⊆ A (via pruning), then the fastest known algorithm (Gabow et al., 1986) runs in O(|B| + L log L) time.
9
Koo et al. (2010) used an identical automaton for theirsecond-order model, but leaving out the grand-sibling scores.

TREE
GSIB
TSIB
SEQ
ASIB

No pruning|Ainsame, + |Aoutm| ≤ Kh | ≤ J
2
O(L ) O(KL + L log L) O(KL + L log L)
O(L4 )O(K 2 L2 )O(JK 2 L)
O(L4 )O(KL3 )O(J 2 KL)
O(L3 )O(K 2 L)O(K 2 L)32
O(L )O(KL )
O(JKL)PTB-YM §22, 1st ord
PTB-YM §22, 2nd ord
PTB-YM §22, 2nd ord, +ASIB, +HB
PTB-YM §22, 3rd ord
PTB-YM §22, 3rd ord, gold tags
This work (PTB-YM §23, 3rd ord)
Koo et al. (2010)
Huang and Sagae (2010)
Zhang and Nivre (2011)
Martins et al. (2011)
Zhang and McDonald (2012)
This work (PTB-S §23, 3rd ord)
Rush and Petrov (2012)

Table 1: Theoretical runtimes of each subproblem
without pruning, limiting the number of candidate
heads, and limiting (in addition) the number ofmodifiers. Note the O(L log L) total runtime per
AD3 iteration in the latter case.
maximized in time O(L3 ) with dynamic programming, yielding O(L4 ) total runtime.
Tri-sibling head automata. In addition, we define left and right-side tri-sibling head automata
that remember the previous two modifiers of ahead word. This corresponds to the following
component function (for the right-side case):
P
TSIB
fh,→
(z|Aout ) = p+1
k=2 σTSIB (h, mk−2 , mk−1 , mk ).

UAS Tok/sec
91.38 4,063
93.15 1,338
93.28 1,018
93.29
709
94.01
722
93.07
735
92.46
112†
92.1–
587†
92.9–
680†
92.53
66†
93.06
220
92.82
604
92.7– 4,460

Table 2: Results for the projective English dataset.
We report unlabeled attachment scores (UAS) ignoring punctuation, and parsing speeds in tokens
per second. Our speeds include the time necessary
for pruning, evaluating features, and decoding, as
measured on a Intel Core i7 processor @3.4 GHz.
The others are speeds reported in the cited papers;
those marked with † were converted from times per
sentence.

h,→

Again, each of these functions can be maximized
in time O(L3 ), yielding O(L4 ) runtime.
Sequential head bigram model. Head bigrams
can be captured with a simple sequence model:
P
f SEQ (z) = L
m=2 σHB (m, π(m), π(m − 1)).
Each score σHB (m, h, h0 ) is obtained via featuresthat look at the heads of consecutive words (as in
Martins et al. (2011)). This function can be maximized in time O(L3 ) with the Viterbi algorithm.
Arbitrary siblings. We handle arbitrary siblings
as in Martins et al. (2011), defining O(L3 ) compoASIB
nent functions of the form fh,m,s(zhh,mi , zhh,si ) =σASIB (h, m, s). In this case, the quadratic problem
in Eq. 3 can be solved directly in constant time.
Tab. 1 details the time complexities of each subproblem. Without pruning, each iteration of AD3
has O(L4 ) runtime. With a simple strategy that
limits the number of candidate heads per word toa constant K, this drops to cubic time.10 Further
speed-ups are possible with more pruning: by limiting the number of possible modifiers to a constant J, the runtime would reduce to O(L log L).
10

In our experiments, we employed this strategy with K =10, by pruning with a first-order probabilistic model. Following Koo and Collins (2010), for each word m, we also
pruned away incoming arcs hh, mi with posterior probability
less than 0.0001 times the probability of the most likely head.

4

Experiments

We first evaluated our non-projective parser in a
projective English dataset, to see how its speed andaccuracy compares with recent projective parsers,
which can take advantage of dynamic programming. To this end, we converted the Penn Treebank to dependencies through (i) the head rulesof Yamada and Matsumoto (2003) (PTB-YM) and(ii) basic dependencies from the Stanford parser
2.0.5 (PTB-S).11 We trained by running 10 epochsof cost-augmented MIRA (Crammer et al., 2006).
To ensure valid parse trees at test time, we rounded
fractional solutions as in Martins et al. (2009)—
yet, solutions were integral ≈ 95% of the time.
Tab. 2 shows the results in the dev-set (topblock) and in the test-set (two bottom blocks). In
the dev-set, we see consistent gains when more expressive features are added, the best accuracies being achieved with the full third-order model; thiscomes at the cost of a 6-fold drop in runtime compared with a first-order model. By looking at thetwo bottom blocks, we observe that our parser
has slightly better accuracies than recent projective parsers, with comparable speed levels (withthe exception of the highly optimized vine cascade
approach of Rush and Petrov, 2012).
11
We train on sections §02–21, use §22 as validation data,
and test on §23. We trained a simple 2nd-order tagger with
10-fold jackknifing to obtain automatic part-of-speech tagsfor §22–23, with accuracies 97.2% and 96.9%, respectively.

Arabic
Bulgarian
ChineseCzech
DanishDutch
GermanEnglishJapanese
Portuguese
SloveneSpanishSwedishTurkishFirst Ord.
UAS Tok/sec
77.23 2,481
91.76 5,678
88.49 18,094
87.66 1,840
89.42 4,110
83.61 3,884
90.52 5,331
91.21 3,127
92.78 23,895
91.14 4,273
82.81 4,315
83.61 4,347
89.36 5,622
75.98 6,418

Sec. Ord.
UAS Tok/sec
78.50
388
92.82 2,049
90.14 4,284
90.00
751
91.20 1,053
86.37 1,294
91.85 1,788
93.03 1,317
93.14 5,660
92.71 1,316
85.21
722
84.97
623
90.98 1,387
76.50 1,721

Third Ord.
UAS Tok/sec
79.64
197
93.10 1,273
89.98 2,592
90.32
501
91.48
650
86.19
599
92.41
965
93.22
785
93.52 2,996
92.69
740
86.01
366
85.59
318
91.14
684
76.90
793

Best published UAS
UAS Tok/sec
81.12- Ma1193.50- Ma11
91.89- Ma1089.46- Ma11
91.86- Ma11
85.81
121 Ko10
91.89- Ma11
92.68- Ma11
93.72- Ma11
93.03
79 Ko1086.95- Ma11
87.48- ZM12
91.44- ZM12
77.55
258 Ko10

RP12
UAS Tok/sec
91.9 3,980
90.9 7,800
90.8 2,880
92.3 8,600
91.5 2,900
90.1 5,320
-

ZM12
UAS
93.08
91.35
93.24
91.69
87.48
91.44
-

Table 3: Results for the CoNLL-2006 datasets and the non-projective English dataset of CoNLL-2008.
“Best Published UAS” includes the most accurate parsers among Nivre et al. (2006), McDonald et al.
(2006), Martins et al. (2010, 2011), Koo et al. (2010), Rush and Petrov (2012), Zhang and McDonald(2012). The last two are shown separately in the rightmost columns.
In our second experiment (Tab. 3), we used 14
datasets, most of which are non-projective, fromthe CoNLL 2006 and 2008 shared tasks (Buchholz and Marsi, 2006; Surdeanu et al., 2008).
Our third-order model achieved the best reported
scores for English, Czech, German, and Dutch—which includes the three largest datasets and theones with the most non-projective dependencies—
and is on par with the state of the art for theremaining languages. To our knowledge, thespeeds are the highest reported among higherorder non-projective parsers, and only about 3–
4 times slower than the vine parser of Rush andPetrov (2012), which has lower accuracies.

5

work was partially supported by the EU/FEDER
programme, QREN/POR Lisboa (Portugal), underthe Intelligo project (contract 2012/24803), by a
FCT grant PTDC/EEI-SII/2312/2012, and by NSF
grant IIS-1054319.

References
S. Buchholz and E. Marsi. 2006. CoNLL-X sharedtask on multilingual dependency parsing. In International Conference on Natural Language Learning.
X. Carreras. 2007. Experiments with a higher-orderprojective dependency parser. In International Conference on Natural Language Learning.

Conclusions

We presented new third-order non-projective
parsers which are both fast and accurate. We decoded with AD3 , an accelerated dual decomposition algorithm which we adapted to handle large
components, including specialized head automata
for the third-order features, and a sequence modelfor head bigrams. Results are above the state of
the art for large datasets and non-projective languages. In the hope that other researchers may find
our implementation useful or are willing to contribute with further improvements, we made ourparsers publicly available as open source software.

Acknowledgments
We thank all reviewers for their insightful comments and Lingpeng Kong for help in converting
the Penn Treebank to Stanford dependencies. This

Y. J. Chu and T. H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396–
1400.
K. Crammer, O. Dekel, J. Keshet, S. Shalev-Shwartz,
and Y. Singer. 2006. Online passive-aggressive algorithms. Journal of Machine Learning Research,
7:551–585.
J. Edmonds. 1967. Optimum branchings. Journalof Research of the National Bureau of Standards,
71B:233–240.
J. M. Eisner. 1996. Three new probabilistic models
for dependency parsing: An exploration. In Proc.
of International Conference on Computational Linguistics, pages 340–345.
H. N. Gabow, Z. Galil, T. Spencer, and R. E. Tarjan.
1986. Efficient algorithms for finding minimum
spanning trees in undirected and directed graphs.
Combinatorica, 6(2):109–122.

L. Huang and K. Sagae. 2010. Dynamic programming
for linear-time incremental parsing. In Proc. of Annual Meeting of the Association for Computational
Linguistics, pages 1077–1086.
N. Komodakis, N. Paragios, and G. Tziritas. 2007.
MRF optimization via dual decomposition:
Message-passing revisited. In Proc. of International
Conference on Computer Vision.
T. Koo and M. Collins. 2010. Efficient third-order dependency parsers. In Proc. of Annual Meeting of the
Association for Computational Linguistics, pages 1–
11.
T. Koo, A. M. Rush, M. Collins, T. Jaakkola, andD. Sontag. 2010. Dual decomposition for parsing
with non-projective head automata. In Proc. of Empirical Methods for Natural Language Processing.
S. Kübler, R. McDonald, and J. Nivre. 2009. Dependency parsing. Morgan & Claypool Publishers.
A. F. T. Martins, N. A. Smith, and E. P. Xing. 2009.
Concise integer linear programming formulations
for dependency parsing. In Proc. of Annual Meetingof the Association for Computational Linguistics.
A. F. T. Martins, N. A. Smith, E. P. Xing, M. A. T.
Figueiredo, and P. M. Q. Aguiar. 2010. Turboparsers: Dependency parsing by approximate variational inference. In Proc. of Empirical Methods for
Natural Language Processing.
A. F. T. Martins, N. A. Smith, P. M. Q. Aguiar, and
M. A. T. Figueiredo. 2011. Dual decomposition
with many overlapping components. In Proc. of Empirical Methods for Natural Language Processing.
A. F. T. Martins, M. A. T. Figueiredo, P. M. Q. Aguiar,
N. A. Smith, and E. P. Xing. 2012. Alternating directions dual decomposition. Arxiv preprint
arXiv:1212.6550.
R. T. McDonald and F. C. N. Pereira. 2006. Online
learning of approximate dependency parsing algorithms. In Proc. of Annual Meeting of the European
Chapter of the Association for Computational Linguistics.
R. McDonald and G. Satta. 2007. On the complexity of non-projective data-driven dependency parsing. In Proc. of International Conference on Parsing
Technologies.
R. T. McDonald, F. Pereira, K. Ribarov, and J. Hajic. 2005. Non-projective dependency parsing using spanning tree algorithms. In Proc. of Empirical
Methods for Natural Language Processing.
R. McDonald, K. Lerman, and F. Pereira. 2006. Multilingual dependency analysis with a two-stage discriminative parser. In Proc. of International Conference on Natural Language Learning.

J. Nivre, J. Hall, J. Nilsson, G. Eryiǧit, and S. Marinov.
2006. Labeled pseudo-projective dependency parsing with support vector machines. In Procs. of International Conference on Natural Language Learning.
J. Nocedal and S. J. Wright. 1999. Numerical optimization. Springer-Verlag.
Alexander M Rush and Slav Petrov. 2012. Vine pruning for efficient multi-pass dependency parsing. In
Proc. of Conference of the North American Chapterof the Association for Computational Linguistics.
A. Rush, D. Sontag, M. Collins, and T. Jaakkola. 2010.
On dual decomposition and linear programming relaxations for natural language processing. In Proc.
of Empirical Methods for Natural Language Processing.
D. Smith and J. Eisner. 2008. Dependency parsing bybelief propagation. In Proc. of Empirical Methods
for Natural Language Processing.
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 International Conference on Natural
Language Learning.
R.E. Tarjan. 1977. Finding optimum branchings. Networks, 7(1):25–36.
H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In
Proc. of International Conference on Parsing Technologies.
H. Zhang and R. McDonald. 2012. Generalized
higher-order dependency parsing with cube pruning.
In Proc. of Empirical Methods in Natural Language
Processing.
Y. Zhang and J. Nivre. 2011. Transition-based dependency parsing with rich non-local features. In Proc.
of the Annual Meeting of the Association for Computational Linguistics.