Online Adaptor Grammars with Hybrid Inference

Online Adaptor Grammars with Hybrid Inference Ke Zhai Computer Science and UMIACS University of Maryland College Park, MD USA zhaike@cs.umd.edu Jordan Boyd-Graber Computer Science University of Colorado Boulder, CO USA jordan.boyd.graber@colorado.edu Shay B. Cohen School of Informatics University of Edinburgh Edinburgh, Scotland, UK scohen@inf.ed.ac.uk Abstract Adaptor grammars are a flexible, powerful formalism for defining nonparametric, un- supervised models of grammar productions. This flexibility comes at the cost of expensive inference. We address the difficulty of infer- ence through an online algorithm which uses a hybrid of Markov chain Monte Carlo and variational inference. We show that this in- ference strategy improves scalability without sacrificing performance on unsupervised word segmentation and topic modeling tasks. 1 Introduction Nonparametric Bayesian models are effective tools to discover latent structure in data (M¨uller and Quin- tana, 2004). These models have had great success in text analysis, especially syntax (Shindo et al., 2012). Nonparametric distributions provide support over a countably infinite long-tailed distributions common in natural language (Goldwater et al., 2011). We focus on adaptor grammars (Johnson et al., 2006), syntactic nonparametric models based on probabilistic context-free grammars. Adaptor gram- mars weaken the strong statistical independence as- sumptions PCFGs make (Section 2). The weaker statistical independence assumptions that adaptor grammars make come at the cost of ex- pensive inference. Adaptor grammars are not alone in this trade-off. For example, nonparametric exten- sions of topic models (Teh et al., 2006) have substan- tially more expensive inference than their parametric counterparts (Yao et al., 2009). A common approach to address this compu- tational bottleneck is through variational infer- ence (Wainwright and Jordan, 2008). One of the advantages of variational inference is that it can be easily parallelized (Nallapati et al., 2007) or trans- formed into an online algorithm (Hoffman et al., 2010), which often converges in fewer iterations than batch variational inference. Past variational inference techniques for adap- tor grammars assume a preprocessing step that looks at all available data to establish the support of these nonparametric distributions (Cohen et al., 2010). Thus, these past approaches are not directly amenable to online inference. Markov chain Monte Carlo (MCMC) inference, an alternative to variational inference, does not have this disadvantage. MCMC is easier to implement, and it discovers the support of nonparametric mod- els during inference rather than assuming it a priori. We apply stochastic hybrid inference (Mimno et al., 2012) to adaptor grammars to get the best of both worlds. We interleave MCMC inference inside vari- ational inference. This preserves the scalability of variational inference while adding the sparse statis- tics and improved exploration MCMC provides. Our inference algorithm for adaptor grammars starts with a variational algorithm similar to Cohen et al. (2010) and adds hybrid sampling within varia- tional inference (Section 3). This obviates the need for expensive preprocessing and is a necessary step to create an online algorithm for adaptor grammars. Our online extension (Section 4) processes exam- ples in small batches taken from a stream of data. As data arrive, the algorithm dynamically extends the …

Content truncated to 500 words