Reverse Revision and Linear Tree Combination for Dependency Parsing

Giuseppe Attardi, Felice Dell’OrlettaNAACL 2009

TL;DR

This paper introduces "Reverse Revision," a novel two-pass dependency parsing approach that significantly improves accuracy by having a second parser analyze the sentence in reverse, leveraging features from the first pass. They also propose a linear-time algorithm for combining the outputs of multiple parsers, achieving state-of-the-art results on several benchmarks.

What Problem Does This Paper Address?

Dependency parsing aims to uncover the grammatical relationships between words in a sentence, often represented as a tree structure. Transition-based parsers, while efficient, struggle with long-range dependencies, leading to accuracy drops. Existing methods to address this, like ensemble methods or graph-based parsers, often incur quadratic time complexity. This paper tackles the challenge of improving dependency parsing accuracy, particularly for long dependencies, while maintaining near-linear computational complexity.

Methods

The core innovation is the Reverse Revision approach. It's a two-pass system:

  1. Forward Pass: A standard deterministic Shift/Reduce dependency parser (like DeSR) processes the sentence from left to right.
  2. Reverse Pass: A second deterministic Shift/Reduce parser analyzes the sentence from right to left. Crucially, this second parser is augmented with additional features derived from the parse tree produced by the first parser. These features can include information about the predicted head's lemma, part-of-speech, and dependency label, as well as relative positions of words.

For combining the outputs of multiple parsers (specifically, a Left-to-Right, a Right-to-Left, and the Reverse Revision parser), they propose a Linear Voting Combination algorithm. Unlike MST-based combination methods that require quadratic time, their algorithm builds the combined tree incrementally in linear time ($O(kn)$, where $n$ is the number of nodes and $k$ is the number of parsers). It greedily selects arcs based on their predicted weight, ensuring the resulting structure is always a valid tree.

Datasets

The experiments were conducted on:

  • CoNLL 2007 Shared Task languages: Italian, Czech, and English.
  • CoNLL-X Shared Task languages: All thirteen languages from this task.

Key Insights and Ideas

  • The Power of Reverse Analysis: Analyzing a sentence in reverse, informed by a forward pass, provides a powerful complementary perspective that helps correct errors, especially those related to long-range dependencies.
  • Feature Engineering is Key: The success of the Reverse Revision parser hinges on effectively extracting and utilizing features from the first parser's output.
  • Linear Combination Outperforms MST: For combining parsers, their linear-time algorithm achieves competitive or superior results compared to quadratic-time MST-based methods, demonstrating that a greedy, top-down combination can be highly effective.
  • Low-Accuracy Parsers as Learners: The authors found that using a lower-accuracy parser as a source of features for the stacked parser (Rev2) can paradoxically lead to better overall performance, suggesting that noisy but diverse predictions can be beneficial for learning.

Key Results

  • The Reverse Revision (Rev2) parser consistently improves accuracy over the standard Left-to-Right (LR) parser, with improvements ranging from 0.38% (Chinese) to 3.84% (Dutch) on CoNLL 2007 languages.
  • For Czech and Italian, the Right-to-Left (RL) parser achieved higher accuracy than LR, and Rev2 even higher.
  • The Linear Voting Combination method achieved the best or second-best Labeled Attachment Scores (LAS) on CoNLL 2007 languages (best for Czech and Italian, second best for English).
  • On the CoNLL-X languages, the combination parser often achieved the best accuracy among the thirteen languages.
  • Speed: The linear combination algorithm ran in 11.2 seconds on the CoNLL-X test set, significantly faster than the 92.5 seconds required by an MST-based combination.

Limitations and Future Work

  • Comparison to Graph-Based Parsers: While their linear combination method performs well, it falls short of the accuracy achieved by integrating a graph-based parser with a transition-based parser in some cases.
  • Feature Tuning: The authors suggest that further tuning of feature selection for the Reverse Revision parser could lead to even greater improvements.
  • Generalization: While tested on multiple languages, exploring the method's performance on languages with significantly different linguistic structures could be a future direction.

Summary updated

BibTeX
@inproceedings{attardi2009reverse,
  author = {Giuseppe Attardi and Felice Dell’Orletta},
  title = {{Reverse Revision and Linear Tree Combination for Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2009},
}
Figure