Exercise-Solution

md5 kBSolution of HMM POS tagging exercise

POS Tagging with Hidden Markov Models

t = 3 · 'runs'

t = 2 · 'cat'

t = 1 · 'the'

A[DT→NN]=1 · B[NN|cat]=1/6

A[NN→VB]=1 · B[VB|runs]=0.5

DT = 0.25

NN = 0

VB = 0

DT = 0

NN ≈ 0.042

VB = 0

DT = 0

NN = 0

VB ≈ 0.021

Given the HMM you computed in Part 1, use the Viterbi algorithm to find the most likely tag sequence for the following sentence:

the cat runs\text{the cat runs}

Solution

Part 1

  1. As we can see from the corpus, the possible tags are NN, VB, and DT, so: States (Q): Q={NN,VB,DT}Q = \{NN, VB, DT\}

  2. All unique words in the corpus form the following vocabulary Vocabulary (V): V={the,dog,runs,lion,is,an,animal,cat}V = \{\text{the}, \text{dog}, \text{runs}, \text{lion}, \text{is}, \text{an}, \text{animal}, \text{cat}\}

  3. Prior Probabilities (π\pi):

    • π(DT)=0.5\pi(DT) = 0.5, since 2 out of 4 sentences start with a determiner (the).
    • π(NN)=0.5\pi(NN) = 0.5, since 2 out of 4 sentences start with a noun.
    • π(VB)=0.0\pi(VB) = 0.0, since no sentence starts with a verb.
  4. 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
  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

t = 3
word = runs

t = 2
word = cat

t = 1
word = the

Start

DT
0.25

NN
0

VB
0

DT
0

NN
1/24 ≈ 0.042

VB
0

DT
0

NN
0

VB
1/48 ≈ 0.021

Best path

Step-by-Step Computation

Initialization (t=1, word="the")(t = 1,\ \text{word} = \text{"the"}):

v(DT,1)=π(DT)×B[DT∣the]=0.5×0.5=0.25v(DT, 1) = \pi(DT) \times B[DT \mid \text{the}] = 0.5 \times 0.5 = \mathbf{0.25} v(NN,1)=π(NN)×B[NN∣the]=0.5×0=0v(NN, 1) = \pi(NN) \times B[NN \mid \text{the}] = 0.5 \times 0 = 0 v(VB,1)=π(VB)×B[VB∣the]=0×0=0v(VB, 1) = \pi(VB) \times B[VB \mid \text{the}] = 0 \times 0 = 0

Recursion (t=2, word="cat")(t = 2,\ \text{word} = \text{"cat"}):

v(DT,2)=0∵B[DT∣cat]=0v(DT, 2) = 0 \quad \because B[DT \mid \text{cat}] = 0 v(NN,2)=v(DT,1)×A[DT→NN]×B[NN∣cat]=0.25×1×16=124≈0.042v(NN, 2) = v(DT,1) \times A[DT \to NN] \times B[NN \mid \text{cat}] = 0.25 \times 1 \times \tfrac{1}{6} = \mathbf{\tfrac{1}{24} \approx 0.042} v(VB,2)=0∵B[VB∣cat]=0v(VB, 2) = 0 \quad \because B[VB \mid \text{cat}] = 0

Recursion (t=3, word="runs")(t = 3,\ \text{word} = \text{"runs"}):

v(DT,3)=0∵B[DT∣runs]=0v(DT, 3) = 0 \quad \because B[DT \mid \text{runs}] = 0 v(NN,3)=0∵B[NN∣runs]=0v(NN, 3) = 0 \quad \because B[NN \mid \text{runs}] = 0 v(VB,3)=v(NN,2)×A[NN→VB]×B[VB∣runs]=124×1×0.5=148≈0.021v(VB, 3) = v(NN,2) \times A[NN \to VB] \times B[VB \mid \text{runs}] = \tfrac{1}{24} \times 1 \times 0.5 = \mathbf{\tfrac{1}{48} \approx 0.021}

Backtracking:

tt Winning state Came from
3 VB NN
2 NN DT
1 DT —
Result

the/DTcat/NNruns/VB\boxed{\text{the}/DT \quad \text{cat}/NN \quad \text{runs}/VB}

In HMM POS tagging exercise