Training Deterministic Parsers with Non-Deterministic Oracles

By Yoav Goldberg, Joakim Nivre. 2013

134 citations recorded by the source corpus.

Greedy transition-based parsers are very fast but tend to suffer from error propagation. This problem is aggravated by the fact that they are normally trained using oracles that are deterministic and incomplete in the sense that they assume a unique canonical path through the transition system and are only valid as long as the parser does not stray from this path. In this paper, we give a general characterization of oracles that are nondeterministic and complete, present a method for deriving such oracles for transition systems that satisfy a property we call arc decomposition, and instantiate this method for three well-known transition systems from the literature. We say that these oracles are dynamic, because they allow us to dynamically explore alternative and nonoptimal paths during training — in contrast to oracles that statically assume a unique optimal path. Experimental evaluation on a wide range of data sets clearly shows that using dynamic oracles to train greedy parsers gives substantial improvements in accuracy. Moreover, this improvement comes at no cost in terms of efficiency, unlike other techniques like beam search.

Subfields: Artificial Intelligence, Molecular Biology, Information Extraction

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

In Information Extraction

Citations in the corpus

Globally Normalized Transition-Based Neural Networks (2016, background): “Goldberg and Nivre (2013) describe improvements to a greedy parsing approach that makes use of methods from imitation learning (Ross et al., 2011) to augment the training set.”
Dependency-Based Word Embeddings (2014, background): “in parsing technology (Goldberg and Nivre, 2012; Goldberg and Nivre, 2013) that allow parsing to syntactic dependencies with very high speed and near state-of-the-art accuracy.”
Simple and Accurate Dependency Parsing Using Bidirectional LSTM Feature Representations (2016, methodology): “We perform error-exploration training using the dynamic-oracle deﬁned in (Goldberg and Nivre, 2013).”
Learning to Search Better than Your Teacher (2015, positive): “In general, ﬁnding the optimal action at states not in the optimal trajectory can be tricky (e.g., (Goldberg & Nivre, 2013; Goldberg et al., 2014)).”
A Primer on Neural Network Models for Natural Language Processing (2015, background): “The main intuition behind the recursive neural networks is that each subtree is represented as a d dimensional vector, and the representation of a node p with children c1 and c2 is a function of the representation of the nodes: vec(p) = f(vec(c1), vec(c2)), where f is a composition function taking…”
Improved Transition-based Parsing by Modeling Characters instead of Words with LSTMs (2015, methodology): “We include greedy transition-based parsers that, like ours, do not apply a beam search (Zhang and Clark, 2008b) or a dynamic oracle (Goldberg and Nivre, 2013).”
Easy-First Dependency Parsing with Hierarchical Tree LSTMs (2016, methodology): “This is consistent with previous work on training with error-exploration and dynamic oracles (Goldberg and Nivre, 2013b), showing that the technique is not restricted to models trained with sparse linear models.”
Joint Syntacto-Discourse Parsing and the Syntacto-Discourse Treebank (2017, methodology): “We use the “training with exploration” strategy (Goldberg and Nivre, 2013) and the dynamic oracle mechanism described in Cross and Huang (2016) to make sure the model can handle unseen parsing conﬁgurations properly.”
Imitation learning for language generation from unaligned data (2016, background): “Imitation learning algorithms for structured prediction have been applied successfully to a variety of tasks, such as dependency parsing (Goldberg and Nivre, 2013) and dynamic feature selection (He et al., 2013).”
Show, Control and Tell: A Framework for Generating Controllable and Grounded Captions (2018, background): “Analyzing further the syntactic dependencies between words, we can recover a higher abstraction level in which words can be organized into a tree-like structure: in a dependency tree [12, 14, 6], each word is linked together with its modiﬁers (Fig.”
A Neural Probabilistic Structured-Prediction Method for Transition-Based Natural Language Processing (2017, background): “Zhang & Nivre, 2011; Goldberg & Nivre, 2013) and constituent parsing (Zhang & Clark, 2011b; Zhu, Zhang, Chen, Zhang, & Zhu, 2013; Zhang, Zhang, Che, & Liu, 2013), for which features play a important role, the transition-based method gives highly competitive accuracies and efficiencies.”
A Bayesian Model for Generative Transition-based Dependency Parsing (2015, background): “In contrast to dynamic oracles (Goldberg and Nivre, 2013), we are only interested in derivations of the correct parse tree, so the oracle can assume that given c there exists a derivation for G.”
A Minimal Span-Based Neural Constituency Parser (2017, background): “the recurrent representation of spans (Kiperwasser and Goldberg, 2016), and the use of a dynamic oracle and exploration policy during training (Goldberg and Nivre, 2013)) and extends these insights to span-oriented models, which support a wider range of decoding procedures.”