Explanation of dirichlet-topic.pl
Graham NeubigAugust 3, 2010

1

Introduction

This is a description of the math behind the script dirichlet-topic.pl.

2

Problem Definition

Let’s say we have a collection of topics T = t1 , . . . , tI , each described by its word counts Wi =wi1 , . . . , wiJ , where wij = k indicates that word j appears in topic i k times. We will call the collectionof all topic counts (the corpus) W.
Our goal is to estimate reasonable posterior probabilities of topics given each word P (ti |wj ). The
most obvious way to do so is maximum likelihood estimation
PM L (ti |wj ) =where w·j indicates the sum
w·j =∑wij,w·jwĩj .

ĩHowever, in most cases, there will be many low-frequency words where wij = 0, which will unreasonably cause P (ti |wj ) to be equal to zero. In order to ﬁx this problem, we can use smoothing. Herewe will use additive smoothing:wij + αP (ti )PS (ti |wj ) =.
(1)
w·j + αIt can be shown that additive smoothing is equivalent to using a Dirichlet distribution as a priorprobability for the multinomial distribution of P (ti |wj ) [1].
The α we have introduced here is essentially a way to control the strength of the prior. If α
is very large, the prior will be very strong, and it will take many observations to shift the topic
distribution. If α is very small, the equation will act similarly to maximum likelihood estimation, andmay cause over-ﬁtting in the topic distribution of infrequent words. The next section describes how
dirichlet-topic.pl automatically determines this α using Dirichlet processes.

3Dirichlet Processes

A Dirichlet process is a method in non-parametric Bayesian statistics that allows for reasonable estimation of probabilities for relatively complicated distributions using only a single hyperparameter α.
A good summary of Dirichlet processes can be found in Teh [2], but we will cover only the relevant
details here (very informally).
1

A Dirichlet process is a type of generative distribution for discrete spaces. The most interesting characteristic of “processes” compared to other generative distributions is that that distributionchanges every time it generates a new element. Let’s say we have a Dirichlet process for w1 thatgenerates the following topic sequence t1 t1 t2 t1 .
First, before generating any elements, the distribution is equal to Equation (1) where wi j = 0 for
all wj :0 + αP (t1 )P0 (t1 |wj ) == P (t1 ).
0+α
In other words, before generating any elements, the distribution is equal to the prior topic distribution,
as should be expected.
The ﬁrst topic t1 is generated based on this prior, and we set w1j = 1. We generate the second
topic, also t1 , according to the new distribution with w1j = 1:
P1 (t1 |wj ) =1 + αP (t1 ).
1+αWe continue to generate the last two topics,
0 + αP (t2 ),2+α
2 + αP (t1 )P3 (t1 |wj ) =.
3+α
P2 (t2 |wj ) =If we put these together we get
P (t1 t1 t2 t1 |wj ) =0 + αP (t1 ) 1 + αP (t1 ) 0 + αP (t2 ) 2 + αP (t1 ),0+α
1+α2+α3+αwhich can be further simpliﬁed into∏0
k=0 (k + αP (t2 ))k=0 (k + αP (t1 )).
∏3
k=0 (k + α)∏2
P (t1 t1 t2 t1 |wj ) =It should be noted that this is probability is exchangable, that is the probability will be the same
regardless of the order of the sequence, as long as the topic counts are equal (it doesn’t matter whether
the sequence is t1 t1 t2 t1 or t1 t1 t1 t2 ). We can generalize this distribution using topic counts wij asfollows:∏I ∏ni −1(k + αP (ti ))P (w1j = n1 , . . . , wIj = nI ) = i=1 ∏k=0,n·k=0 (k + α)
wheren· =I∑

ni .

i=1

Using this probability for a single word’s topic counts, we can ﬁnd the likelihood for the full corpus:
P (W) =J ∏I
∏

i=1

j=1

∏wij −1(k + αP (ti ))
∏k=0.
w·j
k=0 (k + α)

In the next section, we will ﬁnd the α that maximizes this likelihood.

2

4

Parameter Estimation

We can estimate the parameters using Newton’s method if we can calculate the derivative and second
derivative of the likelihood for the entire corpus. In order to do this, we ﬁrst take the log likelihood:
LL(W) = logP (W) =w·jij −1I w∑
J ∑∑∑log(k + αP (ti )) −log(k + α)].
[ (j=1 i=1k=0

k=0

As this is a single large sum, all we need to do is take the derivative of each component:
LL0 (W) =ij −1
J ∑I w∑∑[

j=1 i=1 k=0

LL00 (W) =j=1 i=1 k=0w·j

k=0ij −1J ∑I w∑∑[∑ 1P (ti )−],
k + αP (ti )k+α∑−P (ti )2
1+]
2(k + αP (ti ))(k + α)2w·j

k=0

Updating α can be performed by calculating these ﬁrst and second order derivatives and plugging in
the values to Newton’s method.
However, this equation requires a signiﬁcant amount of repetitive calculation. Looking at theequation for the ﬁrst order derivative, we can see that for every element wij ≥ k − 1, this equation
calculates and adds P (ti )/(k + αP (ti )) once, and for every element w·j ≥ k − 1, the equation calculates
and subtracts 1/(k + α) once. We can reduce this computation by ﬁrst calculating a variable mi k thatcounts the number of elements of wij greater than or equal to k:
mik =

J∑

I(wij ≥ k).

j=1

Using this variable, we can calculate the derivatives in a much more eﬃcient fashion:
LL0 (W) =KiI ∑∑i=1 k=1

LL00 (W) =KiI ∑∑i=1 k=1·∑P (ti )1−m·k,
k + αP (ti )
k+αK

mik

k=1−mik·∑
1P (ti )+m·k,
2(k + αP (ti ))(k + α)22K

k=1

where Ki is the largest value for which mik > 0. This is the method that is being used in dirichlet-topic.pl.

References[1] David J. C. MacKay and Linda C. Peto. A hierarchical Dirichlet language model. Natural language
engineering, 1(03):289–308, 1994.
[2] Y.W. Teh, M.I. Jordan, M.J. Beal, and D.M. Blei. Hierarchical dirichlet processes. Journal of theAmerican Statistical Association, 101(476):1566–1581, 2006.

3