Tree Revision Learning for Dependency Parsing

Giuseppe Attardi, Massimiliano CiaramitaNAACL 2007 · OpenReview

Abstract

This paper introduces a "revision learning" stage for dependency parsing that corrects the output of a fast, deterministic parser. By training a classifier to recognize and fix common structural mistakes using a small set of "revision rules," the authors achieve significant accuracy gains (up to 16% error reduction) while maintaining the linear-time efficiency required for large-scale applications.

Introduction

Dependency parsing—the process of identifying grammatical relationships between words—is a cornerstone of natural language processing. While deterministic "shift-reduce" parsers are incredibly fast ($O(n)$ complexity), they are prone to local errors because they make "greedy" decisions as they scan a sentence. The traditional way to fix these errors is "re-ranking," where a parser generates the top $N$ most likely trees and a second, more complex model picks the best one. However, re-ranking is computationally expensive. This research addresses a gap: can we improve a parser's accuracy by simply "fixing" its single best guess, rather than generating and evaluating thousands of alternatives?

Methodology: Tree Revision

The authors propose a two-stage pipeline consisting of base parsing followed by tree revision. First, a fast, deterministic shift-reduce parser (specifically the DeSR parser) creates an initial dependency tree. Second, a tree revision pass scans the tree. For every word, a discriminative classifier (an averaged perceptron) decides whether its "head" (the word it depends on) is correct. If it looks wrong, the classifier predicts a Revision Rule to fix it.

Instead of trying to predict a new head from scratch, the model learns a set of atomic movements on the graph. For example, uu moves the dependency link up two levels in the current tree, while +1 moves the link to the token immediately to the right. By combining these steps, the model can "nudge" incorrect arrows to their proper places. Because the revision stage only looks at the existing tree and local features, it remains highly efficient ($O(n)$).

Commonly used revision rules and their frequencies.

Experimental Results

The model was evaluated on two major benchmarks: the English Wall Street Journal (Penn Treebank) and the Swedish Treebank from the CoNLL-X Shared Task. The revision stage provided a substantial boost across both languages. In the English dataset, the base MaxEnt parser's Unlabeled Attachment Score (UAS) jumped from 84.96% to 90.27%. This represents a 16.05% relative reduction in error, bringing a simple linear parser close to the performance of much slower, state-of-the-art models like MST-2.

Performance comparison of base and revision parsers.

In Swedish, the model achieved a 11.64% relative error reduction, reaching a UAS of 89.76%, which was competitive with the best systems in the CoNLL-X competition. Furthermore, the revision step is extremely fast, processing roughly 61 words per second, making it viable for real-world information retrieval tasks.

Discussion and Key Insights

The authors found that in the English dataset, just 20 simple revision rules were sufficient to correct 80% of the parser's errors. This suggests that parser mistakes are often systematic and predictable. Most dependency errors are "local"—a word is attached to a grandparent instead of a parent, or a neighboring noun. Consequently, local corrections are often enough to achieve high accuracy without a global overhaul.

Unlike re-ranking, which multiplies the work by the number of candidate trees ($N$), this method only adds a single linear pass over the sentence. The revision model is trained specifically on the errors the base parser makes on the training set, essentially learning the "blind spots" of the primary algorithm.

Conclusion

Tree revision learning offers a powerful way to enhance deterministic parsers. While the current model treats each revision as an independent decision and faces theoretical risks of creating cycles, its empirical performance is strong. Future work could incorporate more "global" features, such as semantic information from named-entity recognizers, into the revision phase to catch even more complex errors.

Citation: Giuseppe Attardi, Massimiliano Ciaramita. Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference. 2007.

Summary updated

Abstract

Giuseppe Attardi, Massimiliano Ciaramita. Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference. 2007.
BibTeX
@inproceedings{attardi2007tree,
  author = {Giuseppe Attardi and Massimiliano Ciaramita},
  title = {{Tree Revision Learning for Dependency Parsing}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=rJWOj7ZdZr},
}
Figure