Natural Language Processing · M2 · papers

Q2B · Laplace smoothing on a second corpus

Solved re-exam · February 2026

M2-relevant questions from an actual TEE paper · original marks retained for longer practice

Question. Consider the following training corpus:
1. cats chase mice in the garden
2. dogs bark loudly at night
3. birds sing in the morning
4. children play games in the park
Using a bigram language model with Laplace smoothing, evaluate the probability of the test sentence: “cats bark in the park.” Assume <s> and </s> as start and end of the sentence. [10 marks]

Answer

Given

cats chase mice in the garden
dogs bark loudly at night
birds sing in the morning
children play games in the park

Test: cats bark in the park. Add one start token <s> and one end token </s> to every training and test sentence.

To find

The Laplace-smoothed bigram probability of the complete test sentence, including its end token.

Formula: which one and why

P_{+1}(w_i\mid w_{i-1})=\frac{C(w_{i-1},w_i)+1}{C(w_{i-1})+V}

C(previous,current) counts that adjacent pair in the training corpus. C(previous) counts its occurrences as a history. V is the vocabulary size. Add-one smoothing is necessary because an unseen pair must not force the whole sentence probability to zero.

P(w_1,\ldots,w_n,\langle/s\rangle\mid\langle s\rangle)=\prod_{i=1}^{n+1}P(w_i\mid w_{i-1})

Solution

Step 1. Fix the token and vocabulary convention

Lowercase words and remove the final punctuation. The supplied course key counts both boundary tokens in V. Following that convention: at, bark, birds, cats, chase, children, dogs, games, garden, in, loudly, mice, morning, night, park, play, sing, the, <s>, </s> gives V = 20. The start marker supplies history; it is not an extra probability factor before the first word.

Step 2. List every required transition

The complete test chain is <s> → cats → bark → in → the → park → </s>.

Step 3. Count first, then add one

Required bigram	History count	Pair count	Smoothed probability
<s> → cats	4	1	(1+1)/(4+20) = 1/12
cats → bark	1	0	(0+1)/(1+20) = 1/21
bark → in	1	0	(0+1)/(1+20) = 1/21
in → the	3	3	(3+1)/(3+20) = 4/23
the → park	3	1	(1+1)/(3+20) = 2/23
park → </s>	1	1	(1+1)/(1+20) = 2/21

Count only adjacent words, never words that merely appear in the same sentence. The unseen pairs have count zero, so their numerator becomes one.

Step 4. Multiply all six probabilities

P=\frac{2}{24}\times\frac{1}{21}\times\frac{1}{21}\times\frac{4}{23}\times\frac{2}{23}\times\frac{2}{21}

Start with subtotal 1. At each row, multiply the previous subtotal by exactly one next factor. Simplify the fraction after multiplication, but do not round it.

Factor being included	Previous subtotal × next factor = new subtotal
1. <s> → cats	$1\times\frac{1}{12}=\frac{1}{12}$
2. cats → bark	$\frac{1}{12}\times\frac{1}{21}=\frac{1}{252}$
3. bark → in	$\frac{1}{252}\times\frac{1}{21}=\frac{1}{5292}$
4. in → the	$\frac{1}{5292}\times\frac{4}{23}=\frac{1}{30429}$
5. the → park	$\frac{1}{30429}\times\frac{2}{23}=\frac{2}{699867}$
6. park → </s>	$\frac{2}{699867}\times\frac{2}{21}=\frac{4}{14697207}$

The last subtotal is the complete product. Only now convert the fraction to a decimal.

P=\frac{4}{14697207}\approx 2.72160554\times10^{-7}

Step 5. Interpret the result

This is a joint sentence probability, so a small value is normal. Do not add transition probabilities; each word must occur in sequence, so the chain multiplies them.

Final answer

P ≈ 2.72160554 × 10^-7 with the stated course vocabulary convention.

Yaad rakho: Pair count mein 1 jodo, previous-word count mein V; phir saare fractions multiply karo.

Convention note: Some implementations exclude <s> from the predicted vocabulary. Their V is one smaller and their numerical probability differs. In an exam, state V explicitly and follow the convention specified in the question or class solution.