Natural Language Processing · TEE · papers

Q4B · A second HMM sequence

Solved re-exam · February 2026

Actual re-examination · 9 February 2026 · 100 marks · 3 hours

Question. Consider the following POS tagged corpus. Apply Hidden Markov Model (HMM) approach to:
1. Dog/Noun eats/Verb bread/Noun
2. The/Det cat/Noun sleeps/Verb
3. A/Det dog/Noun eats/Verb fish/Noun
i. Construct the emission probability matrix.
ii. Construct the transmission probability matrix.
iii. Calculate the probability of the given sequence of events: The/Det dog/Noun eats/Verb bread/Noun.
Note: Include start and end characters for all the sentences. [10 marks]

Answer

The repeated verb eats has a different emission count from the final paper; recalculate it rather than copying the previous numerical result.

Given

SentenceTagged sequence
1dog/Noun eats/Verb bread/Noun
2the/Det cat/Noun sleeps/Verb
3a/Det dog/Noun eats/Verb fish/Noun

Lowercase the corpus. Test sequence: the/Det dog/Noun eats/Verb bread/Noun. Add Start and End markers.

To find

Emission and transition matrices, then the probability of the supplied tagged sequence.

Formula: which one and why

P(w\mid t)=\frac{C(t,w)}{C(t)}LaTeX: P(w\mid t)=\frac{C(t,w)}{C(t)}
P(t_j\mid t_i)=\frac{C(t_i,t_j)}{\sum_kC(t_i,t_k)}LaTeX: P(t_j\mid t_i)=\frac{C(t_i,t_j)}{\sum_kC(t_i,t_k)}

Emission divides the word’s tag-specific count by the total tokens with that tag. Transition divides the tag-pair count by all transitions leaving the previous tag, including End.

P(\mathbf w,\mathbf t)=P(t_1\mid\mathrm{Start})\prod_iP(w_i\mid t_i)\prod_{i=2}^{n}P(t_i\mid t_{i-1})P(\mathrm{End}\mid t_n)LaTeX: P(\mathbf w,\mathbf t)=P(t_1\mid\mathrm{Start})\prod_iP(w_i\mid t_i)\prod_{i=2}^{n}P(t_i\mid t_{i-1})P(\mathrm{End}\mid t_n)

Solution

Step 1. Count tag totals and word frequencies

Det: the=1, a=1, total2. Noun: dog=2, bread=1, cat=1, fish=1, total5. Verb: eats=2, sleeps=1, total3.

Step 2. Construct emission matrix

Tag / wordabreadcatdogeatsfishsleepsthe
Det1/20000001/2
Noun01/51/52/501/500
Verb00002/301/30

Step 3. Count transitions from the three chains

Start → Noun → Verb → Noun → End
Start → Det → Noun → Verb → End
Start → Det → Noun → Verb → Noun → End

FromDet countNoun countVerb countEnd countTotal
Start21003
Det02002
Noun00325
Verb02013

Step 4. Divide outgoing counts

From / toDetNounVerbEnd
Start2/31/300
Det0100
Noun003/52/5
Verb02/301/3

All nonterminal rows sum to one. No smoothing is requested.

Step 5. Write every sequence factor

EventProbability
Start → Det2/3
Det emits the1/2
Det → Noun1
Noun emits dog2/5
Noun → Verb3/5
Verb emits eats2/3
Verb → Noun2/3
Noun emits bread1/5
Noun → End2/5

Step 6. Multiply all factors

P=\frac23\times\frac12\times1\times\frac25\times\frac35\times\frac23\times\frac23\times\frac15\times\frac25LaTeX: P=\frac23\times\frac12\times1\times\frac25\times\frac35\times\frac23\times\frac23\times\frac15\times\frac25

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 includedPrevious subtotal × next factor = new subtotal
1. Start → Det1\times\frac{2}{3}=\frac{2}{3}LaTeX: 1\times\frac{2}{3}=\frac{2}{3}
2. Det emits the\frac{2}{3}\times\frac{1}{2}=\frac{1}{3}LaTeX: \frac{2}{3}\times\frac{1}{2}=\frac{1}{3}
3. Det → Noun\frac{1}{3}\times1=\frac{1}{3}LaTeX: \frac{1}{3}\times1=\frac{1}{3}
4. Noun emits dog\frac{1}{3}\times\frac{2}{5}=\frac{2}{15}LaTeX: \frac{1}{3}\times\frac{2}{5}=\frac{2}{15}
5. Noun → Verb\frac{2}{15}\times\frac{3}{5}=\frac{2}{25}LaTeX: \frac{2}{15}\times\frac{3}{5}=\frac{2}{25}
6. Verb emits eats\frac{2}{25}\times\frac{2}{3}=\frac{4}{75}LaTeX: \frac{2}{25}\times\frac{2}{3}=\frac{4}{75}
7. Verb → Noun\frac{4}{75}\times\frac{2}{3}=\frac{8}{225}LaTeX: \frac{4}{75}\times\frac{2}{3}=\frac{8}{225}
8. Noun emits bread\frac{8}{225}\times\frac{1}{5}=\frac{8}{1125}LaTeX: \frac{8}{225}\times\frac{1}{5}=\frac{8}{1125}
9. Noun → End\frac{8}{1125}\times\frac{2}{5}=\frac{16}{5625}LaTeX: \frac{8}{1125}\times\frac{2}{5}=\frac{16}{5625}

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

P=\frac{16}{5625}\approx0.0028444444LaTeX: P=\frac{16}{5625}\approx0.0028444444

Final answer

P = 16/5625 ≈ 0.0028444444 for these words and specified tags jointly. The two occurrences of eats give P(eats | Verb) = 2/3.

Yaad rakho: Same tag structure ho sakta hai, lekin word emission counts dobara count karna.

Boundary reminder: Include P(Det | Start) = 2/3 and P(End | Noun) = 2/5. The handwritten key’s final line instead inserts the overall Det fraction 2/10 and omits End; the complete boundary-aware probability requested here is 0.0028444444.