Bidirectional Transition-Based Dependency Parsing

Yunzhe Yuan, Yong Jiang, Kewei TuAAAI 2019 · DOI

Abstract

Transition-based dependency parsers are widely used for their speed, yet they suffer from cascading errors due to their unidirectional, greedy nature. This paper introduces a bidirectional framework that trains both left-to-right (L2R) and right-to-left (R2L) parsers. These models are reconciled during inference using a novel joint decoding algorithm guided by dynamic oracles. This approach effectively leverages the complementary error distributions of the two directional parsers, leading to significant accuracy improvements across multiple languages and benchmarks.

Introduction

In natural language processing, dependency parsing identifies the syntactic structure of sentences. Transition-based parsers are popular because they build trees incrementally and efficiently. However, a major drawback is their "left-to-right" bias: early greedy decisions can lead to errors that propagate through the rest of the sentence.

The authors observe that while an L2R parser typically struggles with the end of a sentence, an R2L parser—trained on reversed input—tends to make mistakes at the beginning. The core contribution of this work is a method to combine these two perspectives into a single, highly accurate parse tree.

Methodology

The framework involves training two independent BiLSTM-based parsers (L2R and R2L) using an arc-hybrid transition system. At test time, three joint decoding strategies are explored to reach a consensus:

  1. Vanilla Joint Scoring: Selecting the tree with the highest combined score from both parsers.
  2. Dual Decomposition (DD): An iterative optimization technique that adjusts scores until both parsers agree.
  3. Joint Decoding Guided by Dynamic Oracle (DO): The primary innovation. During inference, the output of one parser serves as the "gold" reference for the other. A dynamic oracle provides rewards for actions that move each parser closer to the other's current structure.

Key Insights: Complementary Errors and Convergence

Analysis of error distributions confirms that L2R and R2L parsers are "mirror images." L2R parsers are more prone to failure in the final 30% of a sentence, whereas R2L parsers fail more frequently in the first 30%.

Error distributions of L2R, R2L, and DO-guided parsers across normalized sentence positions.

The DO-guided method acts as a bridge, allowing parsers to migrate toward a consensus structure efficiently. Unlike Dual Decomposition, which often fails to converge even after 100 iterations, the DO-guided method typically reaches a high-accuracy agreement in just 4 iterations.

Results and Discussion

The DO-guided bidirectional parser consistently outperforms unidirectional baselines and other joint decoding methods across diverse benchmarks, including the Penn Treebank (PTB), Chinese Treebank (CTB), and Universal Dependencies (UD) 2.2.

UAS performance over iterations comparing Dual Decomposition (DD) and Dynamic Oracle (DO) methods.

On the PTB, the DO method achieved a Unlabeled Attachment Score (UAS) of 94.60%, a significant jump from the 93.54% L2R baseline. Similar gains were observed cross-lingually (e.g., German UAS improved from 81.62% to 83.02%).

Conclusion

By reconciling the directional biases of transition-based parsers through dynamic oracle-guided joint decoding, this work provides a robust and efficient framework for bidirectional parsing. While it introduces some overhead in inference speed, the substantial gains in accuracy and the rapid convergence of the DO method make it a compelling advancement for syntactic analysis.

Summary updated

BibTeX
@inproceedings{yuan2019bidirectional,
  author = {Yunzhe Yuan and Yong Jiang and Kewei Tu},
  title = {{Bidirectional Transition-Based Dependency Parsing}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017434},
}
Figure