Online Learning of Approximate Dependency Parsing Algorithms

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

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/}
}

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
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
3. Y.J. Chu and T.H. Liu. 1965. On the shortest arborescence of a directed graph. Science Sinica, 14:1396– 1400. find
4. M. Collins and B. Roark. 2004. Incremental parsing with the perceptron algorithm. In Proc. ACL. find our card
5. M. Collins, J. Hajič, L. Ramshaw, and C. Tillmann. 1999. A statistical parser for Czech. In Proc. ACL. find
6. M. Collins. 2002. Discriminative training methods for hidden Markov models: Theory and experiments with perceptron algorithms. In Proc. EMNLP. find our card
7. K. Crammer and Y. Singer. 2003. Ultraconservative online algorithms for multiclass problems. JMLR. find
8. H. Daum´e and D. Marcu. 2005. Learning as search optimization: Approximate large margin methods for structured prediction. In Proc. ICML. find
9. J. Edmonds. 1967. Optimum branchings. Journal of Research of the National Bureau of Standards, 71B:233–240. find
10. J. Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proc. COL-ING. find our card
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
12. K. Hall and V. N´ov´ak. 2005. Corrective modeling for non-projective dependency parsing. In Proc. IWPT. find
13. R. Hudson. 1984. Word Grammar. Blackwell. find
14. M. T. Kromann. 2001. Optimaility parsing and local cost functions in discontinuous grammars. In Proc. FG-MOL. find
15. M. T. Kromann. 2003. The danish dependency treebank and the dtag treebank tool. In Proc. TLT. find
16. R. McDonald, K. Crammer, and F. Pereira. 2005a. Flexible text segmentation with structured multilabel classifi cation. In Proc. HLT-EMNLP. find
17. R. McDonald, K. Crammer, and F. Pereira. 2005b. Online large-margin training of dependency parsers. In Proc. ACL. find our card
18. R. McDonald, F. Pereira, K. Ribarov, and J. Hajič. 2005c. Non-projective dependency parsing using spanning tree algorithms. In Proc. HLT-EMNLP. find our card
19. I.A. Meĺčuk. 1988. Dependency Syntax: Theory and Practice. State University of New York Press. find
20. R. Moore. 2005. A discriminative framework for bilingual word alignment. In Proc. HLT-EMNLP. find
21. J. Nivre and J. Nilsson. 2005. Pseudo-projective dependency parsing. In Proc. ACL. find
22. A. Ratnaparkhi. 1996. A maximum entropy model for part-of-speech tagging. In Proc. EMNLP. find
23. B. Taskar, D. Klein, M. Collins, D. Koller, and C. Manning. 2004. Max-margin parsing. In Proc. EMNLP. find
24. H. Yamada and Y. Matsumoto. 2003. Statistical dependency analysis with support vector machines. In Proc. IWPT. find our card
25. A 2nd-Order Non-projective MST Parsing is NP-hard find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/continual-2006-mcdonald-online-learning-approximate-dependency-parsing/