# Q4B · HMM emission, transition and sequence

Subject: Natural Language Processing

Exam: TEE

Reader: https://deep-learning-study-room.vercel.app/nlp/#tee/mocks/timed-final-2025/final-2025-q4b

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/tee/mocks/timed-final-2025--final-2025-q4b/

TEE · actual previous paper · 100 marks · 180 minutes

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

### Answer

### Given

| Sentence | Tagged sequence |
| --- | --- |
| 1 | cat/Noun chase/Verb mice/Noun |
| 2 | the/Det dog/Noun runs/Verb |
| 3 | a/Det cat/Noun eats/Verb cheese/Noun |

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



$$
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?



$$
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.



$$
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

| Tag / word | a | cat | chase | cheese | dog | eats | mice | runs | the |
| --- | --- | --- | --- | --- | --- | --- | --- | --- | --- |
| Det | 1/2 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1/2 |
| Noun | 0 | 2/5 | 0 | 1/5 | 1/5 | 0 | 1/5 | 0 | 0 |
| Verb | 0 | 0 | 1/3 | 0 | 0 | 1/3 | 0 | 1/3 | 0 |

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

| From | To Det | To Noun | To Verb | To End | Outgoing total |
| --- | --- | --- | --- | --- | --- |
| Start | 2 | 1 | 0 | 0 | 3 |
| Det | 0 | 2 | 0 | 0 | 2 |
| Noun | 0 | 0 | 3 | 2 | 5 |
| Verb | 0 | 2 | 0 | 1 | 3 |

### Step 5. Divide each row by its outgoing total

| From / To | Det | Noun | Verb | End |
| --- | --- | --- | --- | --- |
| Start | 2/3 | 1/3 | 0 | 0 |
| Det | 0 | 1 | 0 | 0 |
| Noun | 0 | 0 | 3/5 | 2/5 |
| Verb | 0 | 2/3 | 0 | 1/3 |

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

| Event in order | Probability |
| --- | --- |
| Start → Det | 2/3 |
| Det emits the | 1/2 |
| Det → Noun | 1 |
| Noun emits cat | 2/5 |
| Noun → Verb | 3/5 |
| Verb emits eats | 1/3 |
| Verb → Noun | 2/3 |
| Noun emits mice | 1/5 |
| Noun → End | 2/5 |

### Step 7. Multiply, including the end transition



$$
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 | 

$$
1\times\frac{2}{3}=\frac{2}{3}
$$

 |
| 2. Det emits the | 

$$
\frac{2}{3}\times\frac{1}{2}=\frac{1}{3}
$$

 |
| 3. Det → Noun | 

$$
\frac{1}{3}\times1=\frac{1}{3}
$$

 |
| 4. Noun emits cat | 

$$
\frac{1}{3}\times\frac{2}{5}=\frac{2}{15}
$$

 |
| 5. Noun → Verb | 

$$
\frac{2}{15}\times\frac{3}{5}=\frac{2}{25}
$$

 |
| 6. Verb emits eats | 

$$
\frac{2}{25}\times\frac{1}{3}=\frac{2}{75}
$$

 |
| 7. Verb → Noun | 

$$
\frac{2}{75}\times\frac{2}{3}=\frac{4}{225}
$$

 |
| 8. Noun emits mice | 

$$
\frac{4}{225}\times\frac{1}{5}=\frac{4}{1125}
$$

 |
| 9. Noun → End | 

$$
\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.



$$
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.