Natural Language Processing · TEE · formulas

Estimate transition and emission probabilities from tagged data

HMM & decoding

Formulas explained through full worked examples

P(t'\mid t)=\frac{C(t,t')}{C(t)\text{ with a following tag/end event}}

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

In a transition denominator, count the previous tag's outgoing events. In an emission denominator, count all tokens bearing that tag. With explicit end transitions the totals align conveniently. Keep the two numerator types separate: tag→tag counts are not word→tag counts.

Question. A tagged corpus contains 116454 determiner tags DT, each counted with an outgoing event. DT is followed by NN 56509 times. Estimate P(NN|DT).

Given

C(DT)=116454; C(DT,NN)=56509.

To find

The DT→NN transition probability.

Formula and why it applies

P(NN\mid DT)=C(DT,NN)/C(DT)

The denominator is the number of previous DT contexts because DT is the condition.

Solution

Step 1. Identify the transition count

DT followed by NN occurs 56509 times.

Step 2. Identify the conditional total

There are 116454 DT contexts.

Step 3. Divide

P(NN\mid DT)=\frac{56509}{116454}\approx0.485247

Final answer. P(NN|DT)≈0.485247.

Question. The tag VBZ occurs 21627 times, and 10073 of those tokens are the word “is”. Estimate P(is|VBZ).

Given

C(VBZ)=21627; C(is,VBZ)=10073.

To find

The emission probability of is from VBZ.

Formula and why it applies

P(is\mid VBZ)=C(is,VBZ)/C(VBZ)

The condition is the tag VBZ; we ask which word it emits.

Solution

Step 1. Choose the word-tag count

The required word is is with tag VBZ: count 10073.

Step 2. Choose the tag total

All VBZ-tagged word tokens: count 21627.

Step 3. Divide

P(is\mid VBZ)=\frac{10073}{21627}\approx0.465760

Final answer. P(is|VBZ)≈0.465760. This is different from P(VBZ|is).

Question. Use the tagged sentences “dogs/N chase/V cats/N” and “cats/N sleep/V”. Estimate the initial tag probabilities, all nonzero transitions including END, and emissions.

Given

Corpus: START dogs/N chase/V cats/N END; START cats/N sleep/V END.

To find

Initial distribution, transition rows and emission rows.

Formula and why it applies

\pi_t=C(START,t)/2,\quad a_{tu}=C(t,u)/C(t),\quad b_t(w)=C(w,t)/C(t)

The corpus explicitly tells us the tags, so we can count training frequencies directly.

Solution

Step 1. Count tag tokens

N occurs 3 times: dogs, cats, cats. V occurs 2 times: chase, sleep.

Step 2. Count sentence starts

Both sentences start with N.

\pi_N=2/2=1,\quad \pi_V=0/2=0

Step 3. Count transitions

Pair	Count
N→V	2
N→END	1
V→N	1
V→END	1

Step 4. Normalize transition rows

Current	To N	To V	To END
N	0	2/3	1/3
V	1/2	0	1/2

Step 5. Count and normalize emissions

Tag	dogs	cats	chase	sleep
N	1/3	2/3	0	0
V	0	0	1/2	1/2

Final answer. π=(1,0); transitions and emissions are given in the completed tables. Each complete probability row sums to 1.

Yaad rakho: Tag→tag table aur tag→word table ko mix mat karna.