A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing

Summary

The paper compares graph-based and transition-based dependency parsing within one framework based on beam search and a discriminatively trained perceptron. It shows that a transition-based parser does not have to be greedy: decoding with a beam of partial action sequences, combined with perceptron training with early update (stop and update as soon as the gold sequence falls out of the beam), gives a strong transition-based parser. A graph-based parser is formulated with the same beam-search decoder. Because the two approaches use different kinds of features, the authors combine them into a single model whose score sums both feature sets, and report that the combination improves over each parser alone on English and Chinese.

How Mova uses it

• en/src/parse.rs: the English UD parser is an arc-standard transition system (SHIFT / LEFT(label) / RIGHT(label)) with weight tables trained by an averaged perceptron. Decoding uses a beam of 8 hypotheses, and training uses beam search with early update, as in this paper.
• Only the transition-based half is used; the graph-based parser and the combined model are not implemented.

Effectiveness in Mova

Measured (beam with early update vs greedy, same features): EWT test LAS 79.00 → 79.77, dev 77.33 → 79.17, PUD 74.48 → 76.33. In the en crate summary with Mova's own tags: EWT UAS/LAS 84.2/79.8 with the beam vs 83.4/79.0 greedy.

👨‍🔬💥

More ideas (a second reading)

• I1. en/src/parse.rs: add a second scorer over whole trees, with sibling and grandparent features on the arc set, and add its score to the beam ranking of the transition parser. Measure LAS on EWT test against the current arc-standard parser and on the two-fold check.
• I2. Beam curve: report dev LAS for beam sizes 1, 2, 4, 8 and 16 with the en parse-eval command, as the paper does for its curves. Pick the beam at the knee of the curve, not the largest one, to keep the parser fast.
• I3. Complete-match rate: add the share of sentences with a fully correct tree to en parse-eval. The paper reports it next to head accuracy, and it shows whether a parser is usable without repair.

Topics: Dependency parsing

Cite

The paper itself, not this card. BibTeX from the library's record of the work.

@inproceedings{zhang2008tale,
  title = {{A Tale of Two Parsers: Investigating and Combining Graph-based and Transition-based Dependency Parsing}},
  author = {Zhang, Yue and Clark, Stephen},
  booktitle = {Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing},
  year = {2008},
  url = {https://aclanthology.org/D08-1059/}
}

References

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

1. Sabine Buchholz and Erwin Marsi. 2006. CoNLL-X shared task on multilingual dependency parsing. In Proceedings of CoNLL, pages 149–164, New York City, USA, June. find our card
2. Xavier Carreras, Mihai Surdeanu, and Lluis Marquez. 2006. Projective dependency parsing with perceptron. In Proceedings of CoNLL, New York City, USA, June. find
3. Xavier Carreras. 2007. Experiments with a higher-order projective dependency parser. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 957–961, Prague, Czech Republic, June. find
4. Michael Collins and Brian Roark. 2004. Incremental parsing with the perceptron algorithm. In Proceedings of ACL, pages 111–118, Barcelona, Spain, July. find our card
5. Michael Collins. 2002. Discriminative training methods for hidden markov models: Theory and experiments with perceptron algorithms. In Proceedings of EMNLP, pages 1–8, Philadelphia, USA, July. find our card
6. Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the ACM Southeast Conference, Athens, Georgia, March. find
7. Xiangyu Duan, Jun Zhao, and Bo Xu. 2007. Probabilistic models for action-based chinese dependency parsing. In Proceedings of ECML/ECPPKDD, Warsaw, Poland, September. find
8. Jason Eisner. 1996. Three new probabilistic models for dependency parsing: An exploration. In Proceedings of COLING, pages 340–345, Copenhagen, Denmark, August. find our card
9. Johan Hall, Jens Nilsson, Joakim Nivre, Gülsen Eryigit, Beáta Megyesi, Mattias Nilsson, and Markus Saers. 2007. Single malt or blended? a study in multilingual parser optimization. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 933– 939, Prague, Czech Republic, June. find
10. Keith Hall. 2007. K-best spanning tree parsing. In Proceedings of ACL, Prague, Czech Republic, June. find
11. Richard Johansson and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of CoNLL, pages 206–210, New York City, USA, June. find
12. Richard Johansson and Pierre Nugues. 2007. Incremental dependency parsing using online learning. In Proceedings of the CoNLL/EMNLP, pages 1134–1138, Prague, Czech Republic. find
13. Philip Koehn, Franz Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of NAACL/HLT, Edmonton, Canada, May. find
14. Terry Koo, Xavier Carreras, and Michael Collins. 2008. Simple semi-supervised dependency parsing. In Proceedings of ACL/HLT, pages 595–603, Columbus, Ohio, June. find
15. Ryan McDonald and Joakim Nivre. 2007. Characterizing the errors of data-driven dependency parsing models. In Proceedings of EMNLP/CoNLL, pages 122– 131, Prague, Czech Republic, June. find our card
16. R McDonald and F Pereira. 2006. Online learning of approximate dependency parsing algorithms. In In Proc. of EACL, pages 81–88, Trento, Italy, April. find our card
17. Ryan McDonald, Koby Crammer, and Fernando Pereira. 2005. Online large-margin training of dependency parsers. In Proceedings of ACL, pages 91–98, Ann Arbor, Michigan, June. find our card
18. Tetsuji Nakagawa. 2007. Multilingual dependency parsing using global features. In Proceedings of the CoNLL Shared Task Session of EMNLP/CoNLL, pages 952–956, Prague, Czech Republic, June. find
19. Joakim Nivre and Ryan McDonald. 2008. Integrating graph-based and transition-based dependency parsers. In Proceedings of ACL/HLT, pages 950–958, Columbus, Ohio, June. find
20. Joakim Nivre, Johan Hall, Jens Nilsson, Gülşen Eryiǧit, and Svetoslav Marinov. 2006. Labeled pseudo-projective dependency parsing with support vector machines. In Proceedings of CoNLL, pages 221–225, New York City, USA, June. find
21. K Sagae and A Lavie. 2006a. Parser combination by reparsing. In In Proc. HLT/NAACL, pages 129–132, New York City, USA, June. find
22. Kenji Sagae and Alon Lavie. 2006b. A best-first probabilistic shift-reduce parser. In Proceedings of COL-ING/ACL (poster), pages 691–698, Sydney, Australia, July. find
23. Honglin Sun and Daniel Jurafsky. 2004. Shallow semantic parsing of Chinese. In Proceedings of NAACL/HLT, Boston, USA, May. find
24. H Yamada and Y Matsumoto. 2003. Statistical dependency analysis using support vector machines. In Proceedings of IWPT, Nancy, France, April. find

This page in Markdown → https://md.mova.elamur.ai/free/en/docs/papers/zhang-2008-tale-two-parsers-investigating-combining/