Natural Language Processing · M2 · papers

Q2B · Laplace-smoothed bigram probability

Solved final paper · December 2025

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

Question. Consider the following training corpus:
1. artists paint murals in city
2. musicians play songs in city
3. painters paint murals on walls
4. signs are near city
Using a bigram language model with Laplace smoothing, evaluate the probability of the test sentence: “artists paint murals near city”. Assume the <s> and </s> for each sentence. [10 marks]

Answer

Given

artists paint murals in city
musicians play songs in city
painters paint murals on walls
signs are near city

Test: artists paint murals near city. 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: are, artists, city, in, murals, musicians, near, on, paint, painters, play, signs, songs, walls, <s>, </s> gives V = 16. 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> → artists → paint → murals → near → city → </s>.

Step 3. Count first, then add one

Required bigram	History count	Pair count	Smoothed probability
<s> → artists	4	1	(1+1)/(4+16) = 1/10
artists → paint	1	1	(1+1)/(1+16) = 2/17
paint → murals	2	2	(2+1)/(2+16) = 1/6
murals → near	2	0	(0+1)/(2+16) = 1/18
near → city	1	1	(1+1)/(1+16) = 2/17
city → </s>	3	3	(3+1)/(3+16) = 4/19

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}{20}\times\frac{2}{17}\times\frac{3}{18}\times\frac{1}{18}\times\frac{2}{17}\times\frac{4}{19}

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> → artists	$1\times\frac{1}{10}=\frac{1}{10}$
2. artists → paint	$\frac{1}{10}\times\frac{2}{17}=\frac{1}{85}$
3. paint → murals	$\frac{1}{85}\times\frac{1}{6}=\frac{1}{510}$
4. murals → near	$\frac{1}{510}\times\frac{1}{18}=\frac{1}{9180}$
5. near → city	$\frac{1}{9180}\times\frac{2}{17}=\frac{1}{78030}$
6. city → </s>	$\frac{1}{78030}\times\frac{4}{19}=\frac{2}{741285}$

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

P=\frac{2}{741285}\approx 2.69801763\times10^{-6}

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.69801763 × 10^-6 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.