Bayesian Inference for PCFGs via Markov Chain Monte Carlo

Proceedings of NAACL HLT 2007, pages 139–146, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics Bayesian Inference for PCFGs via Markov chain Monte Carlo Mark Johnson Cognitive and Linguistic Sciences Brown University Mark Johnson@brown.edu Thomas L. Griffiths Department of Psychology University of California, Berkeley Tom Griffiths@berkeley.edu Sharon Goldwater Department of Linguistics Stanford University sgwater@stanford.edu Abstract This paper presents two Markov chain Monte Carlo (MCMC) algorithms for Bayesian inference of probabilistic con- text free grammars (PCFGs) from ter- minal strings, providing an alternative to maximum-likelihood estimation using the Inside-Outside algorithm. We illus- trate these methods by estimating a sparse grammar describing the morphology of the Bantu language Sesotho, demonstrat- ing that with suitable priors Bayesian techniques can infer linguistic structure in situations where maximum likelihood methods such as the Inside-Outside algo- rithm only produce a trivial grammar. 1 Introduction The standard methods for inferring the parameters of probabilistic models in computational linguistics are based on the principle of maximum-likelihood esti- mation; for example, the parameters of Probabilistic Context-Free Grammars (PCFGs) are typically es- timated from strings of terminals using the Inside- Outside (IO) algorithm, an instance of the Ex- pectation Maximization (EM) procedure (Lari and Young, 1990). However, much recent work in ma- chine learning and statistics has turned away from maximum-likelihood in favor of Bayesian methods, and there is increasing interest in Bayesian methods in computational linguistics as well (Finkel et al., 2006). This paper presents two Markov chain Monte Carlo (MCMC) algorithms for inferring PCFGs and their parses from strings alone. These can be viewed as Bayesian alternatives to the IO algorithm. The goal of Bayesian inference is to compute a distribution over plausible parameter values. This “posterior” distribution is obtained by combining the likelihood with a “prior” distribution P(θ) over pa- rameter values θ. In the case of PCFG inference θ is the vector of rule probabilities, and the prior might assert a preference for a sparse grammar (see be- low). The posterior probability of each value of θ is given by Bayes’ rule: P(θ|D) ∝ P(D|θ)P(θ). (1) In principle Equation 1 defines the posterior prob- ability of any value of θ, but computing this may not be tractable analytically or numerically. For this reason a variety of methods have been developed to support approximate Bayesian inference. One of the most popular methods is Markov chain Monte Carlo (MCMC), in which a Markov chain is used to sam- ple from the posterior distribution. This paper presents two new MCMC algorithms for inferring the posterior distribution over parses and rule probabilities given a corpus of strings. The first algorithm is a component-wise Gibbs sampler which is very similar in spirit to the EM algo- rithm, drawing parse trees conditioned on the cur- rent parameter values and then sampling the param- eters conditioned on the current set of parse trees. The second algorithm is a component-wise Hastings sampler that “collapses” the probabilistic model, in- tegrating over the rule probabilities of the PCFG, with the goal of speeding convergence. Both …

Content truncated to 500 words