Online Large-Margin Training of Dependency Parsers

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

Cite

The paper itself, not this card. BibTeX from the library's record of the work. DOI 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}
}

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
2. Y. Censor and S.A. Zenios. 1997. Parallel optimization : theory, algorithms, and applications. Oxford University Press. find
3. E. Charniak. 2000. A maximum-entropy-inspired parser. In Proc. NAACL. find
4. S. Clark and J.R. Curran. 2004. Parsing the WSJ using CCG and log-linear models. In Proc. ACL. find
5. M. Collins and B. Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL. find our card
6. M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A statistical parser for Czech. In Proc. ACL. find
7. M. Collins. 1999. Head-Driven Statistical Models for Natural Language Parsing. Ph.D. thesis, University of Pennsylvania. find
8. M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. find our card
9. K. Crammer and Y. Singer. 2001. On the algorithmic implementation of multiclass kernel based vector machines. JMLR. find
10. K. Crammer and Y. Singer. 2003. Ultraconservative online algorithms for multiclass problems. JMLR. find
11. K. Crammer, O. Dekel, S. Shalev-Shwartz, and Y. Singer. 2003. Online passive aggressive algorithms. In Proc. NIPS. find
12. A. Culotta and J. Sorensen. 2004. Dependency tree kernels for relation extraction. In Proc. ACL. find
13. Y. Ding and M. Palmer. 2005. Machine translation using probabilistic synchronous dependency insertion grammars. In Proc. ACL. find our card
14. J. Eisner and G. Satta. 1999. Efficient parsing for bilexical context-free grammars and head-automaton grammars. In Proc. ACL. find
15. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COLING. find our card
16. J. Hajič. 1998. Building a syntactically annotated corpus: The Prague dependency treebank. Issues of Valency and Meaning. find
17. L. Huang and D. Chiang. 2005. Better k-best parsing. Technical Report MS-CIS-05-08, University of Pennsylvania. find
18. Richard Hudson. 1984. Word Grammar. Blackwell. find
19. T. Joachims. 2002. Learning to Classify Text using Support Vector Machines. Kluwer. find
20. J. Lafferty, A. McCallum, and F. Pereira. 2001. Conditional random fields: Probabilistic models for segmenting and labeling sequence data. In Proc. ICML. find
21. M. Marcus, B. Santorini, and M. Marcinkiewicz. 1993. Building a large annotated corpus of english: the penn treebank. Computational Linguistics. find our card
22. J. Nivre and M. Scholz. 2004. Deterministic dependency parsing of english text. In Proc. COLING. find our card
23. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. EMNLP. find
24. A. Ratnaparkhi. 1999. Learning to parse natural language with maximum entropy models. Machine Learning. find
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
26. F. Sha and F. Pereira. 2003. Shallow parsing with conditional random fields. In Proc. HLT-NAACL. find
27. Y. Shinyama, S. Sekine, K. Sudo, and R. Grishman. 2002. Automatic paraphrase acquisition from news articles. In Proc. HLT. find
28. B. Taskar, C. Guestrin, and D. Koller. 2003. Max-margin Markov networks. In Proc. NIPS. find
29. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP. find
30. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. find our card

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/narrative-2005-mcdonald-online-large-margin-training-dependency/