[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)

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

# Non-Projective Dependency Parsing using Spanning Tree Algorithms

**Authors:** [Ryan McDonald](https://md.mova.elamur.ai/free/en/docs/papers/authors/ryan-mcdonald/), [Fernando Pereira](https://md.mova.elamur.ai/free/en/docs/papers/authors/fernando-pereira/), Kiril Ribarov, [Jan Hajič](https://md.mova.elamur.ai/free/en/docs/papers/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

[**410** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/) of the 140673 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)

**Authors (4)**

1. Ryan McDonald
2. Fernando Pereira
3. Kiril Ribarov
4. Jan Hajič

Citations and author metrics from OpenAlex (); 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

- 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.
- 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

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).

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

## Cite

The paper itself, not this card. BibTeX from the library's record of the work.

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

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

## References

30 references, 7 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. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2C+J%2E+Hajic%CC%8C%2C+L%2E+Ramshaw%2C+and+C%2E+Tillmann%2E+1999%2E+A+statistical+parser+for+Czech%2E+In+Proc%2E+ACL%2E)
3. M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+2002%2E+Discriminative+training+methods+for+hidden+Markov+models%3A+Theory+and+experiments+with+perceptron+algorithms%2E+In+Proc%2E+EMNLP%2E) [our card](https://md.mova.elamur.ai/free/en/docs/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. [find](https://scholar.google.com/scholar?q=A%2E+Culotta+and+J%2E+Sorensen%2E+2004%2E+Dependency+tree+kernels+for+relation+extraction%2E+In+Proc%2E+ACL%2E)
9. Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proc. ACL. [find](https://scholar.google.com/scholar?q=Y%2E+Ding+and+M%2E+Palmer%2E+2005%2E+Machine+translation+using+probabilistic+synchronous+dependency+insertion+grammars%2E+In+Proc%2E+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/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. [find](https://scholar.google.com/scholar?q=J%2E+Eisner%2E+1996%2E+Three+new+probabilistic+models+for+dependency+parsing%3A+An+exploration%2E+In+Proc%2E+COLING%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/ast-1996-eisner-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. [find](https://scholar.google.com/scholar?q=M%2E+Marcus%2C+B%2E+Santorini%2C+and+M%2E+Marcinkiewicz%2E+1993%2E+Building+a+large+annotated+corpus+of+English%3A+the+Penn+Treebank%2E+Computational+Linguistics%2C+19%282%29%3A313%E2%80%93330%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
20. R. McDonald, K. Crammer, and F. Pereira. 2005. Online large-margin training of dependency parsers. In Proc. ACL. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+K%2E+Crammer%2C+and+F%2E+Pereira%2E+2005%2E+Online+large%2Dmargin+training+of+dependency+parsers%2E+In+Proc%2E+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)
21. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. [find](https://scholar.google.com/scholar?q=J%2E+Nivre+and+J%2E+Nilsson%2E+2005%2E+Pseudo%2Dprojective+dependency+parsing%2E+In+Proc%2E+ACL%2E)
22. J. Nivre and M. Scholz. 2004. Deterministic dependency parsing of english text. In Proc. COLING. [find](https://scholar.google.com/scholar?q=J%2E+Nivre+and+M%2E+Scholz%2E+2004%2E+Deterministic+dependency+parsing+of+english+text%2E+In+Proc%2E+COLING%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/aclbulk-2004-nivre-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. [find](https://scholar.google.com/scholar?q=H%2E+Yamada+and+Y%2E+Matsumoto%2E+2003%2E+Statistical+dependency+analysis+with+support+vector+machines%2E+In+Proc%2E+IWPT%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/parsers-2003-yamada-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)