The effect of non-tightness on Bayesian estimation of PCFGs

The effect of non-tightness on Bayesian estimation of PCFGs Shay B. Cohen Department of Computer Science Columbia University scohen@cs.columbia.edu Mark Johnson Department of Computing Macquarie University mark.johnson@mq.edu.au Abstract Probabilistic context-free grammars have the unusual property of not always defining tight distributions (i.e., the sum of the “probabili- ties” of the trees the grammar generates can be less than one). This paper reviews how this non-tightness can arise and discusses its im- pact on Bayesian estimation of PCFGs. We begin by presenting the notion of “almost ev- erywhere tight grammars” and show that lin- ear CFGs follow it. We then propose three dif- ferent ways of reinterpreting non-tight PCFGs to make them tight, show that the Bayesian es- timators in Johnson et al. (2007) are correct under one of them, and provide MCMC sam- plers for the other two. We conclude with a discussion of the impact of tightness empiri- cally. 1 Introduction Probabilistic Context-Free Grammars (PCFGs) play a special role in computational linguistics because they are perhaps the simplest probabilistic models of hierarchical structures. Their simplicity enables us to mathematically analyze their properties to a de- tail that would be difficult with linguistically more accurate models. Such analysis is useful because it is reasonable to expect more complex models to ex- hibit similar properties as well. The problem of inferring PCFG rule probabili- ties from training data consisting of yields or strings alone is interesting from both cognitive and engi- neering perspectives. Cognitively it is implausible that children can perceive the parse trees of the lan- guage they are learning, but it is more reasonable to assume that they can obtain the terminal strings or yield of these trees. Unsupervised methods for learning a grammar from terminal strings alone is also interesting from an engineering perspective be- cause such training data is cheap and plentiful, while the manually parsed data required by supervised methods are expensive to produce and relatively rare. Cohen and Smith (2012) show that inferring PCFG rule probabilities from strings alone is com- putationally intractable, so we should not expect to find an efficient, general-purpose algorithm for the unsupervised problem. Instead, approximation algo- rithms are standardly used. For example, the Inside- Outside (IO) algorithm efficiently implements the Expectation-Maximization (EM) procedure for ap- proximating a Maximum Likelihood estimator (Lari and Young, 1990). Bayesian estimators for PCFG rule probabilities have also been attracting attention because they provide a theoretically-principled way of incorporating prior information. Kurihara and Sato (2006) proposed a Variational Bayes estima- tor based on a mean-field approximation, and John- son et al. (2007) proposed MCMC samplers for the posterior distribution over rule probabilities and the parse trees of the training data strings. PCFGs have the interesting property (which we expect most linguistically more realistic models to also possess) that the distributions they define are not always properly normalized or “tight”. In a non-tight PCFG the partition function (i.e., sum of the “probabilities” of all the trees generated by the PCFG) is less than one. (Booth and Thompson, …

Content truncated to 500 words