Perplexity on Reduced Corpora

Proceedings of the 52nd Annual Meeting of the Association for Computational Linguistics, pages 797–806, Baltimore, Maryland, USA, June 23-25 2014. c⃝2014 Association for Computational Linguistics Perplexity on Reduced Corpora Hayato Kobayashi∗ Yahoo Japan Corporation 9-7-1 Akasaka, Minato-ku, Tokyo 107-6211, Japan hakobaya@yahoo-corp.jp Abstract This paper studies the idea of remov- ing low-frequency words from a corpus, which is a common practice to reduce computational costs, from a theoretical standpoint. Based on the assumption that a corpus follows Zipf’s law, we derive trade- off formulae of the perplexity of k-gram models and topic models with respect to the size of the reduced vocabulary. In ad- dition, we show an approximate behavior of each formula under certain conditions. We verify the correctness of our theory on synthetic corpora and examine the gap be- tween theory and practice on real corpora. 1 Introduction Removing low-frequency words from a corpus (often called cutoff) is a common practice to save on the computational costs involved in learning language models and topic models. In the case of language models, we often have to remove low-frequency words because of a lack of com- putational resources, since the feature space of k- grams tends to be so large that we sometimes need cutoffs even in a distributed environment (Brants et al., 2007). In the case of topic models, the in- tuition is that low-frequency words do not make a large contribution to the statistics of the models. Actually, when we try to roughly analyze a corpus with topic models, a reduced corpus is enough for the purpose (Steyvers and Griffiths, 2007). A natural question arises: How many low- frequency words can we remove while maintain- ing sufficient performance? Or more generally, by how much can we reduce a corpus/model us- ing a certain strategy and still keep a sufficient level of performance? There have been many stud- ∗This work was mainly carried out while the author was with Toshiba Corporation. ies addressing the question as it pertains to differ- ent strategies (Stolcke, 1998; Buchsbaum et al., 1998; Goodman and Gao, 2000; Gao and Zhang, 2002; Ha et al., 2006; Hirsimaki, 2007; Church et al., 2007). Each of these studies experimen- tally discusses trade-off relationships between the size of the reduced corpus/model and its perfor- mance measured by perplexity, word error rate, and other factors. To our knowledge, however, there is no theoretical study on the question and no evidence for such a trade-off relationship, es- pecially for topic models. In this paper, we first address the question from a theoretical standpoint. We focus on the cutoff strategy for reducing a corpus, since a cutoff is simple but powerful method that is worth study- ing; as reported in (Goodman and Gao, 2000; Gao and Zhang, 2002), a cutoff is competitive with sophisticated strategies such as entropy prun- ing. As the basis of our theory, we assume Zipf’s law (Zipf, 1935), which is an empirical rule repre- senting a long-tail property of words in a corpus. Our approach is essentially the …

Content truncated to 500 words