One of the most widely used methods natural language is ngram modeling. This article explains what an ngram model is, how it is computed, and what the probabilities of an ngram model tell us.
What is an ngram?
An ngram is a contiguous sequence of n items from a given sequence of text.
Given a sentence, s
, we can construct a list of ngrams 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 (ngrams of length 2) by finding
consecutive pairs of words.


Calculating ngram Probability
Given a list of ngrams we can count the number of occurrences of each ngram; this count determines the frequency with which an ngram occurs throughout our document.


With this small corpus we only count one occurrence of each ngram. By dividing these counts by the size of all ngrams in our list we would get a probability of 0.5 of each ngram 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 ngram 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 ngrams using the Chain Rule of conditional probability.
P(x1, x2, ..., xn) = P(x1)P(x2x1)...P(xnx1,...xn1)
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 ngram probabilities that we can estimate using the counts of ngrams 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 ngrams 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 ngram 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.