Inherent Dependency Displacement Bias of Transition-Based Algorithms

Proceedings of the 12th Conference on Language Resources and Evaluation (LREC 2020), pages 5147–5155 Marseille, 11–16 May 2020 c⃝ European Language Resources Association (ELRA), licensed under CC-BY-NC 5147 Inherent Dependency Displacement Bias of Transition-Based Algorithms Mark Anderson Carlos G´omez-Rodr´ıguez Universidade da Coru˜na, CITIC FASTPARSE Lab, LyS Research Group, Departamento de Computaci´on y Tecnolog´ıas de la Informaci´on Campus Elvi˜na, s/n, 15071 A Coru˜na, Spain {m.anderson,carlos.gomez}@udc.es Abstract A wide variety of transition-based algorithms are currently used for dependency parsers. Empirical studies have shown that performance varies across different treebanks in such a way that one algorithm outperforms another on one treebank and the reverse is true for a different treebank. There is often no discernible reason for what causes one algorithm to be more suitable for a certain treebank and less so for another. In this paper we shed some light on this by introducing the concept of an algorithm’s inherent dependency displacement distribution. This characterises the bias of the algorithm in terms of dependency displacement, which quantify both distance and direction of syntactic relations. We show that the similarity of an algorithm’s inherent distribution to a treebank’s displacement distribution is clearly correlated to the algorithm’s parsing performance on that treebank, specificially with highly significant and substantial correlations for the predominant sentence lengths in Universal Dependency treebanks. We also obtain results which show a more discrete analysis of dependency displacement does not result in any meaningful correlations. Keywords: dependency parsing, transition-based algorithms, dependency displacement 1. Introduction Dependency parsing, and in particular the transition-based family of parsers, has a large variety of parsing algorithms to choose from. When comparing different algorithms, em- pirical results on collections of corpora often show differ- ences in accuracy that can heavily vary across different lan- guages or treebanks, so that a given algorithm can be the best choice for one corpus while being outperformed in an- other. However, despite these nontrivial patterns in accuracy vari- ations having been observed in many experiments in the last decade, both with non-neural and neural implementa- tions (Nivre, 2008; Ballesteros and Nivre, 2013; Chen and Manning, 2014; Fern´andez-Gonz´alez et al., 2016), very lit- tle is known about what makes an algorithm more fitting for a corpus beyond obvious facts (like non-projective al- gorithms being better for highly non-projective treebanks). This makes the practical choice of a particular algorithm for a language a matter of trial and error. For example, Malt- Optimizer chooses between projective and non-projective algorithm according to the amount of non-projective depen- dencies observed in the treebank, but then the choice of a specific algorithm among projective (or non-projective) op- tions is made by running all of the projective (or the non- projective) algorithms and choosing the one that achieves the highest accuracy (Ballesteros and Nivre, 2012). Contribution We shed some light on this issue by per- forming two complementary analyses: 1. An analysis of the performance of transition-based algorithms with respect to dependency displacement (signed distance) which highlights that a shallow level of analysis is not sufficient to …

Content truncated to 500 words