A Dynamic Oracle for Arc-Eager Dependency Parsing

Proceedings of COLING 2012: Technical Papers, pages 959–976, COLING 2012, Mumbai, December 2012. A Dynamic Oracle for Arc-Eager Dependency Parsing Yoav Goldber g1 Joakim Nivre1,2 (1) Google Inc. (2) Uppsala University yogo@google.com, joakim.nivre@lingfil.uu.se ABSTRACT The standard training regime for transition-based dependency parsers makes use of an oracle, which predicts an optimal transition sequence for a sentence and its gold tree. We present an improved oracle for the arc-eager transition system, which provides a set of optimal transitions for every valid parser configuration, including configurations from which the gold tree is not reachable. In such cases, the oracle provides transitions that will lead to the best reachable tree from the given configuration. The oracle is efficient to implement and provably correct. We use the oracle to train a deterministic left-to-right dependency parser that is less sensitive to error propagation, using an online training procedure that also explores parser configurations resulting from non-optimal sequences of transitions. This new parser outperforms greedy parsers trained using conventional oracles on a range of data sets, with an average improvement of over 1.2 LAS points and up to almost 3 LAS points on some data sets. KEYWORDS: dependency parsing, transition system, oracle. 959 1 Introduction The basic idea in transition-based dependency parsing is to define a nondeterministic transition system for mapping sentences to dependency trees and to perform parsing as search for the optimal transition sequence for a given sentence (Nivre, 2008). A key component in training transition-based parsers is an oracle, which is used to derive optimal transition sequences from gold parse trees. These sequences can then be used as training data for a classifier that approximates the oracle at parsing time in deterministic classifier-based parsing (Yamada and Matsumoto, 2003; Nivre et al., 2004), or it can be used to determine when to perform updates in online training of a beam search parser (Zhang and Clark, 2008). Currently, such oracles work by translating a given tree to a static sequence of parser transitions which, if run in sequence, will produce the gold tree. Most transition systems, including the arc-eager and arc-standard systems described in Nivre (2003, 2004), exhibit spurious ambiguity and map several sequences to the same gold tree. In such cases, the oracles implicitly define a canonical derivation order. We call such oracles static, because they produce a single static sequence of transitions that is supposed to be followed in its entirety. Static oracles are usually specified as rules over individual parser configurations – if the configuration has properties X and the gold tree is Y , then the correct transition is Z – giving the impression that they define a function from configurations to transitions. However, these rules are only correct for configurations that are part of the canonical transition sequence defined by the oracle. Thus, static parsing oracles are only correct as functions from gold-trees to transition sequences, and not as functions from configurations to transitions. There are at least two limitations to training parsers using static oracles. First, because of spurious …

Content truncated to 500 words