Arc-Hybrid Non-Projective Dependency Parsing with a Static-Dynamic Oracle

Miryam de Lhoneux, Sara Stymne, Joakim NivreIWPT 2017 · OpenReview

Abstract

Miryam de Lhoneux, Sara Stymne, Joakim Nivre. Proceedings of the 15th International Conference on Parsing Technologies.

2017. This paper introduces a method to handle non-projective sentences in transition-based dependency parsing by integrating a SWAP transition into the arc-hybrid system. By employing a hybrid oracle—static for the SWAP transition and dynamic for standard transitions—the authors achieve significant accuracy improvements, particularly in languages with high degrees of non-projectivity.

Introduction

In dependency parsing, the goal is to identify grammatical relationships between words. While transition-based parsers are highly efficient, they are traditionally optimized for projective trees, where dependency arcs do not cross. However, many languages, such as Ancient Greek, exhibit non-projective structures with crossing dependencies.

To address this, parsers can use a SWAP transition to reorder words. However, incorporating SWAP often compromises arc-decomposability, a property necessary for dynamic oracles. Dynamic oracles are essential for robust training as they allow the parser to learn optimal actions even after making mistakes. This paper explores a middle ground: a static-dynamic oracle that enables non-projective parsing without losing the benefits of dynamic training.

Methods: The Static-Dynamic Oracle

The authors extend the standard arc-hybrid transition system, which utilizes a stack and a buffer, by adding a SWAP transition. The SWAP operation moves the top element of the stack back to the buffer, effectively reordering words to resolve non-projective arcs into a projective sequence.

Transitions in the arc-hybrid system illustrating arc construction.

The innovation lies in the hybrid training strategy:

  1. Static for SWAP: The oracle is rigid regarding reordering. It mandates a SWAP transition only when the gold-standard projective order requires it, preventing the parser from exploring suboptimal reorderings.
  2. Dynamic for Standard Transitions: For LEFT, RIGHT, and SHIFT moves, the oracle remains dynamic. It calculates the Hamming loss (the number of gold arcs that can no longer be built) for any given move, teaching the parser how to recover from errors.

By "forcing" the reordering while allowing "exploration" of arc-building, the authors bypass the mathematical complexity of a fully dynamic non-projective oracle while retaining the advantages of error-exploration training.

Experimental Setup and Results

The system was evaluated on five treebanks from the Universal Dependencies CoNLL 2017 shared task, representing a spectrum of non-projectivity: Ancient Greek (high), Basque (moderate), Portuguese (low), English (very low), and Arabic (minimal).

The "Static-Dynamic" (S-Dy) system was compared against a purely static version, a projective baseline, and a pseudo-projective parser (PProj).

Parsing performance (LAS) across languages with varying non-projectivity.

Key results include:

  • Consistent Improvements: The S-Dy system outperformed the static version across all tested languages, with gains ranging from 0.5 to 3.5 Labeled Attachment Score (LAS) points.
  • Ancient Greek Breakthrough: On the highly non-projective Ancient Greek dataset, the S-Dy parser achieved a score of 59.53, a substantial improvement over the projective baseline of 46.98.
  • Competitive Performance: The system performed on par with the more complex pseudo-projective method, demonstrating that online reordering via SWAP is a simpler and effective alternative.

Conclusion and Future Work

The static-dynamic oracle approach effectively mitigates error propagation. Traditional static parsers often fail when encountering unfamiliar states caused by early mistakes; the dynamic component of this oracle teaches the parser to make the best possible moves in such scenarios.

While successful, the oracle remains static regarding the SWAP transition itself. Future research aims to develop a fully dynamic oracle that can quantify the cost of incorrect swap actions. Additionally, while experimental results are promising, a formal mathematical proof of arc-decomposability under this hybrid system remains an open challenge.

Summary updated

BibTeX
@inproceedings{lhoneux2017arc,
  author = {Miryam de Lhoneux and Sara Stymne and Joakim Nivre},
  title = {{Arc-Hybrid Non-Projective Dependency Parsing with a Static-Dynamic Oracle}},
  booktitle = {IWPT},
  year = {2017},
  url = {https://openreview.net/forum?id=gy1_AjkMxHF},
}
Figure