select words randomly in proportion to their frequencies

Question

I have a large text and I need to select words randomly in proportion to their frequencies.

A raw method is to put all the words in an array (N indexes) and to use a random (uniform) generator to generate numbers between 0 to N.

For example, a word $w_1$ occurs 5000 times in the text and the word $w_3$ occurs 100 times. $w_1$ should be selected with a probability that is 50 times larger than the probability for $w_3$.

This "raw" method does not seem to be effective (or feasible) if a I have a large text. Is there a better way to select the items randomly and in proportion to their frequencies?

Answer 1

Your method should be effective (or you've got a problem with your random number generator). Whether it is efficient is a separate question.

You might scale better by taking weighted samples from the $V$ possible word types rather than unweighted samples from all $N$ tokens. As documents get longer, Heaps Law suggests that these are related as $V=kN^\beta$ with $k$ between 10 and 100 and $\beta$ between around 0.5 (all depending on the texts) so the amount of storage increases more slower than $N$.

There are then two steps:

• figure out how many times each word type occurs in the text
• sample from a multinomial with these probabilities

In case you'd like to do this in python using (numpy and nltk):

from __future__ import division
import nltk
import numpy.random as npr

## make a tiny document
txt = 'A B c c c D E E' 

## lower case and tokenise its contents
tokens = [word.lower() for word in word_tokenize(txt)]

## count how many times each word type occurs
fd = nltk.FreqDist(tokens)

## construct probabilities for each type
probs = [c/fd.N() for c in fd.viewvalues()]

## decide how long you'd like the new document to be
new_doc_len = 1000 ## new document should have 1000 words

## generate new word type counts
new_counts = npr.multinomial(new_doc_len, probs)

These new word type counts are of course one bootstrap sample from the original document. You could regenerate the words as well, but there's probably no point since you've removed the inter-word correlations by sampling from the margin.

Answer 2

You assume that your word frequencies follow a multinomial distribution. The code below is in R but should be easy to implement in any language. I used letters instead of words but the same principle applies.

words <- c("a", "b", "a", "b", "c", "a", "b", "a")
c <- count(words)

Determine the estimated probabilities of observing words by calculating their maximum likelihood estimates.

p_hat_words <- c$freq / sum(c$freq)

Randomly draw from a bag of words that follow the estimated word probabilities. You can modify the number of trials (n) and sizes of trials (size) as you wish.

rmultinom(n=1, size=100, p_hat_words)

> rmultinom(n=1, size=100, p_hat_words)
     [,1]
[1,]   53
[2,]   38
[3,]    9