📄 Bayesian Inference for PCFGs via Markov Chain Monte Carlo

Summary

The paper offers Bayesian alternatives to the usual maximum-likelihood way of learning probabilistic context-free grammars (PCFGs) from unannotated strings with the Inside-Outside (IO) algorithm. The authors put a product of Dirichlet priors on rule probabilities and derive two Markov chain Monte Carlo samplers. The first is a Gibbs sampler that alternates between drawing parse trees given the current rule probabilities and drawing new probabilities given those trees. The second is a Hastings sampler that integrates the rule probabilities out ("collapsed") so that it works directly on parses. Both rely on a dynamic-programming routine that samples trees from an inside chart. As a test case, they induce morphological segmentations of verbs in Sesotho, an agglutinating Bantu language, using a highly ambiguous grammar. IO collapses to a degenerate solution that treats each word as one morpheme. With a sparsity-favouring prior, the Hastings sampler recovers meaningful structure. This matters because it shows that priors can steer unsupervised grammar induction where pure likelihood maximisation fails.

Key points

• The paper presents two MCMC algorithms for PCFG inference from strings alone:
  • a component-wise Gibbs sampler over trees and θ;
  • a collapsed component-wise Hastings sampler that marginalises θ.
• Dirichlet priors are conjugate to PCFG tree distributions, so the posterior over θ given parses is again Dirichlet. Its parameters are the rule counts plus α.
• The Sesotho verb grammar has 81,755 productions, roughly 20 times more than the number of training strings. This makes estimation heavily underconstrained.
• IO converges to the trivial analysis Word → V with probability 1, which scores 0 on segmentation.
• With a uniform α below about 10⁻², the Hastings sampler finds nontrivial structure. At α = 10⁻⁵ it achieves an f-score of 0.75 on morphemes (ignoring labels), and 0.54 of words are segmented entirely correctly. Results stay good across several orders of magnitude of α.

Interesting ideas

• I1. Sampling whole trees from an inside chart. The method builds the standard inside table and then descends top-down, choosing expansions in proportion to their inside scores. This yields exact samples from the parse distribution, which is useful anywhere a CKY-style chart already exists, such as segmentation or tagging lattices.
• I2. Gibbs sampling as a "stochastic EM." The method replaces the E-step with sampling parses and the M-step with sampling parameters. Since parses are independent given θ, this keeps EM's easy parallelism while giving a posterior rather than a single point estimate.
• I3. Annealing and jittering for convergence. One trick is raising the parse distribution to the power 1/τ, with τ starting near 5 and lowered to 1. Another is perturbing IO's initial estimate. Both are cheap, model-agnostic tricks for escaping poor early states in other EM or sampling setups.
• I4. Warning about naive MAP-EM with tiny α. Subtracting (1 − α) from expected counts can push many rule probabilities to zero, leaving some training strings with no parse at all. This is a useful caution when adding sparse Dirichlet priors to an existing EM pipeline.
• I5. Sparsity as the key inductive bias. A grammar that encodes only structural templates, together with a strong preference for few active rules, was enough to turn a degenerate solution into a sensible one. The same design pattern could suit unsupervised morphology for other agglutinative languages.