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

By Yue Zhang, Stephen Clark. Conference on Empirical Methods in Natural Language Processing, 2008

338 citations recorded by the source corpus.

Graph-based and transition-based approaches to dependency parsing adopt very different views of the problem, each view having its own strengths and limitations. We study both approaches under the framework of beam-search. By developing a graph-based and a transition-based dependency parser, we show that a beam-search decoder is a competitive choice for both methods. More importantly, we propose a beam-search-based parser that combines both graph-based and transition-based parsing into a single system for training and decoding, showing that it outperforms both the pure graph-based and the pure transition-based parsers. Testing on the English and Chinese Penn Treebank data, the combined system gave state-of-the-art accuracies of 92.1% and 86.2%, respectively.

Subfields: Artificial Intelligence, Molecular Biology

View Paper: https://www.semanticscholar.org/paper/ad1181d188f730b7917a95ae452efb48f830c90a

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Molecular Biology

Citations in the corpus

Syntactic Processing Using the Generalized Perceptron and Beam Search (2011, methodology): “We showed in Zhang and Clark (2008a) that a naive single-beam decoder which treats partial words in the same way as full words failed to give a competitive accuracy.”
Easy-First Dependency Parsing with Hierarchical Tree LSTMs (2016, methodology): “1 (CTB5), using the train/test/dev splits of (Zhang and Clark, 2008; Dyer et al., 2015) with gold partof-speech tags, also following (Dyer et al.”
Head-Driven Phrase Structure Grammar Parsing on Penn Treebank (2019, background): “ing have different data splitting on CTB (Zhang and Clark, 2008; Liu and Zhang, 2017b), we report our parsing performance on both data splitting.”
Transition-based Dependency Parsing with Rich Non-local Features (2011, methodology): “In the aspect of decoding, beam-search (Johansson and Nugues, 2007; Zhang and Clark, 2008; Huang et al., 2009) and partial dynamic-programming (Huang and Sagae, 2010) have been applied to improve upon greedy one-best search, and positive results were reported.”
A Fast and Accurate Dependency Parser using Neural Networks (2014, methodology): “Depen-dencies are converted using the Penn2Malt tool with the head-ﬁnding rules of (Zhang and Clark, 2008).”
Exploiting Multi-typed Treebanks for Parsing with Deep Multi-task Learning (2016, neutral): “Aside from resource utilization, attempts have also been made to integrate different parsing models through stacking (Torres Martins et al., 2008; Nivre and McDonald, 2008) or joint inference (Zhang and Clark, 2008; Zhang et al., 2014).”
Generative Incremental Dependency Parsing with Neural Networks (2015, background): “Beam-search decoders for transition-based parsing (Zhang and Clark, 2008) keep a beam of partial derivations, advancing each derivation by one transition at a time.”
Training Deterministic Parsers with Non-Deterministic Oracles (2013, methodology): “, 2008) and beam search and structured prediction (Zhang and Clark, 2008; Zhang and Nivre, 2011).”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, methodology): “For natural language processing tasks such as Chinese word segmentation (Zhang & Clark, 2007), dependency parsing (Yamada & Matsumoto, 2003; Nivre & Scholz, 2004; Zhang & Clark, 2008; Huang & Sagae, 2010; c©2017 AI Access Foundation.”
An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing (2010, methodology): “The reported results in (Zhang and Clark, 2008) use a beam size of 64, compared to our constant of k = 6.”
Structured Training for Neural Network Transition-Based Parsing (2015, background): “Zhang and Clark (2008) showed that a beamsearch decoding algorithm utilizing the structured perceptron training algorithm can greatly improve accuracy.”
Learning Structured Perceptrons for Coreference Resolution with Latent Antecedents and Non-local Features (2014, background): “This contrasts with previous work on, e.g., syntactic parsing (Collins and Roark, 2004; Huang, 2008; Zhang and Clark, 2008) and linearization (Bohnet et al., 2011), and even simpler structured prediction problems, where early updates are not even necessary, such as part-of-speech tagging (Collins,…”
Sequence-to-Dependency Neural Machine Translation (2017, background): “These kinds of feature template have beeb proven effective in dependency parsing task (Zhang and Clark, 2008).”
Distilling an Ensemble of Greedy Dependency Parsers into One MST Parser (2016, methodology): “This approach to training a model is wellstudied for a FOG parser, but not for a transitionbased parser, which is comprised of a collection of classifiers trained to choose good sequences of transitions—not to score whole trees for good attachment accuracy.”
meProp: Sparsified Back Propagation for Accelerated Deep Learning with Reduced Overfitting (2017, methodology): “For the transition-based dependency parsing task, existing approaches typically can achieve the UAS score from 91.4 to 91.5 (Zhang & Clark, 2008; Nivre et al., 2007; Huang & Sagae, 2010).”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, background): “In the standard approach to beam search for transition-based parsing (Zhang and Clark, 2008), the beam stores partial derivations with the same number of transitions performed, and the lowestscoring ones are removed when the size of the beam exceeds a set threshold.”