# Please Mind the Root: Decoding Arborescences for Dependency Parsing

arXiv: https://arxiv.org/abs/2010.02550 · HTML: https://mlsanity.com/paper/2010.02550/

## Key facts

- Cited by 11 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 6 Oct 2020.

## Built on by (most cited first, 11 of 11)

- [A Cross-Linguistic Pressure for Uniform Information Density in Word Order](https://mlsanity.com/paper/2306.03734/) (2023)
- [Measuring and Reducing Model Update Regression in Structured Prediction for NLP](https://mlsanity.com/paper/2202.02976/) (2022)
- [Computational historical linguistics and language diversity in South Asia](https://mlsanity.com/paper/2203.12524/) (2022)
- [The Architectural Bottleneck Principle](https://mlsanity.com/paper/2211.06420/) (2022)
- [On Finding the K-best Non-projective Dependency Trees](https://mlsanity.com/paper/2106.00780/) (2021)
- [Hexatagging: Projective Dependency Parsing as Tagging](https://mlsanity.com/paper/2306.05477/) (2023)
- [Unbiased and Efficient Sampling of Dependency Trees](https://mlsanity.com/paper/2205.12621/) (2022)
- [SynJax: Structured Probability Distributions for JAX](https://mlsanity.com/paper/2308.03291/) (2023)
- [Maximum Spanning Trees Are Invariant to Temperature Scaling in Graph-based Dependency Parsing](https://mlsanity.com/paper/2106.08159/) (2021)
- [Efficient Sampling of Dependency Structures](https://mlsanity.com/paper/2109.06521/) (2021)
- [Thai Universal Dependency Treebank](https://mlsanity.com/paper/2405.07586/) (2024)

## Abstract (arXiv)

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.