PCFGs, Topic Models, Adaptor Grammars and Learning Topical Collocations and the Structure of Proper Names

Proceedings of the 48th Annual Meeting of the Association for Computational Linguistics, pages 1148–1157, Uppsala, Sweden, 11-16 July 2010. c⃝2010 Association for Computational Linguistics PCFGs, Topic Models, Adaptor Grammars and Learning Topical Collocations and the Structure of Proper Names Mark Johnson Department of Computing Macquarie University mjohnson@science.mq.edu.au Abstract This paper establishes a connection be- tween two apparently very different kinds of probabilistic models. Latent Dirich- let Allocation (LDA) models are used as “topic models” to produce a low- dimensional representation of documents, while Probabilistic Context-Free Gram- mars (PCFGs) define distributions over trees. The paper begins by showing that LDA topic models can be viewed as a special kind of PCFG, so Bayesian in- ference for PCFGs can be used to infer Topic Models as well. Adaptor Grammars (AGs) are a hierarchical, non-parameteric Bayesian extension of PCFGs. Exploit- ing the close relationship between LDA and PCFGs just described, we propose two novel probabilistic models that com- bine insights from LDA and AG models. The first replaces the unigram component of LDA topic models with multi-word se- quences or collocations generated by an AG. The second extension builds on the first one to learn aspects of the internal structure of proper names. 1 Introduction Over the last few years there has been consider- able interest in Bayesian inference for complex hi- erarchical models both in machine learning and in computational linguistics. This paper establishes a theoretical connection between two very differ- ent kinds of probabilistic models: Probabilistic Context-Free Grammars (PCFGs) and a class of models known as Latent Dirichlet Allocation (Blei et al., 2003; Griffiths and Steyvers, 2004) models that have been used for a variety of tasks in ma- chine learning. Specifically, we show that an LDA model can be expressed as a certain kind of PCFG, so Bayesian inference for PCFGs can be used to learn LDA topic models as well. The importance of this observation is primarily theoretical, as cur- rent Bayesian inference algorithms for PCFGs are less efficient than those for LDA inference. How- ever, once this link is established it suggests a vari- ety of extensions to the LDA topic models, two of which we explore in this paper. The first involves extending the LDA topic model so that it generates collocations (sequences of words) rather than indi- vidual words. The second applies this idea to the problem of automatically learning internal struc- ture of proper names (NPs), which is useful for definite NP coreference models and other applica- tions. The rest of this paper is structured as follows. The next section reviews Latent Dirichlet Alloca- tion (LDA) topic models, and the following sec- tion reviews Probabilistic Context-Free Grammars (PCFGs). Section 4 shows how an LDA topic model can be expressed as a PCFG, which pro- vides the fundamental connection between LDA and PCFGs that we exploit in the rest of the paper, and shows how it can be used to define a “sticky topic” version of LDA. The follow- ing section reviews Adaptor Grammars (AGs), a …

Content truncated to 500 words