PCFG Induction for Unsupervised Parsing and Language Modelling

Proceedings of the 2014 Conference on Empirical Methods in Natural Language Processing (EMNLP), pages 1353–1362, October 25-29, 2014, Doha, Qatar. c⃝2014 Association for Computational Linguistics PCFG Induction for Unsupervised Parsing and Language Modelling James Scicluna Universit´e de Nantes, CNRS, LINA, UMR6241, F-44000, France james.scicluna@univ-nantes.fr Colin de la Higuera Universit´e de Nantes, CNRS, LINA, UMR6241, F-44000, France cdlh@univ-nantes.fr Abstract The task of unsupervised induction of probabilistic context-free grammars (PCFGs) has attracted a lot of attention in the field of computational linguistics. Although it is a difficult task, work in this area is still very much in demand since it can contribute to the advancement of language parsing and modelling. In this work, we describe a new algorithm for PCFG induction based on a principled approach and capable of inducing accurate yet compact artificial natural language grammars and typical context-free gram- mars. Moreover, this algorithm can work on large grammars and datasets and infers correctly even from small samples. Our analysis shows that the type of grammars induced by our algorithm are, in theory, capable of modelling natural language. One of our experiments shows that our algorithm can potentially outperform the state-of-the-art in unsupervised parsing on the WSJ10 corpus. 1 Introduction The task of unsupervised induction of PCFGs has attracted a lot of attention in the field of compu- tational linguistics. This task can take the form of either parameter search or structure learning. In parameter search, a CFG is fixed and the fo- cus is on assigning probabilities to this grammar using Bayesian methods (Johnson et al., 2007) or maximum likelihood estimation (Lari and Young, 1990). In structure learning, the focus is on build- ing the right grammar rules from scratch. We take the latter approach. Unsupervised structure learning of (P)CFGs is a notoriously difficult task (de la Higuera, 2010; Clark and Lappin, 2010), with theoretical results showing that in general it is either impossible to achieve (Gold, 1967; de la Higuera, 1997) or requires impractical resources (Horning, 1969; Yang, 2012). At the same time, it is well known that context-free structures are needed for better language parsing and modelling, since less expres- sive models (such as HMMs) are not good enough (Manning and Sch¨utze, 2001; Jurafsky and Mar- tin, 2008). Moreover, the trend is towards unsu- pervised (rather than supervised) learning meth- ods due to the lack in most languages of annotated data and the applicability in wider domains (Merlo et al., 2010). Thus, despite its difficulty, unsuper- vised PCFG grammar induction (or induction of other similarly expressive models) is still an im- portant task in computational linguistics. In this paper, we describe a new algorithm for PCFG induction based on a principled approach and capable of inducing accurate yet compact grammars. Moreover, this algorithm can work on large grammars and datasets and infers correctly even from small samples. We show that our algo- rithm is capable of achieving competitive results in both unsupervised parsing and language mod- elling of typical context-free languages and arti- ficial natural language grammars. We …

Content truncated to 500 words