[Mova](https://md.mova.elamur.ai/free/en/) · [this page in HTML](https://mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/)

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

# Online Large-Margin Training of Dependency Parsers

**Authors:** [Ryan McDonald](https://md.mova.elamur.ai/free/en/docs/papers/authors/ryan-mcdonald/), Koby Crammer, [Fernando Pereira](https://md.mova.elamur.ai/free/en/docs/papers/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-snapshot · 2026-10-14[**421** citations in our library](https://md.mova.elamur.ai/free/en/docs/papers/cited-by/narrative-2005-mcdonald-online-large-margin-training-dependency/) of the 140673 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 · 16067 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 · 15619 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 · 31029 citations · 515 works

Citations and author metrics from openalex-snapshot (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

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

## For Mova

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

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. [DOI 10.3115/1219840.1219852](https://doi.org/10.3115/1219840.1219852)

```
@inproceedings{mcdonald2005online,
  title = {{Online Large-Margin Training of Dependency Parsers}},
  author = {McDonald, Ryan and Crammer, Koby and Pereira, Fernando},
  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.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-non-projective-dependency-parsing-spanning/)
- [next → Algorithms for Deterministic Incremental Dependency Parsing](https://md.mova.elamur.ai/free/en/docs/papers/narrative-2008-nivre-algorithms-deterministic-incremental-dependency-parsing/)
- [↑ 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. D.M. Bikel. 2004. Intricacies of Collins parsing model. Computational Linguistics. [find](https://scholar.google.com/scholar?q=D%2EM%2E+Bikel%2E+2004%2E+Intricacies+of+Collins+parsing+model%2E+Computational+Linguistics%2E)
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. [find](https://scholar.google.com/scholar?q=E%2E+Charniak%2E+2000%2E+A+maximum%2Dentropy%2Dinspired+parser%2E+In+Proc%2E+NAACL%2E)
4. S. Clark and J.R. Curran. 2004. Parsing the WSJ using CCG and log-linear models. In Proc. ACL. [find](https://scholar.google.com/scholar?q=S%2E+Clark+and+J%2ER%2E+Curran%2E+2004%2E+Parsing+the+WSJ+using+CCG+and+log%2Dlinear+models%2E+In+Proc%2E+ACL%2E)
5. 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/)
6. 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)
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. [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/)
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. [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)
13. 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/)
14. J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head-automaton grammars. In Proc. ACL. [find](https://scholar.google.com/scholar?q=J%2E+Eisner+and+G%2E+Satta%2E+1999%2E+Efficient+parsing+for+bilexical+context%2Dfree+grammars+and+head%2Dautomaton+grammars%2E+In+Proc%2E+ACL%2E)
15. 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/)
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. [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%2E) [our card](https://md.mova.elamur.ai/free/en/docs/papers/bank-1993-marcus-building-large-annotated-corpus-english/)
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. 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)
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. [find](https://scholar.google.com/scholar?q=S%2E+Riezler%2C+T%2E+King%2C+R%2E+Kaplan%2C+R%2E+Crouch%2C+J%2E+Maxwell%2C+and+M%2E+Johnson%2E+2002%2E+Parsing+the+Wall+Street+Journal+using+a+lexical%2Dfunctional+grammar+and+discriminative+estimation+techniques%2E+In+Proc%2E+ACL%2E)
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. [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/)