Quantifying training challenges of dependency parsers

Lauriane Aufrant, Guillaume Wisniewski, François YvonCOLING 2018

TL;DR

This paper introduces a novel metric, "COMPLEXITY," to quantify how difficult specific dependency structures are to learn for natural language parsers. By analyzing learning curves, they demonstrate that not all dependencies are created equal, and this metric can reveal parser strengths and weaknesses, particularly in low-resource scenarios and cross-lingual transfer.

What Problem Does This Paper Address?

Training dependency parsers, which analyze the grammatical structure of sentences by identifying head-dependent relationships, often requires large amounts of annotated data (treebanks). However, it's unclear if all types of grammatical dependencies are equally challenging to learn. Some dependencies, like those between a noun and its determiner, seem intuitively straightforward, while others, like complex semantic attachments, might require significantly more data. This paper aims to quantify this difference in learning difficulty, moving beyond simple overall accuracy metrics to understand what makes a dependency hard or easy to learn. This understanding is crucial for developing more efficient training strategies, comparing parsers more effectively, and assessing the true value of techniques like cross-lingual transfer, especially when dealing with limited data.

Methods

The core of this work is the introduction of a new metric called COMPLEXITY. This metric is derived from analyzing the learning curves of dependency parsers. Specifically, the authors:

  1. Define Dependency Classes: They group dependencies based on criteria like child Part-of-Speech (PoS) tag and attachment direction (e.g., ADJ-NOUN where the adjective modifies the noun to its right).
  2. Generate Learning Curves: For each class, they train parsers on progressively larger subsets of a treebank (from 5 to 500 sentences) and measure the accuracy (UAS - Unlabeled Attachment Score) at each step. They normalize these scores to focus on the learning rate rather than absolute performance.
  3. Calculate COMPLEXITY: The COMPLEXITY of a class is calculated as the signed area between the learning curve of the overall parser performance and the learning curve of that specific dependency class. A negative COMPLEXITY indicates a class that is "easy to learn" (its learning curve is above the average), meaning most of its information is captured early in training. A positive COMPLEXITY indicates a "complex" class (its learning curve is below average), requiring more data to learn effectively.

They also propose using composite scores by separating classes into "simple" and "complex" based on their COMPLEXITY, allowing for a more nuanced comparison of parsers.

Datasets

The primary dataset used is the Universal Dependencies (UD) 2.0 dataset, which comprises 73 treebanks across a wide array of language families. For their experiments, they downsized treebanks to a maximum of 500 training sentences and resampled smaller trainsets. They also mention using specific treebanks for cross-lingual experiments, such as Romanian, French, Italian, Spanish, and Bulgarian.

Key Insights and Ideas

  • Dependencies are not created equal: The paper strongly supports the intuition that some dependency structures are inherently easier to learn than others, requiring far less data.
  • COMPLEXITY as a diagnostic tool: The proposed COMPLEXITY metric provides a quantitative way to understand why a parser performs well or poorly, going beyond simple accuracy scores. It highlights which types of dependencies are challenging for a given parser.
  • Learning curves reveal parser behavior: The shape of learning curves for specific dependency classes can reveal how efficiently a parser utilizes new training data for different grammatical structures.
  • Cross-lingual transfer benefits complex dependencies: While overall cross-lingual transfer might not always outperform small amounts of monolingual data, it appears to be more effective for conveying knowledge about complex dependencies, which are harder to acquire with limited target-language data.

Key Results

  • Clear separation of simple and complex classes: The learning curves for different dependency classes consistently fall into two distinct groups: those that converge quickly (simple) and those that improve gradually (complex).
  • Parser-specific strengths and weaknesses: The COMPLEXITY metric revealed that different parsers (BEAM, UDPIPE, MSTPARSER) have varying difficulties with different dependency classes. For example, UDPIPE struggled with deterministic classes like determiners, while MSTPARSER excelled at learning verb dependencies.
  • Significant score differences for simple vs. complex: Even with small datasets (10 sentences), parsers showed a substantial performance gap between simple and complex dependencies, a gap that largely persisted with larger datasets.
  • Cross-lingual transfer equivalence: For cross-lingual parsers, the performance on simple dependencies was equivalent to a few dozen monolingual sentences, while complex dependencies were equivalent to hundreds, suggesting that cross-lingual transfer's main value lies in acquiring knowledge for harder structures.

Limitations and Future Work

  • Language-specific nuances: While the COMPLEXITY metric aims for language-independent trends, the paper acknowledges that some class properties can still depend on the specific language or even corpus.
  • Scope of class criteria: The current analysis primarily focuses on PoS/direction classes. The authors suggest exploring other criteria (e.g., relation labels, distance) for a more comprehensive understanding.
  • Future work: The authors propose extending this analysis to other cross-lingual transfer algorithms, unsupervised parsers, and even other sequence labeling tasks like PoS tagging. They also suggest further experiments to understand what linguistic properties make a class complex and how to leverage this information to improve parsing.

Summary updated

BibTeX
@inproceedings{aufrant2018quantifying,
  author = {Lauriane Aufrant and Guillaume Wisniewski and François Yvon},
  title = {{Quantifying training challenges of dependency parsers}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2018},
}
Figure