One of the most widely used methods natural language is n-gram modeling. This article explains what an n-gram model is, how it is computed, and what the probabilities of an n-gram model tell us.
What is an n-gram?
An n-gram is a contiguous sequence of n items from a given sequence of text.
Given a sentence, s, we can construct a list of n-grams from s by finding
pairs of words that occur next to each other. For example, given the sentence
“I am Sam” you can construct bigrams (n-grams of length 2) by finding
consecutive pairs of words.
>>> s = "I am Sam."
>>> tokens = s.split(" ")
>>> bigrams = [(tokens[i],tokens[i+1]) for i in range(0,len(tokens)-1)]
>>> bigrams
[('I', 'am'), ('am', 'Sam.')]
Calculating n-gram Probability
Given a list of n-grams we can count the number of occurrences of each n-gram; this count determines the frequency with which an n-gram occurs throughout our document.
>>> from collections import Counter
>>> count = Counter(bigrams)
>>> count
[(('am', 'Sam.'), 1), (('I', 'am'), 1)]
With this small corpus we only count one occurrence of each n-gram. By dividing these counts by the size of all n-grams in our list we would get a probability of 0.5 of each n-gram occurring.
Let’s look a larger corpus of words and see what the probabilities can tell us. The following sequence of bigrams was computed from data downloaded from HC Corpora. It lists the 20 most frequently encountered bigrams out of 97,810,566 bigrams in the entire corpus.
This data represents the most frequently used pairs of words in the corpus along with the number of times they occur.
of the 421560
in the 380608
to the 207571
for the 190683
on the 184430
to be 153285
at the 128980
and the 114232
in a 109527
with the 99141
is a 99053
for a 90209
from the 82223
with a 78918
will be 78049
of a 78009
I was 76788
I have 76621
going to 75088
is the 70045
By consulting our frequency table of bigrams, we can tell that the sentence
There was heavy rain last night is much more likely to be grammatically
correct than the sentence There was large rain last night by the fact that the
bigram heavy rain occurs much more frequently than large rain in our corpus.
Said another way, the probability of the bigram heavy rain is larger than the
probability of the bigram large rain.
Sentences as probability models
More precisely, we can use n-gram models to derive a probability of the sentence
,W, as the joint probability of each individual word in the sentence, wi.
P(W) = P(w1, w2, ..., wn)
This can be reduced to a sequence of n-grams using the Chain Rule of conditional probability.
P(x1, x2, ..., xn) = P(x1)P(x2|x1)...P(xn|x1,...xn-1)
As a concrete example, let’s predict the probability of the sentence There was heavy rain.
P('There was heavy rain') = P('There', 'was', 'heavy', 'rain')
P('There was heavy rain') = P('There')P('was'|'There')P('heavy'|'There was')P('rain'|'There was heavy')
Each of the terms on the right hand side of this equation are n-gram probabilities that we can estimate using the counts of n-grams in our corpus. To calculate the probability of the entire sentence, we just need to lookup the probabilities of each component part in the conditional probability.
Unfortunately, this formula does not scale since we cannot compute n-grams of every length. For example, consider the case where we have solely bigrams in our model; we have no way of knowing the probability `P(‘rain’|‘There was’) from bigrams.
By using the Markov Assumption, we can simplify our equation by assuming that future states in our model only depend upon the present state of our model. This assumption means that we can reduce our conditional probabilities to be approximately equal so that
P('rain'|'There was heavy') ~ P('rain'|'heavy')
More generally, we can estimate the probability of a sentence by the probabilities of each component part. In the equation that follows, the probability of the sentence is reduced to the probabilities of the sentence’s individual bigrams.
P('There was heavy rain') ~ P('There')P('was'|'There')P('heavy'|'was')P('rain'|'heavy')
Applications
What can we use n-gram models for? Given the probabilities of a sentence we can determine the likelihood of an automated machine translation being correct, we could predict the next most likely word to occur in a sentence, we could automatically generate text from speech, automate spelling correction, or determine the relative sentiment of a piece of text.