Natural Language Processing · TEE · formulas

Adjusted counts and relative discounting

Smoothing & perplexity

Formulas explained through full worked examples

The slides also express smoothing through an adjusted count c*. Instead of writing the smoothed probability with denominator N+V, they rescale its numerator so the denominator can remain N. Algebraically these are equivalent:

c^*=(c+1)\frac{N}{N+V},\qquad P_L(w)=\frac{c^*}{N}LaTeX: c^*=(c+1)\frac{N}{N+V},\qquad P_L(w)=\frac{c^*}{N}
d=\frac{c^*}{c}\quad(c>0)LaTeX: d=\frac{c^*}{c}\quad(c>0)

The relative discount d compares adjusted and original counts. It is undefined when c=0 because division by zero is undefined. Add-one smoothing moves the distribution toward uniformity: frequent events are reduced, but some rare seen events may increase. It is not correct to claim that every nonzero count must decrease under Laplace smoothing.

Question. For N=20 and V=5, a word has original count c=10. Find its adjusted count, smoothed probability and relative discount.

Given

N=20; V=5; c=10.

To find

c*, P_L and d.

Formula and why it applies

c^*=(c+1)N/(N+V),\quad P_L=c^*/N,\quad d=c^*/cLaTeX: c^*=(c+1)N/(N+V),\quad P_L=c^*/N,\quad d=c^*/c

These expressions rewrite add-one smoothing without changing its probability.

Solution

Step 1. Form the new total
N+V=20+5=25LaTeX: N+V=20+5=25
Step 2. Find the adjusted count
c^*=(10+1)\frac{20}{25}=11(0.8)=8.8LaTeX: c^*=(10+1)\frac{20}{25}=11(0.8)=8.8
Step 3. Find the probability
P_L=8.8/20=0.44LaTeX: P_L=8.8/20=0.44
Step 4. Find the relative discount
d=8.8/10=0.88LaTeX: d=8.8/10=0.88
Final answer. c*=8.8, P_L=0.44, d=0.88. The original probability 0.5 is reduced.

Question. Under N=20, V=5, a rare word occurs once. Compute its adjusted count and compare the original and smoothed probabilities.

Given

N=20; V=5; c=1.

To find

c*, original P and smoothed P_L.

Formula and why it applies

c^*=(c+1)N/(N+V)LaTeX: c^*=(c+1)N/(N+V)

The same smoothing rule may increase a rare event's probability.

Solution

Step 1. Original probability
P=1/20=0.05LaTeX: P=1/20=0.05
Step 2. Adjusted count
c^*=(1+1)(20/25)=1.6LaTeX: c^*=(1+1)(20/25)=1.6
Step 3. Smoothed probability
P_L=1.6/20=0.08LaTeX: P_L=1.6/20=0.08
Final answer. c*=1.6 and P_L=0.08, which exceeds the original 0.05.

Question. For N=20 and V=5, an in-vocabulary word has count zero. Find its adjusted count and smoothed probability. Can a relative discount be calculated?

Given

c=0; N=20; V=5.

To find

c*, P_L and whether d exists.

Formula and why it applies

c^*=(c+1)N/(N+V),\qquad P_L=c^*/NLaTeX: c^*=(c+1)N/(N+V),\qquad P_L=c^*/N

The pseudo-count creates positive mass for the unseen vocabulary item.

Solution

Step 1. Adjusted count
c^*=(0+1)(20/25)=0.8LaTeX: c^*=(0+1)(20/25)=0.8
Step 2. Smoothed probability
P_L=0.8/20=0.04LaTeX: P_L=0.8/20=0.04
Step 3. Relative discount

d would be 0.8/0. That is undefined, so do not report a finite discount.

Final answer. c*=0.8 and P_L=0.04; relative discount is undefined for c=0.