Natural Language Processing · TEE · papers
Q6b · HMM tables and path
2024-02-12 · re-exam · recovered AI paper
Previous examination · complete worked answers
Answer
Given
| Sentence | Given tags |
|---|---|
| Rita can teach Will | N M V N |
| Spot will see Will | N M V N |
| Will Rita spot Geeta | N N V N |
| Geeta will pat Spot | N M V N |
Required path: Geeta will spot Rita / N M V N. Given initial probabilities: {'N': Fraction(1, 2), 'M': Fraction(1, 4), 'V': Fraction(1, 4)}
To find
Emission and transition tables and the specified tag-path joint probability
Formula: which one and why
LaTeX: P(w\mid t)=\frac{c(t,w)}{c(t)}
LaTeX: P(t_j\mid t_i)=\frac{c(t_i,t_j)}{\sum_kc(t_i,t_k)}The second formula is the declared no-END convention. Reset at sentence boundaries; never create a transition from the last word of one training sentence to the first of the next.
Step 1. Count emissions
| Tag | Total occurrences | Rita | can | teach | Will | Spot | will | see | spot | Geeta | pat |
|---|---|---|---|---|---|---|---|---|---|---|---|
| N | 9 | 2 | 0 | 0 | 3 | 2 | 0 | 0 | 0 | 2 | 0 |
| M | 3 | 0 | 1 | 0 | 0 | 0 | 2 | 0 | 0 | 0 | 0 |
| V | 4 | 0 | 0 | 1 | 0 | 0 | 0 | 1 | 1 | 0 | 1 |
Step 2. Divide each emission by its tag count
| Tag | Rita | can | teach | Will | Spot | will | see | spot | Geeta | pat |
|---|---|---|---|---|---|---|---|---|---|---|
| N | 2/9 | 0 | 0 | 1/3 | 2/9 | 0 | 0 | 0 | 2/9 | 0 |
| M | 0 | 1/3 | 0 | 0 | 0 | 2/3 | 0 | 0 | 0 | 0 |
| V | 0 | 0 | 1/4 | 0 | 0 | 0 | 1/4 | 1/4 | 0 | 1/4 |
Step 3. Count transitions inside each sentence
| From | Outgoing transitions | Sentence-final count | N | M | V |
|---|---|---|---|---|---|
| N | 5 | 4 | 1 | 3 | 1 |
| M | 3 | 0 | 0 | 0 | 3 |
| V | 4 | 0 | 4 | 0 | 0 |
Step 4. Convert to a transition table
| From / to | N | M | V |
|---|---|---|---|
| N | 1/5 | 3/5 | 1/5 |
| M | 0 | 0 | 1 |
| V | 1 | 0 | 0 |
Here sentence-final tags are excluded from the no-END outgoing denominator. If END is explicitly modeled, divide all tag→tag and tag→END counts by the total tag count instead; the row then includes END. Do not mix denominators.
Step 5. Multiply the given path, in order
| Factor | Probability | Running product |
|---|---|---|
| Initial N | 1/2 | 1 × 1/2 = 1/2 |
| Emit Geeta | 2/9 | 1/2 × 2/9 = 1/9 |
| Transition N→M | 3/5 | 1/9 × 3/5 = 1/15 |
| Emit will | 2/3 | 1/15 × 2/3 = 2/45 |
| Transition M→V | 1 | 2/45 × 1 = 2/45 |
| Emit spot | 1/4 | 2/45 × 1/4 = 1/90 |
| Transition V→N | 1 | 1/90 × 1 = 1/90 |
| Emit Rita | 2/9 | 1/90 × 2/9 = 1/405 |
Final answer
The two displayed probability tables are the estimated HMM. Zero means unobserved without smoothing, not logically impossible.
No-END path joint probability = 1/405 = 0.00246913580247. If a normalized END-state model is explicitly adopted instead, this complete terminated sequence has probability 4/6561 = 0.000609663161103. These are different model conventions, not contradictory answers.