---
title: "Non-Projective Dependency Parsing using Spanning Tree Algorithms — McDonald 2005"
description: "The paper casts weighted dependency parsing as a search for maximum spanning trees in a directed… 1.1 points. 30 references, cited by 411 papers here."
authors: ["Ryan McDonald", "Fernando Pereira", "Kiril Ribarov", "Jan Hajič"]
year: 2005
venue: "Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing"
source: "https://aclanthology.org/H05-1066/"
doi: "10.3115/1220575.1220641"
licence: "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)"
licence_url: "https://creativecommons.org/licenses/by-nc-sa/3.0/"
summary_licence: "Elamur Cosmic License"
canonical: "https://research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/)

[home](https://md.research.elamur.ai/free/en/) / [papers](https://md.research.elamur.ai/free/en/papers/) / [2005](https://md.research.elamur.ai/free/en/papers/2005/) / Non-Projective Dependency Parsing using Spanning Tree Algorithms

# Non-Projective Dependency Parsing using Spanning Tree Algorithms

**Authors:** [Ryan McDonald](https://md.research.elamur.ai/free/en/authors/ryan-mcdonald/), [Fernando Pereira](https://md.research.elamur.ai/free/en/authors/fernando-pereira/), Kiril Ribarov and [Jan Hajič](https://md.research.elamur.ai/free/en/authors/jan-hajic/) · **Year:** 2005 · **Venue:** Proceedings of the Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing (HLT/EMNLP) **Link:** [aclanthology.org/H05-1066](https://aclanthology.org/H05-1066/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**847** citations](https://openalex.org/works?filter=cites:W2122922578) OpenAlex, 2026-10-14 · [**411** citations in our library](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/cited-by/) of the 140,884 papers whose bibliographies we read · [Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing](https://aclanthology.org/volumes/H05-1/) · [licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/H05-1066/)
- [PDF](https://aclanthology.org/H05-1066.pdf)
- [DOI 10.3115/1220575.1220641](https://doi.org/10.3115/1220575.1220641)
- [OpenAlex](https://openalex.org/W2122922578)

**Authors (4)**

1. [Ryan McDonald](https://openalex.org/A5022489655) [Semantic Scholar](https://www.semanticscholar.org/author/143957226) · h 48 · 16,067 citations · 113 works
2. [Fernando Pereira](https://openalex.org/A5044708805) [ORCID](https://orcid.org/0000-0001-6100-947X) · [Semantic Scholar](https://www.semanticscholar.org/author/145366908) · h 74 · 31,029 citations · 515 works
3. [Kiril Ribarov](https://openalex.org/A5079189227) [Semantic Scholar](https://www.semanticscholar.org/author/2111414) · h 4 · 879 citations · 21 works
4. [Jan Hajič](https://openalex.org/A5102738283) [ORCID](https://orcid.org/0000-0002-3503-7730) · [Semantic Scholar](https://www.semanticscholar.org/author/144002335) · h 39 · 8,442 citations · 278 works

Citations and author metrics: OpenAlex, 2026-10-14; authors with the same name are not always told apart.

## What it is about

The paper casts weighted dependency parsing as a search for maximum spanning trees in a directed graph. Eisner's algorithm covers all projective trees in O(n^3), and the Chu-Liu-Edmonds algorithm covers non-projective trees in O(n^2), with the same edge scores. The scores are trained with online large-margin learning (MIRA) on the Prague Dependency Treebank, where fewer than 2% of Czech dependencies are non-projective. The non-projective decoder gains up to 1.1 points of attachment accuracy over the projective one (factored MIRA 84.4% on all of PDT) and parses faster. On projective English trees from the Penn Treebank, the spanning-tree decoder is slightly worse than Eisner's (90.2% against 90.9%).

## Ideas

- I3. treeagree: report the share of non-projective content (non-punctuation) arcs in the silver corpus, so the projectivity gate rests on numbers rather than assumption.

## For Mova

- I1. gparse: add a Chu-Liu-Edmonds decoder next to `gparse/src/eisner.rs`, run on the same biaffine arc scores and selected by a flag; measure LAS against Eisner on EWT test and on GUM test (test only).
- I2. en: measure the ceiling of the projective arc-standard parser as the share of gold EWT test arcs that are non-projective and the UAS lost to projectivity, with `en parse-eval`; keep projective decoding if the loss is small.

The non-projective cases in the paper are extraposed relative clauses, such as "a dog yesterday which was a Yorkshire Terrier", so the chapters to read are 21-clause-structure and 25-relative-clauses, with 29-ellipsis-word-order-information-structure for other displacement. The code touched is `en/src/parse.rs` (projective only), `gparse/src/eisner.rs` and `tools/treeagree`. Measure first: the non-projective arc share and the projective ceiling on EWT test (idea I2).

## Institutions

[🎓**University of Pennsylvania** Philadelphia · United States 143 works · 56,645 citations](https://md.research.elamur.ai/free/en/universities/university-of-pennsylvania/) · [🎓**Charles University** Prague · Czechia 99 works · 18,879 citations](https://md.research.elamur.ai/free/en/universities/charles-university/)

Topics[Dependency parsing](https://md.research.elamur.ai/free/en/topics/dependency-parsing/)

## Cite

Cite as Ryan McDonald, Fernando Pereira, Kiril Ribarov and Jan Hajič. 2005. Non-Projective Dependency Parsing using Spanning Tree Algorithms. Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing.

The paper itself, not this card. BibTeX from the library's record of the work. [DOI 10.3115/1220575.1220641](https://doi.org/10.3115/1220575.1220641)

```bibtex
@inproceedings{mcdonald2005non,
  title = {{Non-Projective Dependency Parsing using Spanning Tree Algorithms}},
  author = {Ryan McDonald, Fernando Pereira, Kiril Ribarov and Jan Hajič},
  booktitle = {Proceedings of Human Language Technology Conference and Conference on Empirical Methods in Natural Language Processing},
  year = {2005},
  doi = {10.3115/1220575.1220641},
  url = {https://doi.org/10.3115/1220575.1220641}
}
```

- [← previous Coarse-to-Fine n-Best Parsing and MaxEnt Discriminative Reranking](https://md.research.elamur.ai/free/en/papers/charniak-2005-coarse-fine-n-best-parsing/)
- [next → Online Large-Margin Training of Dependency Parsers](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-online-large-margin-training-dependency/)
- [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/)

## References

30 references, 10 of them with a card of ours. ↗ leads to the work, «find» searches for one we have no id for yet.

1. Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. [find](https://scholar.google.com/scholar?q=Y%2EJ%2E+Chu+and+T%2EH%2E+Liu%2E+1965%2E+On+the+shortest+arborescence+of+a+directed+graph%2E+Science+Sinica%2C+14%3A1396%E2%80%93+1400%2E)
2. M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A statistical parser for Czech. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/collins-1999-statistical-parser-czech/)
3. M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. [our card](https://md.research.elamur.ai/free/en/papers/collins-2002-discriminative-training-methods-hidden-markov/)
4. T.H. Cormen, C.E. Leiserson, and R.L. Rivest. 1990. Introduction to Algorithms. MIT Press/McGraw-Hill. [find](https://scholar.google.com/scholar?q=T%2EH%2E+Cormen%2C+C%2EE%2E+Leiserson%2C+and+R%2EL%2E+Rivest%2E+1990%2E+Introduction+to+Algorithms%2E+MIT+Press%2FMcGraw%2DHill%2E)
5. K. Crammer and Y. Singer. 2003. Ultraconservative online algorithms for multiclass problems. JMLR. [find](https://scholar.google.com/scholar?q=K%2E+Crammer+and+Y%2E+Singer%2E+2003%2E+Ultraconservative+online+algorithms+for+multiclass+problems%2E+JMLR%2E)
6. K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online passive aggressive algorithms. In Proc. NIPS. [find](https://scholar.google.com/scholar?q=K%2E+Crammer%2C+O%2E+Dekel%2C+S%2E+Shalev%2DShwartz%2C+and+Y%2E+Singer%2E+2003%2E+Online+passive+aggressive+algorithms%2E+In+Proc%2E+NIPS%2E)
7. K. Crammer, R. McDonald, and F. Pereira. 2004. New large margin algorithms for structured prediction. In Learning with Structured Outputs Workshop (NIPS). [find](https://scholar.google.com/scholar?q=K%2E+Crammer%2C+R%2E+McDonald%2C+and+F%2E+Pereira%2E+2004%2E+New+large+margin+algorithms+for+structured+prediction%2E+In+Learning+with+Structured+Outputs+Workshop+%28NIPS%29%2E)
8. A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/culotta-2004-dependency-tree-kernels-relation-extraction/)
9. Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/ding-2005-machine-translation-probabilistic-synchronous-dependency/)
10. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233– 240. [find](https://scholar.google.com/scholar?q=J%2E+Edmonds%2E+1967%2E+Optimum+branchings%2E+Journal+of+Research+of+the+National+Bureau+of+Standards%2C+71B%3A233%E2%80%93+240%2E)
11. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COLING. [our card](https://md.research.elamur.ai/free/en/papers/eisner-1996-three-new-probabilistic-models-dependency/)
12. J. Hajič, E. Hajicova, P. Pajas, J. Panevova, P. Sgall, and B. Vidova Hladka. 2001. The Prague Dependency Treebank 1.0 CDROM. Linguistics Data Consortium Cat. No. LDC2001T10. [find](https://scholar.google.com/scholar?q=J%2E+Hajic%CC%8C%2C+E%2E+Hajicova%2C+P%2E+Pajas%2C+J%2E+Panevova%2C+P%2E+Sgall%2C+and+B%2E+Vidova+Hladka%2E+2001%2E+The+Prague+Dependency+Treebank+1%2E0+CDROM%2E+Linguistics+Data+Consortium+Cat%2E+No%2E+LDC2001T10%2E)
13. J. Hajič. 1998. Building a syntactically annotated corpus: The Prague dependency treebank. Issues of Valency and Meaning, pages 106–132. [find](https://scholar.google.com/scholar?q=J%2E+Hajic%CC%8C%2E+1998%2E+Building+a+syntactically+annotated+corpus%3A+The+Prague+dependency+treebank%2E+Issues+of+Valency+and+Meaning%2C+pages+106%E2%80%93132%2E)
14. H. Hirakawa. 2001. Semantic dependency analysis method for Japanese based on optimum tree search algorithm. In Proc. of PACLING. [find](https://scholar.google.com/scholar?q=H%2E+Hirakawa%2E+2001%2E+Semantic+dependency+analysis+method+for+Japanese+based+on+optimum+tree+search+algorithm%2E+In+Proc%2E+of+PACLING%2E)
15. Klaus-U. Höffgen. 1993. Learning and robust learning of product distributions. In Proceedings of COLT’93, pages 77–83. [find](https://scholar.google.com/scholar?q=Klaus%2DU%2E+Ho%CC%88ffgen%2E+1993%2E+Learning+and+robust+learning+of+product+distributions%2E+In+Proceedings+of+COLT%E2%80%9993%2C+pages+77%E2%80%9383%2E)
16. W. Hou. 1996. Algorithm for finding the first k shortest arborescences of a digraph. Mathematica Applicata, 9(1):1–4. [find](https://scholar.google.com/scholar?q=W%2E+Hou%2E+1996%2E+Algorithm+for+finding+the+first+k+shortest+arborescences+of+a+digraph%2E+Mathematica+Applicata%2C+9%281%29%3A1%E2%80%934%2E)
17. R. Hudson. 1984. Word Grammar. Blackwell. [find](https://scholar.google.com/scholar?q=R%2E+Hudson%2E+1984%2E+Word+Grammar%2E+Blackwell%2E)
18. G. Leonidas. 2003. Arborescence optimization problems solvable by Edmonds’ algorithm. Theoretical Computer Science, 301:427 – 437. [find](https://scholar.google.com/scholar?q=G%2E+Leonidas%2E+2003%2E+Arborescence+optimization+problems+solvable+by+Edmonds%E2%80%99+algorithm%2E+Theoretical+Computer+Science%2C+301%3A427+%E2%80%93+437%2E)
19. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of English: the Penn Treebank. Computational Linguistics, 19(2):313–330. [our card](https://md.research.elamur.ai/free/en/papers/marcus-1993-building-large-annotated-corpus-english/)
20. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-online-large-margin-training-dependency/)
21. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/nivre-2005-pseudo-projective-dependency-parsing/)
22. J. Nivre and M. Scholz. 2004. Deterministic dependency parsing of english text. In Proc. COLING. [our card](https://md.research.elamur.ai/free/en/papers/nivre-2004-deterministic-dependency-parsing-english-text/)
23. Y. Shinyama, S. Sekine, K. Sudo, and R. Grishman. 2002. Automatic paraphrase acquisition from news articles. In Proc. HLT. [find](https://scholar.google.com/scholar?q=Y%2E+Shinyama%2C+S%2E+Sekine%2C+K%2E+Sudo%2C+and+R%2E+Grishman%2E+2002%2E+Automatic+paraphrase+acquisition+from+news+articles%2E+In+Proc%2E+HLT%2E)
24. R. Snow, D. Jurafsky, and A. Y. Ng. 2004. Learning syntactic patterns for automatic hypernym discovery. In NIPS 2004. [find](https://scholar.google.com/scholar?q=R%2E+Snow%2C+D%2E+Jurafsky%2C+and+A%2E+Y%2E+Ng%2E+2004%2E+Learning+syntactic+patterns+for+automatic+hypernym+discovery%2E+In+NIPS+2004%2E)
25. R.E. Tarjan. 1977. Finding optimum branchings. Networks, 7:25–35. [find](https://scholar.google.com/scholar?q=R%2EE%2E+Tarjan%2E+1977%2E+Finding+optimum+branchings%2E+Networks%2C+7%3A25%E2%80%9335%2E)
26. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In Proc. NIPS. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+C%2E+Guestrin%2C+and+D%2E+Koller%2E+2003%2E+Max%2Dmargin+Markov+networks%2E+In+Proc%2E+NIPS%2E)
27. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP. [find](https://scholar.google.com/scholar?q=B%2E+Taskar%2C+D%2E+Klein%2C+M%2E+Collins%2C+D%2E+Koller%2C+and+C%2E+Manning%2E+2004%2E+Max%2Dmargin+parsing%2E+In+Proc%2E+EMNLP%2E)
28. W. Wang and M. P. Harper. 2004. A statistical constraint dependency grammar (CDG) parser. In Workshop on Incremental Parsing: Bringing Engineering and Cognition Together (ACL). [find](https://scholar.google.com/scholar?q=W%2E+Wang+and+M%2E+P%2E+Harper%2E+2004%2E+A+statistical+constraint+dependency+grammar+%28CDG%29+parser%2E+In+Workshop+on+Incremental+Parsing%3A+Bringing+Engineering+and+Cognition+Together+%28ACL%29%2E)
29. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. [our card](https://md.research.elamur.ai/free/en/papers/yamada-2003-statistical-dependency-analysis-support-vector/)
30. D. Zeman. 2004. Parsing with a Statistical Dependency Model. Ph.D. thesis, Univerzita Karlova, Praha. [find](https://scholar.google.com/scholar?q=D%2E+Zeman%2E+2004%2E+Parsing+with+a+Statistical+Dependency+Model%2E+Ph%2ED%2E+thesis%2C+Univerzita+Karlova%2C+Praha%2E)