Variational Inference for Adaptor Grammars

Human Language Technologies: The 2010 Annual Conference of the North American Chapter of the ACL, pages 564–572, Los Angeles, California, June 2010. c⃝2010 Association for Computational Linguistics Variational Inference for Adaptor Grammars Shay B. Cohen School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA scohen@cs.cmu.edu David M. Blei Computer Science Department Princeton University Princeton, NJ 08540, USA blei@cs.princeton.edu Noah A. Smith School of Computer Science Carnegie Mellon University Pittsburgh, PA 15213, USA nasmith@cs.cmu.edu Abstract Adaptor grammars extend probabilistic context-free grammars to define prior dis- tributions over trees with “rich get richer” dynamics. Inference for adaptor grammars seeks to find parse trees for raw text. This paper describes a variational inference al- gorithm for adaptor grammars, providing an alternative to Markov chain Monte Carlo methods. To derive this method, we develop a stick-breaking representation of adaptor grammars, a representation that enables us to define adaptor grammars with recursion. We report experimental results on a word segmentation task, showing that variational inference performs comparably to MCMC. Further, we show a significant speed-up when parallelizing the algorithm. Finally, we report promising results for a new application for adaptor grammars, dependency grammar induction. 1 Introduction Recent research in unsupervised learning for NLP focuses on Bayesian methods for probabilistic gram- mars (Goldwater and Griffiths, 2007; Toutanova and Johnson, 2007; Johnson et al., 2007). Such meth- ods have been made more flexible with nonparamet- ric Bayesian (NP Bayes) methods, such as Dirichlet process mixture models (Antoniak, 1974; Pitman, 2002). One line of research uses NP Bayes meth- ods on whole tree structures, in the form of adaptor grammars (Johnson et al., 2006; Johnson, 2008b; Johnson, 2008a; Johnson and Goldwater, 2009), in order to identify recurrent subtree patterns. Adaptor grammars provide a flexible distribu- tion over parse trees that has more structure than a traditional context-free grammar. Adaptor gram- mars are used via posterior inference, the compu- tational problem of determining the posterior distri- bution of parse trees given a set of observed sen- tences. Current posterior inference algorithms for adaptor grammars are based on MCMC sampling methods (Robert and Casella, 2005). MCMC meth- ods are theoretically guaranteed to converge to the true posterior, but come at great expense: they are notoriously slow to converge, especially with com- plex hidden structures such as syntactic trees. John- son (2008b) comments on this, and suggests the use of variational inference as a possible remedy. Variational inference provides a deterministic al- ternative to sampling. It was introduced for Dirich- let process mixtures by Blei and Jordan (2005) and applied to infinite grammars by Liang et al. (2007). With NP Bayes models, variational methods are based on the stick-breaking representation (Sethu- raman, 1994). Devising a stick-breaking represen- tation is a central challenge to using variational in- ference in this setting. The rest of this paper is organized as follows. In §2 we describe a stick-breaking representation of adaptor grammars, which enables variational infer- ence (§3) and a well-defined incorporation of recur- sion into adaptor grammars. In §4 we give …

Content truncated to 500 words