Knowing the Unseen: Estimating Vocabulary Size over Unseen Samples

Proceedings of the 47th Annual Meeting of the ACL and the 4th IJCNLP of the AFNLP, pages 109–117, Suntec, Singapore, 2-7 August 2009. c⃝2009 ACL and AFNLP Knowing the Unseen: Estimating Vocabulary Size over Unseen Samples Suma Bhat Department of ECE University of Illinois spbhat2@illinois.edu Richard Sproat Center for Spoken Language Understanding Oregon Health & Science University rws@xoba.com Abstract Empirical studies on corpora involve mak- ing measurements of several quantities for the purpose of comparing corpora, creat- ing language models or to make general- izations about specific linguistic phenom- ena in a language. Quantities such as av- erage word length are stable across sam- ple sizes and hence can be reliably esti- mated from large enough samples. How- ever, quantities such as vocabulary size change with sample size. Thus measure- ments based on a given sample will need to be extrapolated to obtain their estimates over larger unseen samples. In this work, we propose a novel nonparametric estima- tor of vocabulary size. Our main result is to show the statistical consistency of the estimator – the first of its kind in the lit- erature. Finally, we compare our proposal with the state of the art estimators (both parametric and nonparametric) on large standard corpora; apart from showing the favorable performance of our estimator, we also see that the classical Good-Turing estimator consistently underestimates the vocabulary size. 1 Introduction Empirical studies on corpora involve making mea- surements of several quantities for the purpose of comparing corpora, creating language models or to make generalizations about specific linguistic phenomena in a language. Quantities such as av- erage word length or average sentence length are stable across sample sizes. Hence empirical mea- surements from large enough samples tend to be reliable for even larger sample sizes. On the other hand, quantities associated with word frequencies, such as the number of hapax legomena or the num- ber of distinct word types changes are strictly sam- ple size dependent. Given a sample we can ob- tain the seen vocabulary and the seen number of hapax legomena. However, for the purpose of comparison of corpora of different sizes or lin- guistic phenomena based on samples of different sizes it is imperative that these quantities be com- pared based on similar sample sizes. We thus need methods to extrapolate empirical measurements of these quantities to arbitrary sample sizes. Our focus in this study will be estimators of vocabulary size for samples larger than the sam- ple available. There is an abundance of estima- tors of population size (in our case, vocabulary size) in existing literature. Excellent survey arti- cles that summarize the state-of-the-art are avail- able in (Bunge and Fitzpatrick, 1993) and (Gan- dolfi and Sastri, 2004). Of particular interest to us is the set of estimators that have been shown to model word frequency distributions well. This study proposes a nonparametric estimator of vo- cabulary size and evaluates its theoretical and em- pirical performance. For comparison we consider some state-of-the-art parametric and nonparamet- ric estimators of vocabulary …

Content truncated to 500 words