N-gram Language Models: Predicting the Next Word

N-gram Language Models: Predicting the Next Word

Ever wondered how computers can predict the next word in a sentence? Or suggest relevant phrases while you're typing? The answer lies in a fascinating area of natural language processing called N-gram language modeling. Let's explore what it is, how it works, and why it's so useful.

What are N-grams?

An N-gram is simply a sequence of 'N' items (words, characters, or even syllables) from a text or speech. So, if we look at the sentence "I love to eat pizza", here's what the N-grams would be:

• Unigram (N=1): I, love, to, eat, pizza
• Bigram (N=2): I love, love to, to eat, eat pizza
• Trigram (N=3): I love to, love to eat, to eat pizza
• And so on...

N-gram language models use these sequences to predict the likelihood of a word appearing given the previous words.

Estimating Probabilities with Maximum Likelihood Estimation (MLE)

To build an N-gram language model, we need to estimate the probabilities of different N-grams. A common method is called Maximum Likelihood Estimation (MLE). The basic idea is simple: count how often each N-gram appears in a large body of text (called a corpus) and then normalize those counts to get probabilities. Normalization means dividing by a total count so the probabilities are between 0 and 1 and sum to 1.

For example, to calculate the probability of a bigram (two-word sequence), we use this formula:

P(word2 | word1) = Count(word1 word2) / Count(word1)

In simpler terms: Divide the number of times "word1 word2" appears by the number of times "word1" appears.

Example: A Mini-Corpus

Let's say we have this tiny corpus:

• <s> I am Sam </s>
• <s> Sam I am </s>
• <s> I do not like green eggs and ham </s>

The <s> and </s> symbols mark the beginning and end of sentences, respectively. They are crucial for getting the model to learn when sentences start and stop!

Here are some bigram probabilities we can calculate:

• P(I | <s>) = 2/3 = 0.67 (Two sentences start with "I" out of three sentences)
• P(Sam | <s>) = 1/3 = 0.33 (One sentence starts with "Sam" out of three sentences)
• P(am | I) = 2/3 = 0.67 ("am" follows "I" twice, and "I" appears three times)
• P(</s> | Sam) = 1/2 = 0.5 ("Sam" ends a sentence once out of the two times "Sam" appears)
• P(Sam | am) = 1/2 = 0.5 ("Sam" follows "am" once, and "am" appears twice)
• P(do | I) = 1/3 = 0.33 ("do" follows "I" once, and "I" appears three times)

MLE basically maximizes the chance the n-gram will occur given a set of data. If the word "The" occurs 500 times in a corpus of 1 million words, the probability is 500/1000000 or 0.0005. It's not the *best* estimate of the probability of "The" *everywhere* but its the probability that maximizes the chance of seeing "The" 500 times in a million-word corpus.

Real-World Examples and Linguistic Phenomena

Bigram statistics capture syntactic rules. For example, what usually comes after "eat" is usually a noun (I eat pizza). The probability of sentences that start with "I" is high due to how often people start sentences like that. Lastly, cultural phenomena. The probability people are looking for Chinese food vs English food.

Practical Considerations: Scaling Up

Real-world language models are HUGE. This brings about some practical challenges:

• Log Probabilities: Probabilities are always between 0 and 1. Multiplying many probabilities together can lead to a very small number (numerical underflow). To avoid this, we use log probabilities (which are negative). Adding log probabilities is equivalent to multiplying normal probabilities.
• Longer Contexts: Trigrams, 4-grams, and 5-grams are much more powerful than bigrams, however, they also require significantly more data to train.
• Massive Datasets: Google's Web 5-gram corpus is from 1 trillion words. Projects like the "infini-gram" allow for n-grams of ANY length to be used (practically speaking.)
• Efficiency: Quantization is the method of using only 4-8 bits to store the probabilities instead of 8-byte floats. Hashes replace word strings to reduce space. Pruning removes less important n-grams to reduce the model size.

Evaluating Language Models: Training, Development, and Test Sets

How do we know if our language model is any good? We need to evaluate its performance.

• Extrinsic Evaluation: The *best* way is to embed it into an application and see how much that application improves! This end-to-end testing determines if improvements to the language model help the actual task.
• Intrinsic Evaluation: But end-to-end testing can be expensive, so a metric called perplexity (below) measures the quality of a model independently of any application.

To evaluate the model, we split the data into three distinct sets:

• Training Set: Used to *train* the model (learn the probabilities).
• Development Set (Devset): Used to *tune* the model and experiment with different parameters.
• Test Set: Used to provide a final, unbiased evaluation of the model's performance. It should be unseen during training and development.

Training on the test set introduces bias so the evaluation metric will have huge inaccuracies.

The test set should reflect the language we want to use the model for, and the devset should be drawn from the same kind of text as the test set to measure how we would do on the test set.

Perplexity: Measuring the "Surprise"

Perplexity measures how well a language model predicts a sample of text. The lower the perplexity, the better the language model. It's based on the probability the model assigns to the test set. Perplexity has an inverse relationship with probability. Minimizing perplexity is equivalent to maximizing the test set probability according to the language model.

The formula for perplexity looks complicated, but the idea is to take the inverse probability of the test set, normalized by the number of words.

Consider this example:

Model	Perplexity
Unigram	962
Bigram	170
Trigram	109

The trigram model is less surprised than the unigram model. More information allows higher probability and therefore lower perplexity.

Perplexity as Weighted Average Branching Factor

A branching factor of a language is the number of next words that can follow. A deterministic language consists of only three colors L = {red, blue, green}. It is deterministic because each word can follow any word, giving it a branching factor of 3.

The perplexity on the test set "red red red red blue" is 3 since each color can follow each other with equal probability of 1/3. But suppose red was more likely in the training set a different LM B, and so B has the following probabilities:

• P(red) = 0.8
• P(green) = 0.1
• P(blue) = 0.1

This would cause a lower perplexity for the language model B since most of the time the next color will be red. So although the branching factor is still 3, the perplexity is smaller. The probability of the test set will be higher.

Sampling Sentences: Generating Text

One way to understand what a language model has learned is to sample sentences from it. This involves randomly generating words based on the model's probability distribution.

Generalizing vs. Overfitting

N-gram models are dependent on the training corpus and often encode specific facts. As 'N' increases, the model gets better at modeling the training corpus, but is not guaranteed to work well on other data.

If two data sets are different, the models will reflect that.

For example, models trained on Shakespeare and the Wall Street Journal produce entirely different results. To handle this problem, use a training corpus of the same dialect or variety to the test data.

Also, subword tokenization models any word as a sequence of smaller, known subwords to handle words it has never seen before. The test set can never contain unseen tokens.

Smoothing, Interpolation, and Backoff: Handling Unseen N-grams

What happens if a particular N-gram doesn't appear in our training data? This can cause problems. Smoothing techniques shave off a bit of probability mass from some more frequent events and give it to unseen events to avoid zero probabilities and improve generalization.

• Laplace (Add-One) Smoothing: Add one to all the n-gram counts. It introduces concepts like adjusted counts, discounting, and relative discount but doesn't perform well enough to be used in modern n-gram models.
• Add-k Smoothing: Instead of adding one, add a fractional count 'k'.
• Language Model Interpolation: Combines trigram, bigram, and unigram probabilities, all weighted. Using less context can sometimes improve results with those the model hasn't learned much about. The weights (lambdas) are learned from a held-out corpus.
• Stupid Backoff: If a higher-order n-gram has a zero count, simply back off to a lower order n-gram, weighed by a fixed weight. Doesn't try to make the language model a true probability distribution.

The Future of N-gram Models

While N-gram models might seem simple, they're a powerful tool for understanding language and predicting text. They form the foundation for more advanced language models used in everything from search engines to chatbots.