# Computing probability of sentence using N-grams

I have implemented N-grams by constructing a tree (or a trie, technically) that stores frequencies of each N-gram. Each path in the tree represents an N-gram and its frequency: the path consists of N nodes (each node containing a word), followed by a leaf node containing the frequency. So, each path in the tree is of length N + 1.

I'm now trying to compute the probability of observing a given sentence, and am having some trouble, particularly when N > 2.

For the sentence <s> Hello world </s> using N = 1, the probability is P(<s>) * P(Hello) * P(world) * P(</s>).

Using N = 2, the probability is P(Hello | <s>) * P(world | Hello) * P(</s> | world).

But for N = 3, I'm not sure what to do. If I compute P(Hello | <s>) * P(world | <s> Hello), then my tree will give an error since <s> Hello is a bigram and the tree is only defined for trigrams.

I considered maybe wrapping each sentence an additional time, e.g. <s> <s> Hello world </s> </s> then computing P(Hello | <s> <s>) * P(world | <s> Hello) * P(</s> | Hello world) * P(</s> | world </s>), but this seems non-intuitive and involves mutating the corpus in an ugly way.

What is the proper way to compute this probability?

• I don't understand what your question is. Are you really asking "How do I compute P(world | <s> Hello) given the frequencies of all trigrams?"
– D.W.
Sep 24 '15 at 5:36

## 2 Answers

The $N$-gram model assumes a generative model in which the next word generated depends only on the preceding $N-1$ words. Using Bayes' law, we get that the probability of a sentence $w_1,\ldots,w_n$ is $$P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) \cdots P(w_N|w_1\ldots w_{N-1}) P(w_{N+1}|w_2\ldots w_N) \cdots P(w_n | w_{n-N+1}\ldots w_{n-1}).$$ In the particular cases $N=1,2,3$, this gives $$P(w_1\cdots w_n) = P(w_1) P(w_2) \cdots P(w_n), \\ P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_2) \cdots P(w_n|w_{n-1}), \\ P(w_1\cdots w_n) = P(w_1) P(w_2|w_1) P(w_3|w_1w_2) P(w_4|w_2w_3) \cdots P(w_n|w_{n-2}w_{n-1}).$$ This means that your expression for $N=2$ is wrong.

In practice, we don't want to store special tables for the first $N-1$ characters. There are two ways around this. First, we can ignore entirely the first $N-1$ words. This makes sense when the text is very long, and we don't expect the first few words to make a big difference in the resulting probability. Second, we can include a special "blank" symbol and add it to our tables, so that (for example) $P(w_1)$ is stored as $P(w_1|\not{b}\ldots \not{b})$.

Usually one stores not the actual probabilities but rather their logarithm. The reason is that adding numbers is faster than multiplying them. As an added benefit, you don't have to worry about the dynamic range of the floating point data type you use (the actual probability could be rather close to 0 and could cause underflow, but this is unlikely for its logarithm).

Another thing to keep in mind is that the results are more meaningful as the text becomes longer. Your example is very short and doesn't serve as a good test case.

• I should mention -- I'm also computing these probabilities for the purpose of random sentence generation, so in that case I can't really ignore the first N - 1 words since they have to be generated. The second approach also seems reasonable for this purpose but that seems like it accomplishes the same thing as just computing separate unigram and bigram tables (which would use less space), no? Sep 25 '15 at 3:11
• @Intredasting The approaches are equivalent, use whichever you prefer. Sep 25 '15 at 5:22

You seem to be having trouble figuring out how to compute P(world | <s> Hello). If so, here's how to compute that probability, from the trigram frequencies.

Let f(W X Y) denote the frequency of the trigram W X Y. Now find all words Y that can appear after <s> Hello, and compute the sum of f(<s> Hello Y) over all such Y. This sum is the frequency of the bigram <s> Hello, so call it f(<s> Hello).

Now a reasonable estimate for P(world | <s> Hello) is simply f(<s> Hello World) / f(<s> Hello).

In practice, I recommend you use Laplace smoothing or some other kind of smoothing, to handle zero counts better.

• I am using Good-Turing smoothing for handling zero counts :) Sep 24 '15 at 18:31
• @Intredasting, yup, that works. :-) Did my answer resolve your doubt / answer your question?
– D.W.
Sep 24 '15 at 19:07
• I think Yuval's answer is a bit closer to what I'm looking for. Sep 25 '15 at 3:03