Please Mind the Root: Decoding Arborescences for Dependency Parsing

Ran Zmigrod, Tim Vieira, Ryan Cotterell

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.

1. Introduction

In graph-based dependency parsing, sentences are modeled as graphs where words are nodes and syntactic relationships are weighted directed edges. The parsing task is typically framed as finding the Maximum Weight Arborescence (MWA), often solved using the Chu-Liu/Edmonds (CLE) algorithm. However, a significant discrepancy exists between the mathematical definition of an arborescence and the linguistic requirements of dependency trees. Specifically, frameworks like Universal Dependencies (UD) mandate that a sentence must have exactly one root node. Standard MWA algorithms do not enforce this "root constraint," frequently resulting in malformed trees with multiple root edges.

2. The Efficiency-Constraint Trade-off

Historically, the NLP community has addressed the root constraint in two ways:

  1. Implicit Learning: Relying on the model (e.g., a deep neural network) to learn the constraint from training data.
  2. Brute-Force Decoding: Running the CLE algorithm $n$ times—once for each possible root—to find the best single-root tree. This increases decoding complexity from $O(n^2)$ to $O(n^3)$.

This paper argues that implicit learning is unreliable, especially in low-resource settings, and that $O(n^3)$ decoding is an unnecessary bottleneck for large-scale applications.

3. Adapting the Gabow and Tarjan Algorithm

The authors introduce an $O(n^2)$ solution by adapting a forgotten algorithm from Gabow and Tarjan (1984). The algorithm functions through a recursive "contract and expand" strategy:

  • Initial Search: It first identifies the standard MWA. If the single-root constraint is met, the process is complete.
  • Constraint Enforcement: If multiple root edges are present, the algorithm must determine which edge to remove to satisfy the constraint while maximizing the total tree weight.
  • Cycle Management: Removing an edge can inadvertently create cycles. The algorithm efficiently manages these by identifying "critical cycles" and treating them as single nodes during contraction.
  • Optimization: By utilizing advanced data structures like Union-Find and radix sort, the algorithm maintains the optimal $O(n^2)$ runtime, matching the efficiency of standard CLE.

4. Experimental Results

The authors evaluated the impact of the root constraint across 63 Universal Dependency Treebanks (v2.3).

4.1 The Failure of Implicit Learning

The study found that while high-resource languages (e.g., English) rarely violate the root constraint, low-resource languages suffer significantly. For instance, in Kurmanji, a state-of-the-art parser produced malformed trees 24% of the time. On average, the Stanza parser had a 1.80% malformed rate, which rose to 6.21% for low-resource languages. This suggests that models often rely on surface correlates (like word position) which are insufficient when data is sparse.

4.2 Impact on Accuracy

Enforcing the constraint significantly improved structural validity. While Unlabeled Attachment Score (UAS) gains were marginal, Exact Match (EM) scores saw dramatic increases. In the case of Kurmanji, the EM score improved by 22.22%. This indicates that the model often assigns high scores to the correct tree, but requires the hard constraint to break ties with malformed candidates.

5. Conclusion and Future Work

Enforcing the single-root constraint is vital for linguistically valid dependency parsing, particularly for low-resource languages. The adapted Gabow and Tarjan algorithm provides a mathematically sound and computationally efficient $O(n^2)$ solution. While this work focuses on edge-factored, non-projective models, the authors recommend that this decoding method become a standard feature in NLP parsing libraries to ensure structural integrity across all languages and resource levels.

Summary updated

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.
BibTeX
@inproceedings{zmigrod2020please,
  author = {Ran Zmigrod and Tim Vieira and Ryan Cotterell},
  title = {{Please Mind the Root: Decoding Arborescences for Dependency Parsing}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=QwCVjpWvD_i},
}
Figure