Compound Probabilistic Context-Free Grammars for Grammar Induction

Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics, pages 2369–2385 Florence, Italy, July 28 - August 2, 2019. c⃝2019 Association for Computational Linguistics 2369 Compound Probabilistic Context-Free Grammars for Grammar Induction Yoon Kim Harvard University Cambridge, MA, USA yoonkim@seas.harvard.edu Chris Dyer DeepMind London, UK cdyer@google.com Alexander M. Rush Harvard University Cambridge, MA, USA srush@seas.harvard.edu Abstract We study a formalization of the grammar in- duction problem that models sentences as be- ing generated by a compound probabilistic context free grammar. In contrast to traditional formulations which learn a single stochastic grammar, our context-free rule probabilities are modulated by a per-sentence continuous latent variable, which induces marginal de- pendencies beyond the traditional context-free assumptions. Inference in this grammar is performed by collapsed variational inference, in which an amortized variational posterior is placed on the continuous variable, and the la- tent trees are marginalized with dynamic pro- gramming. Experiments on English and Chi- nese show the effectiveness of our approach compared to recent state-of-the-art methods for grammar induction from words with neu- ral language models. 1 Introduction Grammar induction is the task of inducing hier- archical syntactic structure from data. Statistical approaches to grammar induction require specify- ing a probabilistic grammar (e.g. formalism, num- ber and shape of rules), and fitting its parameters through optimization. Early work found that it was difficult to induce probabilistic context-free gram- mars (PCFG) from natural language data through direct methods, such as optimizing the log like- lihood with the EM algorithm (Lari and Young, 1990; Carroll and Charniak, 1992). While the rea- sons for the failure are manifold and not com- pletely understood, two major potential causes are the ill-behaved optimization landscape and the overly strict independence assumptions of PCFGs. More successful approaches to grammar induction have thus resorted to carefully-crafted auxiliary objectives (Klein and Manning, 2002), priors or Code: https://github.com/harvardnlp/compound-pcfg non-parametric models (Kurihara and Sato, 2006; Johnson et al., 2007; Liang et al., 2007; Wang and Blunsom, 2013), and manually-engineered fea- tures (Huang et al., 2012; Golland et al., 2012) to encourage the desired structures to emerge. We revisit these aforementioned issues in light of advances in model parameterization and infer- ence. First, contrary to common wisdom, we find that parameterizing a PCFG’s rule probabil- ities with neural networks over distributed rep- resentations makes it possible to induce linguis- tically meaningful grammars by simply optimiz- ing log likelihood. While the optimization prob- lem remains non-convex, recent work suggests that there are optimization benefits afforded by over-parameterized models (Arora et al., 2018; Xu et al., 2018; Du et al., 2019), and we in- deed find that this neural PCFG is significantly easier to optimize than the traditional PCFG. Second, this factored parameterization makes it straightforward to incorporate side information into rule probabilities through a sentence-level continuous latent vector, which effectively allows different contexts in a derivation to coordinate. In this compound PCFG—continuous mixture of PCFGs—the context-free assumptions hold con- ditioned on the latent vector but not uncondition- ally, thereby obtaining longer-range dependencies within …

Content truncated to 500 words