Experiments with a Higher-Order Projective Dependency Parser

Xavier CarrerasEMNLP 2007

TL;DR

This paper introduces a dependency parsing model that considers "higher-order" relationships between words, going beyond simple head-modifier pairs to include siblings and grandchildren. While this richer model significantly improves parsing accuracy, it comes at a substantial computational cost in terms of time and memory.

What Problem Does This Paper Address?

Dependency parsing aims to represent the grammatical structure of a sentence as a tree, where words are linked by directed dependencies indicating their grammatical relationships (e.g., which word modifies which). Traditional dependency parsers often rely on "first-order" models, which consider only the direct head-modifier relationship. However, many linguistic ambiguities, like prepositional phrase attachment (e.g., "They sold cars in the U.S." - does "in the U.S." modify "sold" or "cars"?), require looking at more distant or indirect relationships. This paper addresses the challenge of incorporating these "higher-order" linguistic cues into dependency parsing models to improve accuracy, while acknowledging the inherent complexity and computational cost.

Methods

The authors extend Eisner's (1996) projective dynamic programming parsing algorithm to handle "higher-order" dependency relationships. Their model decomposes a dependency structure into factors that include not only the main head-modifier-label triple but also information about the head's closest child towards the modifier (ch), the modifier's furthest child within the head-modifier span (Cmi), and the modifier's furthest child outside that span (Cmo). This allows for the definition of richer, "second-order" features that capture these extended relationships. The models are trained using the averaged perceptron algorithm.

Datasets

The experiments were conducted on data from the CoNLL-2007 shared task on dependency parsing, specifically focusing on the multilingual track. The paper mentions using treebanks for ten languages, including Catalan, Czech, and English for detailed analysis. For evaluation, a portion of the training data (first 10,000 tokens) was held out as a validation set.

Key Insights and Ideas

  • Higher-order features are powerful: Incorporating relationships beyond direct head-modifier links (like siblings and grandchildren) significantly boosts parsing accuracy. This suggests that richer contextual information is crucial for resolving complex linguistic ambiguities.
  • Computational cost is a major trade-off: The gains in accuracy come at a steep price. The proposed higher-order models require significantly more time and memory for training and parsing, making them impractical for very long sentences or languages with many dependency labels.
  • Projective parsing is maintained: The authors successfully extend a projective parsing algorithm, meaning the resulting dependency trees do not have crossing dependencies, which simplifies inference.

Key Results

  • The richest higher-order model (including ch, Cmi, and Cmo) achieved the best accuracy for English in the CoNLL-2007 shared task and the second-best accuracies for Basque and Czech.
  • Compared to a first-order model, the higher-order models showed clear improvements in labeled attachment scores (LAS) across Catalan, Czech, and English. For example, the best model achieved 89.59% LAS for English, compared to 83.75% for a first-order model.
  • The paper also highlights the benefit of parameter averaging, showing that an averaged first-order model significantly outperforms an unaveraged one.
  • The computational cost is substantial: parsing speeds can be as low as 1.21 sentences per minute for Arabic, with memory requirements reaching up to 1.8GB.

Limitations and Future Work

The primary limitation acknowledged is the significant computational expense (time and memory) of the inference algorithms for higher-order models. This makes them impractical for certain scenarios. The authors suggest that future research should focus on developing methods to efficiently incorporate higher-order relations into discriminative parsing models.

Summary updated

BibTeX
@inproceedings{carreras2007experiments,
  author = {Xavier Carreras},
  title = {{Experiments with a Higher-Order Projective Dependency Parser}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2007},
}
Figure