A Random Text Model for the Generation of Statistical Language Invariants

Proceedings of NAACL HLT 2007, pages 105–112, Rochester, NY, April 2007. c⃝2007 Association for Computational Linguistics A Random Text Model for the Generation of Statistical Language Invariants Chris Biemann NLP Dept., University of Leipzig Johannisgasse 26 04103 Leipzig, Germany biem@informatik.uni-leipzig.de Abstract A novel random text generation model is introduced. Unlike in previous random text models, that mainly aim at producing a Zipfian distribution of word frequencies, our model also takes the properties of neighboring co-occurrence into account and introduces the notion of sentences in random text. After pointing out the defi- ciencies of related models, we provide a generation process that takes neither the Zipfian distribution on word frequencies nor the small-world structure of the neighboring co-occurrence graph as a constraint. Nevertheless, these distribu- tions emerge in the process. The distribu- tions obtained with the random generation model are compared to a sample of natu- ral language data, showing high agree- ment also on word length and sentence length. This work proposes a plausible model for the emergence of large-scale characteristics of language without as- suming a grammar or semantics. 1 Introduction G. K. Zipf (1949) discovered that if all words in a sample of natural language are arranged in de- creasing order of frequency, then the relation be- tween a word’s frequency and its rank in the list follows a power-law. Since then, a significant amount of research in the area of quantitative lin- guistics has been devoted to the question how this property emerges and what kind of processes gen- erate such Zipfian distributions. The relation between the frequency of a word at rank r and its rank is given by f(r) ∝ r-z, where z is the exponent of the power-law that corresponds to the slope of the curve in a log plot (cf. figure 2). The exponent z was assumed to be exactly 1 by Zipf; in natural language data, also slightly differ- ing exponents in the range of about 0.7 to 1.2 are observed (cf. Zanette and Montemurro 2002). B. Mandelbrot (1953) provided a formula with a closer approximation of the frequency distributions in language data, noticing that Zipf’s law holds only for the medium range of ranks, whereas the curve is flatter for very frequent words and steeper for high ranks. He also provided a word generation model that produces random words of arbitrary average length in the following way: With a prob- ability w, a word separator is generated at each step, with probability (1-w)/N, a letter from an al- phabet of size N is generated, each letter having the same probability. This is sometimes called the “monkey at the typewriter” (Miller, 1957). The frequency distribution follows a power-law for long streams of words, yet the equiprobability of letters causes the plot to show a step-wise rather than a smooth behavior, as examined by Ferrer i Cancho and Solé (2002), cf. figure 2. In the same study, a smooth rank distribution could be obtained by setting the letter probabilities according to letter frequencies …

Content truncated to 500 words