A Tabular Method for Dynamic Oracles in Transition-Based Parsing

A Tabular Method for Dynamic Oracles in Transition-Based Parsing Yoav Goldberg Department of Computer Science Bar Ilan University, Israel yoav.goldberg@gmail.com Francesco Sartorio Department of Information Engineering University of Padua, Italy sartorio@dei.unipd.it Giorgio Satta Department of Information Engineering University of Padua, Italy satta@dei.unipd.it Abstract We develop parsing oracles for two trans- ition-based dependency parsers, including the arc-standard parser, solving a problem that was left open in (Goldberg and Nivre, 2013). We experimentally show that using these or- acles during training yields superior parsing accuracies on many languages. 1 Introduction Greedy transition-based dependency parsers (Nivre, 2008) incrementally process an input sentence from left to right. These parsers are very fast and provide competitive parsing accuracies (Nivre et al., 2007). However, greedy transition-based parsers still fall behind search-based parsers (Zhang and Clark, 2008; Huang and Sagae, 2010) with respect to accuracy. The training of transition-based parsers relies on a component called the parsing oracle, which maps parser configurations to optimal transitions with re- spect to a gold tree. A discriminative model is then trained to simulate the oracle’s behavior. A parsing oracle is deterministic if it returns a single canon- ical transition. Furthermore, an oracle is partial if it is defined only for configurations that can reach the gold tree, that is, configurations representing pars- ing histories with no mistake. Oracles that are both deterministic and partial are called static. Tradition- ally, only static oracles have been exploited in train- ing of transition-based parsers. Recently, Goldberg and Nivre (2012; 2013) showed that the accuracy of greedy parsers can be substantially improved without affecting their pars- ing speed. This improvement relies on the intro- duction of novel oracles that are nondeterministic and complete. An oracle is nondeterministic if it re- turns the set of all transitions that are optimal with respect to the gold tree, and it is complete if it is well-defined and correct for every configuration that is reachable by the parser. Oracles that are both non- deterministic and complete are called dynamic. Goldberg and Nivre (2013) develop dynamic or- acles for several transition-based parsers. The con- struction of these oracles is based on a property of transition-based parsers that they call arc decompos- ition. They also prove that the popular arc-standard system (Nivre, 2004) is not arc-decomposable, and they leave as an open research question the construc- tion of a dynamic oracle for the arc-standard system. In this article, we develop one such oracle (§4) and prove its correctness (§5). An extension to the arc-standard parser was presented by Sartorio et al. (2013), which relaxes the bottom-up construction order and allows mixing of bottom-up and top-down strategies. This parser, called here the LR-spine parser, achieves state-of- the-art results for greedy parsing. Like the arc-stand- ard system, the LR-spine parser is not arc-decom- posable, and a dynamic oracle for this system was not known. We extend our oracle for the arc-stand- ard system to work for the LR-spine system as well (§6). The dynamic oracles developed by Goldberg and Nivre (2013) for …

Content truncated to 500 words