Please Mind the Root: D ecoding Arborescences for Dependency Parsing (2020)

Abstract: The connection between dependency trees and spanning trees is exploited by the NLP community to train and to decode graph-based dependency parsers. However, the NLP literature has missed an important difference between the two structures: only one edge may emanate from the root in a dependency tree. We analyzed the output of state-of-the-art parsers on many languages from the Universal Dependency Treebank: although these parsers are often able to learn that trees which violate the constraint should be assigned lower probabilities, their ability to do so unsurprisingly de-grades as the size of the training set decreases. In fact, the worst constraint-violation rate we observe is 24%. Prior work has proposed an inefficient algorithm to enforce the constraint, which adds a factor of n to the decoding runtime. We adapt an algorithm due to Gabow and Tarjan (1984) to dependency parsing, which satisfies the constraint without compromising the original runtime.

## introduction developing probabilistic models of dependency trees requires efficient exploration over a set of possible dependency trees, which grows exponentially with the length of the input sentence n. under an edge-factored model @xcite @xcite , finding the maximum-a-posteriori dependency tree is equivalent to finding the maximum weight spanning tree in a weighted directed graph. more precisely, spanning trees in directed graphs are known as arborescences. the maximum-weight arborescence can be found in o(n foot_1 ) @xcite . 2 however, an oversight in the relationship between dependency trees and arborescences has gone largely unnoticed in the dependency parsing literature. most dependency annotation standards enforce a root constraint: exactly one edge may emanate from the root node. 3 for example, the universal dependency treebank (ud; @xcite ), a large-scale multilingual syntactic annotation effort, states in their documentation (ud contributors): there should be just one node with the root dependency relation in every tree. this oversight implies that parsers may return malformed dependency trees. indeed, we examined the output of a state-of-the-art parser @xcite for 63 ud treebanks. we saw that decoding without a root constraint resulted in 1.80% (on average) of the decoded dependency trees being malformed. this increased to 6.21% on languages that contain less than one thousand training instances with the worst case of 24% on kurmanji. the nlp literature has proposed two solutions to enforce the root constraint: (1) allow invalid dependency trees-hoping that the model can learn to assign them low probabilities and decode singly rooted trees, or (2) return the best of n runs of the cle each with a fixed edge emanating from the root @xcite . 4 the first solution is clearly problematic as it may allow parsers to predict malformed dependency trees. this issue is further swept under the rug with "forgiving" evaluation metrics, such as attachment scores, which give @xcite ) opt for the simpler cle algorithm @xcite @xcite , which has a worst-case bound of o(n 3 ), but is often fast in practice. partial credit for malformed output. 5 the second solution, while correct, adds an unnecessary factor of n to the runtime of root-constrained decoding. in this paper, we identify a much more efficient solution than (2). we do so by unearthing an o(n 2 ) algorithm due to @xcite from the theoretical computer science literature. this algorithm appears to have gone unnoticed in nlp literature; foot_5 we adapt the algorithm to correctly and efficiently handle the root constraint during decoding in edge-factored non-projective dependency parsing. 7 ## approach in this section, the marker indicates that a recently introduced concept is illustrated the worked example in fig. 2 . let @xmath0, v, e) be a rooted weighted directed graph where v is a set of nodes, e is a set of weighted edges, e ⊆ {(i w -a j) | i, @xmath1, @xmath2, foot_7 and ρ ∈ v is a designated root node with no incoming edges. in terms of dependency parsing, each non-ρ node corresponds to a token in the sentence, and ρ represents the special root token that is not a token in the sentence. edges represent possible dependency relations between tokens. the edge weights are scores from a model (e.g., linear @xcite , or neural network @xcite ). fig. 1 shows an example. we allow g to be a multigraph, i.e., we allow multiple edges between pairs of nodes. multi-graphs are a natural encoding of labeled dependency relations where possible labels between words are captured by multiple edges be-tween nodes in the graph. multi-graphs pose no difficulty as only the highest-weight edge between two nodes may be selected in the returned tree. an arborescence of g is a subgraph @xmath3, v, e ) where e ⊆ e such that: in §2.1, we describe an efficient algorithm for finding the best (highest-weight) arborescence part 1: we call any cycle c in -a g a critical cycle. naturally, (c2) implies that critical cycles can never be part of an arborescence. however, they help us identify optimal arborescences for certain subproblems. specifically, if we were to "break" the cycle at any node @xmath4, we would have an opti- ) and so we get part 2: breaking cycles is done with a recursive algorithm that solves the "outer problem" of fitting the (unbroken) cycle into an optimal arborescence. the algorithm treats the cycle as a single contracted node. formally, a cycle contraction takes a graph g and a (not necessarily critical) cycle c, and creates a new graph denoted g /c with the same root, nodes (v c ∪ {c}) where c / ∈ v is a new node that represents the cycle, and contains the following set of edges: for any (i j) ). akin to dynamic programming, this choice edge weight ( due to georgiadis (2003) ) gives the best "cost-to-go" for breaking the cycle at j. by (c1), we have that for any a @xmath5, there exists exactly one incoming edge (i -a c) to the cycle node c. we can use π to infer where the cycle was broken with π(i -a c) = (i -a j). we call j the entrance site of a c . consequently, we can stitch together an arborescence as π(a c ) ∪ c (j) . we use the shorthand a c c (j) for this operation due to its visual similarity to unraveling a cycle. g /c may also have a critical cycle, so we have to apply this reasoning recursively. this is captured by @xcite 's theorem 1. 10 theorem theorem 1 suggests a recursive strategy for finding g * , which is the basis of many efficient algorithms @xcite @xcite @xcite . we detail one such algorithm in alg 1. alg 1 can be made to run in o(n 2 ) time for dense with the appropriate implementation choices, such as union-find @xcite to maintain membership of nodes to contracted nodes, as well as radix sort @xcite to sort incoming edges to contracted nodes; using a regular sort would add a factor of log n to the runtime. base case 5: optimization case. if g has no critical cycles, then -a g must be the best arborescence with one fewer edges emanating from the root than -a g by our greedy choice of e . ## experiment how often do state-of-the-art parsers generate malformed dependency trees? we examined 63 universal dependency treebanks @xcite and computed the rate of malformed trees when decoding using edge weights generated by pre-trained models supplied by @xcite . on average, we observed that 1.80% of trees are malformed. we were surprised to see that-although the edgefactored model used is not expressive enough to capture the root constraint exactly-there are useful correlates of the root constraint in the surface form of the sentence, which the model appears to use to workaround this limitation. this becomes further evident when we examine the relative change foot_10 in uas (0.0083%) and exact match scores (0.60%) when using the constrained algorithm as opposed to the unconstrained algorithm. nevertheless, given less data, it is harder to learn to exploit the surface correlates; thus, we see an increasing average rate of violation, 6.21%, when examining languages with training set sizes of less than 1, 000 sentences. similarly, the relative change in uas and exact match score increases to 0.0368% and 2.91% respectively. indeed, the worst violation rate was 24% was seen for kurmanji which only contains 20 sentences in the training set. kurmanji consequently had the largest relative changes to both uas and exact match scores of 0.41% and 22.22%. we break down the malformed rate and accuracy changes by training size in tab. 1. furthermore, the correlation between training size and malformed tree rate can be seen in fig. 3 while the correlation between training size and relative accuracy change can be seen in fig. 4 . we provide a full table of the results in app. c. ## conclusion in this paper, we have bridged the gap between the graph-theory and dependency parsing literature. we presented an efficient o(n 2 ) for finding the maximum arborescence of a graph. furthermore, we highlighted an important distinction between dependency trees and arborescences, namely that dependency trees are arborescences subject to a root constraint. previous work uses inefficient algorithms to enforce this constraint. we provide a solution which runs in o(n 2 ). our hope is that this paper will remind future research in dependency parsing to please mind the root.