Ran Zmigrod, Tim Vieira, Ryan Cotterell
Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)
Introduction
In graph-based dependency parsing, the syntactic structure of a sentence is modeled as a directed spanning tree, or arborescence. Words serve as nodes, and edges represent grammatical relationships. A fundamental linguistic requirement, exemplified by the Universal Dependencies (UD) framework, is the root constraint: a sentence must have exactly one root. Specifically, exactly one edge must originate from a designated "root" node to a word within the sentence.
Most modern graph-based parsers treat decoding as a Maximum Weight Spanning Tree (MWST) problem, typically employing the Chu-Liu/Edmonds (CLE) algorithm. However, standard CLE only ensures that every word has a single parent and that the graph is acyclic; it does not guarantee a single root edge. Consequently, parsers often produce "malformed" trees with multiple roots, particularly in low-resource scenarios. This paper identifies this gap and provides an efficient $O(n^2)$ algorithm to enforce the single-root constraint without increasing computational overhead.
Methodology: Efficient Root-Constrained Decoding
The authors adapt a classic algorithm from Gabow and Tarjan (1984) to the task of dependency parsing. The core of the approach is a recursive constrain function that operates on the output of a greedy search to satisfy the root requirement.
The Constrained Algorithm
If the initial search yields multiple root edges, the algorithm intelligently identifies which one to remove to maintain optimality:
- Optimization Case: If removing the lowest-scoring root edge does not introduce a cycle, the algorithm proceeds with the removal.
- Reduction Case: If removal creates a "critical cycle," the algorithm contracts that cycle into a single representative node and recurses. This process effectively breaks the cycle in a way that maximizes the overall tree score while satisfying the root constraint.
Computational Efficiency
By utilizing advanced data structures such as Union-Find and radix sort, the implementation maintains a runtime complexity of $O(n^2)$. This matches the efficiency of the fastest unconstrained CLE implementations, making the structural constraint computationally "free" in terms of asymptotic performance.
Experimental Evaluation
The algorithm was evaluated across 63 Universal Dependency (UD) Treebanks (v2.3), categorized by training set size:
- High Resource: >10,000 sentences (20 languages).
- Medium Resource: 1,000–10,000 sentences (32 languages).
- Low Resource: <1,000 sentences (11 languages).
The evaluation focused on two primary metrics: Unlabeled Attachment Score (UAS) and Exact Match (EM). While UAS measures per-edge accuracy, EM is a better reflection of a parser's true performance, as a tree with multiple roots is fundamentally broken.
Key Insights and Results
The experiments revealed that structural malformation is a significant issue in data-scarce settings. While high-resource models (e.g., English) produced malformed trees only 0.48% of the time, the rate rose to 6.21% for low-resource languages. In extreme cases like Kurmanji (20 training sentences), 24% of decoded trees were initially malformed.
Impact on Accuracy
Enforcing the root constraint led to consistent improvements in parsing accuracy, particularly for Exact Match scores:
- Average EM Improvement: +0.60% across all 63 languages.
- Low-Resource EM Improvement: +2.91% on average.
- Kurmanji Case Study: EM score improved by a staggering 22.22%.
These results suggest that while edge-factored models may not "learn" global constraints from surface features alone, providing mathematical structural guardrails significantly enhances their performance.
Conclusion
This paper demonstrates that the single-root constraint is vital for producing linguistically valid dependency trees, especially for low-resource languages. By providing an $O(n^2)$ algorithm that enforces this constraint without a speed penalty, the authors offer a robust solution for modern dependency parsing pipelines. Future work may extend these efficient constraint-handling techniques to other structured prediction tasks in NLP where global constraints are often ignored for simplicity.
Summary updated