Collapsed Variational Bayesian Inference for PCFGs

Proceedings of the Seventeenth Conference on Computational Natural Language Learning, pages 173–182, Sofia, Bulgaria, August 8-9 2013. c⃝2013 Association for Computational Linguistics Collapsed Variational Bayesian Inference for PCFGs Pengyu Wang Department of Computer Science University of Oxford Oxford, OX1 3QD, United Kingdom Pengyu.Wang@cs.ox.ac.uk Phil Blunsom Department of Computer Science University of Oxford Oxford, OX1 3QD, United Kingdom Phil.Blunsom@cs.ox.ac.uk Abstract This paper presents a collapsed variational Bayesian inference algorithm for PCFGs that has the advantages of two dominant Bayesian training algorithms for PCFGs, namely variational Bayesian inference and Markov chain Monte Carlo. In three kinds of experiments, we illustrate that our al- gorithm achieves close performance to the Hastings sampling algorithm while using an order of magnitude less training time; and outperforms the standard variational Bayesian inference and the EM algorithms with similar training time. 1 Introduction Probabilistic context-free grammars (PCFGs) are commonly used in parsing and grammar induction systems (Johnson, 1998; Collins, 1999; Klein and Manning, 2003; Matsuzaki et al., 2005). The tra- ditional method for estimating the parameters of PCFGs from terminal strings is the inside-outside (IO) algorithm (Baker, 1979). As a special in- stance of the Expectation-Maximization (EM) al- gorithm (Dempster et al., 1977), based on the prin- ciple of maximum-likelihood estimation (MLE), the standard IO algorithm learns relatively uni- form probability distributions for grammars, while the true distributions can be highly skewed (John- son et al., 2007). In order to encourage sparse grammars and avoid overfitting, recent research for training PCFGs has drifted away from MLE in favor of Bayesian inference algorithms that make either deterministic or stochastic approximations (Kurihara and Sato, 2006; Johnson et al., 2006; Johnson et al., 2007). Variational Bayesian inference (VB) (Kurihara and Sato, 2006) for PCFGs extends EM and places no constraints when updating parameters in the M step. By minimising the divergence between the true posterior and an approximate one in which the strong dependencies between the parameters and latent variables are broken, this determinis- tic algorithm efficiently converges to an inaccu- rate and only locally optimal solution like EM. Alternatively, Johnson et al. (2007) proposed two Markov Chain Monte Carlo algorithms for PCFGs that can reach the true posterior after convergence. However, it is often difficult to diagnose a sam- pler’s convergence, and mixing is notoriously slow for distributions with tightly coupled hidden vari- ables such as PCFGs, especially when the data sets are large. Therefore, there remains a challenge for more efficient, but also accurate and deterministic inference algorithms for PCFGs. In this paper, we present a collapsed variational Bayesian inference (CVB) algorithm for PCFGs. It has the same computational complexity as the standard variational Bayesian inference, but offers almost the same performance as the stochastic al- gorithms due to its weak assumptions. The idea of operating VB in the collapsed space was proposed by Teh et al. (2007) and Sung et al. (2008), and it was successfully applied to “bag-of-words” mod- els such as latent Dirichlet allocation (LDA) (Teh et al., 2007) and mixture of Gaussian (Sung et …

Content truncated to 500 words