Bayesian Replacement for
Good-Turing
Introduction toMacKay (1994)“Hierarchical Dirichlet Language Model”
Daichi Mochihashi

daichi.mochihashi@atr.jp
ATR SLT Dept.2 Regular Meeting
May 19, 2004
Modified for Über SVM 2004
Aug 3, 2004

Hiearchical Dirichlet Language Model – p.1/15

Overview
N -gram smoothing is a crucial machineryin speech recognition and machine translation.
But N -gram parameters are so numerous, andthere are not much data (e.g. MAD)⇓We can’t make an exact prediction from such data.
But..
Taking our uncertainty about the parameters into themodel, we can make a stable prediction.
(This is called a Bayesian Method.)
We get a theoretically sound smoothing formula.
Hiearchical Dirichlet Language Model – p.2/15

Introduction
By restricting ourselves to bigram for simplicity,
Empirical (Maximum Likelihood) estimate
fi|jp̂i|j ≡ p̂(wi |wj ) =fj(fi|j , fj : frequency of wj → wi  and wj )(1)

Probability 0 for unseen words after wj
e.g. p(an|quite) = 0 simply if “quite an”
accidentally did not appear in the training data.
Some smoothing is required.

Hiearchical Dirichlet Language Model – p.3/15

Existent smoothing“Adding some” method
Adding some count to every N-gram
Interpreted as an interpolation between p̂ anduniform probability
Laplace smoothing, Lidstone’s law, Jeffreys-Perkslaw, ...
Good-Turing smoothinguses “Bins of N-gram” (number of freq. 1 N-gram, ..)only applicable when fi|j < θ.
shares several flaws also (next slide)

Hiearchical Dirichlet Language Model – p.4/15

Problem of Existent smoothing

Uniform probability to unseen words
p(well|quite) = p(epistemological|quite)?
ad hoc threshold (Good-Turing)frequency of context is ignored.
probability 0.5 = 50/100 = 2/4?
the more frequent the context is, the more stable p̂should be (requires less smoothing)
But this information is discarded in the ordinary
approach.

Hiearchical Dirichlet Language Model – p.5/15

Example of Context Frequency

200he→ 1000 times∴ p(does|he) == 0.2.
he does → 200 times
1000This estimate is very reliable.
1alice→ 5 times∴ p(wandered|alice) = = 0.2
alice wandered → 1 time
5p(does|he) = p(wandered|alice)?
The latter may have been 0.3 or 0.1⇓
Context frequency (1000 and 5) should be considered.
Hiearchical Dirichlet Language Model – p.6/15

Bayesian Hierarchical modelBigrams are governed by a probability tableqi|j = p(wi |wj ).
But we are not confident exactly what q is⇓
Consider (infinite) possible q’s, and average them.
In fact,
Introducing “probability of probability table q”
and taking expectation of the prediction from each q
What governs above “probability of q” is ahyperparameter α of the Dirichlet distribution.
Hiearchical Dirichlet Language Model – p.7/15

Result of Bayesian Hierarchical model

Resultant smoothing is a linear interpolation using
empirical probability p̂i|j and hyperparameter α
fi|j + αiE[p(wi |wj )] = i (fi|j + αi )fj
α0=· p̂i|j +· ᾱifj + α 0
fj + α 0αiwhere α0 = k αk and ᾱi =α0also depends on the frequency fj of context wj
non-uniform interpolation like back-off (αi )

(2)

(3)

ᾱi = p(wi )? (unigram) → No.
Hiearchical Dirichlet Language Model – p.8/15

Example of Bayesian model (2)We assume α(does) = 1.5, α(wandered) = 0.01, α0 = 10.
Then because fhe = 1000 and falice = 5,1000
101.5p(does|he) =· 0.2 +·= 0.1995.
1000 + 10
1000 + 10 10100.015· 0.2 +·= 0.0673.
p(wandered|alice) =5 + 10
5 + 10 10
Very intuitive and different from any conventional methods
that give equal probability 0.2 to both cases!

Hiearchical Dirichlet Language Model – p.9/15

How to derive α?
Only what remains is a hyperparameter α.
Most reasonable point estimate is the αwhich maximizes the probability of observed counts
F = {fi|j } (called “evidence” in Bayesian statistics)
p(F |α) = p(F |q)p(q|α)dq=L  1
j=10···

 1L0LΓ(α)
f0qi i|j · qiαi −1 dq1 · · · dqLi Γ(αi ) i=1i=1L Γ(α0 )
·=i Γ(αi )j=1

i Γ(fi|j + αi )Γ(fj + α0 )(4)Hiearchical Dirichlet Language Model – p.10/15

How to derive α? (2)L 
Γ(α0 )
p(F |α) =·i Γ(αi )j=1

i Γ(fi|j + αi )Γ(fj + α0 )(5)This evidence (likelihood) is convex in α, and has a
global maximum
Maximum of α can be obtained by an iterativeoptimization (MacKay 1994, Minka 2003)
77 lines of MATLAB code last week
Taking a few hours to calculate (for small data).

Hiearchical Dirichlet Language Model – p.11/15

Minka’s Exact Method
Minka (2003) “Estimating a Dirichlet distribution”
j Ψ(fi|j + αj ) − Ψ(αj )
(t+1)
(t)

.
= αi · αij Ψ(fj +k αk ) − Ψ(k αk )(6)dwhere Ψ(x) =log Γ(x)dx
For bigrams, it takes about 30 minutes on P4 2GHz
(dependent on data)
MATLAB code available on request.

Hiearchical Dirichlet Language Model – p.12/15

MacKay’s Approximation

MacKay (1994) approximates Ψ(x) by expansion:
L

L

1

fj + αfjK(α) =+logα2 j=1 α(fj + α)
j=1(7)

V (i) = number of contexts before word i
G(i), H(i) = sufficient statistics from the n-gram table
Then, (no proof is given!)αi = 2V (i)/ K(αi )−G(i)+(K(αi )−G(i))2 + 4H(i)V (i)Consistent to the exact answer (while difference ofperformance needs to be examined.)(8)

Hiearchical Dirichlet Language Model – p.13/15

Is it perfect?

Yes, almost perfect.
But, in general history h, the formula is:fhα0
E[p(wi |h)] =· p̂i|h +· ᾱifh + α 0fh + α 0(9)It uses a MLE (no smoothing) for history frequency fh !
We must estimate fh recursively also by a Bayesianmethod. (current work)
Due to the point estimate of hyperparameterand the assumption of uniform hyperprior.
Hiearchical Dirichlet Language Model – p.14/15

Gamma function
Gamma function Γ(x) is a continuous analogue ofthe factorial
Γ(x) = (x − 1)! if x is an integer ∞Γ(x) is defined by: Γ(x) =exp(−θ)θx−1 dθ.
0

Hiearchical Dirichlet Language Model – p.15/15