Grammar induction from (lots of) words alone

Proceedings of COLING 2016, the 26th International Conference on Computational Linguistics: Technical Papers, pages 23–32, Osaka, Japan, December 11-17 2016. Grammar induction from (lots of) words alone John K Pate Department of Linguistics The University at Buffalo Buffalo, NY 14260, USA johnpate@buffalo.edu Mark Johnson Department of Computing Macquarie University Sydney, NSW 2109, Australia mark.johnson@mq.edu.au Abstract Grammar induction is the task of learning syntactic structure in a setting where that structure is hidden. Grammar induction from words alone is interesting because it is similiar to the problem that a child learning a language faces. Previous work has typically assumed richer but cognitively implausible input, such as POS tag annotated data, which makes that work less relevant to human language acquisition. We show that grammar induction from words alone is in fact feasible when the model is provided with sufficient training data, and present two new streaming or mini-batch algorithms for PCFG inference that can learn from millions of words of training data. We compare the performance of these algorithms to a batch algorithm that learns from less data. The minibatch algorithms outperform the batch algorithm, showing that cheap inference with more data is better than intensive inference with less data. Additionally, we show that the harmonic initialiser, which previous work identified as essential when learning from small POS- tag annotated corpora (Klein and Manning, 2004), is not superior to a uniform initialisation. 1 Introduction How children acquire the syntax of the languages they ultimately speak is a deep scientific question of fundamental importance to linguistics and cognitive science (Chomsky, 1986). The natural language pro- cessing task of grammar induction in principle should provide models for how children do this. However, previous work on grammar induction has learned from small datasets, and has dealt with the resulting data sparsity by modifying the input and using careful search heuristics. While these techniques are use- ful from an engineering perspective, they make the models less relevant to human language acquisition. In this paper, we use scalable algorithms for Probabilistic Context Free Grammar (PCFG) inference to perform grammar induction from millions of words of speech transcripts, and show that grammar induction from words alone is both feasible and insensitive to initialization. To ensure the robustness of our results, we use two algorithms for Variational Bayesian PCFG inference, and adapt two algorithms that have been proposed for Latent Dirichlet Allocation (LDA) topic models. Most importantly, we find that the three algorithms that scale to large datasets improve steadily over training to about the same predictive probability and parsing performance. Moreover, while grammar induction from small datasets of POS-tagged newswire text fails without careful ‘harmonic’ initialization, we find that initialization is much less important when learning directly from larger datasets consisting of words alone. Of the algorithms in this paper, one does 2.5% better with harmonic initialization, another does 5% worse, and the other two are insensitive to initialization. The rest of the paper is organized as follows. In Section 2, we discuss previous grammar induction research, …

Content truncated to 500 words