On the Utility of Curricula in Unsupervised Learning of Probabilistic Grammars

Kewei Tu, Vasant G. Honavar

Abstract

Unsupervised grammar induction remains a fundamental challenge in natural language processing due to the prevalence of local optima during optimization. This paper investigates the efficacy of curriculum learning through the lens of the Incremental Construction Hypothesis (ICH). By presenting training data in increasing order of complexity, learners can sequentially acquire grammatical sub-structures. Our results demonstrate that sentence length serves as a robust proxy for an ideal curriculum, yielding significant improvements in both parsing accuracy and convergence speed within the Dependency Model with Valence (DMV) framework.

Introduction

Learning the structural rules of a language without labeled examples is a classic "chicken-and-egg" problem: parsing requires a grammar, but learning a grammar typically requires parsed data. In unsupervised settings, models often converge on "local minima"—mathematically plausible but linguistically incorrect rule sets. While the intuition of "starting small" (curriculum learning) has been observed to help, the underlying mechanism has remained poorly understood. This research formalizes why curricula work and how they can be effectively implemented for grammar induction.

The Incremental Construction Hypothesis (ICH)

The authors propose the Incremental Construction Hypothesis (ICH) to explain the success of curriculum learning. The hypothesis posits that a complex grammar is composed of discrete sub-structures (rules). An effective curriculum facilitates learning by:

  1. Presenting data corresponding to a simpler "sub-grammar" first.
  2. Ensuring early rules are a strict subset of the final target grammar.
  3. Maintaining consistent probability ratios between rules as the grammar expands.

By mastering basic building blocks (e.g., noun-phrase modification) in simple contexts, the model is better equipped to identify these patterns when they appear in more complex, longer sentences.

Experimental Methodology

The study utilizes the Dependency Model with Valence (DMV), a standard for unsupervised parsing. The researchers compared several strategies:

  • Plain EM: Standard Expectation-Maximization without data ordering.
  • Ideal Curricula: Manually ordered based on known target grammar rules (used in synthetic tests).
  • Length-Based Curricula: A practical proxy using sentence length as the ordering metric.
  • Random Curricula: A control group using random batching.

Experiments were conducted on both synthetic data (generated from a known WSJ30-based grammar) and real-world data (the WSJ30 corpus from the Penn Treebank). To prevent the model from becoming "brittle" or over-fitting to simplified early stages, the authors implemented dynamic smoothing and early stopping.

Key Results and Analysis

Performance Gains

On synthetic data, the theoretical "Ideal" and practical "Length-based" curricula significantly outperformed the baseline. While Plain EM achieved an F-score of approximately 46%, curriculum-based methods reached 54-56%. This confirms that structured discovery of rules leads to a more accurate global optimum.

F-score comparison of various curriculum strategies against the Plain EM baseline.

Convergence and Efficiency

In real-world tests on the WSJ30 corpus, curriculum learning demonstrated superior efficiency. Models using length-based ordering reached higher accuracy levels significantly faster than the baseline. The research also highlighted a "Less is More" paradox: curricula with too many stages can lead to over-fitting on partial grammars, making it difficult for the model to incorporate complex rules later. Optimal results were found when introducing at least 10 new sentences per curriculum stage.

Learning curves showing F-score progression over EM iterations for different curriculum setups.

Length as a Proxy

A major finding is that sentence length is a highly effective proxy for structural complexity. The authors found a high correlation (Kendall’s $\tau \approx 0.76$) between length-based ordering and their theoretically "ideal" rule-based ordering, explaining why simple length-based curricula are so effective in practice.

Conclusion

The Incremental Construction Hypothesis provides a robust framework for understanding curriculum learning in structured tasks. By viewing the curriculum as a sequence of sub-grammar discoveries rather than just a mathematical smoothing technique, researchers can better design training regimes for unsupervised models. Future work may explore "active" curricula, where models dynamically request data to resolve specific grammatical uncertainties.

Summary updated

BibTeX
@inproceedings{tu2011utility,
  author = {Kewei Tu and Vasant G. Honavar},
  title = {{On the Utility of Curricula in Unsupervised Learning of Probabilistic Grammars}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2011},
  doi = {10.5591/978-1-57735-516-8/ijcai11-256},
}
Figure