---
title: "Online Large-Margin Training of Dependency Parsers — McDonald 2005"
description: "The paper trains a linear, edge-scored dependency parser with online MIRA, a margin-based update that changes the… 30 references, cited by 421 papers here."
authors: ["Ryan McDonald", "Koby Crammer", "Fernando Pereira"]
year: 2005
venue: "Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)"
source: "https://aclanthology.org/P05-1012/"
doi: "10.3115/1219840.1219852"
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-online-large-margin-training-dependency/"
---
[Elamur Research](https://md.research.elamur.ai/free/en/) · [this page in HTML](https://research.elamur.ai/free/en/papers/mcdonald-2005-online-large-margin-training-dependency/)

[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/) / Online Large-Margin Training of Dependency Parsers

# Online Large-Margin Training of Dependency Parsers

**Authors:** [Ryan McDonald](https://md.research.elamur.ai/free/en/authors/ryan-mcdonald/), Koby Crammer and [Fernando Pereira](https://md.research.elamur.ai/free/en/authors/fernando-pereira/) · **Year:** 2005 · **Venue:** Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05) **Link:** [aclanthology.org/P05-1012](https://aclanthology.org/P05-1012/) · **Licence:** [CC BY-NC-SA 3.0](https://creativecommons.org/licenses/by-nc-sa/3.0/) — summary only

[**791** citations](https://openalex.org/works?filter=cites:W2116410915) OpenAlex, 2026-10-14 · [**421** citations in our library](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-online-large-margin-training-dependency/cited-by/) of the 140,884 papers whose bibliographies we read · [Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)](https://aclanthology.org/volumes/P05-1/) · [licence](https://creativecommons.org/licenses/by-nc-sa/3.0/)

- [Publisher's page](https://aclanthology.org/P05-1012/)
- [PDF](https://aclanthology.org/P05-1012.pdf)
- [DOI 10.3115/1219840.1219852](https://doi.org/10.3115/1219840.1219852)
- [OpenAlex](https://openalex.org/W2116410915)

**Authors (3)**

1. [Ryan McDonald](https://openalex.org/A5022489655) [Semantic Scholar](https://www.semanticscholar.org/author/143957226) · h 48 · 16,067 citations · 113 works
2. [Koby Crammer](https://openalex.org/A5006419939) [ORCID](https://orcid.org/0000-0001-8824-5747) · [Semantic Scholar](https://www.semanticscholar.org/author/1693407) · h 39 · 15,619 citations · 164 works
3. [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

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

## What it is about

The paper trains a linear, edge-scored dependency parser with online MIRA, a margin-based update that changes the weights as little as possible while the correct tree beats the k best wrong trees by a loss-dependent margin. It runs on top of Eisner's O(n^3) projective decoder, with no pruning. On English it reaches 90.9% attachment accuracy, against 90.6% for an averaged perceptron on the same features (the MIRA gain is significant at p \< 0.005), and 83.3% on Czech. The number k of competing trees matters little: accuracy is 90.73–90.92 for k from 1 to 20, with the best value at k = 10 (90.92) and 90.88 at k = 5, while training time grows about linearly with k. Against the lexicalized Collins parser, the dependency model parses section 23 in about 6 minutes instead of 98, at 90.9% against 91.4% for the Collins-derived dependencies.

## Ideas

- I3. Determinism check for any of I1 and I2: run each setting twice and confirm identical LAS before any claim of a gain (BTreeMap order in the trainer).

## For Mova

- I1. en/src/parse.rs: replace the single-best perceptron update with a k-best margin update (k = 5, as in the paper); measure cv LAS on the train folds, and EWT test LAS once per release, against the current update.
- I2. en/src/parse.rs: scale the update step by the number of wrong heads in the predicted tree (the loss term of MIRA); measure cv LAS and cv UAS on the same folds.
- I4. `en beam-curve` with the k-best update: check whether accuracy peaks early and then degrades for large k, as the paper's Table 4 shows, on cv of the train folds.

The paper is the closest published model to the `en` parser's training loop, so the chapters are 20-syntax-overview and 21-clause-structure, where head-dependent decisions are described. Crates and files: `en/src/parse.rs` (trainer, beam 8, early update) and the `en beam-curve` command. Measure first: cv LAS for k = 1 against k = 5 on the same folds, each run twice (idea I1 and I3).

## Institutions

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

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

## Cite

Cite as Ryan McDonald, Koby Crammer and Fernando Pereira. 2005. Online Large-Margin Training of Dependency Parsers. Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05).

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

```bibtex
@inproceedings{mcdonald2005online,
  title = {{Online Large-Margin Training of Dependency Parsers}},
  author = {Ryan McDonald, Koby Crammer and Fernando Pereira},
  booktitle = {Proceedings of the 43rd Annual Meeting of the Association for Computational Linguistics (ACL'05)},
  year = {2005},
  doi = {10.3115/1219840.1219852},
  url = {https://doi.org/10.3115/1219840.1219852}
}
```

- [← previous Non-Projective Dependency Parsing using Spanning Tree Algorithms](https://md.research.elamur.ai/free/en/papers/mcdonald-2005-non-projective-dependency-parsing-spanning/)
- [next → A Shortest Path Dependency Kernel for Relation Extraction](https://md.research.elamur.ai/free/en/papers/bunescu-2005-shortest-path-dependency-kernel-relation/)
- [↑ back to papers of 2005](https://md.research.elamur.ai/free/en/papers/2005/)

## References

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

1. D.M. Bikel. 2004. Intricacies of Collins parsing model. Computational Linguistics. [our card](https://md.research.elamur.ai/free/en/papers/bikel-2004-intricacies-collins-parsing-model/)
2. Y. Censor and S.A. Zenios. 1997. Parallel optimization : theory, algorithms, and applications. Oxford University Press. [find](https://scholar.google.com/scholar?q=Y%2E+Censor+and+S%2EA%2E+Zenios%2E+1997%2E+Parallel+optimization+%3A+theory%2C+algorithms%2C+and+applications%2E+Oxford+University+Press%2E)
3. E. Charniak. 2000. A maximum-entropy-inspired parser. In Proc. NAACL. [our card](https://md.research.elamur.ai/free/en/papers/charniak-2000-maximum-entropy-inspired-parser/)
4. S. Clark and J.R. Curran. 2004. Parsing the WSJ using CCG and log-linear models. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/clark-2004-parsing-wsj-ccg-log-linear/)
5. M. Collins and B. Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/collins-2004-incremental-parsing-perceptron-algorithm/)
6. 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/)
7. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=M%2E+Collins%2E+1999%2E+Head%2DDriven+Statistical+Models+for+Natural+Language+Parsing%2E+Ph%2ED%2E+thesis%2C+University+of+Pennsylvania%2E)
8. 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/)
9. K. Crammer and Y. Singer. 2001. On the algorithmic implementation of multiclass kernel based vector machines. JMLR. [find](https://scholar.google.com/scholar?q=K%2E+Crammer+and+Y%2E+Singer%2E+2001%2E+On+the+algorithmic+implementation+of+multiclass+kernel+based+vector+machines%2E+JMLR%2E)
10. 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)
11. 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)
12. 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/)
13. 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/)
14. J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head-automaton grammars. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/eisner-1999-efficient-parsing-bilexical-context-free/)
15. 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/)
16. J. Hajič. 1998. Building a syntactically annotated corpus: The Prague dependency treebank. Issues of Valency and Meaning. [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%2E)
17. L. Huang and D. Chiang. 2005. Better k-best parsing. Technical Report MS-CIS-05-08, University of Pennsylvania. [find](https://scholar.google.com/scholar?q=L%2E+Huang+and+D%2E+Chiang%2E+2005%2E+Better+k%2Dbest+parsing%2E+Technical+Report+MS%2DCIS%2D05%2D08%2C+University+of+Pennsylvania%2E)
18. Richard Hudson. 1984. Word Grammar. Blackwell. [find](https://scholar.google.com/scholar?q=Richard+Hudson%2E+1984%2E+Word+Grammar%2E+Blackwell%2E)
19. T. Joachims. 2002. Learning to Classify Text using Support Vector Machines. Kluwer. [find](https://scholar.google.com/scholar?q=T%2E+Joachims%2E+2002%2E+Learning+to+Classify+Text+using+Support+Vector+Machines%2E+Kluwer%2E)
20. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML. [find](https://scholar.google.com/scholar?q=J%2E+Lafferty%2C+A%2E+McCallum%2C+and+F%2E+Pereira%2E+2001%2E+Conditional+random+fields%3A+Probabilistic+models+for+segmenting+and+labeling+sequence+data%2E+In+Proc%2E+ICML%2E)
21. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of english: the penn treebank. Computational Linguistics. [our card](https://md.research.elamur.ai/free/en/papers/marcus-1993-building-large-annotated-corpus-english/)
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. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. EMNLP. [our card](https://md.research.elamur.ai/free/en/papers/ratnaparkhi-1996-maximum-entropy-model-part-speech/)
24. A. Ratnaparkhi. 1999. Learning to parse natural language with maximum entropy models. Machine Learning. [find](https://scholar.google.com/scholar?q=A%2E+Ratnaparkhi%2E+1999%2E+Learning+to+parse+natural+language+with+maximum+entropy+models%2E+Machine+Learning%2E)
25. S. Riezler, T. King, R. Kaplan, R. Crouch, J. Maxwell, and M. Johnson. 2002. Parsing the Wall Street Journal using a lexical-functional grammar and discriminative estimation techniques. In Proc. ACL. [our card](https://md.research.elamur.ai/free/en/papers/riezler-2002-parsing-wall-street-journal-lexical/)
26. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. HLT-NAACL. [find](https://scholar.google.com/scholar?q=F%2E+Sha+and+F%2E+Pereira%2E+2003%2E+Shallow+parsing+with+conditional+random+fields%2E+In+Proc%2E+HLT%2DNAACL%2E)
27. 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)
28. 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)
29. 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)
30. 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/)