Training Deterministic Parsers with Non-Deterministic Oracles

Training Deterministic Parsers with Non-Deterministic Oracles Yoav Goldberg Bar-Ilan University Department of Computer Science Ramat-Gan, Israel yoav.goldberg@gmail.com Joakim Nivre Uppsala University Department of Linguistics and Philology Uppsala, Sweden joakim.nivre@lingfil.uu.se Abstract 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 deter- ministic 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 com- plete, present a method for deriving such ora- cles for transition systems that satisfy a prop- erty we call arc decomposition, and instanti- ate this method for three well-known transi- tion systems from the literature. We say that these oracles are dynamic, because they allow us to dynamically explore alternative and non- optimal 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 substan- tial improvements in accuracy. Moreover, this improvement comes at no cost in terms of efficiency, unlike other techniques like beam search. 1 Introduction Greedy transition-based parsers are easy to imple- ment and are very efficient, but they are generally not as accurate as parsers that are based on global search (McDonald et al., 2005; Koo and Collins, 2010) or as transition-based parsers that use beam search (Zhang and Clark, 2008) or dynamic pro- gramming (Huang and Sagae, 2010; Kuhlmann et al., 2011). This work is part of a line of research trying to push the boundaries of greedy parsing and narrow the accuracy gap of 2–3% between search- based and greedy parsers, while maintaining the ef- ficiency and incremental nature of greedy parsers. One reason for the lower accuracy of greedy parsers is error propagation: once the parser makes an error in decoding, more errors are likely to fol- low. This behavior is closely related to the way in which greedy parsers are normally trained. Given a treebank oracle, a gold sequence of transitions is derived, and a predictor is trained to predict transi- tions along this gold sequence, without considering any parser state outside this sequence. Thus, once the parser strays from the golden path at test time, it ventures into unknown territory and is forced to react to situations it has never been trained for. In recent work (Goldberg and Nivre, 2012), we introduced the concept of a dynamic oracle, which is non-deterministic and not restricted to a single golden path, but instead provides optimal predic- tions for any possible state the parser might be in. Dynamic oracles are non-deterministic in the sense that they return a set of valid transitions for a given parser state and gold tree. Moreover, they are well- defined and optimal also for states from which the …

Content truncated to 500 words