Strength in Numbers: Averaging and Clustering Effects in Mixture of Experts for Graph-Based Dependency Parsing

Xudong Zhang, Joseph Le Roux, Thierry CharnoisACL 2021

TL;DR

This paper explores how combining multiple dependency parsers (a "mixture of experts" or MoE) can improve accuracy and robustness. They demonstrate that simply averaging predictions from multiple parsers ("averaging effect") significantly reduces variance and boosts performance. While a more complex "clustering effect" aims to assign specific parsers to specific inputs, it proves difficult to train effectively and offers limited gains over simple averaging.

What Problem Does This Paper Address?

Dependency parsing, a core task in Natural Language Processing (NLP), aims to identify the grammatical relationships between words in a sentence. While individual parsers have become quite sophisticated, they often struggle with certain sentence structures or exhibit high variance in their predictions, meaning their performance can fluctuate significantly. Combining multiple parsers, a common technique in machine learning, offers a way to leverage the strengths of different models and mitigate their weaknesses. However, understanding why these combinations work and how to best train them remains an open question, particularly for graph-based dependency parsers. This paper investigates two key mechanisms within a mixture of experts framework: averaging and clustering, to understand their impact on parsing performance.

Methods

The authors frame dependency parser combinations as a probabilistic mixture model. They introduce two key concepts:

  • Averaging Effect: This is the simplest form of combination, where the predictions of multiple parsers are averaged. This is shown to be beneficial for reducing variance and improving overall accuracy.
  • Clustering Effect: This more advanced approach uses a "gating network" to learn which expert parser is best suited for a given input sentence. This allows the model to dynamically assign more weight to specific parsers based on the input's characteristics.

They also propose an efficient decoding method called LMBR (Labeled Minimum Bayesian Risk) that combines arc and label predictions from multiple experts. For training, they adapt an EM-inspired approach to handle the challenges of learning the gating network, particularly to avoid "over-specialization" where one expert dominates.

Datasets

The paper evaluates their methods on two standard datasets for dependency parsing:

  • English Penn Treebank (PTB): A widely used dataset for English.
  • CoNLL09 Chinese dataset: A dataset for Chinese dependency parsing.

Key Insights and Ideas

  • Averaging is King (Mostly): Simply averaging the predictions of multiple parsers consistently improves performance and reduces variance. This "averaging effect" is robust and easy to implement.
  • Clustering is Tricky: While the idea of assigning specific parsers to specific inputs (clustering) is appealing, it's difficult to train effectively. The authors found that achieving good initialization is crucial, and even then, the gains over simple averaging are often marginal, especially when many experts are involved.
  • Variance Reduction is Key: The primary benefit of averaging comes from reducing the variance in predictions. This leads to more stable and reliable parsing results.
  • State-of-the-Art Achieved: By combining their MoE approach with strong individual parsers (both first-order and second-order), the authors achieve state-of-the-art results on the tested datasets.
  • Overfitting to Specific Inputs: The clustering mechanism can lead to "over-specialization," where the gating network learns to rely too heavily on a few experts for specific types of inputs, potentially harming overall generalization.

Key Results

  • Improved Accuracy: Averaging models consistently showed improved UAS (Unlabeled Attachment Score) and LAS (Labeled Attachment Score) compared to single parsers. For example, on PTB, averaging with 6 experts improved LAS by around 0.2-0.6% absolute over single experts.
  • Reduced Variance: The experiments demonstrated a clear reduction in variance as the number of experts increased, aligning with theoretical predictions. Figure 1 shows this log-variance decrease is nearly linear with log K.
  • State-of-the-Art Performance: The proposed methods, particularly when combined with BERT embeddings (BFOP, BSOP), achieved state-of-the-art results on the PTB and CoNLL09 datasets. For instance, on PTB test sets, their BFOP and BSOP models with 6 experts achieved UAS scores around 96.4-96.6.
  • Clustering Gains are Modest: Clustering provided only a small absolute improvement (0.01%-0.06%) on UAS and LAS on development sets, with some exceptions.

Limitations and Future Work

  • Clustering Training Difficulty: The authors acknowledge the difficulty in training the clustering mechanism effectively, particularly the need for good initialization and the risk of over-specialization.
  • Overparameterization: The use of many experts can lead to a large number of parameters, raising questions about redundancy.
  • Future Work: The authors suggest investigating the "subnetwork hypothesis" to see if distillation can yield smaller, equally performant models. They also mention exploring more sophisticated mixture models (e.g., infinite mixtures) and further research into the benefits of clustering.

Summary updated

BibTeX
@inproceedings{zhang2021strength,
  author = {Xudong Zhang and Joseph Le Roux and Thierry Charnois},
  title = {{Strength in Numbers: Averaging and Clustering Effects in Mixture of Experts for Graph-Based Dependency Parsing}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2021},
}
Figure