Replicating and Extending "Because Their Treebanks Leak": Graph Isomorphism, Covariants, and Parser Performance

Mark Anderson, Anders Søgaard, Carlos Gómez-Rodríguez

TL;DR

This paper revisits a previous claim that graph isomorphism (DUG) explains significant variation in dependency parser performance. By carefully controlling for confounding factors like training data size and sentence length, the authors demonstrate that DUG's apparent predictive power largely disappears. They advocate for more rigorous statistical analysis and controlled experiments in NLP research.

What Problem Does This Paper Address?

The field of Natural Language Processing (NLP) often relies on statistical analyses to understand why certain models perform better than others on specific tasks. A recent study by Søgaard (2020) proposed "directed unlabelled graph isomorphism" (DUG) as a key factor explaining differences in dependency parser performance across various treebanks. DUG essentially measures the proportion of dependency trees in a test set that have already been seen in the training set. The original study suggested this metric accounted for a substantial portion of performance variation. However, this claim was based on a small sample size and potentially overlooked important confounding variables. This paper aims to replicate and extend that study, critically examining the validity of DUG as a predictor of parser performance by addressing methodological limitations and controlling for known covariates.

Methods

The authors begin by attempting to reproduce the original study's findings using the same settings and data. They then extend the analysis by:

  • Using multiple parsers and datasets: They employ UDPipe 1.2 and UDPipe 2.0 on a larger set of Universal Dependencies (UD) treebanks, going beyond the original paper's limited scope.
  • Controlling for covariants: They explicitly investigate the influence of two main factors that are correlated with DUG: training data size (number of sentences) and mean sentence length of the test data.
  • Employing sentence-length binning: Instead of a single overall analysis, they divide sentences into bins based on their length and analyze DUG and parser performance within each bin. This helps to reveal length-specific effects.
  • Performing controlled experiments: They create controlled experimental setups by sampling subsets of treebanks and fixing training data size and sentence length. This allows for a more direct assessment of DUG's impact in isolation.
  • Using correlation coefficients (Spearman's ρ) and linear regression: While the original study used linear regression, this paper also heavily relies on correlation coefficients to assess relationships between variables, especially after controlling for covariants. They also use linear models with adjusted features (e.g., log-transformed training size).

Datasets

The primary datasets used are Universal Dependencies (UD) treebanks. The original paper used a subset of treebanks from the CoNLL 2018 shared task. This replication study expands the analysis to a larger number of UD treebanks, utilizing UDPipe 1.2 and UDPipe 2.0 systems.

Key Insights and Ideas

  • DUG's predictive power is largely an artifact of covariants: The paper strongly suggests that the observed correlation between DUG and parser performance in the original study was primarily driven by the influence of training data size and sentence length, not DUG itself.
  • Sentence length is a critical factor: The relationship between DUG and parser performance is highly dependent on sentence length. For very short or very long sentences, DUG is almost always 1.0 or 0.0, respectively, offering little explanatory power. Meaningful variation in DUG occurs only within a specific range of sentence lengths (around 9-14 tokens).
  • Cross-validation with small sample sizes can be misleading: The authors highlight that using cross-validation with small datasets can lead to unreliable and even negative explained variance, indicating that the linear models failed to fit the data.
  • Controlled experiments are crucial for isolating effects: The controlled experiment, where covariants were fixed, revealed a strong correlation between DUG and parser performance, suggesting that DUG can be a strong predictor under specific, idealized conditions, but this doesn't reflect real-world scenarios where covariants are present.
  • Visualisation is key: The paper emphasizes the importance of visualizing data (e.g., scatter plots) to understand relationships before relying solely on statistical models, especially when dealing with potential non-linearities or confounding factors.

Key Results

  • Replication of original findings is weak: When replicating the original analysis with the same settings, the DUG explained variance was much smaller.
  • Covariants dominate: When controlling for training data size and sentence length, the correlation between DUG and LAS (the parser performance metric) becomes negligible (e.g., Spearman's ρ of 0.01 with a p-value of 0.926 after removing background signals).
  • Sentence length binning reveals nuanced relationships: DUG is close to 1.0 for short sentences and 0.0 for long sentences, with a narrow window (9-14 tokens) showing meaningful variation.
  • Controlled experiment shows strong DUG-LAS correlation: In a controlled setting with fixed sentence length (12 tokens) and sampled treebanks, a strong correlation (p = 0.82, p<0.001) between DUG and LAS was observed.

Limitations and Future Work

  • Limitations: The authors acknowledge that their controlled experiment was limited to 9 treebanks and a fixed sentence length of 12 tokens due to data availability and system constraints. They also note that the original paper's methodology, particularly its reliance on cross-validation with small sample sizes, was problematic.
  • Future Work: The paper implicitly suggests that future NLP research should adopt more rigorous statistical practices, including:
  • Carefully controlling for known covariants.
  • Utilizing sentence-length binning for analyses sensitive to length.
  • Employing controlled experiments to isolate the impact of specific features.
  • Prioritizing data visualization to gain a deeper understanding of relationships.
  • Being cautious about drawing strong conclusions from analyses on small sample sizes or without proper control for confounding factors.

Summary updated

BibTeX
@inproceedings{anderson2021replicating,
  author = {Mark Anderson and Anders Søgaard and Carlos Gómez-Rodríguez},
  title = {{Replicating and Extending "Because Their Treebanks Leak": Graph Isomorphism, Covariants, and Parser Performance}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
  url = {https://openreview.net/forum?id=B4U-s4ZK73K},
}
Figure