Natural Language Processing · M2 · mocks

Q4 (3 marks)

M2 Mock B · unseen pairs & decoding

M2 · confirmed 2 + 2 + any two of 3 + 3 + 3 · worked practice

Q4

A two-state HMM has initial probabilities P(N)=0.6, P(V)=0.4. Transition rows (N→N,N→V)=(0.3,0.7) and (V→N,V→V)=(0.8,0.2). Emissions are P(fish|N)=0.5, P(fish|V)=0.4, P(swim|N)=0.1 and P(swim|V)=0.6. Find the best tag path for “fish swim”, without end transitions. (3 marks)

Given

Two states N,V; all start, transition and relevant emission probabilities are supplied.

To find

Largest joint score and its tag sequence.

Formula and why it applies

\delta_1(t)=P(t)P(w_1\mid t)

\delta_2(t)=P(w_2\mid t)\max_s[\delta_1(s)P(t\mid s)]

Viterbi keeps the best path ending at each tag and stores its predecessor. Enumerating four paths gives the same result for this tiny example.

Solution

Step 1. Initialise fish

\delta_1(N)=0.6\times0.5=0.3

\delta_1(V)=0.4\times0.4=0.16

Step 2. Score both paths ending in N

NN:0.3\times0.3\times0.1=0.009

VN:0.16\times0.8\times0.1=0.0128

Keep VN at N; predecessor V.

Step 3. Score both paths ending in V

NV:0.3\times0.7\times0.6=0.126

VV:0.16\times0.2\times0.6=0.0192

Keep NV at V; predecessor N.

Step 4. Choose and backtrack

0.126 > 0.0128. End at V and follow its stored predecessor N.

Best sequence: N,V, with joint score 0.126.