Grammar induction from (lots of) words alone

John K Pate, Mark JohnsonCOLING 2016

TL;DR

This paper tackles the challenge of teaching computers to understand sentence structure (grammar induction) using only raw text, mimicking how children learn. They demonstrate that with enough data and scalable algorithms, this is feasible and surprisingly robust to initial assumptions, suggesting a more principled approach to computational language acquisition.

What Problem Does This Paper Address?

Learning grammar from scratch is a fundamental problem in linguistics and AI, mirroring how children acquire language without explicit instruction. Traditional approaches to grammar induction often rely on pre-processed data, like part-of-speech tags, which makes them less relevant to human learning. This paper aims to bridge this gap by focusing on "grammar induction from words alone," meaning the model only sees sequences of words and must infer the underlying syntactic structure. A key challenge here is data sparsity: with limited data, it's hard to learn reliable patterns. Previous work has addressed this with specialized initialization techniques and by using richer input. This paper questions whether these complexities are necessary if we can leverage large amounts of data and employ efficient inference methods.

Methods

The core of this work lies in developing and evaluating scalable algorithms for Probabilistic Context-Free Grammar (PCFG) inference. They adapt existing Variational Bayesian (VB) inference techniques, originally designed for Latent Dirichlet Allocation (LDA) topic models, to the PCFG setting. Specifically, they explore:

  • Batch VB: A standard approach that processes the entire dataset to update parameters.
  • Streaming VB: A novel algorithm that makes a single pass through the data, processing it in minibatches. This is inspired by streaming LDA algorithms.
  • Stochastic VB: Another novel algorithm that uses minibatches to take steps towards optimizing the model's objective function, inspired by stochastic VB for LDA.
  • Collapsed VB: An existing algorithm for PCFGs that integrates out model parameters for a tighter inference bound.

A key aspect is their use of the Dependency Model with Valence (DMV) as their underlying grammar model, reformulated as a PCFG. They also investigate the impact of initialization strategies, comparing a "harmonic initialization" (which biases rules based on adjacent word co-occurrence) with a simpler "uniform initialization."

Datasets

The experiments were conducted on two corpora of spontaneous speech transcripts:

  • Switchboard: A portion of the Penn Treebank, converted to dependency annotations. Sentences were filtered to be between 4 and 15 words long.
  • Fisher: A corpus of telephone transcripts, also filtered to sentences between 4 and 15 words.

These datasets are notable for containing disfluencies, making them more challenging than clean, edited text. The combined vocabulary is 40,597 word types.

Key Insights and Ideas

  • Data Trumps Initialization: The most significant finding is that with a large enough dataset (millions of words), the choice of initialization (harmonic vs. uniform) has minimal impact on the final grammar quality. This suggests that learning from abundant data can overcome the need for complex, potentially brittle, initialization heuristics.
  • Scalability is Key: Algorithms that can efficiently process large datasets (streaming and stochastic VB) perform comparably to or better than batch methods, demonstrating the importance of computational efficiency for real-world language acquisition scenarios.
  • Harmonic Initialization's Limited Role: While harmonic initialization showed some early benefits, especially for streaming and stochastic VB, its advantage diminishes as training progresses. This suggests it might capture non-syntactic regularities that are useful early on but are eventually superseded by true syntactic learning.
  • Mimicking Child Learning: By focusing on words alone and large datasets, the approach moves closer to a principled model of how children learn language, without relying on external linguistic annotations.

Key Results

  • Performance Convergence: All scalable algorithms (streaming, stochastic, and collapsed VB) steadily improve or stabilize as inference proceeds over large datasets, achieving similar predictive log probabilities and directed attachment accuracies.
  • Initialization Insensitivity: For most algorithms and at later stages of training, there was no clear advantage to harmonic initialization. In some cases, it even slightly worsened performance.
  • Algorithm Differences: Collapsed VB achieved the best predictive log probability, likely due to its tighter inference bound. Streaming VB showed a temporary drop in predictive probability with harmonic initialization but later achieved a small improvement in parse accuracy. Stochastic VB performed well with small datasets, possibly due to its conservative gradient-based updates.
  • Batch VB Limitations: Batch VB required many iterations to converge on large datasets, making it computationally infeasible for the full training corpus.

Limitations and Future Work

  • Model Simplicity: The paper uses a PCFG-based model (DMV). Future work could explore richer models of syntax.
  • Distributed Representations: The authors suggest that future work should investigate learning distributed word representations jointly with syntactic structure.
  • Computational Effort: While scalable algorithms are explored, the paper notes that batch VB is computationally intensive for large datasets. Further optimization of inference algorithms could be beneficial.
  • Initialization Nuances: While largely insensitive, there were minor differences in initialization's impact, particularly early in training. Further exploration of what these early patterns represent could be valuable.

Summary updated

BibTeX
@inproceedings{pate2016grammar,
  author = {John K Pate and Mark Johnson},
  title = {{Grammar induction from (lots of) words alone}},
  booktitle = {International Conference on Computational Linguistics},
  year = {2016},
}
Figure