Natural Language Processing · M2 · mocks

Q4 (3 marks)

M2 Mock C · mixed numerical practice

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

Q4

Training sentences with tags are: “the/D cat/N sleeps/V” and “a/D dog/N runs/V”. Estimate start/end-inclusive transition probabilities and the joint probability of “the cat sleeps” with path D,N,V. (3 marks)

Given

Two paths start→D→N→V→end. Four distinct words the,a,cat,dog and two verbs sleeps,runs. Use unsmoothed estimates and lowercase tokens.

To find

Transitions, required emissions and full path score.

Formula and why it applies

P(t_j\mid t_i)=\frac{C(t_i\to t_j)}{\sum_k C(t_i\to t_k)}

P(w\mid t)=\frac{C(w,t)}{C(t)}

Transition denominators count outgoing transitions from the previous state. Emission denominators count all tokens tagged with the emitting state.

Solution

Step 1. Count transitions

start→D, D→N, N→V and V→end each occur twice. Each state has just one observed next state.

Step 2. Divide to get probabilities

P(D\mid start)=P(N\mid D)=P(V\mid N)=P(end\mid V)=\frac22=1

Step 3. Estimate emissions

P(\text{the}\mid D)=\frac12

P(\text{cat}\mid N)=\frac12

P(\text{sleeps}\mid V)=\frac12

Step 4. Multiply in word order

P=1\times\frac12\times1\times\frac12\times1\times\frac12\times1=\frac18=0.125

Joint probability=0.125. Each of the four observed transition probabilities is 1.