Constrained Arc-Eager Dependency Parsing

Joakim Nivre, Yoav Goldberg, Ryan T. McDonaldComput. Linguistics 2014 · OpenReview

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.

Comparison of unconstrained (left) and span-constrained (right) parsing for a named entity.

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.

  1. 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).
  2. 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.

The workflow for Korean parsing, utilizing segmentation and phrasal chunking as span constraints.

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

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.
BibTeX
@inproceedings{nivre2014constrained,
  author = {Joakim Nivre and Yoav Goldberg and Ryan T. McDonald},
  title = {{Constrained Arc-Eager Dependency Parsing}},
  booktitle = {Comput. Linguistics},
  year = {2014},
  url = {https://openreview.net/forum?id=JjsBZgO5ay},
}
Figure