Calculating the optimal step of arc-eager parsing for non-projective trees

Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics, pages 2273–2283 April 19 - 23, 2021. ©2021 Association for Computational Linguistics 2273 Calculating the optimal step of arc-eager parsing for non-projective trees Mark-Jan Nederhof School of Computer Science University of St Andrews, UK markjan.nederhof@googlemail.com Abstract It is shown that the optimal next step of an arc- eager parser relative to a non-projective depen- dency structure can be calculated in cubic time, solving an open problem in parsing theory. Ap- plications are in training of parsers by means of a ‘dynamic oracle’. 1 Introduction A deterministic transition-based dependency parser is often driven by a classifier that determines the next step, given features extracted from the cur- rent configuration (Nivre et al., 2004). The clas- sifier may be trained on parser configurations and steps that exactly correspond to ‘gold’ trees from a treebank. However, better accuracy is generally obtained by also including configurations reached by letting the parser stray from the gold trees, to let the classifier learn how best to recover from any mistakes. This is associated with the term dy- namic oracle. If the parser is projective while the gold trees are non-projective moreover, then it is unavoidable that configurations be considered that do not correspond to the gold trees. Determining the desired output of the classifier requires calculation of the best next step given an arbitrary configuration and a gold tree. Typically, this is the step that allows the most accurate tree to be reached, in terms of the gold tree.1 For a gold tree that is projective, the optimal step can be determined in linear time for arc-eager parsing (Goldberg and Nivre, 2012, 2013) and for shift-reduce parsing (Nederhof, 2019). For a non- projective gold tree, the optimal step can be deter- mined for several types of non-projective parsers (G´omez-Rodr´ıguez et al., 2014; G´omez-Rodr´ıguez and Fern´andez-Gonz´alez, 2015; de Lhoneux et al., 1There are alternative perspectives on how to determine the best next step; cf. Straka et al. (2015). 2017; Fern´andez-Gonz´alez and G´omez-Rodr´ıguez, 2018), as well as for shift-reduce parsing (Neder- hof, 2019). However, for arc-eager parsing, the problem has been unsolved until now. Aufrant et al. (2018) propose an approximation of the optimal step, based on the procedure for projective gold trees, and demonstrate the advantages of training a projective parser directly on non-projective trees. The current paper introduces an exact calculation of the optimal step for arc-eager parsing and a non- projective gold tree, within the same framework as Nederhof (2019), which consists of a generic cubic-time tabular dependency parsing algorithm and a fixed context-free grammar that is applied on a string extracted from the current configuration, with edge weights determined by the gold tree. For arc-eager parsing, the context-free grammar is considerably more complex than in the case of shift-reduce parsing. This is a consequence of the- oretical properties of arc-eager parsing, which we first need to investigate in detail before we can define ‘optimality’ of the next step. 2 …

Content truncated to 500 words