Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time

Calculating the Optimal Step in Shift-Reduce Dependency Parsing: From Cubic to Linear Time Mark-Jan Nederhof School of Computer Science University of St Andrews, UK markjan.nederhof@googlemail.com Abstract We present a new cubic-time algorithm to calculate the optimal next step in shift-reduce dependency parsing, relative to ground truth, commonly referred to as dynamic oracle. Un- like existing algorithms, it is applicable if the training corpus contains non-projective struc- tures. We then show that for a projective training corpus, the time complexity can be improved from cubic to linear. 1 Introduction A deterministic parser may rely on a classifier that predicts the next step, given features extracted from the present configuration (Yamada and Matsumoto, 2003; Nivre et al., 2004). It was found that accuracy improves if the classifier is trained not just on configurations that correspond to the ground-truth, or ‘‘gold’’, tree, but also on configurations that a parser would typically reach when a classifier strays from the optimal predictions. This is known as a dynamic oracle.1 The effective calculation of the optimal step for somekindsofparsingrelieson‘arc-decomposibility’, as in the case of Goldberg and Nivre (2012, 2013). This generally requires a projective training cor- pus; an attempt to extend this to non-projective training corpora had to resort to an approxima- tion (Aufrant et al., 2018). It is known how to calculate the optimal step for a number of non- 1A term we avoid here, as dynamic oracles are neither oracles nor dynamic, especially in our formulation, which allows gold trees to be non-projective. Following, for example, Kay (2000), an oracle informs a parser whether a step may lead to the correct parse. If the gold tree is non-projective and the parsing strategy only allows projective trees, then there are no steps that lead to the correct parse. At best, there is an optimal step, by some definition of optimality. An algorithm to compute the optimal step, for a given configuration, would typically not change over time, and therefore is not dynamic in any generally accepted sense of the word. projective parsing algorithms, however (G´omez- Rodr´ıguez et al., 2014; G´omez-Rodr´ıguez and Fern´andez-Gonz´alez, 2015; Fern´andez-Gonz´alez G´omez-Rodr´ıguez, 2018a); see also de Lhoneux et al. (2017). Ordinary shift-reduce dependency parsing is known at least since Fraser (1989); see also Nasr (1995). Nivre (2008) calls it ‘‘arc-standard parsing.’’ For shift-reduce dependency parsing, calculation of the optimal step is regarded to be difficult. The best known algorithm is cubic and is only applicable if the training corpus is projective (Goldberg et al., 2014). We present a new cubic-time algorithm that is also applicable to non-projective training corpora. Moreover, its architecture is modular, expressible as a generic tabular algorithm for dependency parsing plus a context-free grammar that expresses the allow- able transitions of the parsing strategy. This dif- fers from approaches that require specialized tabular algorithms for different kinds of parsing (G´omez-Rodr´ıguez et al., 2008; Huang and Sagae, 2010; Kuhlmann et al., 2011). The generic tabular algorithm is interesting in its own right, and can be used to determine the opti- …

Content truncated to 500 words