A queueing-theory model of word frequency distributions

A queuing-theory model of word frequency distributions Robert Munro University of Sydney rmunro@it.usyd.edu.au Abstract This paper describes a novel model for term frequency distributions that is derived from queuing-theory. It is compared with Poisson distributions, in terms of how well the models describe the observed distributions of terms, and it is demonstrated that a model for term frequency distributions based on queue utilisation generally gives a better fit. It is further demonstrated that the ratio of the fit/error between the Poisson and queue utilisation distributions may be used as a good indication of how inter- esting a word is in relation to the topic of the discourse. A number of possible reasons for this are discussed. 1 Introduction When a given term occurs in a document, what is the probability that it will occur again, and how will this probability change when you have seen � , � or � instances of this term? While NLP is a vast field, the majority of research is devoted to looking for intelligent ways to auto- mate and speed up processes such as grammati- cal and/or semantic parsing, which a human could complete with an equivalent or much higher accu- racy. Where NLP can exceed human accuracy is in extraction of patterns from large scale corpora (Banko and Brill, 2001). Lexical systems, such as term collocations, co-occurrences and frequency distributions, are one such area. Typically, a word’s occurrence across docu- ments have been assumed to be Poisson in dis- tribution. When this hasn’t worked, a combina- tion of two Poisson mixtures has been attempted with suggestions that when this fails combina- tions of three or more are appropriate (Bookstein and Swanson, 1974; Church and Gale, 1995). 1.1 Contribution of this paper It is demonstrated here that the distribution of a queue utilisation (QU) is a more accurate repre- sentation for word frequency distributions than a Poisson distribution. A Poisson distribution cap- tures the ‘burstiness’ of the frequency of a given word, otherwise known as the clustered-ness or self-collocation of a word. Here, it is shown that while the underlying assumption of bursti- ness holds, there are better representations for capturing this. While it has previously been observed that words that best singularly describe the topic (var- iously labeled the ‘interest words’ or ‘content words’ of a discourse) are the words that least obey a Poisson distribution (Church, 2000), this has typically been used only as an observed trend, and without the search for what method best fits modelling this other distribution (if any). The significance of the relationship between the fits of a Poisson and QU distribution is ex- plored, and it is demonstrated that the level of dis- parity between the fits of Poisson and QU distri- butions can be used to extract words that best sin- gularly describe participants in news topics with a very high level of accuracy. This paper reports some preliminary results in using such a method on a large corpus of newswires, and discusses the results in …

Content truncated to 500 words