# N-gram language model question

I have this question I found regarding n-gram modelling in the textbook Speech and Language Processing:

Suppose we didn't use the end symbol </s>. Train an unsmoothed bigram grammar on the following corpus without using the end-symbol </s>.

<s> a b
<s> b b
<s> b a
<s> a a

Demonstrate that your bigram model does not assign a single probability distribution across all sentence lengths by showing that the sum of the probability of the four possible 2 word sentences over the alphabet {a, b} is 1.0 and the sum of the probability of all possible 3 word sentences over the alphabet {a, b} is also 1.0.
Note:
<s> means beginning of sentence.
</s> means end of sentence.

Speech and Language Processing, Daniel Jarafsky and James H. Martin, 3rd ed., Exercise 3.5, p.55

My attempt was:

Two word sentences:
P(a | b) = count(b a) / count(b) = 1 / 4
P(b | a) = count(a b) / count(a) = 1 / 4
P(a | a) = count(a a) / count(a) = 1 / 4
P(b | b) = count(b b) / count(b) = 1 / 4


sum = 1

but when I get to 3 word sentences:

P(a | a, a) = count(a a a) / count(a) = 1 / 64

Now, you get 8 three word sentences which sums to 8 / 64

This is where I am getting lost. I need some pointing in the right direction.

For these 2-word sentences, notice that the original equation for the MLE approximation of the probabilities of the bigram is:

$$P(w_i|w_{i-1}) = \frac{C(w_{i-1}w_i)}{\sum_w{C(w_{i-1}w)}} = \frac{C(w_{i-1}w_i)}{C(w_{i-1})},$$

where the denominator $$C(w_{i-1})$$ only equals the count of $$w_{i-1}$$ iff there is an end-symbol $$\text{}$$, otherwise the number of times $$w_{i-1}$$ appears at the end of the sentence has to be subtracted from its count. Therefore, the "count" function you are using in the denominator is wrong, and the true probabilities in your particular corpus are:

$$$$\begin{split} P(a|a) &= \frac{C(aa)}{C(a)} &= \frac{1}{2} \\ P(b|a) &= \frac{C(ab)}{C(a)} &= \frac{1}{2} \\ P(a|b) &= \frac{C(ba)}{C(b)} &= \frac{1}{2} \\ P(b|b) &= \frac{C(bb)}{C(b)} &= \frac{1}{2} \\ P(a|\text{}) &= \frac{C(\text{}a)}{C(\text{})} = \frac{2}{4} &= \frac{1}{2} \\ P(b|\text{}) &= \frac{C(\text{}b)}{C(\text{})} = \frac{2}{4} &= \frac{1}{2} \\ \end{split}$$$$

and now the sum of the probabilities of all possible 2-word sentences with this vocabulary becomes equal to 1:

$$\sum_{w, v\in\{a, b\}^2}P(\text{}wv) = \sum_{w, v\in\{a, b\}^2} P(w|\text{})\cdot P(v|w) = \sum_{w, v\in\{a, b\}^2} \frac{1}{4} = 1 .$$

in the Trigram model:

$$P(w_k|w_1, . . . ,w_{k−1}) =P(w_k|w_{k−2},w_{k−1})$$

hence, the Probability of sentence $$w_1....w_N$$ is as follows:

$$\prod_{k=1}^N {P(w_k|w_{k−2}w_{k−1})}$$

and $$P(w_3|w_2,w_1) = \cfrac{count(w_3,w_2,w_1)}{count(w_2,w_1)}$$

in words: you must divide $$count(w_3,w_2,w_1)$$ by the number of times $$(w_2,w_1)$$ appeared one after the other, and not separately. Then it should sum to $$1$$.

I m not sure, but I think this will help you. Here we use the tri-gram model, because the bi-gram model is not used for 3 words, and the answer is not the same as the bi-gram model for this corpus. $$P(a|a,b) = 0/1 = 0$$ $$P(b|b,a) = 0/1 =0$$

Similarly, all combinations of $$\{a,b\}$$ have a zero answer.