# Q4 (3 marks)

Subject: Natural Language Processing

Exam: M2

Reader: https://deep-learning-study-room.vercel.app/nlp/#m2/mocks/mock-b/q4

Canonical: https://deep-learning-study-room.vercel.app/read/nlp/m2/mocks/mock-b--q4/

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.