Some Languages Seem Easier to Parse Because Their Treebanks Leak

Anders SøgaardEMNLP 2020 · OpenReview

Abstract

Anders Søgaard. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP).

2020.

Introduction

In Natural Language Processing (NLP), dependency parsing—the task of mapping the grammatical structure of a sentence—shows significant performance variance across languages. While a state-of-the-art parser might achieve 95% accuracy on Polish, it may drop to 20% on Basque. Traditionally, these discrepancies are attributed to treebank size, morphological complexity, or sentence length. However, Anders Søgaard argues that these factors do not tell the whole story. He investigates "structural leakage": the phenomenon where the abstract structural "skeletons" of test sentences are identical to those seen during training, allowing models to rely on memorization rather than linguistic understanding.

Quantifying Structural Leakage

To measure this leakage, the author proposes using graph isomorphisms. By stripping away specific words and labels (e.g., "subject" or "object"), dependency trees are reduced to their underlying skeletons.

Examples of dependency tree structures used for isomorphism checking.

The study examines two types of skeletons:

  1. Undirected, Unlabeled Graphs (UUGs): Basic connections between words.
  2. Directed, Unlabeled Graphs (DUGs): Connections including the direction of grammatical relationships.

Using the VF2 algorithm, the author calculates how many test sentence skeletons are exact matches for those in the training data. Linear regression is then used to determine how well leakage predicts parser performance compared to traditional metrics.

Key Results

The study evaluated 45 languages using Universal Dependencies (UD) version 2.5 and results from the CoNLL 2018 shared task. The findings reveal that structural leakage is a dominant predictor of parsing success, second only to total training data size.

Leakage percentages across various languages, showing extreme redundancy in some treebanks.

Quantitative highlights include:

  • Predictive Power: Replacing "Sentence Length" with "DUG-Leakage" in a linear model increases the explained variance in performance from 17% to 22.8%.
  • Extreme Redundancy: Some treebanks are highly repetitive. In Telugu and Classical Chinese, over 90% of test sentence structures were already present in the training set.
  • Morphology vs. Leakage: Surprisingly, morphological complexity and the ratio of open-class words were poor predictors of performance compared to structural leakage.

Discussion and Future Work

The prevalence of structural leakage suggests a significant evaluation bias in current NLP benchmarks. Randomly splitting datasets into training and test sets rewards models that recognize familiar shapes rather than those that generalize linguistic rules. Basque remains a notable outlier, performing worse than predicted by its leakage or size, suggesting unique linguistic challenges remain.

To address this, the paper proposes a new evaluation standard: testing parsers specifically on non-isomorphic trees—structures the model has never encountered. This would provide a "leak-proof" measure of true generalization. While focused on dependency parsing, the concept of structural leakage likely extends to other tasks such as machine translation and semantic role labeling.

Reference: Søgaard, A. (2020). Some Languages Seem Easier to Parse Because Their Treebanks Leak. Proceedings of EMNLP 2020.

Summary updated

Abstract

Anders Søgaard. Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP). 2020.
BibTeX
@inproceedings{sgaard2020some,
  author = {Anders Søgaard},
  title = {{Some Languages Seem Easier to Parse Because Their Treebanks Leak}},
  booktitle = {Conference on Empirical Methods in Natural Language Processing},
  year = {2020},
  url = {https://openreview.net/forum?id=1uk9da4cxV1},
}
Figure