A Root of a Problem: Optimizing Single-Root Dependency Parsing (2021)

Abstract: We describe two approaches to single-root dependency parsing that yield significant speed ups in such parsing. One approach has been previously used in dependency parsers in practice, but remains undocumented in the parsing literature, and is considered a heuristic. We show that this approach actually finds the optimal dependency tree. The second approach relies on simple reweighting of the inference graph being input to the dependency parser and has an optimal running time. Here, we again show that this approach is fully correct and identifies the highest-scoring parse tree. Our experiments demonstrate a manyfold speed up compared to a previous graph-based state-of-the-art parser without any loss in accuracy or optimality.

## introduction dependency parsing is one of the core steps in many natural language processing pipelines. given its wide and large-scale use, both in academic and commercial settings, even moderate improvements in the speed and accuracy of a dependency parser may significantly impact its utility. in this paper, we show how to improve the speed of graph-based dependency parsers @xcite ) without compromising at all on accuracy. graph-based dependency parsers work in two steps. the first step forms a complete weighted directed graph of words and a special root token by computing the weights using a trained statistical model. 2 the second step then executes the main inference procedure: it identifies a directed spanning tree (often referred to as 1 our code is available at https://github.com/ stanojevic/fast-mst-algorithm . 2 the weights of edges entering root are -∞. while some of the previous work to optimize the speed of graph-based parsers focused on the first step @xcite , we demonstrate in figure 1 that most of the parsing time is actually spent on the spanning tree inference routine. as sentence length increases, the gap between the spanning tree inference time and time spent on constructing the weighted graph increases significantly. 3 mst search is often done using the chu-liu-edmonds (cle) algorithm @xcite that runs in o(n 3 ) where n is the sentence length. @xcite presents a relatively complicated way of implementing the cle algorithm in o(n 2 ). tarjan's algorithm is often cited in nlp literature, but to the best of our knowledge has never been implemented for dependency parsing. this is due to the common algorithm appeared in current implementation worst-case claimed worst-case dense graph average-case dense graph claimed worst-case sparse graph @xcite o(n 2 log n) o(n 2 ) o(n 2 ) o(m log n) naïve mentioned in @xcite and in section 3 n/a o(n 3 ) o(n 3 ) o(mn + n 2 log n) root preselection code of some parsers (undocumented) and thoroughly discussed in section 3 o(n 3 ) o(n 3 ) o(n 2 ) o(mn + n 2 log n) reweighting introduced in section 4 o(n 2 ) o(n 2 ) o(n 2 ) o(m + n log n) we test this claim, and show that significant improvements can be made over cle. the (unconstrained) mst algorithm such as cle produces a tree with one root node, namely the special token root , but that root node may have multiple edges coming out of it. yet, in some widely-used dependency treebanks, such as universal dependencies @xcite , only one edge is permitted to come out of root . we will refer to the task of finding an mst that contain only one outgoing edge out of root as single-root or constrained mst parsing. @xcite provide an implementation of the non-trivial gabow and tarjan algorithm to compute a constrained mst with only one dependency edge coming out of root . while both gabow and @xcite argue that this algorithm could be implemented in o(n 2 ), they do not describe or follow such an implementation. the only existing implementation of this algorithm runs in o(n 2 log n), which is the best worst-case asymptotic running time tested in the literature for single-root dependency parsing. in this paper, we provide two alternative approaches of computing the constrained mst by using an unconstrained mst algorithm as a subroutine. both of these algorithms are very simple to implement and understand. we prove that the first one of them, on average, has the same asymptotic running time as the unconstrained algorithm used as a subroutine. the second algorithm has the same worst-case asymptotic runtime as the unconstrained algorithm which is optimal for complete graphs. worst-case complexity does not guarantee that an algorithm will be fast in practice @xcite : the actual speed might be influenced by constant factors, memory access patterns and the difficulty of the typical input instances @xcite . this is why we test all our algorithms in a typical settings encountered in dependency parsing. additionally, we propose a simple heuristic that recognizes if the input instance is "easy" and if so returns the correct solution even before running the full algorithm. as a guide to this paper, the algorithms for single-root dependency parsing, both previously published ones and the ones presented in this paper, are shown in ## the gabow-tarjan algorithm gabow and @xcite present an algorithm that solves a much more general combinatorial optimization problem than single-root mst parsing. concretely, they abstract a family of optimization problems as an optimization of a minimum weight base of a matroid. we will not describe here the full theory and workings of this algorithm but just present a few important points as related to the aspect of mst parsing. for a good introduction to the use of matroids for combinatorial optimization see @xcite . many combinatorial optimization problems can be framed as a search for the minimum weight base of a matroid, a structure that consists of a set of "independent subsets" of a ground set, generalizing the notion of linear independence in vector spaces. let us consider a minimum spanning tree problem over undirected graphs. this can be solved with a graphic matroid. in this matroid, the ground set contains all the edges of the graph, while independent sets contain all forests (sets of edges that do not form a cycle). a base of this matroid is a spanning tree. finding a minimum weight base of graphic matroid is equivalent to finding a minimum spanning tree. 4 gabow and tarjan extend the definition of the problem by introducing a coloring of the elements of matroid's ground set: every element can be marked as green or red. in the case of graphic matroid the coloring would be applied to the edges of the graph. gabow and tarjan described a matroid optimization method that finds a minimum weight base that contains exactly q red elements, given @xmath0. let β i stand for a set of all optimal bases with i red elements. let swap (e, f ) for base b stand for a pair of matroid's ground elements for which it holds that b/{e}∪{f } is also a base and that e is green and f is red. swaps can be ranked from smallest to largest by weight(f ) -weight(e). gabow and tarjan prove the following theorem: theorem 1 (augmentation theorem; gabow and @xcite . suppose b is a base in β i-1 and β @xmath1. if (e, f ) is a smallest swap for b, then b/{e} ∪ {f } ∈ β i . the augmentation theorem specifies the general approach of the gabow and tarjan algorithm: start by finding the optimal base for the smallest possible number of red elements (this number is matroid/task dependent) and then increase the number of red elements by incrementally finding the smallest swap that introduces more red elements. stop when we have the desired number of red elements in the base. while this general algorithm applies to undirected spanning trees (they form a matroid), it does not straightforwardly apply to directed spanning trees because they do not form a matroid. to accommodate for this gabow and tarjan extend their definition of a swap so that, instead of one, multiple swaps lead from one optimal base to another of a lower order. so how does this relate to single-root dependency parsing? if we color all edges red, except for those that are connected to the artificial root node which will be colored green, we can look for a directed mst with only one green edge (or equivalently with n -1 red edges). this is a special case of the general gabow and @xcite algorithm. an adaptation of that algorithm to dependency parsing was presented by @xcite . while it is stated by both gabow and @xcite and @xcite that this algorithm can be implemented in o(n 2 ) for dense graphs by using data structures from @xcite , it is not trivial to see how to do that. indeed, to the best of our knowledge, the only implementation of this algorithm for dependency parsing runs in o(n 2 log n). even implementing the original unconstrained @xcite algorithm is non-trivial, and its presentations with this level of efficiency in the literature historically include errors. the correct efficient o(n 2 ) algorithm is distilled and described in our appendix a, and in our experiments we contrast its implementation against the less efficient ones. ## the root preselection algorithm there is a simple meta-algorithm algorithm for single-root (constrained) dependency parsing, when given access to an unconstrained solver as a subroutine. imagine we want to find the best single-root dependency tree that contains an arc from root to a single particular word in the sentence. we can accomplish this by disconnecting all other words from the root and running the unconstrained mst parser (equivalently, give the relevant edges weight of -∞). now, we can repeat this process for all the words and compare the weights of the singleroot dependency trees that are found for each word. the best tree in this comparison will be globally best single-root dependency tree. if the runtime complexity of the underlying unconstrained mst parser is o(t (n)) for a sentence of length n, the asymptotic runtime of this meta-algorithm is o(nt (n)). we refer to this algorithm as naïve algorithm. in practice, a simple heuristic is applied in several dependency parsers on top of naïve algorithm (parser-v3, stanza, supar). the adapted algorithm with the heuristic first runs the usual unconstrained mst parsing. if the tree that is found contains only one word connected to the root, the algorithm returns it as the answer. otherwise, the parser applies the naïve algorithm but only over the words connected to the root in the unconstrained parse. since this adapted algorithm preselects the nodes to which to apply the naïve algorithm we refer to it as the root preselection algorithm. we turn to explain that this undocumented heuristic is actually correct, and will always return the best single-rooted tree. we basically describe why the root edge in the constrained case has to be one of the root edges in the unconstrained spanning tree. the reason for this stems from an extension of augmentation theorem for directed graphs by gabow and tarjan. this theorem establishes the connection between the optimal solution of i -1 red elements and an optimal solution of i red elements. it relates them with the optimal swap (in the extended version for directed graphs it is multiple swaps), where each swap removes a green element and replaces it with a red element. what this means in the context of dependency parsing is that an optimal solution with i edges connected to root contains all the edges connected to root from the optimal solution with i -1 edges connected to root . this recurrence implies that the edge to root from the constrained single-root dependency parse is present in the unconstrained case, so it is valid for the algorithm above to concentrate only on finding the optimal edge in the set of root edges provided by the unconstrained algorithm. the runtime of this algorithm depends on the number of words connected to root in the unconstrained mst. if there is only one edge to root in the unconstrained mst, the complexity is o(t (n)). if there is more than one edge from root , the complexity is o((r + 1)t (n)). we can write this complexity for any number r of edges connected to root as o ((r + 1 -i 1 (r)) t (n)) where i 1 (•) is an indicator function that returns 1 if the input is 1, otherwise it returns 0. clearly, the worst case of this algorithm is the same as the worst case of the naïve algorithm because r can be as large as n, but it is interesting to see what is the average computational complexity for this algorithm. to study the average time complexity of preselection algorithm we need to compute expected runtime under some probability distribution of the number of edges connected to root in the unconstrained mst: this average complexity expresses the intuition that if the weights of the graph are more likely to produce unconstrained mst with small number of root edges, the algorithm will be faster. so what can we say about the probability over the number of root edges? in practice there are two extreme cases: graph weights in the initial stages of training and in the final stage after training. we will analyze them both in turn. for the initial stage of training, when the parsing model is only initialized, it is reasonable to assume that the distribution over possible spanning trees is uniform. we can compute the probability of having r root edges by finding the ratio of the number of spanning trees rooted in root that contain r root edges and the total number of spanning trees rooted in root . the total number of spanning trees is given by cayle's formula (n+1) n-1 (cayley, 1889). 5 the number of spanning trees with root edges that go trough particular r nodes can be computed using matrix-tree theorem @xcite . to compute the number of spanning trees with any r root edges we need to correct the number by multiplying with the number of r combinations. this gives us the following distribution over the number of root edges: when we put equation 2 into equation 1, we get that the average case complexity under the uniform distribution of spanning trees is: this expectation is monotonically increasing with n. we can compute the upper bound with: this shows that the preselection algorithm for constrained mst parsing performs, on average, just as well as any unconstrained mst algorithm with only a small constant overhead. this is true under the assumption of uniform distribution over trees. the probability of the number of roots that need to be explored depends only mildly on the number of words: the larger n the larger is the probability of having multiple root edges, but for any n it converges to a small value. the number of having more then r number of edges drops rapidly for any n: p (@xmath2.02, p (@xmath3.004, p (@xmath4.0005. in other words, it is very unlikely that this algorithm will need to explore more than a few of different root edges. what about the distribution of root edges with unconstrained mst after training? for that case we can expect the distribution to be even more peaked over having only few root edges because the training data often has only few root edges (or only one in the case of universal dependencies). to test that we collected 10 sentences for each sentence length from the english portion of news commentary v16 corpus. we ran the english bi-affine model of stanza @xcite and computed the average number of root edges for each sentence length. the plot with these counts is shown in figure 2 as trained weights line. the plot also shows random weights which represents the uniform spanning tree distribution. to simulate this distribution we sample the weight of each edge of the graph from the uniform distribution. it is easy to see that in expectation all spanning trees will have the same weight. zmigrod et al. mention that the distribution of the number of root edges in a trained model depends on the amount of training data. the trained english model in this plot should represent the distribution with the smallest number of root edges since this language has the largest amount of training data. the random weights on this plot should be approximately a lower bound on the number of root edges of a model with small amount of training data. this plot shows that in the weights produced by a trained english model, the number of unconstrained msts with multiple roots is small. this means that the root preselection algorithm will perform even better than in the random weights setting. this plot also confirms that the expected number of root edges for a randomly initialized weights is smaller than 2 for any sentence length. clearly, the variance in the number of roots is much higher in the random weights than in the trained weights. while the preselection algorithm is used in practice by several implementations, to the best of our knowledge, the proof of its correctness and of its average-case complexity analysis that was presented in this section is new. ## the root reweighting algorithm we turn to present a new algorithm for singleroot dependency parsing that is as fast as the best unconstrained dependency parsing algorithm even in the worst case. it is based on a very simple observation that subtracting a constant value c from the weights of all edges coming out of root : by choosing the right constant @xmath5. let us denote by w(•) the function that provides the value of the weight of an edge in the original graph. let n stand for the number of words. in a complete graph we have n + 1 nodes due to the artificial root token. any spanning tree in this graph will have n edges. in the original graph, before the constant is subtracted, we know for certain that the score of any spanning tree is not smaller than n min e w(e) and not bigger than n max e w(e). after constant c is subtracted from all edges coming out of root , all trees with k root edges will have their score decreased by k • c. in this modified graph, any spanning tree with k root edges will have score that is upper bounded by n max e w(e) -kc and lower bound of n min e w(e)-kc. we want the lowest scoring single-root tree to have a higher score than any k-root tree for @xmath6. more formally, we want the following equation to hold: this implies that c should satisfy: a value of c that satisfies this constraint is: so by applying unconstrained mst over a graph with the following weight function we in fact obtain the best single-root solution: there are multiple advantages of this algorithm. first, it is simple to understand and implement. assuming an existing implementation of any unconstrained mst algorithm, this algorithm could be implemented very easily, without incurring further cost to the asymptotic complexity. a full implementation (in python) is described in appendix b.1. it is simpler to implement even in comparison to the root preselection algorithm described in section 3. the second advantage is that we could use any implementation of an unconstrained mst as a subroutine. as mentioned before, there is no precise description nor implementation of gabow and tarjan algorithm that runs in o(n 2 ). the fastest implementation of gabow and tarjan is by zmigrod et al. that runs in o(n 2 log n). the root reweighting algorithm can easily be implemented in o(n 2 ) by just using the unconstrained mst algorithm of @xcite as a subroutine. the third advantage is that, unlike the preselection algorithm, the reweighting algorithm always runs the unconstrained mst algorithm only once per sentence. this means that it will be asymptotically fast for any distribution of spanning trees. finally, in comparison to @xcite , the reweighting algorithm provides for a great flexibility in choosing the underlying unconstrained mst algorithm that is used as a subroutine. in our experiments we use the mst algorithm of tarjan for dense graphs that runs in o(n 2 ). if the graph were sparse, for example, due to pruning of unlikely or forbidden edges, we could use the unconstrained mst algorithm of @xcite as a subroutine which runs in o(m + n log n) where m is the number of edges in the input graph. in addition, if we want to perform single-root projective mst parsing, we could use the algorithm of @xcite as a subroutine. our algorithm also applies to k-best parsing. assuming any existing unconstrained k-best parsing algorithm (such in short, this simple algorithm has all the advantages of the previous single-root algorithms and none of their disadvantages. ## the arcmax trick the reweighting algorithm from section 4 that uses tarjan's algorithm as a subroutine is the best possible algorithm we could hope for in the worst-case with respect to asymptotic complexity. no algorithm can be asymptotically faster than o(n 2 ) for complete graphs. tarjan's algorithm, works in two phases. the first one recursively contracts cycles that result by picking the best edge that enters each node. the second phase then reverses the recursion by expanding each contraction. to do all of this, the algorithm needs to keep track of all the contracted cycles and of modifications to the weights entering the cycles. all of these operations are asymptotically optimal, but they do incur some constant overhead. there are some input instances whose structure is such that we can avoid this overhead and avoid running the full tarjan's algorithm altogether. @xcite show that the neural models are often learned so accurately that just picking the input arc with the highest weight for each word often gives a valid tree. if for each node we just pick the arc with the highest weight and check if these arcs form a tree we could avoid running the whole mst algorithm. we call this trick arcmax trick. in principle it could be applied to any mst algorithm, but it would not give equal benefits to all of them. zhang et al. apply it over the cle algorithm but in that case it is redundant: cle, as its first step, performs the same step as arcmax. zhang et al. do not report any speed improvements. we show that a speedup can be achieved if this trick is used as a procedure before tarjan's algorithm. tarjan's algorithm requires that the graph is strongly connected. in order to achieve this we have to add edges that enter root and set their weight to -∞. this means that tarjan's algorithm will always find cycles to contract even if the problem is simple and could be solved by picking the maximum edges entering each word. to address this, we add the arcmax trick to tarjan's algorithm. checking whether arcmax edges form a nonprojective tree can be done in linear time: do depth-first search from the root node and in the end check if all words are visited. checking for the projective tree can also be done in linear time by constructing a shift-reduce oracle (linear time), running it over the sentence (linear time) and checking whether in the end the only token left on the stack is root (constant time). the code for the checks of projective and non-projective trees is in appendix b.2. for the single-root constraint we need to ex40 60 80 100 sentence length 0 10 20 30 40 50 60 70 time in ms arcmax + gt / zmigrod et al. arcmax + preselection + tarjan arcmax + reweighting + tarjan tend this trick to also verify that the extracted tree has only one edge coming out of root . for the root preselection and reweighting algorithms we have a choice of when to apply the arcmax trick: before the single-root algorithm or inside it just before it calls the unconstrained mst algorithm that is used as a subroutine. for root preselection, in practice, there is no difference in performance. however, for reweighting the choice is crucial. after reweighting is applied, the edges coming out of root will not be the best edges that enter any word, therefore arcmax will never be useful since it will not produce any complete tree. this is why the arcmax trick can be applied to parsing with the reweighting algorithm only if it is used before reweighting is called. ## experiments in this section we experimentally answer some questions about the performance (speed) of different variations of the algorithms we described. we test algorithms in two settings. the first setting has the graph weights from a trained english dependency paring model from the state-of-the-art stanza parser @xcite . the parser is applied to sentences of different length selected from the news commentary v16 corpus. 6 for each length we select exactly ten sentences. the second setting uses graphs with weights sampled from a uniform distribution. this setting should be similar to the initial stages of training of most models. the number of generated random graphs is the same as the number of sentences from the trained setting. we will refer to the first setting as trained weights and to the latter as random weights. we stress that we do not test for accuracy, but for speed. accuracy of all the tested algorithms remains unchanged. which unconstrained algorithm is the fastest? figure 3 shows the plots for two different settings for cle, tarjan and arc-max+tarjan. in the trained setting it is visible that worst-case complexity analysis is in fact not informative about the actual performance of the algorithm. cle outperforms tarjan's algorithm precisely because it can stop the algorithm if the problem is easy, as described in section 5. in the random setting, tarjan's algorithm works better than cle. when we add arcmax trick to tarjan we get an algorithm that works best in both settings: it optimizes execution on the easy trained setting and it uses robustness of tarjan's algorithm in the random setting without slowing it down. use arcmax before or after single-root step? as mentioned in section 5 there are two places where the arcmax trick could be used. we argued that using it before the singleroot step is preferable. the results in figure 6 confirm that. if we apply the arcmax trick to all of these algorithms, they all get much faster but the relative speed between them stays the same. to see that, compare the results in figures 4a and 5 . we do not show the results on the random setting because they are equivalent to those without arcmax in figure 4b . when using all of the techniques in our paper together, namely arcmax+reweighting+tarjan, we get an algorithm that is on average 11x faster than the algorithm of zmigrod et al. when applied to the output of a trained parser. a better implementation of zmigrod et al. could possibly make this algorithm more competitive but it is unlikely that it would compensate for this large performance gap. is reweighting algorithm always the fastest? while the reweighting algorithm both theoretically and practically improves over the preselection algorithm, it should be mentioned that the performance in practice depends on the implementation of tarjan's algorithm as the underlying unconstrained mst algorithm. if instead of tarjan we used cle, the preselection algorithm will work better on the trained input (see figure 11 in appendix). the main reason for that is that cle algorithm, unlike tarjan, has a computational complexity that varies, depending on the input, between o(n 2 ) and o(n 3 ). on trained input, in general, cle tends to be closer to its best-case complexity because there are not many cycles to be contracted. however, the reweighting algorithm changes the weights of a graph in such a way that there are always cycles that need to be contracted and thereby causes cle to be closer to its worstcase complexity. this problem does not exist with tarjan's algorithm that both in best and worst-case runs in o(n 2 ). our recommendation is to use arcmax+reweighting+tarjan as the fastest and most stable algorithm, but if some other unconstrained algorithm is used in place of tarjan's, it should be tested if the reweighting algorithm runs faster than preselection. ## conclusion we demonstrated how to obtain significant speed-ups in single-root dependency parsing. the two proposed algorithms are fast, flexible, easy to understand and simple to implement in comparison to previously published ones.