Algorithms for Deterministic Incremental Dependency Parsing

By Joakim Nivre. 2008

489 citations recorded by the source corpus.

Abstract Parsing algorithms that process the input from left to right and construct a single derivation have often been considered inadequate for natural language parsing because of the massive ambiguity typically found in natural language grammars. Nevertheless, it has been shown that such algorithms, combined with treebank-induced classifiers, can be used to build highly accurate disambiguating parsers, in particular for dependency-based syntactic representations. In this article, we first present a general framework for describing and analyzing algorithms for deterministic incremental dependency parsing, formalized as transition systems. We then describe and analyze two families of such algorithms: stack-based and list-based algorithms. In the former family, which is restricted to projective dependency structures, we describe an arc-eager and an arc-standard variant; in the latter family, we present a projective and a non-projective variant. For each of the four algorithms, we give proofs of correctness and complexity. In addition, we perform an experimental evaluation of all algorithms in combination with SVM classifiers for predicting the next parsing action, using data from thirteen languages. We show that all four algorithms give competitive accuracy, although the non-projective list-based algorithm generally outperforms the projective algorithms for languages with a non-negligible proportion of non-projective constructions. However, the projective algorithms often produce comparable results when combined with the technique known as pseudo-projective parsing. The linear time complexity of the stack-based algorithms gives them an advantage with respect to efficiency both in learning and in parsing, but the projective list-based algorithm turns out to be equally efficient in practice. Moreover, when the projective algorithms are used to implement pseudo-projective parsing, they sometimes become less efficient in parsing (but not in learning) than the non-projective list-based algorithm. Although most of the algorithms have been partially described in the literature before, this is the first comprehensive analysis and evaluation of the algorithms within a unified framework.

Subfields: Artificial Intelligence, Natural Language Processing

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 Natural Language Processing

Citations in the corpus

Grammar as a Foreign Language (2014, methodology): “Inspired by shift-reduce transition-based parsers (Nivre, 2008; Zhu et al., 2013), we introduce a stack where the words are provided to the LSTM as additional inputs during decoding.”
Transition-Based Dependency Parsing with Stack Long Short-Term Memory (2015, background): “…been addressed by development of alternative transition sets that simplify the modeling problem by making better attachment decisions (Nivre, 2007; Nivre, 2008; Nivre, 2009; Choi and McCallum, 2013; Bohnet and Nivre, 2012), through feature engineering (Zhang and Nivre, 2011; Ballesteros and…”
A Primer on Neural Network Models for Natural Language Processing (2015, methodology): “Some algorithms in language processing, including those for transition-based parsing (Nivre, 2008), require performing feature extraction over a stack.”
Generative Incremental Dependency Parsing with Neural Networks (2015, methodology): “Our parsing model is based on transition-based arc-standard projective dependency parsing (Nivre and Scholz, 2004).”
Syntactic Annotations for the Google Books NGram Corpus (2012, methodology): “We use a deterministic transition-based dependency parsing model (Nivre, 2008) with an arc-eager transition strategy.”
Consequences of the Now-or-Never bottleneck for signed versus spoken languages (2015, background): “ Acquisition as Learning to Process (Section 4): Transition-based parsers learn a sequence of processing actions (transitions), rather than a grammar (Nivre, 2008; Go mezRodrí guez et al., 2014), making the learning process simple and flexible.”
Training Deterministic Parsers with Non-Deterministic Oracles (2013, background): “The transition-based parsing framework (Nivre, 2008) assumes a transition system, an abstract machine that processes sentences”
Structured Training for Neural Network Transition-Based Parsing (2015, background): “Transition-based parsers (Nivre, 2008) have been shown to provide a good balance between efficiency and accuracy.”
Greedy, Joint Syntactic-Semantic Parsing with Stack LSTMs (2016, methodology): “(3)Note that in the original arc-eager algorithm (Nivre, 2008), SHIFT and RIGHT-ARC actions move the item on the buffer front to the stack, whereas we only copy it (to allow the semantic operations to have access to it).”
Sequence-to-Action: End-to-End Semantic Graph Generation for Semantic Parsing (2018, background): “Transition-based approaches are important in both dependency parsing (Nivre, 2008; Henderson et al., 2013) and AMR parsing (Wang et al.”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, background): “Transition-based dependency parsers scan an input sentence from left to right, performing a sequence of transition actions to predict its parse tree (Nivre, 2008).”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, methodology): “Transition-based dependency parsing algorithms that perform greedy local inference have proven to be very successful at fast and accurate discriminative parsing (Nivre, 2008; Zhang and Nivre, 2011; Chen and Manning, 2014).”
Practical Semantic Parsing for Spoken Language Understanding (2019, methodology): “Transition-based parsers are widely used for dependency parsing (Nivre, 2008; Dyer et al., 2015) and they have been also applied to semantic parsing tasks (Wang et al.”
Improving Arabic Dependency Parsing with Lexical and Inflectional Morphological Features (2010, methodology): “Besides the work we describe in §3, Nivre (2008) reports experiments on Arabic parsing using his MaltParser (Nivre et al., 2007), trained on the PADT.”
Neural Network Methods for Natural Language Processing (2017, methodology): “, 2011], and exploration-training with dynamic oracles [Goldberg and Nivre, 2013]. Application of these techniques in the context of RNN generators is proposed by Bengio et al. [2015] under the term scheduled sampling. e second problem can be treated by discarding of the locally normalized objectiv”