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-evalcommand, 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.
Library summary
Written for the Research library (claude-opus-5-5) from the paper text, in our own words: the license "CC BY-NC-SA 3.0 (ACL Anthology, before 2016)" does not allow redistributing the text itself. Original — aclanthology.org/D08-1059.pdf
Summary
Graph-based and transition-based dependency parsers, exemplified by MSTParser and MaltParser, reach similar accuracy but make different kinds of errors. Graph-based parsers score whole trees with exact inference, which limits the features they can use. Transition-based parsers score individual actions with rich features, but their greedy decoding lets errors propagate. Zhang and Clark place both paradigms in one beam-search framework, trained with an averaged perceptron and the "early update" strategy. They build three projective parsers:
- a graph-based parser with MSTParser features plus extra non-local features;
- a transition-based parser using MaltParser's actions with beam search;
- a combined parser whose single linear model adds both kinds of scores.
All parameters of the combined model are trained jointly. Beam search proves competitive for both paradigms, and the combined model beats each pure parser. It reaches 92.1% on the English Penn Treebank and 86.2% on Chinese CTB 5, close to or above the best published results. The work shows that approximate search lets complementary models be merged and trained as one system rather than ensembled after the fact.
Key points
- The graph-based decoder extends the incremental Covington algorithm with a beam, runs in O(n²) time, and guarantees projective trees. It adds grandchild and arity features that are impractical for dynamic-programming decoders.
- The transition-based parser keeps B action sequences using the Shift, ArcRight, ArcLeft and Reduce actions. It is trained globally, unlike earlier beam parsers that estimated each action's probability separately.
- The combined parser scored 92.1% on PTB (English) and 86.2% on CTB 5 (Chinese). The Chinese result improves on the previous best (Duan et al., 2007) by 1.8%.
- For Chinese, constituency trees were converted to dependencies with head-finding rules (mostly from Sun and Jurafsky, 2004), and the input used gold-standard POS tags.
- Evaluation measured the share of non-root words with the correct head, root accuracy and complete match, all excluding punctuation. Unlike ensemble or feature-stacking approaches (Nivre and McDonald, 2008), the combination is a single, consistently trained model.
Cite
@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
- 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
- Xavier Carreras, Mihai Surdeanu, and Lluis Marquez. 2006. Projective dependency parsing with perceptron. In Proceedings of CoNLL, New York City, USA, June. find
- 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
- 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
- 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
- Michael A. Covington. 2001. A fundamental algorithm for dependency parsing. In Proceedings of the ACM Southeast Conference, Athens, Georgia, March. find
- 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
- 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
- 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
- Keith Hall. 2007. K-best spanning tree parsing. In Proceedings of ACL, Prague, Czech Republic, June. find
- Richard Johansson and Pierre Nugues. 2006. Investigating multilingual dependency parsing. In Proceedings of CoNLL, pages 206–210, New York City, USA, June. find
- 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
- Philip Koehn, Franz Och, and Daniel Marcu. 2003. Statistical phrase-based translation. In Proceedings of NAACL/HLT, Edmonton, Canada, May. find
- 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 our card
- 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
- 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
- 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
- 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
- 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
- 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
- K Sagae and A Lavie. 2006a. Parser combination by reparsing. In In Proc. HLT/NAACL, pages 129–132, New York City, USA, June. find
- 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
- Honglin Sun and Daniel Jurafsky. 2004. Shallow semantic parsing of Chinese. In Proceedings of NAACL/HLT, Boston, USA, May. find
- H Yamada and Y Matsumoto. 2003. Statistical dependency analysis using support vector machines. In Proceedings of IWPT, Nancy, France, April. find