On Finding the K-best Non-projective Dependency Trees

Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing, pages 1324–1337 August 1–6, 2021. ©2021 Association for Computational Linguistics 1324 On Finding the K-best Non-projective Dependency Trees Ran Zmigrod Tim Vieira Ryan Cotterell , University of Cambridge Johns Hopkins University ETH Z¨urich rz279@cam.ac.uk tim.f.vieira@gmail.com ryan.cotterell@inf.ethz.ch Abstract The connection between the maximum span- ning tree in a directed graph and the best de- pendency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important de- tail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to ef- ficiently solve this problem for finding the one-best dependency tree, no research has at- tempted to extend this solution to finding the K-best dependency trees. This is arguably a more important extension as a larger propor- tion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint viola- tions increases by an average of 13 times when decoding with K =50 as opposed to K =1. In this paper, we provide a simplification of the K-best spanning tree algorithm of Camerini et al. (1980). Our simplification allows us to obtain a constant time speed-up over the original algorithm. Furthermore, we present a novel extension of the algorithm for decoding the K-best dependency trees of a graph which are subject to a root constraint.1 1 Introduction Non-projective, graph-based dependency parsers are widespread in the NLP literature. (McDonald et al., 2005; Dozat and Manning, 2017; Qi et al., 2020). However, despite the prevalence of K-best dependency parsing for other parsing formalisms— often in the context of re-ranking (Collins and Koo, 2005; Sangati et al., 2009; Zhu et al., 2015; Do and Rehbein, 2020) and other areas of NLP (Shen et al., 2004; Huang and Chiang, 2005; Pauls and Klein, 2009; Zhang et al., 2009), we have only found three works that consider K-best non-projective 1Our implementation is available at https://github. com/rycolab/spanningtrees. 102 103 104 Training set size (log-scale) 0 5 10 15 20 25 30 35 Root constraint violation rate (%) K = 50 K = 1 Figure 1: Violation rate of the root constraint when using regular K-best decoding (Camerini et al., 1980) on pre-trained models of Qi et al. (2020) for languages with varying training set sizes. dependency parsing (Hall, 2007; Hall et al., 2007; Agi´c, 2012). All three papers utilize the K-best spanning tree algorithm of Camerini et al. (1980). Despite the general utility of K-best methods in NLP, we suspect that the relative lack of interest in K-best non-projective dependency parsing is due to the implementation complexity and nuances of Camerini et al. (1980)’s algorithm.2 We make a few changes to Camerini et al. (1980)’s algorithm, which result in both a sim- pler algorithm and simpler proof of correctness.3 Firstly, both algorithms follow the …

Content truncated to 500 words