Abstract
Arc-eager dependency parsers process sentences in a single left-to-right pass over the input and have linear time complexity with greedy decoding or beam search. We show how such parsers can be constrained to respect two different types of conditions on the output dependency graph: span constraints, which require certain spans to correspond to subtrees of the graph, and arc constraints, which require certain arcs to be present in the graph. The constraints are incorporated into the arc-eager transition system as a set of preconditions for each transition and preserve the linear time complexity of the parser.
Introduction
Data-driven dependency parsers are typically "soft" models, learning statistical patterns from treebanks without strictly adhering to hard structural rules. However, in many real-world scenarios, we possess high-confidence external information that the parser should respect. This paper, authored by Joakim Nivre, Yoav Goldberg, and Ryan McDonald, introduces a framework for incorporating hard "arc" and "span" constraints into the efficient arc-eager transition system.
The Problem: Integrating External Knowledge
Standard transition-based parsers might ignore domain-specific rules or formatting cues. For instance, a title like "Cat on a Hot Tin Roof" should be treated as a single cohesive subtree (a span constraint). Similarly, in imperative sentences, the initial verb is typically the root (an arc constraint). In languages like Korean, white-space-separated units (bunsetsus) provide strong structural hints that can be modeled as spans.
While graph-based parsers can handle such constraints, they often suffer from increased computational complexity. The challenge addressed here is to enforce these "hard" constraints in transition-based parsing while maintaining its hallmark $O(n)$ linear time complexity.
Methodology: Arc and Span Constraints
The authors extend the arc-eager transition system—which uses a stack and a buffer—by adding preconditions to the standard transitions: Left-Arc, Right-Arc, Reduce, and Shift.
- Arc Constraints: These require a specific head-dependent relationship $(i, l, j)$ to exist in the final graph. The parser is restricted from making any transition that would make this required arc "unreachable" (e.g., popping a node from the stack before it has acquired its mandatory head).
- Span Constraints: These require a specific range of words to form a single projective subtree. The system tracks the number of connected components within a span, blocking transitions that would prematurely close a span or leave it with multiple disconnected roots.
Crucially, by preprocessing constraints in $O(n)$ time, these checks become $O(1)$ during parsing, preserving the overall efficiency of the system.
Case Studies and Results
The approach was evaluated on two distinct tasks where external structural knowledge is readily available.
English Imperatives
Using a subset of the Web Treebank consisting of sentences starting with a verb, the authors constrained the first word to be the root. This simple arc constraint improved the Labeled Attachment Score (LAS) from 82.14 to 85.56.
Korean Parsing
In Korean, white-space-delimited phrasal units provide natural span constraints. Enforcing these improved the Unlabeled Attachment Score (UAS) from 94.10 to 94.92 and the LAS from 89.91 to 90.75.
Conclusion
This research demonstrates that hard constraints can be integrated into transition-based parsers without sacrificing speed. This allows for effective domain adaptation without retraining and ensures structural integrity by leveraging external knowledge or formatting cues. Future work may explore automatic constraint discovery and the use of constraints as partial oracles for semi-supervised learning.
Summary updated