[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/)

[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/) / Online Learning of Approximate Dependency Parsing Algorithms

# Online Learning of Approximate Dependency Parsing 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/) · **Year:** 2006 · **Venue:** 11th Conference of the European Chapter of the Association for Computational Linguistics **Link:** [aclanthology.org/E06-1011](https://aclanthology.org/E06-1011/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**267** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/) of the 140673 papers whose bibliographies we read[11th Conference of the European Chapter of the Association for Computational Linguistics](https://aclanthology.org/volumes/E06-1/)[licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/E06-1011/)
- [PDF](https://aclanthology.org/E06-1011.pdf)

**Authors (2)**

1. Ryan McDonald
2. Fernando Pereira

Citations and author metrics from OpenAlex (); authors with the same name are not always told apart.

## What it is about

The maximum spanning tree framework scores a tree as a sum of arc scores, which cannot see neighbouring decisions. The paper adds second-order factors (sibling and grandparent pairs) to projective parsing, using an extension of Eisner's algorithm that stays cubic, and gives an approximate non-projective second-order parser: it starts from the projective solution and greedily rearranges arcs under the tree constraint. It also allows words with several heads, which Danish needs. Training is online large-margin (MIRA-style), which the authors show is robust to approximate inference. On Czech, per-word accuracy rises from 83.0 with the first-order projective parser to 85.2 with the second-order non-projective one; on Danish the F-measure reaches 84.4 and 85.6 with multiple parents. The authors report the best accuracy known to them for both languages at the time.

## Ideas

- I1. gparse/src/eisner.rs: add a second-order sibling term to the projective decoder and measure LAS on EWT dev against first-order decoding, recording tokens per second.
- I2. gparse: after projective decoding, apply the paper's greedy arc rearrangement to sentences with crossing arcs, and measure LAS on GUM test (test only, NC licence) and on the non-projective EWT sentences.
- I3. en/src/parse.rs: replace the averaged perceptron update with a margin-based update whose step size scales with the number of wrong arcs, as in this paper, and measure LAS on EWT dev, twice, for determinism.

## For Mova

The ideas touch the decoder `gparse/src/eisner.rs`, the approximate step that would sit after it, and the update rule in `en/src/parse.rs`. The chapters are `languages/en/21-clause-structure` and `languages/en/25-relative-clauses`, where crossing arcs appear. Measure first I3, a change to the update rule on the existing parser with no new data, and then I1 for the decoder.

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{mcdonald2006online,
  title = {{Online Learning of Approximate Dependency Parsing Algorithms}},
  author = {McDonald, Ryan and Pereira, Fernando},
  booktitle = {11th Conference of the European Chapter of the Association for Computational Linguistics},
  year = {2006},
  url = {https://aclanthology.org/E06-1011/}
}
```

- [← previous GLUCOSE: GeneraLized and COntextualized Story Explanations](https://md.mova.elamur.ai/free/en/docs/papers/commonsense-2020-mostafazadeh-glucose-generalized-contextualized-story-explanations/)
- [next → English Grammar (Wikibooks)](https://md.mova.elamur.ai/free/en/docs/papers/contributors-2026-english-grammar/)
- [↑ back to English](https://md.mova.elamur.ai/free/en/docs/papers/en/)

## References

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

1. E. Charniak. 2000. A maximum-entropy-inspired parser. In Proc. NAACL. [find](https://scholar.google.com/scholar?q=E%2E+Charniak%2E+2000%2E+A+maximum%2Dentropy%2Dinspired+parser%2E+In+Proc%2E+NAACL%2E)
2. D.M. Chickering, D. Geiger, and D. Heckerman. 1994. Learning bayesian networks: The combination of knowledge and statistical data. Technical Report MSR-TR-94-09, Microsoft Research. [find](https://scholar.google.com/scholar?q=D%2EM%2E+Chickering%2C+D%2E+Geiger%2C+and+D%2E+Heckerman%2E+1994%2E+Learning+bayesian+networks%3A+The+combination+of+knowledge+and+statistical+data%2E+Technical+Report+MSR%2DTR%2D94%2D09%2C+Microsoft+Research%2E)
3. 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)
4. M. Collins and B. Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL. [find](https://scholar.google.com/scholar?q=M%2E+Collins+and+B%2E+Roark%2E+2004%2E+Incremental+parsing+with+the+perceptron+algorithm%2E+In+Proc%2E+ACL%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/collins-2004-incremental-parsing-perceptron-algorithm/)
5. 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)
6. 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/)
7. 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)
8. H. Daum´e and D. Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In Proc. ICML. [find](https://scholar.google.com/scholar?q=H%2E+Daum%C2%B4e+and+D%2E+Marcu%2E+2005%2E+Learning+as+search+optimization%3A+Approximate+large+margin+methods+for+structured+prediction%2E+In+Proc%2E+ICML%2E)
9. 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%93240%2E)
10. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COL-ING. [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+COL%2DING%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/ast-1996-eisner-three-new-probabilistic-models-dependency/)
11. 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)
12. K. Hall and V. N´ov´ak. 2005. Corrective modeling for non-projective dependency parsing. In Proc. IWPT. [find](https://scholar.google.com/scholar?q=K%2E+Hall+and+V%2E+N%C2%B4ov%C2%B4ak%2E+2005%2E+Corrective+modeling+for+non%2Dprojective+dependency+parsing%2E+In+Proc%2E+IWPT%2E)
13. R. Hudson. 1984. Word Grammar. Blackwell. [find](https://scholar.google.com/scholar?q=R%2E+Hudson%2E+1984%2E+Word+Grammar%2E+Blackwell%2E)
14. M. T. Kromann. 2001. Optimaility parsing and local cost functions in discontinuous grammars. In Proc. FG-MOL. [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Kromann%2E+2001%2E+Optimaility+parsing+and+local+cost+functions+in+discontinuous+grammars%2E+In+Proc%2E+FG%2DMOL%2E)
15. M. T. Kromann. 2003. The danish dependency treebank and the dtag treebank tool. In Proc. TLT. [find](https://scholar.google.com/scholar?q=M%2E+T%2E+Kromann%2E+2003%2E+The+danish+dependency+treebank+and+the+dtag+treebank+tool%2E+In+Proc%2E+TLT%2E)
16. R. McDonald, K. Crammer, and F. Pereira. 2005a. Flexible text segmentation with structured multilabel classifi cation. In Proc. HLT-EMNLP. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+K%2E+Crammer%2C+and+F%2E+Pereira%2E+2005a%2E+Flexible+text+segmentation+with+structured+multilabel+classifi+cation%2E+In+Proc%2E+HLT%2DEMNLP%2E)
17. R. McDonald, K. Crammer, and F. Pereira. 2005b. 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+2005b%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/)
18. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005c. Non-projective dependency parsing using spanning tree algorithms. In Proc. HLT-EMNLP. [find](https://scholar.google.com/scholar?q=R%2E+McDonald%2C+F%2E+Pereira%2C+K%2E+Ribarov%2C+and+J%2E+Hajic%CC%8C%2E+2005c%2E+Non%2Dprojective+dependency+parsing+using+spanning+tree+algorithms%2E+In+Proc%2E+HLT%2DEMNLP%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)
19. I.A. Meĺčuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. [find](https://scholar.google.com/scholar?q=I%2EA%2E+Mel%CC%81c%CC%8Cuk%2E+1988%2E+Dependency+Syntax%3A+Theory+and+Practice%2E+State+University+of+New+York+Press%2E)
20. R. Moore. 2005. A discriminative framework for bilingual word alignment. In Proc. HLT-EMNLP. [find](https://scholar.google.com/scholar?q=R%2E+Moore%2E+2005%2E+A+discriminative+framework+for+bilingual+word+alignment%2E+In+Proc%2E+HLT%2DEMNLP%2E)
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. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. EMNLP. [find](https://scholar.google.com/scholar?q=A%2E+Ratnaparkhi%2E+1996%2E+A+maximum+entropy+model+for+part%2Dof%2Dspeech+tagging%2E+In+Proc%2E+EMNLP%2E)
23. 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)
24. 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/)
25. A 2nd-Order Non-projective MST Parsing is NP-hard [find](https://scholar.google.com/scholar?q=A+2nd%2DOrder+Non%2Dprojective+MST+Parsing+is+NP%2Dhard)