(1) Data: Text and Words¶

Before we can do things with words, we need some words. First we need some text, possibly from a file. Then we can break the text into words. I happen to have a big text called big.txt. We can read it, and see how big it is (in characters):

So, six million characters.

Now let's break the text up into words (or more formal-sounding, tokens). For now we'll ignore all the punctuation and numbers, and anything that is not a letter.

So, a million words. Here are the first 10:

(2) Models: Bag of Words¶

The list WORDS is a list of the words in the TEXT, but it can also serve as a generative model of text. We know that language is very complicated, but we can create a simplified model of language that captures part of the complexity. In the bag of words model, we ignore the order of words, but maintain their frequency. Think of it this way: take all the words from the text, and throw them into a bag. Shake the bag, and then generating a sentence consists of pulling words out of the bag one at a time. Chances are it won't be grammatical or sensible, but it will have words in roughly the right proportions. Here's a function to sample an n word sentence from a bag of words:

Another representation for a bag of words is a Counter, which is a dictionary of {'word': count} pairs. For example,

A Counter is like a dict, but with a few extra methods. Let's make a Counter for the big list of WORDS and get a feel for what's there:

In 1935, linguist George Zipf noted that in any big text, the nth most frequent word appears with a frequency of about 1/n of the most frequent word. He get's credit for Zipf's Law, even though Felix Auerbach made the same observation in 1913. If we plot the frequency of words, most common first, on a log-log plot, they should come out as a straight line if Zipf's Law holds. Here we see that it is a fairly close fit:

(3) Task: Spelling Correction¶

Given a word w, find the most likely correction c = correct(w).

Approach: Try all candidate words c that are known words that are near w. Choose the most likely one.

How to balance near and likely?

For now, in a trivial way: always prefer nearer, but when there is a tie on nearness, use the word with the highest WORDS count. Measure nearness by edit distance: the minimum number of deletions, transpositions, insertions, or replacements of characters. By trial and error, we determine that going out to edit distance 2 will give us reasonable results. Then we can define correct(w):

The functions known and edits0 are easy; and edits2 is easy if we assume we have edits1:

Now for edits1(word): the set of candidate words that are one edit away. For example, given "wird", this would include "weird" (inserting an e) and "word" (replacing a i with a o), and also "iwrd" (transposing w and i; then known can be used to filter this out of the set of final candidates). How could we get them? One way is to split the original word in all possible places, each split forming a pair of words, (a, b), before and after the place, and at each place, either delete, transpose, replace, or insert a letter:

Can we make the output prettier than that?

So far so good. You can probably think of a dozen ways to make this better. Here's one: in the text "three, too, one, blastoff!" we might want to correct "too" with "two", even though "too" is in the dictionary. We can do better if we look at a sequence of words, not just an individual word one at a time. But how can we choose the best corrections of a sequence? The ad-hoc approach worked pretty well for single words, but now we could use some real theory ...

(4) Models: Word and Sequence Probabilities¶

If we have a bag of words, what's the probability of picking a particular word out of the bag? We'll denote that probability as $P(w)$. To create the function P that computes this probability, we define a function, pdist, that takes as input a Counter (that is, a bag of words) and returns a function that acts as a probability distribution over all possible words. In a probability distribution the probability of each word is between 0 and 1, and the sum of the probabilities is 1.

Now, what is the probability of a sequence of words? Use the definition of a joint probability:

$P(w_1 \ldots w_n) = P(w_1) \times P(w_2 \mid w_1) \times P(w_3 \mid w_1 w_2) \ldots \times \ldots P(w_n \mid w_1 \ldots w_{n-1})$

In the bag of words model, each word is drawn from the bag independently of the others. So $P(w_2 \mid w_1) = P(w_2)$, and we have:

$P(w_1 \ldots w_n) = P(w_1) \times P(w_2) \times P(w_3) \ldots \times \ldots P(w_n)$

Now clearly this model is wrong; the probability of a sequence depends on the order of the words. But, as the statistician George Box said, All models are wrong, but some are useful. The bag of words model, wrong as it is, has many useful applications.

How can we compute $P(w_1 \ldots w_n)$? We'll use a different function name, Pwords, rather than P, and we compute the product of the individual probabilities:

Yikes—it seems wrong to give a probability of 0 to the last one; it should just be very small. We'll come back to that later. The other probabilities seem reasonable.

(5) Task: Word Segmentation¶

Task: given a sequence of characters with no spaces separating words, recover the sequence of words.

Why? Languages with no word delimiters: 不带空格的词

In English, sub-genres with no word delimiters (spelling errors, URLs).

Approach 1: Enumerate all candidate segementations and choose the one with highest Pwords

Problem: how many segmentations are there for an n-character text?

Approach 2: Make one segmentation, into a first word and remaining characters. If we assume words are independent then we can maximize the probability of the first word adjoined to the best segmentation of the remaining characters.

assert segment('choosespain') == ['choose', 'spain']

segment('choosespain') ==
   max(Pwords(['c'] + segment('hoosespain')),
       Pwords(['ch'] + segment('oosespain')),
       Pwords(['cho'] + segment('osespain')),
       Pwords(['choo'] + segment('sespain')),
       ...
       Pwords(['choosespain'] + segment('')))

To make this somewhat efficient, we need to avoid re-computing the segmentations of the remaining characters. This can be done explicitly by dynamic programming or implicitly with memoization. Also, we shouldn't consider all possible lengths for the first word; we can impose a maximum length. What should it be? A little more than the longest word seen so far.

That's a problem. We'll come back to it later.

Summary:

• Looks pretty good!
• The bag-of-words assumption is a limitation.
• Recomputing Pwords on each recursive call is somewhat inefficient.
• Numeric underflow for texts longer than 100 or so words; we'll need to use logarithms, or other tricks.

(6) Data: Mo' Data, Mo' Better¶

Let's move up from millions to billions and billions of words. Once we have that amount of data, we can start to look at two word sequences, without them being too sparse. I happen to have data files available in the format of "word \t count", and bigram data in the form of "word1 word2 \t count". Let's arrange to read them in:

(7) Theory and Practice: Segmentation With Bigram Data¶

A less-wrong approximation:

$P(w_1 \ldots w_n) = P(w_1 \mid start) \times P(w_2 \mid w_1) \times P(w_3 \mid w_2) \ldots \times \ldots P(w_n \mid w_{n-1})$

This is called the bigram model, and is equivalent to taking a text, cutting it up into slips of paper with two words on them, and having multiple bags, and putting each slip into a bag labeled with the first word on the slip. Then, to generate language, we choose the first word from the original single bag of words, and chose all subsequent words from the bag with the label of the previously-chosen word. To determine the probability of a word sequence, we multiply together the conditional probabilities of each word given the previous word. We'll do this with a function, cPword for "conditional probability of a word."

$P(w_n \mid w_{n-1}) = P(w_{n-1}w_n) / P(w_{n-1}) $

To make segment2, we copy segment, and make sure to pass around the previous token, and to evaluate probabilities with Pwords2 instead of Pwords.

Conclusion? Bigram model is a little better, but not much. Hundreds of billions of words still not enough. (Why not trillions?) Could be made more efficient.

(8) Theory: Evaluation¶

So far, we've got an intuitive feel for how this all works. But we don't have any solid metrics that quantify the results. Without metrics, we can't say if we are doing well, nor if a change is an improvement. In general, when developing a program that relies on data to help make predictions, it is good practice to divide your data into three sets:

1. Training set: the data used to create our spelling model; this was the big.txt file.
2. Development set: a set of input/output pairs that we can use to rank the performance of our program as we are developing it.
3. Test set: another set of input/output pairs that we use to rank our program after we are done developing it. The development set can't be used for this purpose—once the programmer has looked at the development test it is tainted, because the programmer might modify the program just to pass the development test. That's why we need a separate test set that is only looked at after development is done.

For this program, the training data is the word frequency counts, the development set is the examples like "choosespain" that we have been playing with, and now we need a test set.

This confirms that both segmenters are very good, and that segment2 is slightly better. There is much more that can be done in terms of the variety of tests, and in measuring statistical significance.

(9) Theory and Practice: Smoothing¶

Let's go back to a test we did before, and add some more test cases:

The issue here is the finality of a probability of zero. Out of the three 15-letter words, it turns out that "nongovernmental" is in the dictionary, but if it hadn't been, if somehow our corpus of words had missed it, then the probability of that whole phrase would have been zero. It seems that is too strict; there must be some "real" words that are not in our dictionary, so we shouldn't give them probability zero. There is also a question of likelihood of being a "real" word. It does seem that "neverbeforeseen" is more English-like than "zqbhjhsyefvvjqc", and so perhaps should have a higher probability.

We can address this by assigning a non-zero probability to words that are not in the dictionary. This is even more important when it comes to multi-word phrases (such as bigrams), because it is more likely that a legitimate one will appear that has not been observed before.

We can think of our model as being overly spiky; it has a spike of probability mass wherever a word or phrase occurs in the corpus. What we would like to do is smooth over those spikes so that we get a model that does not depend on the details of our corpus. The process of "fixing" the model is called smoothing.

For example, Laplace was asked what's the probability of the sun rising tomorrow. From data that it has risen $n/n$ times for the last n days, the maximum liklihood estimator is 1. But Laplace wanted to balance the data with the possibility that tomorrow, either it will rise or it won't, so he came up with $(n + 1) / (n + 2)$.