Please Mind the Root: Decoding Arborescences for Dependency Parsing

Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing, pages 4809–4819, November 16–20, 2020. c⃝2020 Association for Computational Linguistics 4809 Please Mind the Root: Decoding Arborescences for Dependency Parsing 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 dependency trees and spanning trees is exploited by the NLP com- munity to train and to decode graph-based de- pendency parsers. However, the NLP literature has missed an important difference between the two structures: only one edge may em- anate from the root in a dependency tree. We analyzed the output of state-of-the-art parsers on many languages from the Universal Depen- dency Treebank: although these parsers are of- ten able to learn that trees which violate the constraint should be assigned lower probabil- ities, 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 run- time. We adapt an algorithm due to Gabow and Tarjan (1984) to dependency parsing, which satisfies the constraint without compromising the original runtime.1 1 Introduction Developing probabilistic models of dependency trees requires efficient exploration over a set of pos- sible dependency trees, which grows exponentially with the length of the input sentence n. Under an edge-factored model (McDonald et al., 2005; Ma and Hovy, 2017; Dozat and Manning, 2017), finding the maximum-a-posteriori depen- dency 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(n2) (Tarjan, 1977; Camerini et al., 1979).2 1Our Python library is available at https://github. com/rycolab/spanningtrees. 2Several authors (e.g., Qi et al. (2020); McDonald et al. However, an oversight in the relationship be- tween 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; Nivre et al. (2018)), a large-scale multilingual syntactic anno- tation effort, states in their documentation (UD Contributors): There should be just one node with the root de- pendency relation in every tree. This oversight implies that parsers may return mal- formed dependency trees. Indeed, we examined the output of a state-of-the-art parser (Qi et al., 2020) for 63 UD treebanks. We saw that decoding with- out 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 …

Content truncated to 500 words