Stochastic Divergence Minimization
for Online Collapsed Variational
Bayes Zero Inferenceof Latent Dirichlet Allocation@KDD2015
Issei Sato & Hiroshi Nakagawa
The University of Tokyo

Latent Dirichlet allocation [Blei,2003]
The annual ACM SIGKDD conference isthe premier international forum for data
mining researchers and practitioners fromacademia, industry, and government toshare their ideas, research results andexperiences.

2

Latent Dirichlet allocation [Blei,2003]
The1 annual2 ACM2 SIGKDD3 conference2
is1 the1 premier2 international2 forum2 for1
data3 mining3 researchers10 and1
practitioners10 from1 academia10, industry8,
and1 government7 to1 share6 their1 ideas10,research10 results5 and1 experiences5.

Modeling co-occurrence:
Frequently co-occurring words
are assigned to the same topic (color)z j ,iwd ,i3

De Finetti theorem [De Finetti, 1930s]
A sequence of random variables (x1, x2, . . .) is
infinitely exchangeable iff, for all nnp ( x1 , x2 ,..., xn )    p ( xi |  ) p ( )di 1

Latent Dirichlet allocation [Blei,2003]
Topic distribution for each document

Word distribution for each topicFor each words:kwords

Topicdz j ,iwd ,iPriors Matter [Wallach+,2009]
Topic
distribution
for eachdocument
Asymmetric
Dirichlet
prior

Dir( 1 ,  2 ,...,  K )Dir( 1 ,  2 ,..., V )Word distribution for each topic
Symmetric Dirichlet prior
For each words:

Dir( ,  ,...,  )Dir(  ,  ,...,  )kwords

Topicdz j ,iwd ,iEvaluation: Perplexity
Prediction of held-out words

 1exp log p ( w* | Wtrain )
 N test w*Wtest
KE [n E [nk 1train
k , w*traink] train
d ,ktraindE [n]  V E [ n]k]   kk

Inference algorithms• Variational Bayes (VB)
[Blei+,JMLR2003]• Collapsed Gibbs Sampling (CGS)[Griffiths+,PNAS2004]• Collapsed Variational Bayes (CVB)[Teh+,NIPS2007]• Collapsed Variational Bayes Zero (CVB0)[Asuncion+, UAI2009]kMarginalize out parameters
words

Topic

dz j ,iwd ,iWhy CVB0 works better?
CVB0 uses zero-order Taylor approximation forexpectations in CVB→ CVB0 is less accurate than CVB

CVB0 can be formulated asa local α-divergence minimization[Sato & Nakagawa, ICML2012]

α-divergence minimization
Inference
VB [Blei+,03]
CVB [Teh+,07]

Marginalization－✓

α-divergence
α→0α→0✓α→1 (≒1)

－α→1

CVB0
[Asuncion+, 09]
EP [Minka+,02]

Zero forcing effect

-101

The emphasis in the estimation is on high-frequency topics
or low-frequency topics is forced to be zero

Stochastic Optimization
Scaling up: Batch data → Sub-sampling• Variational Bayes (VB) [Blei+,JMLR2003]→Stochastic Variational Bayes (SVB)[Hoffman+,Sato+,NIPS2010]• Collapsed Variational Bayes Zero (CVB0)[Asuncion+, UAI2009]→Stochastic Collapsed Variational Bayes Zero (SCVB0)[Foulds+, KDD2013]

Framework of SCVB0Problem
How to formulate SO of CVB0
- CVB0 integrates out parameters

Solution
When we manually adjust Dirichlet prior,
CVB0 update ~ MAP update.

SCVB0 ~ Stochastic Approx. of MAP infer.

Question and Problem on SCVB0• Why MAP works better than VB ?
• We cannot use Asym. Dirichlet prior
Our contribution• Formulation of SCVB0→ Stochastic divergence minimization(SDM)• Estimation of Dirichlet prior→ Reformulate DM of [Sato+, ICML2012]

Main Idea
[Sato&Nakagawa, ICML2012]

Infer q( Z )   q( zd ,i )d ,iby DM=CVB0 update

This work

Inferq( Z ,W |  ,  )   q( zd ,i | wd ,i ) q( wd ,i |  ,  )d ,i=CVB0 update

?

by DM
Stochastic Approx.

Our contributions
K

E [nkloo,wd ,i ]  E [ndloo,k ]   kq( wd ,i |  ,  ) ICML2012]
[Sato&Nakagawa,loolooE[n]VE[nk 1kd ]   kq( Z )   q( zd ,i ) by DM
Infer
Leave-One-Outd ,iPerplexity

k=CVB0 update
 1
exp    log q( wd ,i |  ,  )N d ,iThis work

Inferq( Z ,W |  ,  )   q( zd ,i | wd ,i ) q( wd ,i |  ,  )d ,i=CVB0 update

?

by DM
Stochastic Approx.

Testset perplexity ☓ LOO perplexity
NY times ☓CVB0 with Sym.Dir

Testset perplexity ☓ LOO perplexity
NY times ☓CVB0 with Sym.Dir

Empirical Bayes( *,  *)  arg max log p ( D |  ,  ) ,Variational EM( *,  *)  arg max L( D |  ,  ) ,log p ( D |  ,  )  L( D |  ,  )This work
Stochastic Approx.

( *,  *)  arg max log q( D |  ,  ) ,

⇔ min Leave-One-Out Perplexity q( w |  ,  )d ,id ,iSummary
VB
‘03
Data
processing
MemoryUpdate/mini-batch
HDP(Asym. Dir)

SVB
‘10

Batch

O(VK)
✔

Subsamp.
O(VK)

CVB0
‘07
Batch

O(VK)

O(NK)
-✔

✔

SCVB0
‘13ThisworkSubsamp.
O(VK)

Subsamp.
O(VK)

O(VK) O(VsK)✔

V: Vocabulary size
Vs: Vocab. size in sub-samples
K: # of topics
N: Total # of words
Ignore!

Experimental settings
4 datasets
Dataset# of Doc.

Vocab. size

DBLP

0.6M

19K

Wikipedia

1M

130K

Pubmed1M

1M

50K

Pubmed5M

5M

122K

Evaluation: Testset Perplexity
Algorithms: SVB, SCVB0, SDM (This work)# of Topics (Truncation level): 1000

Bayesian optimization
for tuning hyper-parameters
Dataset: Pubmed1M

Experimental result
Dataset: Pubmed5M反省点：査読者との戦いを経て• スコープが狭い– （建前）LDAは引用数1万を超える論文なので、LDAのアルゴリズムの改良自体は重要– （本音）汎用性大事。少なくとも汎用性がありそうな書き方を心がけるべき• 実験が少ない。Twitterの解析とかもやったら？
– （建前）[Foulds+, KDD2013]と同等の実験– （本音）実験の種類はやはり多いほうが良い
少なくとも[Sato+,KDD2012]のときは、Perplexity(4datasets), リンク予測(2datasets), 文書分類(2datasets)としたら褒められた• 外部リンク先に証明のある定理は貢献に入れるべきではない– （建前）
事前にCo-Chairsに可能か確認済なので、メタ査読者に確認を以前KDDの査読者に外部リンクに置くように言われたことがある
そのようにしているKDD論文も過去にある– （本音）Supplemental materialの無い会議では、やはりページ内に収めるように書くべき