Variance of Average Surprisal: A Better Predictor for Quality of Grammar from Unsupervised PCFG Induction

Lifeng Jin, William SchulerACL 2019 · OpenReview

Abstract

Unsupervised grammar induction aims to learn hierarchical structures from raw text without human-labeled examples. Traditionally, data likelihood is used for model selection, but it often fails to correlate with parsing accuracy. This paper demonstrates that Variance of Average Surprisal (VAS) is a superior predictor of grammar quality, significantly improving accuracy across dozens of languages by distinguishing between content and function words.

Introduction

Unsupervised grammar induction is the task of learning the hierarchical structure of a language—represented as trees—from raw text alone. This process is crucial for understanding how linguistic structures can be acquired without explicit supervision, potentially mirroring aspects of human language acquisition.

A constituency tree example, illustrating the hierarchical structure that unsupervised grammar induction aims to recover.

Traditionally, researchers have relied on data likelihood—the probability a model assigns to the observed strings—as the primary objective for optimization and model selection. However, a "likelihood gap" exists: models can achieve high likelihood by accurately predicting word sequences while producing linguistically nonsensical structures. This suggests that maximizing probability alone is insufficient to capture the underlying logic of human grammar.

Methodology: Beyond Data Likelihood

The authors evaluate six predictors to identify which best correlates with human-like parsing accuracy (measured by constituent recall):

  1. Data Likelihood (LL): The standard baseline.
  2. Right-branching score: Preference for right-growing trees.
  3. Rule complexity: The number of unique grammar rules.
  4. Average stack depth: Memory requirements for parsing.
  5. Zipf likelihood ratio: Adherence of rule distributions to power laws.
  6. Variance of Average Surprisal (VAS): The proposed metric.

Surprisal is defined as the negative log-probability of a sentence. Average Surprisal is this value normalized by sentence length. VAS measures the variance of these average surprisal values across a corpus. The intuition is that natural languages contain a mix of "boring" sentences (dominated by high-frequency function words like "the" or "is") and "dense" sentences (rich in rare content words). A linguistically sound grammar should distinguish these types, resulting in high variance across the corpus.

Experiments and Results

The study utilized a broad multilingual dataset, including 12 development languages and 25 test languages from diverse families (e.g., Indo-European, Uralic, Sino-Tibetan, Austronesian).

Parsing Accuracy

VAS demonstrated a significantly stronger Pearson correlation with parsing accuracy (0.627) compared to data likelihood (0.588) on the development set. When used to select the best model from 30 random initializations, VAS provided an average gain of 4.03 points in recall across the 25 test languages compared to using likelihood.

Recall gains (Top 1 diff) for VAS over Likelihood across 25 test languages, showing consistent improvements in most cases.

Typology and Linguistic Categories

VAS also proved superior in predicting word-order typology (e.g., Verb-Object vs. Object-Verb). A VAS-based approach achieved a 69.2 Macro-F1 score, far exceeding the 42.9 achieved by likelihood-based methods. This success stems from the fact that models with high VAS are better at isolating function words into specific categories, creating a sharper contrast between functional and content-heavy sentences.

Conclusion

The success of VAS suggests that human language acquisition might be driven by a bias toward identifying functional/content distinctions rather than just raw statistical co-occurrence. While VAS is currently used as a post-hoc selection metric, future work could involve integrating it directly into the training objective of both PCFGs and modern neural unsupervised parsers.

Summary of: Jin, L., & Schuler, W. (2019). Variance of Average Surprisal: A Better Predictor for Quality of Grammar from Unsupervised PCFG Induction. ACL.

Summary updated

BibTeX
@inproceedings{jin2019variance,
  author = {Lifeng Jin and William Schuler},
  title = {{Variance of Average Surprisal: A Better Predictor for Quality of Grammar from Unsupervised PCFG Induction}},
  booktitle = {Annual Meeting of the Association for Computational Linguistics},
  year = {2019},
  url = {https://openreview.net/forum?id=BBrb09sB9xq},
}
Figure