Natural Language Processing · TEE · papers

Q4B · HMM emission, transition and sequence

Solved final paper · December 2025

Actual final examination · 2 December 2025 · 100 marks · 3 hours

Answer

Given

Test words: the cat eats mice. Given tag sequence: Det → Noun → Verb → Noun. Include Start and End for all sentences. Lowercase the corpus so sentence-initial Cat and cat are one word.

To find

Emission probabilities, transition probabilities and the joint probability of the specified tag-and-word sequence.

Formula: which one and why

LaTeX: P(w\mid t)=\frac{C(t,w)}{C(t)}

An emission probability asks: among tokens carrying this tag t, what fraction are the word w?

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

A transition probability asks: among transitions leaving tag tᵢ, what fraction go to tⱼ? Include End in the outgoing counts. The paper says “transmission”; the standard HMM term is transition.

LaTeX: P(\mathbf w,\mathbf t)=P(t_1\mid\mathrm{Start})\prod_{i=1}^{n}P(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 tokens for each tag

Det has 2 tokens; Noun has 5 tokens; Verb has 3 tokens. The repeated noun cat occurs twice with Noun; every other displayed noun occurs once. The three verb types each occur once.

Step 2. Build the emission matrix

Each row sums to one. A zero means no occurrence under that tag in this unsmoothed training corpus; no add-one smoothing was requested.

Step 3. Write the three tag chains

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

Step 4. Count outgoing transitions

Step 5. Divide each row by its outgoing total

End is terminal, so it has no estimated outgoing row. The four nonterminal rows each sum to one.

Step 6. Choose the factors for the given sequence

Step 7. Multiply, including the end transition

LaTeX: P=\frac23\times\frac12\times1\times\frac25\times\frac35\times\frac13\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 included	Previous subtotal × next factor = new subtotal
1. Start → Det	LaTeX: 1\times\frac{2}{3}=\frac{2}{3}
2. Det emits the	LaTeX: \frac{2}{3}\times\frac{1}{2}=\frac{1}{3}
3. Det → Noun	LaTeX: \frac{1}{3}\times1=\frac{1}{3}
4. Noun emits cat	LaTeX: \frac{1}{3}\times\frac{2}{5}=\frac{2}{15}
5. Noun → Verb	LaTeX: \frac{2}{15}\times\frac{3}{5}=\frac{2}{25}
6. Verb emits eats	LaTeX: \frac{2}{25}\times\frac{1}{3}=\frac{2}{75}
7. Verb → Noun	LaTeX: \frac{2}{75}\times\frac{2}{3}=\frac{4}{225}
8. Noun emits mice	LaTeX: \frac{4}{225}\times\frac{1}{5}=\frac{4}{1125}
9. Noun → End	LaTeX: \frac{4}{1125}\times\frac{2}{5}=\frac{8}{5625}

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

LaTeX: P=\frac8{5625}\approx0.0014222222

Final answer

Joint sequence probability = 8/5625 ≈ 0.0014222222. This is the probability of the specified words and tags together. It is not the probability of the word sequence summed over every possible tag path.

Yaad rakho: Tag se tag = transition; tag se word = emission. Dono alternate multiply, end ko mat bhoolo.

Boundary reminder: The initial factor is P(Det | Start) = 2/3, based on three sentence starts, and the final factor is P(End | Noun) = 2/5. The overall fraction of Det tokens, 2/10, is not the start probability. Using it and omitting End, as in the handwritten key’s last line, computes a different quantity.