On Finding the K-best Non-projective Dependency Trees (2021)

Abstract: The connection between the maximum spanning tree in a directed graph and the best dependency tree of a sentence has been exploited by the NLP community. However, for many dependency parsing schemes, an important detail of this approach is that the spanning tree must have exactly one edge emanating from the root. While work has been done to efficiently solve this problem for finding the one-best dependency tree, no research has attempted to extend this solution to finding the K-best dependency trees. This is arguably a more important extension as a larger proportion of decoded trees will not be subject to the root constraint of dependency trees. Indeed, we show that the rate of root constraint violations 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.

## 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 formalismsoften 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 @xcite our implementation is available at https://github. com/rycolab/spanningtrees . 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. 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. @xcite we make a few changes to camerini et al. (1980)'s algorithm, which result in both a simpler algorithm and simpler proof of correctness. @xcite firstly, both algorithms follow the key property that we can find the second-best tree of a graph by removing a single edge from the graph (theorem 1); this property is used iteratively to enumerate the k-best trees in order. our approach to finding the second-best tree (see §3) is faster because of it performs half as many of the expensive cycle-contraction operations (see §2). overall, this change is responsible for our 1.39x speed-up (see §4). secondly, their proof of correctness is based on reasoning about a complicated ordering on the edges in the k th tree (camerini et al., 1980, section 4); our proof side-steps the complicated ordering by directly reasoning over the ancestry relations of the k th tree. consequently, our proofs of correctness are considerably simpler and shorter. throughout the paper, we provide the statements of all lemmas and theorems in the main text, but defer all proofs to the appendix. in addition to simplifying camerini et al. (1980)'s algorithm, we offer a novel extension. for many dependency parsing schemes such as the universal dependency (ud) scheme (nivre et al., 2018), there is a restriction on dependency trees to only have one edge emanate from the root. @xcite finding the maximally weighted spanning tree that obeys this constraint was considered by gabow and tarjan (1984) who extended the o(n 2 ) maximum spanning tree algorithm of tarjan (1977); camerini et al. (1979). however, no algorithm exists for kbest decoding of dependency trees subject to a root constraint. as such, we provide the first k-best algorithm that returns dependency trees that obey the root constraint. to motivate the practical necessity of our extension, consider fig. 1 . fig. 1 shows the percentage of trees that violate the root constraint when doing one-best and 50-best decoding for 63 languages from the ud treebank (nivre et al., 2018) using the pre-trained model of qi et al. (2020). @xcite we find that decoding without the root constraint has a much more extreme effect when decoding the 50-best than the one-best. specifically, we observe that on average, the number of violations of the root constraint increased by 13 times, with the worst increase being 44 times. the results thus suggest that finding k-best trees that obey the root constraint from a non-projective dependency parser requires a specialist algorithm. we provide a more detailed results table in app. a, including root constraint violation rates for @xmath0, @xmath1, and @xmath2. furthermore, we note that the k-best algorithm may also be used for marginalization of latent variables (correia et al., 2020) and for constructing parsers with global scoring functions (lee et al., 2016). @xcite there are certain exceptions to this such as the prague treebank (bejček et al., 2013). @xcite zmigrod et al. (2020) conduct a similar experiment for only the one-best tree. @xcite we note that qi et al. (2020) do apply the root constraint for one-best decoding, albeit with a sub-optimal algorithm. 2020 ). edges that are part of both the best tree g @xcite and the best dependency tree g @xcite are marked as thick solid edges. edges only in g @xcite are dashed and edges only in g @xcite are dotted. ## finding the best tree we consider the study of rooted directed weighted graphs, which we will abbreviate to simply graphs. @xcite a graph is given by @xmath3, n , e) where n is a set of n + 1 nodes with a designated root node ρ ∈ n and e is a set of directed weighted edges. each edge @xmath4. we assume that self-loops are not allowed in the graph (i.e., (i a i) ∈ e). additionally, we assume our graph is not a multi-graph, therefore, there can exist at most one edge from node i to node j. @xcite when it is clear from context, we abuse notation and use @xmath5. when discussing runtimes, we will assume a fully connected graph (|e| = n 2 ). @xcite an arborescence (henceforth called a tree) of g is a subgraph @xmath6, n , e ) such that e ⊆ e and the following is true: ## finding the second best tree in the following two sections, we provide a simplified reformulation of camerini et al. (1980) to find the k-best trees. the simplifications additionally provide a constant time speed-up over camerini et al. (1980)'s algorithm. we discuss the differences throughout our exposition. the underlying concept behind finding the kbest tree, is that g (k) is the second best tree g @xcite of some subgraph g ⊆ g. in order to explore the space of subgraphs, we introduce the concept of edge inclusion and exclusion graphs. definition 1 (edge inclusion and exclusion). for any graph g and edge @xmath7, the edge-inclusion graph g + e ⊂ g is the graph such that for any @xmath8, @xmath9. similarly, the edgeexclusion graph g -e ⊂ g is the graph such that for any @xmath10, @xmath11. when we discuss finding the k-best dependency trees in §5, we implicitly change the above definition to use d(g + e) and d(g -e) instead of a(g + e) and a(g -e) respectively. in this section, we will specifically focus on finding g @xcite , we extend this to finding the g (k) in §4. finding g @xcite relies on the following fundamental theorem. theorem 1 states that we can find g @xcite by identifying an edge @xmath12. we next show an efficient method for identifying this edge, as well as the weight of g @xcite without actually having to find g @xcite . definition 2 (blue and red edges). for any graph g, tree @xmath13, and edge @xmath14, the set of blue edges b(g, e, d) and red edges r(g, e, d) are defined by 12 b(g, e, d) an example of blue and red edges are given in fig. 4 . ## finding the k th best tree in the previous section, we found an efficient method for finding g @xcite . we now utilize this method to efficiently find the k-best trees. lemma 3. for any graph g and @xmath15, there exists a subgraph g ⊆ g and @xcite and @xcite . lemma 3 suggests that we can find the k-best trees by only examining the second best trees of subgraphs of g. this idea is formalized as algorithm kbest in fig. 7 . a walk-through of the exploration space using kbest for our example graph in fig. 2 is shown in fig. 6 . theorem 3. for any graph g and @xmath16, at any iteration 1 ≤ @xmath17, kbest(g, k) returns g @xcite . ## finding the k th best dependency tree in this section, we present a novel extension to the algorithm presented thus far, that allows us to efficiently find the k-best dependency trees. recall that we consider dependency trees to be spanning trees with a root constraint such that only one edge may emanate from ρ. naïvely, we can use kbest where we initialize the queue with (g + e ρ ) @xcite for each e ρ = (ρ a j) ∈ g. however, this adds a o(n 3 ) component to our runtime as we have to call opt n times. instead, our algorithm maintains the o(kn 2 ) runtime as the regular k-best algorithm. we begin by noting that we can find second best dependency tree, by finding either the best dependency tree with a different root edge or the second best tree with the same root edge. lemma 4. for any graph g and edge e ρ = (ρ a j) ∈ g @xcite , g @@xmath18. lemma 5. for any graph g and @xmath19, if @xmath20, then either e is not in any of the k-1-best trees or there exists a subgraph g ⊆ g and 1 ≤ @xmath21, @xmath22. lemma 5 suggests that we can find the k-best dependency trees, by examining the second best dependency trees of subgraphs of g or finding the best dependency tree with a unique root edge. this figure 9 : k-best dependency tree enumeration algorithm. theorem 4. for any graph g and @xmath23, at iteration 1 ≤ @xmath24, kbest dep(g, k) returns g @xcite . runtime analysis. at the start of the algorithm, we call opt twice and next once. then, at each iteration we either make two calls two next, or two calls to opt and one call to next. as both algorithms have a runtime of o(n 2 ), each iteration has a runtime of o(n 2 ). therefore, running k iterations gives a runtime of o(kn 2 ). ## conclusion in this paper, we provided a simplification to camerini et al. (1980)'s o(kn 2 ) k-best spanning trees algorithm. furthermore, we provided a novel extension to the algorithm that decodes the k-best dependency trees in o(kn 2 ). we motivated the need for this new algorithm as using regular k-best decoding yields up to 36% trees which violation the root constraint. this is a substantial (up to 44 times) increase in the violation rate from decoding the one-best tree, and thus such an algorithm is even more important than in the one-best case. we hope that this paper encourages future research in k-best dependency parsing.