Dirichlet Mixtures in Text Modeling
Mikio Yamamoto and Kugatsu Sadamitsu
CS Technical report CS-TR-05-1
University of Tsukuba
May 30, 2005
Abstract
Word rates in text vary according to global factors such as genre, topic, author, andexpected readership (Church and Gale 1995). Models that summarize such global factors
in text or at the document level, are called ‘text models.’ A finite mixture of Dirichlet
distribution (Dirichlet Mixture or DM for short) was investigated as a new text model.
When parameters of a multinomial are drawn from a DM, the compound for discrete
outcomes is a finite mixture of the Dirichlet-multinomial. A Dirichlet multinomial can be
regarded as a multivariate version of the Poisson mixture, a reliable univariate model for
global factors (Church and Gale 1995). In the present paper, the DM and its compounds
are introduced, with parameter estimation methods derived from Minka’s fixed-point
methods (Minka 2003) and the EM algorithm. The method can estimate a considerable
number of parameters of a large DM, i.e., a few hundred thousand parameters. After
discussion of the relationships within the DM — probabilistic latent semantic analysis(PLSA) (Hofmann 1999), the mixture of unigrams (Nigam et al. 2000), and latent
Dirichlet allocation (LDA) (Blei et al. 2001, 2003) — the products of statistical language
modeling applications are discussed and their performance in perplexity compared. The
DM model achieves the lowest perplexity level despite its unitopic nature.

1

Introduction

Word rates in text vary according to global factors such as genre, topic, author, and expected
readership. Church and Gale (1995) examined the Brown corpus and showed that the English
word ‘said’ occurs with high frequency in the press and ﬁction, but relatively infrequently inthe hobby and learned genres. This observation is basic to their model for word rate variation.
Rosenfeld (1999) wrote that the occurrence of the word ‘winter’ in a document is proportional
to the occurrence of the word ‘summer’ in the same document. This is a basic observation for
his trigger models. Church (2001) states that a document including the word ‘Noriega’ hasa high probability for another occurrence of ‘Noriega’ in the same document, an observation1

basic to his adaptation model. In the present paper, an attempt is made to model these global
factors with a new generative text model (Dirichlet Mixture or DM for short), and to apply
it to improve conventional ngram language models that reveal only local interdependency
among words.
It is well known that global factors are important to language modeling in three language
processing research communities involved in natural language processing, speech processing,and neural networks. In the natural language processing community, Church and Gale (1995)
proposed that word rate distribution can be explained by the Poisson mixture — an inﬁnite
Poisson mixture model, in which the Poisson parameter varies over the factors of a density
function. For example, they demonstrated that an empirical word rate variation closely ﬁts a
special case of the Poisson mixture, the negative binomial where the density function assumes
a gamma distribution. However, because the Poisson mixture is univariate, it is diﬃcult tomanage word rates for every word simultaneously.
Researchers in the speech processing community have proposed and tested a great numberof multivariate models — cache models, trigger models and topic-based models — to capture
distant word dependency in the past two decades. Iyer and Ostendorf (1999) proposed an
m-component mixture of unigram models with a parameter estimation method using the EM
algorithm. Each unigram model for the mixture corresponds to a diﬀerent topic and yields
word rates for that topic. Using topic-based ﬁnite mixture models, language models can begreatly improved in perplexity, though parameter estimation for this model tends to overﬁt
training data.
Recently, ‘generative text models’ such as latent Dirichlet allocation (LDA) have attracted
people in the neural network community. Using generative text models, the probability fora ‘document’ rather than simply ‘sentences’ can be computed. Probability computation inthese models takes advantage of prior distribution of word rate variability garnered from large
document collections. Generative models are statistically well deﬁned and robust for parameter estimation and adaptation because they exploit (hierarchical) Bayesian frameworks, which
rely heavily on a prior and posterior distribution of word rates.
In this paper, a new generative text model was investigated, which uniﬁes the following
concepts developed by the three communities related to language processing:(1) summary of word rate variability as a stochastic distribution(2) ﬁnite topic mixture models of multivariate distributions(3) generative text models based on a (hierarchical) Bayesian framework
Based on (1) and (2), it was assumed that word rate variability can be modeled with a ﬁnite
mixture of Dirichlet distributions. Finite mixtures encapsulate rough topic structures, andeach Dirichlet distribution yields clear word rate variability within each topic for all words
simultaneously. From (3), a robust model is built adopting a Baysian framework, employing
a prior and a posterior distribution to estimate DM parameters and to adapt them to thecontext of thus-processed documents.
2

In Sections 2 and 3 of the paper, the DM model is described, as are parameters estimation
methods, and posterior and predictive distributions of the model. In Section 4, the relationship between DM and other text models is discussed. In Section 5, experimental resultsof applications for statistical language models are presented. The DM model achieves lower
perplexity levels than those employing the mixture of unigrams (MU) and LDA models.

2

The DM and parameter estimation

2.1

The DM and the Polya mixture

The Dirichlet distribution is deﬁned for a random vector, p = (p1 , p2 ...pV ), on a simplex of
V dimensions. Elements of a random vector on a simplex sum to 1. We interpret p as word
occurrence probabilities on V words of a vocabulary, so that the Dirichlet distribution models
word occurrence probabilities. The density function of the Dirichlet for p is:
PD (p; α) = V

Γ(α)

V


v=1 Γ(αv ) v=1

pvαv −1 ,(1)where α = (α1 , α2 , ..., αV ) is a parameter vector, αv > 0 and α = Vv=1 αv .
The Dirichlet mixture distribution (Sjölander et al. 1996) with M components is deﬁned
as the following:
PDM (p; λ, αM
1 ) =
=

M

m=1
M

m=1

λm PD (p; αm )λm VΓ(αm )V

v=1 Γ(αmv ) v=1

pvαmv −1 ,(2)where λ = (λ1 , λ2 , ..., λM ) is a weight vector for each component Dirichlet distribution and
αm = v αmv .
When the random vector p as parameters of a multinomial is drawn from the DM, thecompound distribution for discrete outcomes y = (y1 , y2 , ..., yV ) is:M
PPM (y; λ, α1 ) = PMul (y|p)PDM (p; λ, αM
1 )dp
=
=

M

m=1
M

m=1


λm

PMul (y|p)PD (p; αm )dpλm

VΓ(αm )  Γ(yv + αmv ),Γ(αm + y) v=1 Γ(αmv )3(3)

where
y=



yv .

v

Each yv means occurrence frequency of the v-th word in a document. This distribution
is called the Dirichlet-multinomial mixture or the Polya mixture distribution. The Polyamixture is used to estimate parameters for the DM, α and λ.

2.2Parameter estimation

In this subsection, methods for estimating parameters were introduced for the DM with amaximum likelihood estimator of the Polya mixture. The estimating methods are based on
Minka’s estimation methods for a Dirichlet distribution (Minka 2003) and the EM algorithm(Dempster et al. 1977).
Given the i-th datum or the i-th training document, outcomes can be determined for words
yi = (yi1 , yi2 ...yiV ). For N training documents, the log likelihood function for the training
documents D = (y1 , y2 , ..., yN ) is:L(D; λ, αM
1 ) =

N


log PPM (yi ; λ, αM
1 ).

i=1

The λ and α that maximize the above likelihood function are also DM parameters.
Assuming Z = (z1 , z2 , ..., zN ) and zi is a hidden variable that denotes a component generating the i-th document, the log likelihood for the complete data is:L(D, Z; λ, αM
1 ) =

N


log P (yi, zi ; λ, αM
1 ).

i=1

The Q-function for the EM algorithm or the conditional expectation of the above log likelihoodis:Pim log P (yi, zi = m; λ, αMQ(θ|θ̄) =
1 )
i

=

m


i

Pim log λm +

m


i

V
Γ(αm )  Γ(yiv + αmv ),Pim logΓ(αm + yi ) v=1 Γ(αmv )mwhere
Pim = P (zi = m|yi ; λ̄, ᾱM
1 )

yi =
yiv .
v

4

(4)

λ̄, ᾱM
1 are current values of parameters. The ﬁrst term of (4) can be maximized via thefollowing update formula for λ.

Pim
(5)
λm ∝
i

The second term of (4) can be maximized via the following update formula for α. Ψ(x) isthe digamma function. The update formula is derived from the Minka’s ﬁxed-point iteration(Minka 2003) and the EM algorithm (see Appendix A).
i Pim {Ψ(yik + ᾱmv ) − Ψ(ᾱmv )}αmv = ᾱmv (6)i Pim {Ψ(yi + ᾱm ) − Ψ(ᾱm )}If the leaving-one-out (LOO) likelihood is designated as the function to be maximized, afaster update formula is obtained. The following update formula is based on Minka’s iteration
for the LOO likelihood (Minka 2003) and the EM algorithm (see Appendix B):i Pim {yiv /(yiv − 1 + ᾱmv )}αmv = ᾱmv (7)i Pim {yi /(yi − 1 + ᾱm )}This LOO update function is used to estimate the DM parameters in all following experiments.

3

Inference

3.1

A posterior and predictive distribution

The DM model with parameters estimated using the above methods is regarded as a priorfor the distribution of word occurrence probabilities. In this section, a method is describedfor computing a posterior and expectations for word occurrence probability, given a word
history or a document. The following formula is a posterior distribution for word occurrence
probability given the data history y = (y1, y2 , ..., yV ), assuming a multinomial distribution for
count data y, with parameter p distributed according to a DM with parameter α as a prior:
P (p|y) = =P (y|p)P (p)P (y|p)P (p)dp
PMul (y|p)PDM (p; λ, αM
1 )M
PMul (y|p)PDM (p; λ, α1 )dp

M
=



αmv +yv −1v pv
m=1 Bm
,
M
C
m
m=1

(8)

5

whereBm = λm VΓ(αm )

,
Γ(α
)
mv
v=1
V
Γ(αmv + yv ),Cm = Bm v=1
Γ(αm + y)
V
αm =
αmv ,
v=1
V
y=
yv .
v=1

Expectation of occurrence probability of the w-th word in a vocabulary, P (w ∗|y), is:∗
P (w |y) = pw P (p|y)dp VM
αmv +yv +δ(v−w)−1dp
m=1 Bmv=1 pv=
M
m=1 CmM
V Γ{αmv +yv +δ(v−w)}
m=1 Bmv=1
Γ(αm +y+1)=M
m=1 CmM
αmw +yw
m=1 Cm αm +y
=
(9)
M
C
m
m=1
where δ(k) is Kronecker’s delta,δ(k) =

1, if k = 0,0, others .

In contrast to LDA, DM has a closed formula for computing expectation of word occurrence
probability.

3.2

Model averaging

In the experiment section (Section 5), it is demonstrated that a statistical language modelusing DM outperforms other models with a fewer components, but that performance does not
rise in proportion to the number of components. This problem reﬂects the overﬁtting natureof DM models.
Avoiding the overﬁtting problem, a simple model averaging method is adopted, which
computes a predictive distribution as a mean for each prediction of DM with a diﬀerent
number of components. It is assumed that there are N diﬀerent DM models, and that
P i(w ∗ |y), i = 1, 2...N is a predictive probability for the word w. The following averaging

6equation is referred to as method 1, in which evidence probability for a history is regarded as
credit weight for each model:
Pma1 (w ∗ |y) =i

P i (y; λ, α)P i (w ∗ |y) PMj
j PPM (y; λ, α)(10)Method 2 is a simpler method, averaging predictive probabilities with a simple arithmetic
mean:
1  i ∗
P (w |y)(11)
Pma2 (w ∗ |y) =N i

4Relationship with other topic-based models

The relationship of the DM with the other topic-based models is demonstrated using graphicalrepresentation of models. The following are evidence probabilities for data y = (y1 , y2 , ..., yV )in each topic-based model.

Mixture of unigrams: P (y) = z p(z)PMul (y|z)

LDA: P (y) = PD (θ|α) v P (wv |θ)yv dθ, where P (wv |θ) = z p(z|θ)p(wv |z)
DM: P (y) = PPM (y)Z’s of the mixture of unigram models and LDA are latent variables representing topics. θ of
LDA is weights for each unigram modeled with the Dirichlet distribution PD (θ; α). Evidence
probability for DM is the Polya distribution described in Sec. 2.1.
Figure 1 is a graphical representation of four models including a probabilistic LSA (PLSA).
Outer and inner squares represent N documents (d) and L words (w) in each document,
respectively. Circles are random variables and double circles are model parameters. Arrows
indicate conditional dependent relationships between variables.
The simplest model is MU. In this model, it is assumed that a document is generated
from just one topic — the ﬁrst chosen topic z, is used to generate all words in the document.
The PLSA model can relax this assumption. Under PLSA, it is possible that each word
in a document is generated with diﬀerent topics. In the result, a document is assumed tohave multiple topics, a realistic assumption. However, PLSA is not a well-deﬁned generativemodel for documents, because the model has no natural method to assign probability to a
new document. LDA is an extension of PLSA. Assuming Dirichlet distribution weights foreach unigram model, LDA can assign probability to new documents.
The DM is another MU extension. For DM, the assumption of MU — one topic for
one document — remains, but distribution of unigram probability is directly modeled by
the Dirichlet distribution. Other models, including PLSA and LDA, can reveal multitopic
structure, but each topic model is quite simple — a unigram model. Though DM assumes
a unitopic structure for each document, its topic models are richer than those of its strong
rivals.
7

Figure 1: Graphical model expressions of generative text models

5

Experiments

The performance of the DM was compared with those of the LDA and the MU in test-set
perplexities using adaptive ngram language models.
Training in all three models relied on the same training data and were evaluated with thesame test data. The training data was a set of 98,211 Japanese newspaper articles from theyear 1999. The test data was a set of 495 randomly selected articles of more than 40 words,
from the year 1998. The vocabulary comprised the 20,000 most frequent words in the training
data, and had a cover rate of 97.1%.
The variational EM method was used to estimate the LDA parameter (Blei et al. 2003),
but α in the Dirichlet parameter for LDA was updated with Minka’s ﬁxed-point iteration
method (Minka 2003), instead of the Newton-Raphson method. For the DM, the estimation
method (1) based on an LOO likelihood was used. Training for both models used the same
stopping criteria — the change of closed perplexity for the training data before and after one
global loop of iteration is less than 0.1%. Models were constructed with both LDA and DM
having 1, 2, 5, 10, 20, 50, 100, 200, and 500 components.
Figure 2 presents the perplexity of each model for its diﬀerent number of components.
Each perplexity is computed as an inverse of probability per word, a geometrical mean of adocument probability, that is, an evidence probability for data. For the DM, the probabilityof the Polya mixture for a document is the document probability. The DM consistently
outperforms both other models. However, DM performance is best at 20 components, as
it saturates with somewhat fewer components. DM is a generalized version of MU and thesaturation suggests that DM suﬀers the MU overﬁtting problem.
Figure 3 presents the perplexity of the adaptive language models for diﬀerent numbers ofcomponents. Adaptive language models predict the probability of the next word by using ahistory, such as a conventional ngram language model. They employ a longer history, suchas an entire previously processed section, rather than just the two words preceding the target
8Figure 2: Comparison of test-set perplexity by document probability
word. In this experiment, the models were adapted to a section of a document from the ﬁrst
to the current word, and then probabilities were computed for the next 20 words. Every 20
words, this operation was repeated. Figure 3 also shows that DM outperforms better thanLDA.
For the next experiment, a trigram language model was developed, dynamically adapted
to longer histories for topic-based models. A unigram rescaling method was used for theadaptation (Gildea and Hofmann 1999). Figure 4 shows the perplexity of combined adaptive
language models. Like the above experiments, the performance of a unigram-rescaling trigram
model with DM is better than that with LDA.
Table 1 shows the best perplexities for each model. The values in parentheses are perplexity reduction rates from baseline models.
LDA is a multitopic text model, which reveals a mixture of topics in a document, while
DM is a unitopic text model, which assumes one topic per document. Generally speaking,there are few documents with just one topic. This raises the question as to why DM is better
than LDA in perplexity for those experiments. While there is no clear answer, it is possiblethat the training and test materials for those experiments were based on newspaper articles,
and thus somewhat focused on a single topic. DM may capture the detailed distributionof word probabilities on topics using multiple Dirichlets, whereas LDA simply captures the
distribution indirectly as a topic proportion or weight for a mixture using a single Dirichlet.
The same experiments need to be conducted with web data, which contains more complex
topical structures.

6

Conclusions

Finite mixture of Dirichlet distributions was investigated as a new text model. Parameter
estimation methods were introduced, based on Minka’s ﬁxed-point methods (Minka 2003)
9

Figure 3: Comparison of test-set perplexity by history adaptation probability(unigram)

Figure 4: Comparison of test-set perplexity by history adaptation probability(trigram)and the EM algorithm using the mixture of the Dirichlet-multinomial distribution. Experimental results for applications of statistical language models were demonstrated and theirperformance compared for perplexity. The DM model achieved the lowest perplexity level
despite its unitopic nature.

References[1] D.M. Blei, A.Y. Ng, and M.I. Jordan. 2001. “Latent Dirichlet Allocation,” Neural Information Processing Systems, vol.14.
[2] D.M. Blei, A.Y. Ng, and M.I. Jordan. 2003. “Latent Dirichlet Allocation,” Journal of
Machine Learning Research, Vol.3, pages 993-1022.
10

Table 1: Minimum perplexity of each aspect model
history
adaptation(unigram)
DM
453.06(32.0%)
DM ave.2 425.97(36.1%)
LDA
467.61(29.9%)
Mixture of –Unigrams

history
adaptation(trigram)
60.74(19.6%)
57.97 (23.2%)
67.13 (11.1%)–

document
probability
434.73474.82520.95[3] Kenneth W. Church and William A. Gale. 1995. Poisson mixtures. Natural Language
Engineering, Vol.1, No.1, pages 163–190.
[4] Kenneth W. Church. 2001. Empirical estimates of adaptation: The chance of two Noriegas is closer to p/2 than p2 . In Proc. of Coling 2000, pages 180–186.
[5] A. P. Dempster, N. M. Laird and D. B. Rubin. 1977. Maximum likelihood from incomplete
data via the EM algorithm. J. of Royal Statistical Society, Series B, Vol.39, pages 1–38.
[6] T. Hofmann. 1999. “Probabilistic latent semantic indexing,” Proc. of the 22nd Annual ACM Conference on Research and Development in Information Retrieval, pp.50-57,
Berkeley, California.
[7] K. Sjölander, K. Karplus, M. Brown, R. Hunghey, A. Krogh, I.S. Mian, and D. Haussler.
1996. “Dirichlet mixtures:a method for improved detection of weak but signiﬁcant protein
sequence homology,” Computer Applications in the Biosciences, vol.12, no.4, pp.327–345.
[8] D. Gildea, and T. Hofmann. 1999. “Topic-based language models using em,” Proc.
of the 6th European Conference on Speech Communication and Technology (EUROSPEECH’99).
[9] R.M. Iyer, and M. Ostendorf. 1999. “Modeling long distance dependence in language:topic mixtures versus dynamic cache models,” IEEE TRANSACTIONS ON
SPEECH AND AUDIO PROCESSING, vol.7, no.1, pp.30–39.
[10] S.T. K. Nigam, A. McCallum, and T. Mitchell. 2000. “Text classiﬁcation from labeled
and unlabeled documents using EM,” Machine Learning, vol.39, no.2/3, pp.103–134.
[11] T.
Minka.
2003.
“Estimatinga
http://www.stat.cmu.edu/ minka/papers/dirichlet/

Dirichlet

distribution,”[12] Ronald Rosenfeld. 1996. A maximum entropy approach to adaptive statistical language
modeling. Computer Speech and Language, Vol.10, No.3, pages 187–228.
11

Derivation of the update formula of α for the MLE

AMinka’s ﬁxed-point iteration method (Minka 1999) and the EM algorithm were used. The
following equations (Minka 2003) were used to get the lower bound of the second term of theequation (4):Γ(ᾱm ) exp (ᾱm − αm )bim
Γ(αm )≥,
Γ(αm + yi )Γ(ᾱm + yi )andΓ(ᾱmv + yiv )aimv≥ cimv ᾱmv
Γ(ᾱmv )
where
yi =



yiv ,

v

αm =

(if yiv ≥ 1),


αmv ,

v

and
ᾱm =



ᾱmv .

v

The lower bound is:VΓ(ᾱm )  Γ(yiv + ᾱmv )Pim logΓ(ᾱm + yi) v=1 Γ(ᾱmv )
m
i



Γ(ᾱm ) exp (ᾱm − αm )bim
aimv+≥
Pim loglog cimv αmv≡ Q (α),
Γ(y
+
ᾱ
)
i
m
m
v
i

where

aimv = Ψ(ᾱmv + yiv ) − Ψ(ᾱmv ) ᾱmv ,bim = Ψ(ᾱm + yi) − Ψ(ᾱm ),Γ(ᾱmv + yiv ) −aimvᾱmv .
cimv =
Γ(ᾱmv )This lower bound can be maximized with the following update formula for αmv .
1 ∂Q (α)=−Pim bi +Pim aimv = 0∂αmv
ᾱmv iii Pim {Ψ(yik + ᾱmv )−Ψ(ᾱmv )}αmv = ᾱmv i Pim {Ψ(yi + ᾱm )−Ψ(ᾱm )}12

Derivation for the update formula of α for the maximum LOO likelihood

B

Given datum yi−v in which one word v is left out of a document, the predictive probability
P (v ∗|yi−v ) for the word v is the following from the equation (9):p(v ∗ |yi−v ) 



Pim

m

αmv + yiv − 1,
αm + yi − 1

where
−v
Pim
 Pim .

The LOO log-likelihood, Lloo , is
Lloo (y|α) iyiv log



v

m

Pim

αmv + yiv − 1.
αm + yi − 1

Since Pim is very nearly to 1 or 0 for almost all cases, the preceding equation can be transformed:

αmv + yiv − 1
Lloo (y|α) 
yiv Pim log
αm + yi − 1ivmUsing the preceding equation, likelihood can be maximized independently for αmv of the m-th
Dirichlet component. The lower bound of the LOO log-likelihood Lm
loo for the m-th component
is:


Lm
yiv Pim qimv log αmv − yi Pim aim αm + (const.),
loo ≥
i

v

where
ᾱmv
,
ᾱmv + yiv − 1
1
.
aim =
ᾱm + yi − 1

qimv =

The following inequalities (Minka 2003) were used to get the above bound:log(n + x) ≥ q log x + (1 − q) log n − q log q − (1 − q) log(1 − q)x̂where q = n+x̂,

log(x) ≤ ax − 1 + log x̂
13where a = 1/x̂.

An update formula for ﬁxed-point iteration is:i Pim {yiv /(yiv − 1 + ᾱmv )}.
αmv = ᾱmv i Pim {yi /(yi − 1 + ᾱm )}14