Online Multiscale Dynamic Topic Models
Tomoharu Iwata

Takeshi Yamada

Yasushi Sakurai

Naonori Ueda

NTT Communication Science Laboratories
2-4 Hikaridai, Seika-cho, Soraku-gun, Kyoto, Japan{iwata,yamada,yasushi,ueda}@cslab.kecl.ntt.co.jp

ABSTRACT
We propose an online topic model for sequentially analyzing
the time evolution of topics in document collections. Topics naturally evolve with multiple timescales. For example, some words may be used consistently over one hundredyears, while other words emerge and disappear over periodsof a few days. Thus, in the proposed model, current topicspeciﬁc distributions over words are assumed to be generated
based on the multiscale word distributions of the previous
epoch. Considering both the long-timescale dependency aswell as the short-timescale dependency yields a more robustmodel. We derive eﬃcient online inference procedures basedon a stochastic EM algorithm, in which the model is sequentially updated using newly obtained data; this means thatpast data are not required to make the inference. We demonstrate the eﬀectiveness of the proposed method in terms ofpredictive performance and computational eﬃciency by examining collections of real documents with timestamps.

Categories and Subject Descriptors
H.2.8 [Database Management]: Database Applications—
Data Mining; I.2.6 [Artiﬁcial Intelligence]: Learning; I.5.1[Pattern Recognition]: Model—Statistical

General Terms
Algorithms

Keywords
Topic model, Time-series analysis, Online learning

1. INTRODUCTION
Great interest is being shown in developing topic models that can analyze and summarize the dynamics of document collections, such as scientiﬁc papers, news articles, andblogs [1, 5, 7, 11, 14, 20, 21, 22]. A topic model is a hierarchical probabilistic model, in which a document is modeled as

Permission to make digital or hard copies of all or part of this work forpersonal or classroom use is granted without fee provided that copies are
not made or distributed for profit or commercial advantage and that copies
bear this notice and the full citation on the first page. To copy otherwise, torepublish, to post on servers or to redistribute to lists, requires prior specificpermission and/or a fee.
KDD’10, July 25–28, 2010, Washington, DC, USA.
Copyright 2010 ACM 978-1-4503-0055-1/10/07 ...$10.00.

a mixture of topics, and a topic is modeled as a probability
distribution over words. Topic models are successfully used
in a wide variety of applications including information retrieval [6], collaborative ﬁltering [10], and visualization [12]as well as the analysis of dynamics.
In this paper, we propose a topic model that permits thesequential analysis of the dynamics of topics with multiple
timescales, we call it the Multiscale Dynamic Topic Model(MDTM), and its eﬃcient online inference procedures. Topics naturally evolve with multiple timescales. Let us consider
the topic ‘politics’ in a news article collection as an example. There are some words that appear frequently over many
years, such as ‘constitution’, ‘congress’, and ‘president’. On
the other hand, some words, such as the names of membersin Congress, may appear frequently over periods of tens ofyears, and other words, such as the names of bills under discussion, may appear for only a few days. Thus, in MDTM,
current topic-speciﬁc distributions over words are assumed
to be generated based on the estimates of multiple timescale
word distributions at the previous epoch. Using these multiscale priors improves the predictive performance of themodel because the information loss is reduced by considering the long-timescale dependency as well as short-timescaledependency.
The online inference and parameter estimation processes
can be achieved eﬃciently based on a stochastic EM algorithm, in which the model is sequentially updated using
newly obtained data; past data does not need to be stored
and processed to make new inferences. Some topics may exhibit strong long-timescale dependence, and others may exhibit strong short-timescale dependence. Furthermore, thedependence may diﬀer over time. Therefore, we infer thesedependencies for each timescale, for each topic, and for eachepoch. By inferring the dependencies from the observed
data, MDTM can ﬂexibly adapt to topic dynamics. A disadvantage of online inference is that it can be more unstable
than batch inference. With MDTM, the stability can be improved by smoothing using multiple estimates with diﬀerent
timescales.
The remainder of this paper is organized as follows. In
Section 2, we formulate a topic model for multiscale dynamics, and describe its online inference procedures. In Section 3, we brieﬂy review related work. In Section 4, we
demonstrate the eﬀectiveness of the proposed method by analyzing the dynamics of real document collections. Finally,
we present concluding remarks and a discussion of future
work in Section 5.

Symbol
Dt
Nt,dW
wt,d,nZzt,d,n
S
θt,d

φt,z

(s)
ξt,z

Table 1: Notation
Description
number of documents at epoch t
number of words in the dth document
at epoch t
number of unique words
nth word in the dth document at epoch t,
wt,d,n ∈ {1, · · · , W }number of topics
topic of the nth word in the dth document
at epoch t, zt,d,n ∈ {1, · · · , Z}
number of scales
multinomial distribution over topics
for the dth document at epochPt,θt,d = {θt,d,z }Z
z=1 , θt,d,z ≥ 0,z θt,d,z = 1
multinomial distribution over words
for the zth topic at epoch t, P
φt,z = {φt,z,w }W
w=1 , φt,z,w ≥ 0,w φt,z,w = 1
multinomial distribution over words
for the zth topic with scale s at epoch t,
P (s)
(s)
(s)
(s)
ξt,z = {ξt,z,w }W
w=1 , ξt,z,w ≥ 0,w ξt,z,w = 1

2. PROPOSED METHOD
2.1 Preliminaries
In the proposed model, documents are assumed to be generated sequentially at each epoch. Suppose we have a set of
Dt documents at the current epoch, t, and each document
Nt,dis represented by wt,d = {wt,d,n }n=1
, i.e. the set of words
in the document. Our notation is summarized in Table 1.
We assume that epoch t is a discrete variable, and we canset the time period for an epoch arbitrarily at, for example,
one day or one year.
Before introducing the proposed model, we review latent
Dirichlet allocation (LDA) [6, 8], which forms the basis of
the proposed model. In LDA, each document has topic proportions θt,d . For each of the Nt,d words in the document,
topic zt,d,n is chosen from the topic proportions, and thenword wt,d,n is generated from a topic-speciﬁc multinomial
distribution over words φzt,d,n . Topic proportions θt,d andword distributions φz are assumed to be generated according to symmetric Dirichlet distributions. Figure 1 (a) showsa graphical model representation of LDA, where shaded andunshaded nodes indicate observed and latent variables, respectively.

2.2 Model
We consider a set of multiple timescale distributions overwords for each topic to incorporate multiple timescale properties. In order to account for the inﬂuence of the past at
diﬀerent timescales to the current epoch, we assume thatcurrent topic-speciﬁc word distributions φt,z are generated
according to the multiscale word distributions at the previ(s)
(s)
(s)
W
ous epoch {ξt−1,z }S
s=1 . Here, ξt−1,z = {ξt−1,z,w }w=1 represents a distribution over words of topic z with scale s at
epoch t − 1. In particular, we use the following asymmetric
Dirichlet distribution for the prior of current word distribution φt,z , in which the Dirichlet parameter is deﬁned sothat its mean becomes proportional to the weighted sum of

ξ (4)
t-1,z

w

ξ (3)
t-1,z

w

w

ξ (2)
t-1,z
w

t-8

t-4

ξ (1)
t-1,z

t-2

λt , z ,4λt , z ,3λt , z ,2φ t,zλt , z ,1

λt , z ,0

ξ (0)
t-1,z

t-1

w

Figure 2: Illustration of multiscale word distributions at epoch t with S = 4. Each histogram shows(s)ξt−1,z , which is a multinomial distribution over words
with timescale s.
multiscale word distributions at the previous epoch,
φt,z ∼ Dirichlet(

S
X

(s)

λt,z,s ξt−1,z ),

(1)

s=0

where λt,z,s is a weight for scale s in topic z at epoch t,and λt,z,s > 0. By estimating weights {λt,z,s }S
s=0 for eachepoch, for each topic, and for each timescale using the current data as described in Section 2.3, MDTM can ﬂexibly
respond to the inﬂuence on the current distribution of theprevious short- and long-timescale distributions. The esti(s)mated multiscale word distributions {ξt−1,z }S
s=1 at the previous epoch are considered as hyperparameters in the current epoch. Their estimation will be explained in Section 2.4.
There are many diﬀerent ways of setting the scales, but(s)for the simple explanation, we set them so that ξt,z indis−1
cates the word distribution from t − 2+ 1 to t, where(s=1)
larger s represents longer timescale, and ξt,z is equivalent
to the estimate of unit time word distribution φt,z . We use(s=0)
uniform word distribution ξt,z,w = W −1 for scale s = 0.
This uniform distribution is used to avoid the zero probability problem. Figure 2 illustrates multiscale word distributions with this setting. Word distributions are likely to besmoothed as the timescale becomes long, and be peaked as
the timescale becomes short. By using the information presented in these various timescales as the prior for the current
distribution with weights, we can infer the current distribution more robustly. In stead of using 2s−1 epochs for scale s,
we can use any number of epochs. For example, if we knowthat the given data exhibit periodicity e.g. of one week andone month, we can use the scale of one week for s = 1 andone month for s = 2. In such case, we can still estimateparameters in the similar way with the algorithm describedin Section 2.4. Typically, we do not know the periodicity of
the given data in advance, we therefore consider the simple
scale setting in the paper.
In LDA, topic proportions θt,d are sampled from a Dirichlet distribution. In order to capture the dynamics of topic
proportions with MDTM, we assume that the Dirichlet parameters αt = {αt,z }Z
z=1 depend on the previous parameters. In particular, we use the following Gamma prior for a
Dirichlet parameter of topic z at epoch t,
αt,z ∼ Gamma(γαt−1,z , γ),(2)where the mean is αt−1,z , and the variance is αt−1,z /γ. By
using this prior, the mean is the same as that at the previous
epoch unless otherwise indicated by the new data. Parame-

t

t-1

t

α

α

α

α

θ

θ

θ

θ

z

z

z

z

w

w

w
N

N

D

D

Z
ξ

β

(a) LDA

N

D

φ

φ

φ

w
N

λ

^

φ

^

λ

N

N

S+1 Z

S+1 Z

(b) MDTM

D

λ
S+1 Z

(c) online MDTM

Figure 1: Graphical models of (a) latent Dirichlet allocation, (b) the multiscale dynamic topic model, and(c) its online inference version.
ter γ controls temporal consistency of the topic proportion
prior.
Assuming that we have already calculated the multiscale(s)Zparameters at epoch t − 1, Ξt−1 = {{ξt−1,z }S
s=0 }z=1 andZ
αt−1 = {αt−1,z }z=1 , MDTM is characterized by the following generative process for the set of documents W t =t{wt,d }D
d=1 at epoch t,
1. For each topic z = 1, · · · , Z:(a) Draw topic proportion prior
αt,z ∼ Gamma(γαt−1,z , γ),(b) Draw word distributionP(s)φt,z ∼ Dirichlet( s λt,z,s ξt−1,z ),2. For each document d = 1, · · · , Dt :(a) Draw topic proportions
θt,d ∼ Dirichlet(αt ),(b) For each word n = 1, · · · , Nt,d :i. Draw topic
zt,d,n ∼ Multinomial(θt,d ),ii. Draw word
wt,d,n ∼ Multinomial(φt,zt,d,n ).
Figure 1 (b) shows a graphical model representation of MDTM.

2.3 Online inference
We present an online inference algorithm for MDTM, thatsequentially updates the model at each epoch using the newly
obtained document set and the multiscale model of the previous epoch. The information in the data up to and including the previous epoch is aggregated into the previous multiscale model. The online inference and parameter estimation
can be eﬃciently achieved by a stochastic EM algorithm [2,3], in which the collapsed Gibbs sampling of latent topics [8]and the maximum likelihood estimation of hyperparameters
are alternately performed [19].
We assume the set of documents W t at current epoch t,
and estimates of parameters from the previous epoch αt−1

and Ξt−1 are given. The joint distribution on the set of
documents, the set of topics, and the topic proportion priors
given the parameters are deﬁned as follows,
P (W t , Zt , αt |αt−1 , γ, Ξt−1 , Λt )=P (αt |αt−1 , γ)P (Zt |αt )P (Wt |Zt , Ξt−1 , Λt ),(3)

Nt,d Dt
where Zt = {{zt,d,n }n=1}d=1 represents a set of topics, andSZΛt = {{λt,z,s }s=0 }z=1 represents a set of weights. The ﬁrst

term on the right hand side of (3) is as follows using (2),P (αt |αt−1 , γ) =γαt−1,z −1
Y γ γαt−1,z αt,zexp(−γαt,z )zΓ(γαt−1,z ), (4)where Γ(·) is the gamma function. We can integrate out thetmultinomial distribution parameters in MDTM, {θt,d }Dd=1
Z
and {φt,z }z=1 , by taking advantage of Dirichlet-multinomial
conjugacy.
The second term is calculated by P (Zt |αt ) =QDt RP (zt,d |θt,d )P (θt,d |αt )dθt,d , and we have the followd=1t
ing equation by integrating out {θt,d }D
d=1 ,
„ P
«D Y Q
αt,z )+ αt,z )Γ(z Γ(Nt,d,zP, (5)P (Zt |αt ) = Q z
Γ(α
)
Γ(N
+
t,z
t,d
z
z αt,z )dwhere Nt,d,z is the number of words in thePdth document
assigned to topic z at epoch t, and Nt,d = z Nt,d,z . Similarly, by integrating out {φt,z }Z
z=1 , the third term is given
as follows,PYΓ( s λt,z,s )P (W t |Zt , Ξt−1 , Λt ) =
Q
P
(s)
z
w Γ(
s λt,z,s ξt−1,z,w )QP(s)Γ(Nt,z,w + s λt,z,s ξt−1,z,w )
P
,
(6)
× w
Γ(Nt,z + s λt,z,s )where Nt,z,w is the number of times
P word w was assigned to
topic z at epoch t, and Nt,z = w Nt,z,w .
The inference of the latent topics Zt can be eﬃciently
computed by using collapsed Gibbs sampling [8]. Let j =(t, d, n) for notational convenience, and zj be the assignment of a latent topic to the nth word in the dth document

at epoch t. Then, given the current state of all but one
variable zj , a new value for zj is sampled from the following
probability,
P (zj = k|W t , Zt\j , αt , Ξt−1 , Λt )∝P
(s)
Nt,d,k\j + αt,k Nt,k,wj \j + s λt,s,k ξt−1,k,wj
PP,(7)
Nt,d\j + z αt,zNt,k\j + s λt,s,k

where \j represents the count yielded by excluding the nthword in the dth document.
The parameters αt and Λt are estimated by maximizing
the joint distribution (3). The ﬁxed-point iteration method
described in [13] can be used for maximizing the joint distribution as follows,P
γαt−1,z − 1 + αt,z d (Ψ(Nt,d,z + αt,z ) − Ψ(αt,z ))PPP,
αt,z ←
γ + d (Ψ(Nt,d + z0 αt,z0 ) − Ψ( z0 αt,z0 ))(8)where Ψ(·) is a digamma function deﬁned by Ψ(x) = ∂ log∂xΓ(x) ,
and,
P (s)
ξt−1,z,w At,z,w
λt,z,s ← λt,z,s w
,
(9)
Bt,z

(1)

1: N̂t,z,w ← N̂t,z,w
2: for s = 2, · · · , S do
3:
if t mod 2s−1 = 0 then
(s)
(s−1)
(s−1)
4:
N̂t,z,w ← N̂t,z,w + N̂t−1,z,w
5:
else
(s)
(s)
6:
N̂t,z,w ← N̂t−1,z,w
7:
end if
8: end for
Figure 3: Algorithm for the approximate update of(s)N̂t,z,w .

While it is simpler to use the actual number of times, Nt,z,w ,instead of the expected number of times, N̂t,z,w , in (12), we(s=1)
use the latter in order to constrain the estimate of ξt,z,w tobe the estimate of φt,z,w as follows,N̂t,z,w(s=1)
ξt,z,w = P= φ̂t,z,w .
w N̂t,z,w

(14)

(s)

where
At,z,w = Ψ(Nt,z,w +

X

(s0 )

λt,z,s0 ξt−1,z,w )−Ψ(

X

(s0 )

λt,z,s0 ξt−1,z,w ),

s0

s0

(10)
Bt,z = Ψ(Nt,z +X
s0X
λt,z,s0 ).
λt,z,s0 ) − Ψ(

(s)

(s)

N̂t,z,w ← N̂t−1,z,w + N̂t,z,w − N̂t−2s−1 ,z,w .

(15)

(11)

s0

By iterating Gibbs sampling with (7) and maximum likelihood estimation with (8) and (9), we can infer latent topics
while optimizing the parameters. Since MDTM uses the past
distributions as the current prior, the label switching problem [17] is not likely to occur when estimated λt,z,s is high,which implies current topics strongly depend on the previous distributions. Label switching can occur when estimated
λt,z,s is low. By allowing low λt,z,s , which is estimated fromthe given data at each epoch and each topic, MDTM canadapt ﬂexibly to changes even if existing topics disappear
and new topics appear in midstream.

2.4 Efficient estimation of multiscale word distributions
By using the topic assignments obtained after iterating thestochastic EM algorithm, we can estimate multiscale word(s)
distributions. Since ξt,z,w represents the probability of word
w in topic z from t − 2s−1 + 1 to t, the estimation is asfollows,Pt(s)0N̂t,z,w(s)
t0 =t−2s−1 +1 N̂t ,z,w
ξt,z,w = P, (12)
=
P Pt
(s)
N̂
t0 ,z,ww
t0 =t−2s−1 +1
w N̂t,z,w(s)

Note that the value N̂t,z,w can be updated sequentially(s)from the previous value N̂t−1,z,w as follows,

where N̂t,z,w is the expected number of times word w was
assigned to topic z from t − 2s + 1 to t, and N̂t,z,w is the
expected number of times at t. The expected number iscalculated by N̂t,z,w = Nt,z φ̂t,z,w , where φ̂t,z,w is a point
estimate of the probability of word w in topic z at epoch t.
Although we integrate out φt,z,w , we can recover its point
estimate as follows,P(s)Nt,z,w + s λt,z,s ξt−1,z,wP
φ̂t,z,w =.
(13)Nt,z + s λt,z,s(s)Therefore, N̂t,z,w can be updated through just two additions
instead of 2s−1 additions.
(s)However, to update N̂t,z,w , we still need to store values
S−1N̂t,z,w from t − 2
to t − 1, which means that O(2S−1 ZW )memory is required in total for updating multiscale word
distributions. Since the memory requirement increases exponentially with the number of scales, this requirement prevents us from modeling long-timescale dynamics. Thus, weconsider approximating the update by decreasing the update frequency for long-timescale distributions as in Algorithm 3; this reduces the memory requirement to O(SZW ),which is linear against the number of scales. Figure 4 illus(s)trates approximate updating N̂t,z,w with S = 3 from t = 4
to t = 8. Each rectangle represents N̂t0 ,z,w , where the num(s)ber represents t0 . Each row at each epoch represents N̂t,z,w ,and shaded rectangles represent that the values that dif(s)fer from the previous values. N̂t,z,w is updated at everys−1
2 nd epoch. Since the dynamics of a word distribution
for a long-timescale is considered to be slower than that fora short-timescale, this approximation, decreasing the update frequency for long-timescale distributions, is reason(s)able. Updating N̂t,z,w with this approximation requires us(s−1)
to store only the previous N̂t,z,w values, and so the memory requirement is O(SZW ). Figure 1 (c) shows a graphicalmodel representation of online inference in MDTM.
For the Dirichlet prior parameter of the word distribution,
we use the weighted sum of the multiscale word distributions
as in (1). The parameter can be rewritten as the weighted
sum of the word distributions for each epoch as follows,
S
X
s=1

(s)

λt,z,s ξt−1,z,w =t−1
Xt0 =t−2S−1

λ0t,z,t0 φ̂t0 ,z,w ,

(16)

s=3

t=4
1 2 3 4t=5
1 2 3 4t=6
1 2 3 4t=7
1 2 3 4t=8
5 6 7 8

s=2

3 4

3 4

5 6

5 6

7 8

s=1

4

5

6

7

8

5

6

7

8

is inappropriate for discrete data such as document collections [9].

4.

EXPERIMENTS

4.1

Setting

We evaluated the multiscale dynamic topic model with on(s)line inference (MDTM) using four real document collections
Figure 4: Illustration of approximate updating N̂t,z,w
with timestamps: NIPS, PNAS, Digg, and Addresses.
from t = 4 to t = 8 with S = 3.
The NIPS data consists of papers from the NIPS (Neural Information Processing Systems) conference from 1987
to 1999. There were 1,740 documents, and the vocabulary
where
size was 14,036. The unit epoch was set to one year, soPthere were 13 epochs. The PNAS data consists of the titles
SX
λt,z,s w N̂t0 ,z,w
0
of papers that appeared in the Proceedings of the National
λt,z,t0 =, (17)
P Pt−1
N̂t00 ,z,w
Academy of Sciences from 1915 to 2005. There were 79,477
w
t00 =t−2s−1
s=dlog2 (t−t0 +1)+1e
documents, and the vocabulary size was 20,534. The unit
is its weight. See Appendix for the derivation. Therefore,
epoch was set at one year, so there were 91 epochs. The Digg
the multiscale dynamic topic model can be seen as an apdata consists of blog posts that appeared in the social news
proximation of a model that depends on the word distriwebsite Digg (http://digg.com) from January 29th to Februbutions for each of the previous epochs. By consideringary 20th in 2009. There were 108,356 documents, and themultiscale word distributions, the number of weight paramvocabulary size was 23,494. The unit epoch was set at one
eters Λt can be decreased from O(2S−1 Z) to O(SZ), andday, so there were 23 epochs. The Addresses data consists
this leads to more robust inference. Furthermore, the useof the State of the Union addresses from 1790 to 2002. Weof multiscaling also decreases the memory requirement fromincreased the number of documents by splitting each tranO(2S−1 ZW ) to O(SZW ) as described above.
script into 3-paragraph “documents” as done in [21]. We
omitted words that occurred in fewer than 10 documents.
There were 6,413 documents, and the vocabulary size was
3. RELATED WORK
6,759. The unit epoch was set at one year, and excluding
A number of methods for analyzing the evolution of topthe years for which data was missing there were 205 epochs.
ics in document collections have been proposed, such as theWe omitted stop-words from all data sets.
dynamic topic model [5], topic over time [21], online latent
We compared MDTM to DTM, LDAall, LDAone, andDirichlet allocation [1], and topic tracking model [11]. HowLDAonline. DTM is a dynamic topic model with online inever, none of the above methods take account of multiscale
ference that does not take multiscale distributions into condynamics. For example, the dynamic topic model (DTM) [5]sideration; it corresponds to MDTM with S = 1. Note that
depends only on the previous epoch distribution. On theDTM used here models dynamics with Dirichlet priors whileother hand, MDTM depends on multiple distributions withthe original DTM with Gaussian priors. LDAall, LDAone,diﬀerent timescales. Therefore, with MDTM, we can modeland LDAonline are based on LDA, and so do not model thethe multiple timescale dependency, and so infer the current
dynamics. LDAall is an LDA that uses all past data formodel more robustly. Moreover, while DTM uses a Gausinference. LDAone is an LDA that uses just the current
sian distribution to account for the dynamics, the proposed
data for inference. LDAonline is an online learning extenmodel uses conjugate priors. Therefore, inference in MDTM
sion of LDA, in which the parameters are estimated using
is relatively simple compared to that in DTM.
those of the previous epoch and the new data [4]. For a fair
The multiscale topic tomography model (MTTM) [14] cancomparison, the hyperparameters in these LDAs were opanalyze the evolution of topics at various resolutions of timescales timized using stochastic EM as described by Wallach [19].
by assuming non-homogeneous Poisson processes. In conWe set the number of latent topics at Z = 50 for all models.
trast, MDTM models the topic evolution within the DirichletIn MDTM, we used γ = 1, and we estimated the Dirichlet
multinomial framework as the same with most topic models
prior for topic proportions subject to αt,z ≥ 10−2 in order
including latent Dirichlet allocation [6]. Another advantage
to avoid overﬁtting. We set the number of scales so that oneof MDTM over MTTM is that it can make inferences inof the multiscale distributions covered the entire period, oran online fashion. Therefore, MDTM can greatly reduce
S = dlog2 T + 1e, where T is the number of epochs. We did
the computational cost as well as the memory requirements
not compare with the multiscale topic tomography model
because past data need not be stored. Online inference is(MTTM) because the perplexity of MTTM was worse thanessential for modeling the dynamics of document collections,that of LDA in [14] and MDTM has a clear advantage overin which large numbers of documents continue to accumuMTTM in that MDTM can make inferences in an online
late at any given moment, such as news articles and blogs,
fashion.
because it is necessary to adapt to the new data immediately
We evaluated the predictive performance of each modelfor topic tracking, and it is impractical to prepare suﬃcient
using the perplexity of held-out words,
memory capacity to store all past data. Online inference
10
test
P PNt,dtest
algorithms for topic models have been proposed [1, 4, 7, 11].
log P (wt,d,n|t, d, Dt )
n=1
d
A,
P
Perplexity = exp @−Singular value decomposition (SVD) is used for analyzing
test
d Nt,dmultiscale patterns in streaming data [15] as well as topic(18)
models. However, since SVD assumes Gaussian noise, ittestwhere Nt,dis the number of held-out words in the dth doctest
ument at epoch t, wt,d,n
is the nth held-out words in the
document, and Dt represents training samples until epocht. A lower perplexity represents higher predictive performance. We used half of the words in 10% of the documents
as held-out words for each epoch, and used the other words
as training samples. We created ten sets of training andtest data by random sampling, and evaluated the average
perplexity over the ten data sets.

4.2 Results
The average perplexities over the epochs are shown in
Table 2, and the perplexities for each epoch are shown in
Figure 5. For all data sets, MDTM achieved the lowest perplexity, which implies that MDTM can appropriately modelthe dynamics of various types of data sets through its useof multiscale properties. DTM had higher perplexity than
MDTM because it could not model the long-timescale dependencies. The reason for the high perplexities of LDAalland LDAonline is that they do not consider the dynamics.
The perplexity achieved by LDAone is high because it uses
only current data and ignores the past information.
The average perplexities over epochs with diﬀerent numbers of topics are shown in Figure 6. Under the same numberof topics, MDTM achieved the lowest perplexities in all of
the cases except when Z = 150 and 200 in the NIPS data.
Even if the number of topics of the other models increases,
the perplexities of the other models did not become better
than that of our model with fewer topics in PNAS, Digg,
and Addresses data. This result indicates that the larger
number of parameters of our model is not a major reason
for the lower perplexity.
The average perplexities over epochs with diﬀerent numbers of scales in MDTM are shown in Figure 7. Note thats = 0 uses the uniform distribution only, while s = 1 uses
the uniform distribution and the previous epoch’s distribution. The perplexities decreased as the number of scales increased. This result indicates the importance of considering
multiscale distributions.
Figure 8 shows the average computational time per epoch
when using a computer with a Xeon5355 2.66GHz CPU.
The computational time for MDTM is roughly linear against
the number of scales. Even though MDTM considers multiple timescale distributions, its computational time is muchsmaller than that of LDAall which considers a single timescale
distribution. This is because that MDTM uses only current
samples for inference, in contrast, LDAall uses all samples
for inference.
Figure 9 shows the estimated λt,z,s with diﬀerent numbers of scales s in MDTM. The sum of the values for eachepoch and for each topic are normalized to one. The parameters decrease as the timescale lengthens. This result
implies that recent distributions are more informative as regards estimating current distributions, which is intuitively
reasonable.
Figure 10 shows two topic examples of the multiscale topic
evolution in NIPS data analyzed by MDTM. Note that weomit words appeared in the longer timescales from the table.
In the longest timescale, basic words for the research ﬁeld areappropriately extracted, such as ‘speech’, ‘recognition’, and‘speaker’ in the speech recognition topic, ‘control’, ‘action’,‘policy’, and ‘reinforcement’ in the reinforcement learning
topic. In the shorter timescale, we can see the evolution oftrends in the research. For example, in the speech recognition research, phoneme classiﬁcation is a popular task until
1995, and probabilistic approaches such as hidden Markov
models (HMM) from 1996 are frequently used.

5.

CONCLUSION

In this paper, we have proposed a topic model with multiscale dynamics and eﬃcient online inference procedures. We
have conﬁrmed experimentally that the proposed method
can appropriately model the dynamics in document data byconsidering multiscale properties, and that it is computationally eﬃcient.
In future work, we could determine the unit time interval
and the length of scale automatically from the given data.
We assumed that the number of topics was known and ﬁxed
over time. We can automatically infer the number of topics
by extending the model to a nonparametric Bayesian modelsuch as the Dirichlet process mixture model [16, 18]. Since
the proposed method is applicable to various kinds of discrete data with timestamps, such as web access log, blog,
and e-mail, we will evaluate the proposed method further
by applying it to other data sets.

6.

REFERENCES[1] L. AlSumait, D. Barbara, and C. Domeniconi. On-line
LDA: Adaptive topic models for mining text streams
with applications to topic detection and tracking. In
ICDM ’08, pages 3–12, 2008.
[2] C. Andrieu, N. de Freitas, A. Doucet, and M. I.
Jordan. An introduction to MCMC for machinelearning. Machine Learning, 50(1):5–43, 2003.
[3] A. Asuncion, M. Welling, P. Smyth, and Y. W. Teh.
On smoothing and inference for topic models. In UAI’09, pages 27–34, 2009.
[4] A. Banerjee and S. Basu. Topic models over text
streams: A study of batch and online unsupervised
learning. In SDM ’07, 2007.
[5] D. M. Blei and J. D. Laﬀerty. Dynamic topic models.
In ICML ’06, pages 113–120, 2006.
[6] D. M. Blei, A. Y. Ng, and M. I. Jordan. Latent
Dirichlet allocation. Journal of Machine Learning
Research, 3:993–1022, 2003.
[7] K. R. Canini, L. Shi, and T. L. Griﬃths. Online
inference of topics with latent Dirichlet allocation. In
AISTATS ’09, volume 5, pages 65–72, 2009.
[8] T. L. Griﬃths and M. Steyvers. Finding scientiﬁc
topics. Proceedings of the National Academy of
Sciences, 101 Suppl 1:5228–5235, 2004.
[9] T. Hofmann. Probabilistic latent semantic analysis. In
UAI ’99, pages 289–296, 1999.
[10] T. Hofmann. Collaborative ﬁltering via Gaussian
probabilistic latent semantic analysis. In SIGIR ’03,
pages 259–266, 2003.
[11] T. Iwata, S. Watanabe, T. Yamada, and N. Ueda.
Topic tracking model for analyzing consumer purchasebehavior. In IJCAI ’09, pages 1427–1432, 2009.
[12] T. Iwata, T. Yamada, and N. Ueda. Probabilistic
latent semantic visualization: topic model for
visualizing documents. In KDD ’08, pages 363–371,
2008.
[13] T. Minka. Estimating a Dirichlet distribution.
Technical report, M.I.T., 2000.

Table 2: Average perplexities over epochs. The value in the parenthesis represents the standard deviation
over data sets.
MDTM
DTM
LDAallLDAoneLDAonline
NIPS
1754.9 (41.3)
1771.6 (37.2)
1802.4 (36.4)
1822.0 (44.0)
1769.8 (41.5)
PNAS
2964.3 (122.0) 3105.7 (146.8) 3262.9 (159.7) 5221.5 (268.7) 3401.7 (149.1)
Digg
3388.9 (37.7)
3594.2 (46.4)
3652.6 (27.1)
5162.9 (43.4)
3500.0 (43.6)
Addresses 1968.8 (56.5)
2105.2 (49.7)
2217.2 (75.3)
3033.5 (70.9)
2251.6 (62.0)
2000

12000
MDTM
DTM
LDAallLDAoneLDAonline

10000
8000

perplexity

perplexity

1900
1800

6000
4000

1700
2000
1600

0
2

4

6

8

10

12

10

30

40

50

epoch

(a) NIPS(b) PNAS

6000

60

70

80

90

6000
MDTM
DTM
LDAallLDAoneLDAonline

5000
perplexity

5000
perplexity

20

epoch

4000
3000

4000
3000
2000

2000

1000
5

10

15

20

50

100

epoch

150

200

epoch

(c) Digg(d) Addresses
Figure 5: Perplexities for each epoch.

1700

1600
1550

3000
2800

4500
perplexity

1650

MDTM
DTM
LDAallLDAoneLDAonline

5000

7000
perplexity

perplexity

MDTM
DTM
LDAallLDAoneLDAonline

8000

6000

perplexity

1750

3200

9000

MDTM
DTM
LDAallLDAoneLDAonline

1800

4000

2600
2400

5000
2200

1500

3500
4000

2000

1450
3000

1400
50

100

150

200

250

300

3000
50

100

150

200

number of topics

number of topics(a) NIPS(b) PNAS

250

300

1800
50

100

150

200

250

300

50

100

number of topics

150

200

250

number of topics(c) Digg(d) Addresses

0

1

2

3

4

5

5200

4600

4800

4400

4000
3600

4000
3800
3600
3400

2800

3200
1

2

3

4

5

#scales#scales(a) NIPS(b) PNAS

6

7

8

2600

4200

3200
0

2800

perplexity

4400

perplexity

1880
1860
1840
1820
1800
1780
1760
1740
1720
1700

perplexity

perplexity

Figure 6: Average perplexities with diﬀerent numbers of topics.

2400
2200
2000
1800

0

1

2

3

4

5

6

0 1 2 3 4 5 6 7 8 9#scales(c) Digg#scales(d) Addresses

Figure 7: Average perplexity of MDTM with diﬀerent numbers of scales.

300

4000

800

3500

700

3000

600

1000

6000

900

5000

800
700

4000

2500

500

2000

400

1500

300

600

3000

500
400

2000
300

1000

200

500

100

0

0

200

1000

0

1

2

3

4

5

all one online

100

0

1

2

(a) NIPS

3

4

5

6

7

8

0

all one online

0

1

2

3

(b) PNAS

4

5

6

0

all one online

01(c) Digg

2

3

4

5

6

7

8

9

all

one online(d) Addresses

Figure 8: Average computational time (sec) of MDTM per epoch with diﬀerent numbers of scales, LDAall,
LDAone, and LDAonline.
0.16

0.24

0.18

0.16

0.16

0.2

0.14

0.08

0.16
0.12

lambda0.1

lambda0.14

0.12

lambdalambda

0.14

0.12
0.1

0.12
0.1

0.08
0.08

0.06
0.04

0.04
1

2

3

4

5

0.08

0.06
0.04
1

2

3

4

5

6

7

8

0.06
1

2

3

4

scale

scale

scale

(a) NIPS(b) PNAS(c) Digg

5

6

1

2

3

4

5

6

7

8

9

scale

(d) Addresses

Figure 9: Average normalized weight λ with diﬀerent scales estimated in MDTM.
[14] R. Nallapati, W. Cohen, S. Ditmore, J. Laﬀerty, and
K. Ung. Multiscale topic tomography. In KDD ’07,
pages 520–529, 2007.
[15] S. Papadimitriou, J. Sun, and C. Faloutsos. Streaming
pattern discovery in multiple time-series. In VLDB
’05, pages 697–708, 2005.
[16] L. Ren, D. B. Dunson, and L. Carin. The dynamichierarchical Dirichlet process. In ICML ’08, pages
824–831, 2008.
[17] M. Stephens. Dealing with label switching in mixture
models. Journal of the Royal Statistical Society B,
62:795–809, 2000.
[18] 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.
[19] H. M. Wallach. Topic modeling: Beyond bag-of-words.
In ICML ’06, pages 997–984, 2006.
[20] C. Wang, D. M. Blei, and D. Heckerman. Continuous
time dynamic topic models. In UAI ’08, pages
579–586, 2008.
[21] X. Wang and A. McCallum. Topics over time: anon-Markov continuous-time model of topical trends.
In KDD ’06, pages 424–433, 2006.
[22] X. Wei, J. Sun, and X. Wang. Dynamic mixture
models for multiple time-series. In IJCAI ’07, pages
2909–2914, 2007.

APPENDIX
t−1
In this appendix, we give the derivation of (16). Let N̂t−2
s−1 ,z =P
P Pt−1
N̂t0 ,z,w , and N̂t,z = w N̂t,z,w . The Dirichw
t0 =t−2s−1
let prior parameter of the word distribution can be rewritten
as the weighted sum of the word distributions for each epoch
using (12) as follows,
S
X

(s)

λt,z,s ξt−1,z,w

s=1

=

S
X

λt,z,sPt−1

N̂t0 ,z,w
t0 =t−2s−1
t−1
N̂t−2s−1 ,z

s=1

=

=

S
X

t−1
X

λt,z,sN̂t0 ,z,wt−1
s=1 t0 =t−2s−1 N̂t−2s−1 ,z
t−1
X

S
X

λt,z,sN̂t0 ,z,wt−1
N̂t−2s−1 ,zt0 =t−2S−1 s=dlog (t−t0 +1)+1e
2

=

t−1
X

S
X

t0 =t−2S−1 s=dlog2 (t−t0 +1)+1e

=

t−1
X
t0 =t−2S−1

λ0t,z,t0 φ̂t0 ,z,w .

λt,z,s N̂t0 ,z N̂t0 ,z,w
t−1
N̂t−2
N̂t0 ,zs−1 ,z(19)

speech recognition word speaker training set tdnn time test speakers

1992–1999
system data letter state letters neural utterances words
phoneme classiﬁcation

state hmm system probabilities model words context hmms
markov probability

1992 – 1995

1996 – 1999

level phonetic segmentation
language segment accuracy
duration continuous units
male

spectral feature false acoustic
independent models
normalization rate trained
gradient

log likelihood models
sequence sequences hidden
hybrid states
frame transition

hidden states models feature
continuous modelingfeatures adaptation human
acoustic

1992 – 1993

1994 – 1995

1996 – 1997

1998 – 1999

sentencescore
dtw
vocabulary
processing
waibelacoustics
error
delay
architecturehittargetscore
scoresthresholddetection
veriﬁcation
putativecardalarmsdependent
performancetalkers
writervocabulary
writing transformation
table
mappingwaibelrecurrent
estimation
dependent
posteriorforwardmlp
backward
targetsclass
framesparameters
clustering
updateentropic
mixtureupdatesﬁgure
decoderdistance
welch

feedback
subject
segmented
reading factor
dictionary
degradation
character
generalization
experimentdiscreteemissionbehaviors
lengthdetection
parameters
term
eq
pdfs
real

space
missingsystems
ergodic
user
weaklyreconstruction
mappingvariables
constrained

1992

1993

1994

1995

1996

1997

1998

1999

(a) Speech recognition
learning state control action time policy reinforcement optimal actions recognition

1992–1999
dynamic space model exploration states programming barto
sutton goal task

function states algorithm model agent decision step reward
markov space

1992 – 1995

1996 – 1999

robot based controller
system forward level
memory real
jordan world

skills policies singh adaptive
iteration stochastictransition values
expected based

grid based memory controller
continuous cost systemtemporal iterationinterpolationrl machine policies
environment iteration mdp
singh ﬁnite
update search

1992 – 1993

1994 – 1995

1996 – 1997

1998 – 1999

watkinsmanagersweeping
tasks
prioritizedmoore lqr
learn
cases
dyna

game
moore
asynchronous
trajectoryatkesonlearnedpoint trials
position
methods

probability
critic actor
skill
supportbellmanconvergencelearnerprobabilities
problems

functionslearn
problemcar traﬃcalgorithms
problems
performance
speed
discretetrial actor
process pole
steps
local
processes
problemproblems
demonstration

ham bellman
convergenceequationprocesses
vector representation
mdps
choiceproblem

local learned
problems
probability
methodcurrent
optionscall
learn
problembelief pomdp
algorithms
criticobservableapproximate
pomdpsactor
partially
problems

1992

1993

1994

1995

1996

1997

1998

1999

(b) Reinforcement learning
Figure 10: Two topic examples of the multiscale topic evolution in NIPS data analyzed by MDTM: (a) speech
recognition, and (b) reinforcement learning topics. The ten most probable words for each epoch, timescale,and topic are shown.