Incrementality in Deterministic Dependency Parsing

By Joakim Nivre. 2004

319 citations recorded by the source corpus.

Deterministic dependency parsing is a robust and efficient approach to syntactic parsing of unrestricted natural language text. In this paper, we analyze its potential for incremental processing and conclude that strict incrementality is not achievable within this framework. However, we also show that it is possible to minimize the number of structures that require non-incremental processing by choosing an optimal parsing algorithm. This claim is substantiated with experimental evidence showing that the algorithm achieves incremental parsing for 68.9% of the input when tested on a random sample of Swedish text. When restricted to sentences that are accepted by the parser, the degree of incrementality increases to 87.9%.

Subfields: Artificial Intelligence

View Paper: https://www.semanticscholar.org/paper/032906f0d86fd6bbf7512d3fffd06fcb83593012

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

Citations in the corpus

Broad-Coverage Semantic Parsing as Transduction (2019, background): “, 2019), but they lack parsing incrementality, which is advocated in terms of computational efficiency and cognitive modeling (Nivre, 2004; Huang and Sagae, 2010).”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, methodology): “Zhang and Nivre (2012) find that global learning and beam search should be used jointly for improving parsing using a discrete transition-based model.”
An Efficient Algorithm for Easy-First Non-Directional Dependency Parsing (2010, result): “This is in line with the Arc-Standard parsing strategy of shift-reduce dependency parsers (Nivre, 2004).”
Sequence-to-Dependency Neural Machine Translation (2017, methodology): “The key difference from conventional NMT decoders is that we use two RNNs, one for translation generation and the other for dependency parse tree construction, in which incremental parsing is performed with the arc-standard shift-reduce algorithm proposed by Nivre (2004).”
A General, Abstract Model of Incremental Dialogue Processing (2009, background): “Following Nivre (2004), we can call this strict incrementality . f:in ≥ out describes modules that potentially collect a certain amount of LB-IUs before producing an RB-IU based on them.”
Learning syntactic structure (2007, background): “An incremental dependency parser is often defined as a dependency parser which assigns a single connected structure to every prefix of an utterance (Nivre 2004).”
Structured Training for Neural Network Transition-Based Parsing (2015, methodology): “Since many of the baselines could not be directly compared to our semi-supervised approach, we re-implemented Zhang and Nivre (2011) and trained on the tri-training corpus.”
Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations (2016, methodology): “Transition-based parsers (Nivre, 2004; Nivre, 2008) treat parsing as a sequence of actions that produce a parse tree, and a classiﬁer is trained to score the possible actions at each stage of the process and guide the parsing process.”
Scene Graph Parsing as Dependency Parsing (2018, background): “This action is often used in other transition-based dependency parsing systems (e.g. arc-eager (Nivre, 2004)).”
MaltParser: A Data-Driven Parser-Generator for Dependency Parsing (2006, unknown): “It can be run inarc-eageror arc-standardmode (Nivre, 2004).”
Transition-Based Dependency Parsing with Stack Long Short-Term Memory (2015, methodology): “Our parser is based on the arc-standard transition inventory (Nivre, 2004), given in Figure 3.”
Training Deterministic Parsers with Non-Deterministic Oracles (2013, background): “We also show that the popular arc-standard system (Nivre, 2004) is not arc-decomposable, and so deriving a dynamic oracle for it remains an open research question.”
Improved Transition-based Parsing by Modeling Characters instead of Words with LSTMs (2015, methodology): “In particular, the parser implements the arc-standard parsing algorithm (Nivre, 2004).”
A Survey of the Usages of Deep Learning for Natural Language Processing (2020, background): “In the arc-standard approach [91], [92], all dependents are connected to a word before the word is connected to its parent.”
Stack-propagation: Improved Representation Learning for Syntax (2016, methodology): ““Symbols” indicates whether the word contains a hyphen, a digit or a punctuation. standard parser configuration1 c consisting of the stack s, the buffer b and the so far constructed dependencies (Nivre, 2004).”
Neural Architectures for Named Entity Recognition (2016, methodology): “We designed a transition inventory which is given in Figure 2 that is inspired by transition-based parsers, in particular the arc-standard parser of Nivre (2004). In this algorithm, we make use of two stacks (designated output and stack representing, respectively, completed chunks and scratch space)”
Consequences of the Now-or-Never bottleneck for signed versus spoken languages (2015, background): “These systems can build analyses even under severe working memory constraints: although the issue of “stacking up” with right-branching languages mentioned by C&C exists for so-called arc-standard parsers (Nivre, 2004), parsers based on the arc-eager model (e.”
Practical Semantic Parsing for Spoken Language Understanding (2019, background): “The example we describe here is that of arc-standard system (Nivre, 2004) for projective dependency parsing.”