Exercise-Solution
md5 kBSolution of HMM POS tagging exercise
POS Tagging with Hidden Markov Models
Given the HMM you computed in Part 1, use the Viterbi algorithm to find the most likely tag sequence for the following sentence:
Solution
Part 1
-
As we can see from the corpus, the possible tags are NN, VB, and DT, so: States (Q):
-
All unique words in the corpus form the following vocabulary Vocabulary (V):
-
Prior Probabilities ():
- , since 2 out of 4 sentences start with a determiner (the).
- , since 2 out of 4 sentences start with a noun.
- , since no sentence starts with a verb.
-
Transition Matrix (A):
| From \ To | NN | VB | DT |
|---|---|---|---|
| DT | 4/4 = 1 | 0 | 0 |
| NN | 0 | 4/4 = 1 | 0 |
| VB | 0 | 0 | 2/2 = 1 |
- Emission Matrix (B):
| Tag \ Word | the | dog | runs | lion | is | an | animal | cat |
|---|---|---|---|---|---|---|---|---|
| DT | 2/4 = 0.5 | 0 | 0 | 0 | 0 | 2/4 = 0.5 | 0 | 0 |
| NN | 0 | 2/6 = 1/3 | 0 | 1/6 | 0 | 0 | 2/6 = 1/3 | 1/6 |
| VB | 0 | 0 | 2/4 = 0.5 | 0 | 2/4 = 0.5 | 0 | 0 | 0 |
Part 2
We apply the Viterbi algorithm to find the most likely tag sequence for: "the cat runs"
Diagram
Step-by-Step Computation
Initialization :
Recursion :
Recursion :
Backtracking:
| Winning state | Came from | |
|---|---|---|
| 3 | VB | NN |
| 2 | NN | DT |
| 1 | DT | — |