Bayesian Inference for PCFGs via Markov Chain Monte Carlo

Mark Johnson, Thomas L. Griffiths, Sharon GoldwaterNAACL 2007 · OpenReview

Abstract

Traditional unsupervised induction of Probabilistic Context-Free Grammars (PCFGs) often relies on the Inside-Outside (IO) algorithm, a form of Expectation-Maximization. However, IO frequently converges to trivial solutions that fail to capture meaningful linguistic structure. This paper presents a Bayesian framework using Markov Chain Monte Carlo (MCMC) techniques—specifically Gibbs and collapsed Hastings samplers—to incorporate sparsity-inducing Dirichlet priors. We demonstrate that this approach successfully learns complex morphological structures in Sesotho, where standard maximum-likelihood methods fail.

Introduction

Unsupervised grammar induction is a fundamental challenge in computational linguistics. The standard approach, the Inside-Outside (IO) algorithm, seeks the Maximum Likelihood Estimate (MLE). While theoretically sound, MLE often favors "trivial" grammars in practice. For instance, in morphological tasks, it may treat every word as an indivisible unit rather than identifying recurring prefixes or roots, as the latter doesn't necessarily increase the likelihood of the observed data without a preference for simplicity.

Methodology

The authors propose a Bayesian alternative that combines the data likelihood with a prior distribution. This prior, typically a Dirichlet distribution with parameter $\alpha$, allows the model to favor sparse grammars where only a small subset of possible rules have significant probability.

Two MCMC algorithms are introduced:

  1. Component-wise Gibbs Sampler: This alternates between sampling parse trees for the corpus given rule probabilities and sampling new rule probabilities given the trees.
  2. Collapsed Hastings Sampler: This integrates out the rule probabilities, sampling parse trees directly from the posterior. This "collapsed" approach often converges faster by reducing the dimensionality of the search space.

The dependencies between variables in these models are represented in the following Bayes net:

Bayes net representation of dependencies among the variables in a PCFG.

Experimental Evaluation

The methods were evaluated on the morphological segmentation of Sesotho verbs from the CHILDES database. The dataset consisted of 2,283 unsegmented verb types. A manually constructed CFG with over 81,000 productions provided a highly ambiguous search space.

The key finding was the importance of the Dirichlet prior parameter $\alpha$. When $\alpha < 1$, the model is biased toward sparsity, effectively penalizing the use of excessive rules. This bias prevents the model from falling into the trivial solutions typical of MLE.

Results

The Bayesian Hastings sampler significantly outperformed the IO algorithm. While the IO algorithm produced an f-score of 0 (collapsing to the trivial grammar), the Bayesian approach achieved an unlabeled f-score of 0.75 and an exact word match accuracy of 0.54.

Accuracy of morphological segmentations of Sesotho verbs as a function of the Dirichlet prior parameter $\alpha$.

As shown in the figure above, performance is remarkably robust across several orders of magnitude for $\alpha$, indicating that even a small bias toward sparsity is sufficient to guide the model toward linguistically plausible structures.

Conclusion

By adopting a Bayesian perspective and utilizing MCMC for inference, we can overcome the limitations of maximum-likelihood estimation in grammar induction. The use of sparsity-inducing priors is crucial for discovering meaningful structure in highly ambiguous data. Future work will explore applying these techniques to more complex syntactic models beyond basic PCFGs.

Summary updated

Abstract

Mark Johnson, Thomas Griffiths, Sharon Goldwater. Human Language Technologies 2007: The Conference of the North American Chapter of the Association for Computational Linguistics; Proceedings of the Main Conference. 2007.
BibTeX
@inproceedings{johnson2007bayesian,
  author = {Mark Johnson and Thomas L. Griffiths and Sharon Goldwater},
  title = {{Bayesian Inference for PCFGs via Markov Chain Monte Carlo}},
  booktitle = {Conference of the North American Chapter of the Association for Computational Linguistics},
  year = {2007},
  url = {https://openreview.net/forum?id=BJEP8QWuWS},
}
Figure