The Infinite PCFG Using Hierarchical Dirichlet Processes

Proceedings of the 2007 Joint Conference on Empirical Methods in Natural Language Processing and Computational Natural Language Learning, pp. 688–697, Prague, June 2007. c⃝2007 Association for Computational Linguistics The Infinite PCFG using Hierarchical Dirichlet Processes Percy Liang Slav Petrov Michael I. Jordan Dan Klein Computer Science Division, EECS Department University of California at Berkeley Berkeley, CA 94720 {pliang, petrov, jordan, klein}@cs.berkeley.edu Abstract We present a nonparametric Bayesian model of tree structures based on the hierarchical Dirichlet process (HDP). Our HDP-PCFG model allows the complexity of the grammar to grow as more training data is available. In addition to presenting a fully Bayesian model for the PCFG, we also develop an ef- ficient variational inference procedure. On synthetic data, we recover the correct gram- mar without having to specify its complex- ity in advance. We also show that our tech- niques can be applied to full-scale parsing applications by demonstrating its effective- ness in learning state-split grammars. 1 Introduction Probabilistic context-free grammars (PCFGs) have been a core modeling technique for many as- pects of linguistic structure, particularly syntac- tic phrase structure in treebank parsing (Charniak, 1996; Collins, 1999). An important question when learning PCFGs is how many grammar symbols to allocate to the learning algorithm based on the amount of available data. The question of “how many clusters (symbols)?” has been tackled in the Bayesian nonparametrics literature via Dirichlet process (DP) mixture mod- els (Antoniak, 1974). DP mixture models have since been extended to hierarchical Dirichlet processes (HDPs) and HDP-HMMs (Teh et al., 2006; Beal et al., 2002) and applied to many different types of clustering/induction problems in NLP (Johnson et al., 2006; Goldwater et al., 2006). In this paper, we present the hierarchical Dirich- let process PCFG (HDP-PCFG). a nonparametric Bayesian model of syntactic tree structures based on Dirichlet processes. Specifically, an HDP-PCFG is defined to have an infinite number of symbols; the Dirichlet process (DP) prior penalizes the use of more symbols than are supported by the training data. Note that “nonparametric” does not mean “no parameters”; rather, it means that the effective num- ber of parameters can grow adaptively as the amount of data increases, which is a desirable property of a learning algorithm. As models increase in complexity, so does the un- certainty over parameter estimates. In this regime, point estimates are unreliable since they do not take into account the fact that there are different amounts of uncertainty in the various components of the pa- rameters. The HDP-PCFG is a Bayesian model which naturally handles this uncertainty. We present an efficient variational inference algorithm for the HDP-PCFG based on a structured mean-field ap- proximation of the true posterior over parameters. The algorithm is similar in form to EM and thus in- herits its simplicity, modularity, and efficiency. Un- like EM, however, the algorithm is able to take the uncertainty of parameters into account and thus in- corporate the DP prior. Finally, we develop an extension of the HDP- PCFG for grammar refinement (HDP-PCFG-GR). Since treebanks generally …

Content truncated to 500 words