A Nested HDP for Hierarchical Topic Models
Authors: John Paisley, Chong Wang, David Blei, Michael I. Jordan
ICLR 2013

Abstract: We develop a nested hierarchical Dirichlet process (nHDP) for hierarchical topic modeling. The nHDP is a generalization of the nested Chinese restaurant process (nCRP) that allows each word to follow its own path to a topic node according to a document-specific distribution on a shared tree. This alleviates the rigid, single-path formulation of the nCRP, allowing a document to more easily express thematic borrowings as a random effect. We demonstrate our algorithm on 1.8 million documents from The New York Times.

A Nested HDP for Hierarchical Topic Models
John Paisley
Department of EECS
UC Berkeley
Chong Wang
Dept. of Machine Learning
Carnegie Mellon University
David Blei
Dept. of Computer Science
Princeton University
Michael I. Jordan
Department of EECS
UC Berkeley
Abstract
We develop a nested hierarchical Dirichlet process (nHDP) for hierarchical topic modeling. The
nHDP is a generalization of the nested Chinese restaurant process (nCRP) that allows each word
to follow its own path to a topic node according to a document-speciﬁc distribution on a shared
tree. This alleviates the rigid, single-path formulation of the nCRP, allowing a document to more
easily express thematic borrowings as a random effect. We demonstrate our algorithm on 1.8 million
documents from The New York Times.1
1 Introduction
Organizing things hierarchically is a natural process of human activity. A hierarchical tree-structured representation of
data can provide an illuminating means for understanding and reasoning about the information it contains. The nested
Chinese restaurant process (nCRP) [2] is a model that performs this task for the problem of topic modeling. It does
this by learning a tree structure for the underlying topics, with the inferential goal being that topics closer to the root
are more general, and gradually become more speciﬁc in thematic content when following a path down the tree.
The nCRP is limited in the hierarchies it can model. We illustrate this limitation in Figure 1. The nCRP models
the topics that go into constructing a document as lying along one path of the tree. This signiﬁcantly limits the
underlying structure that can be learned from the data. The nCRP performs document-speciﬁc path clustering; our
goal is to develop a related Bayesian nonparametric prior that performs word-speciﬁc path clustering. We illustrate
this objective in Figure 1. To this end, we make use of the hierarchical Dirichlet process [3], developing a novel prior
that we refer to as thenested hierarchical Dirichlet process(nHDP). With the nHDP, a top-level nCRP becomes a base
distribution for a collection of second-level nCRPs, one for each document. The nested HDP provides the opportunity
for cross-thematic borrowing that is not possible with the nCRP.
2 Nested Hierarchical Dirichlet Processes
Nested CRPs. Nested Chinese restaurant processes (nCRP) are a tree-structured extension of the CRP that are useful
for hierarchical topic modeling. A natural interpretation of the nCRP is as a tree where each parent has an inﬁnite
number of children. Starting from the root node, a path is traversed down the tree. Given the current node, a child
node is selected with probability proportional to the previous number of times it was selected among its siblings, or a
new child is selected with probability proportional to a parameter α> 0.
For hierarchical topic modeling with the nCRP, each node has an associated discrete distribution on word indices
drawn from a Dirichlet distribution. Each document selects a path down the tree according to a Markov process,
which produces a sequence of topics. A stick-breaking process provides a distribution on the selected topics, after
which words for a document are generated by ﬁrst drawing a topic, and then drawing the word index.
HDPs. The HDP is a multi-level version of the Dirichlet process. It makes use of the idea that the base distribution for
the DP can be discrete. A discrete base distribution allows for multiple draws from the DP prior to place probability
mass on the same subset of atoms. Hence different groups of data can share the same atoms, but place different
probability distributions on them. The HDP draws its discrete base from a DP prior, and so the atoms are learned.
1This is a workshop version of a longer paper. Please see [1] for more details, including a scalable inference algorithm.
1
arXiv:1301.3570v1  [stat.ML]  16 Jan 2013
nCRP
nHDP
Figure 1: An example of path structures for the nested Chinese restaurant process (nCRP) and the nested hierarchical
Dirichlet process (nHDP) for hierarchical topic modeling. With the nCRP, the topics for a document are restricted to
lying along a single path to a root node. With the nHDP, each document has access to the entire tree, but a document-
speciﬁc distribution on paths will place high probability on a particular subtree. The goal of the nHDP is to learn a
thematically consistent tree as achieved by the nCRP, while allowing for the cross-thematic borrowings that naturally
occur within a document.
Nested HDPs. In building on the nCRP framework, our goal is to allow for each document to have access to the
entire tree, while still learning document-speciﬁc distributions on topics that are thematically coherent. Ideally, each
document will still exhibit a dominant path corresponding to its main themes, but with offshoots allowing for random
effects. Our two major changes to the nCRP formulation toward this end are that (i) each word follows its own path to
a topic, and (ii) each document has its own distribution on paths in a shared tree.
With the nHDP, all documents share a global nCRP. This nCRP is equivalently an inﬁnite collection of Dirichlet
processes with a transition rule between DPs starting from a root node. With the nested HDP, we use each Dirichlet
process in the global nCRP as a base for a second-level DP drawn independently for each document. This constitutes
an HDP. Using a nesting of HDPs allows each document to have its own tree where the transition probabilities are
deﬁned over the same subset of nodes, but where the values of these probabilities are document-speciﬁc.
For each node in the tree, we also generate document-speciﬁc switching probabilities that are i.i.d. beta random vari-
ables. When walking down the tree for a particular word, we stop with the switching probability of the current node,
or continue down the tree according to the probabilities of the child HDP. We summarize this process in Algorithm 1.
Sample Results. We present some qualitative results for the nHDP topic model on a set of 1.8 million documents
from The New York Times. These results were obtained using a scalable variational inference algorithm [4] after one
pass through the data set. In Figure 2 we show example topics from the model and their relative structure. We show
four topics from the top level of the tree (shaded), and connect topics according to parent/child relationship. The
model learns a meaningful hierarchical structure; for example, the sports subtree branches into the various sports,
which themselves appear to branch by teams. In the foreign affairs subtree, children tend to group by major subregion
and then branch out into subregion or issue.
Algorithm 1Generating Documents with the Nested Hierarchical Dirichlet Process
Step 1. Generate a global tree by constructing an nCRP.
Step 2. For each document, generate a document tree from the HDP and switching probabilities for each node.
Step 3. Generate a document. For word nin document d,
a) Walking down the tree using HDPs. At current node, continue/stop according to its switching probability.
b) Sample word nfrom the discrete distribution at the terminal node.
2
game
play
team
going
think
season
tournament
   seeded
   final
   second
   victory
   round
cup
team
soccer
americans
match
goal
south
club
west
spade
bridge
open
golf
woods
tennis
tour
hole
hockey
season
devils
team
games
football
season
game
quarterback
bowl
basketball
season
game
team
knicks
season
baseball
game
league
series
run
inning
hit
game
runs
yankees
torre
sox
red
jeter
mets
valentine
piazza
franco
shea points
nets
game
scored
half
knicks
ewing
riley
game
patrick
jordan
bulls
chicago
michael
jackson
phil
giants
jets
season
parcells
fassel
yards
touchdown
game
pass
quarter
dame
notre
bowl
football
season
miami
florida
goal
period
scored
game
second
penguins
pittsburgh
mario
civic
meadowlands rangers
messier
richter
garden
madison
square
board
members
public
yesterday
decision
house
senate
republican
bill
congress
senator
budget
agreement
plan
unions
bills
pay
court
judge
justice
supreme
case
decision
lawyers
case
lawyer
court
judge
charges
health
care
medical
doctors
patients
hospitals
committee
panel
ethics
chairman
subcommittee
legislature
assembly
governor
legislative
senate
senate
judiciary
committee
nomination
roberts
walsh
oliver
north
iran
contra
trial
jury
case
evidence
crime
general
attorney
spitzer
office
eliot
agency
enron
lay
gates
webster
union
workers
labor
contract
employees
benefits
rate
percent
discount
previous
index
percent
money
government
pay
business
economic
agency
advertising
account
media
group
billion
deal
companies
business
corporation
largest
computer
technology
system
companies
software
market
percent
stock
investors
trading
products
food
industry
drug
companies
cars
workers
auto
ford
plant
vehicles
energy
fuel
oil
gas
prices
electricity
natural
carbonpower
plants
steel
air
electric
emissions
pollution
service
phone
network
telephone
wireless
internet
research
scientists
institute
national
laboratory
microsoft
software
windows
operating
gates
sun
sales
stores
retailers
mart
wal
drink
cola
soft
water
cokebank
interest
loans
rates
debt
fund
net
mutual
money
investors
stocks
real
estate
market
mortgage
brokers
securities
firms
morgan
stanley
accounting
  companies
communications
  telephone
  cable
  service
boeing
military
aircraft
pentagon
defense
percent
treasury
yield
prices
fed
rates
  share
  offer
shareholders
  stock
  bid
  takeover
insurance
savings
loan
estate
real
government
officials
foreign
administration
leaders
political
washington
nations
israel
palestinian
peace
arafat
minister
lebanon
syria
beirut
hezbollah
christian
hostages arab
king
egypt
jordan
hussein
military
nato
troops
forces
defense
aircraft
fighter
plane
air
jet
nuclear
missile
arms
defense
treaty
reagan
space
intelligence
afghanistan
bin
laden
taliban
qaeda
european
germany
france
union
east
nato
milosevic
bosnia
yugoslavia
serbia
tribunal
switzerland
  nazi
  holocaust
  jewish
  banks
  gold
soviet
union
gorbachev
moscow
communist
nato
europe
poland
missiles
solidarity
russia
yeltsin
moscow
kremlin
chechnya
clinton
treaty
arms
nuclear
reagan
range
summit
bush
iraq
administration
war
hussein
council
nations
iraq
security
resolution
saudi
arabia
bin
laden
osama
nuclear
weapons
program
inspectors
chemical
iran
gulf
persian
oil
shipping
china
north
korea
south
beijing
nuclear
taiwan
hong
kong
boat
insurance
return
vietnam
asia
indonesia
singapore
cambodia
Figure 2: Tree-structured topics from The New York Times. A shaded node is a top-level node.
References
[1] J. Paisley, C. Wang, D. Blei, and M. I. Jordan, “Nested hierarchical Dirichlet processes,” arXiv:1210.6738, 2012.
[2] D. Blei, T. Grifﬁths, and M. Jordan, “The nested Chinese restaurant process and Bayesian nonparametric inference
of topic hierarchies,”Journal of the ACM, vol. 57, no. 2, pp. 7:1–30, 2010.
[3] Y . Teh, M. Jordan, M. Beal, and D. Blei, “Hierarchical Dirichlet processes,” Journal of the American Statistical
Association, vol. 101, no. 476, pp. 1566–1581, 2006.
[4] M. Hoffman, D. Blei, C. Wang, and J. Paisley, “Stochastic variational inference,”arXiv:1206.7051, 2012.
3


Peer review:
[Review]:
The paper introduces a natural extension to the nested Chinese Restaurant process, where the main limitation was that a single path for the tree (from the root to a leaf) is chosen for each individual document. In this work, a document specific tree is drawn (with associated switching probabilities) which is then used to generate words in the document. Consequently, the words can represent very different topics not necessarily associated with the same path in the tree. 

Though the work is clearly interesting and important for the topic modeling community, the workshop paper could potentially be improved.  The main problem is clearly the length of the submission which does not provide any kind of details (less than 2 pages of content). Though additional information can be found in the cited arxiv paper, I think it would make sense to include in the workshop paper at least the comparison in terms of perplexity (showing that it substantially outperforms nCRP) and maybe some details on efficiency of inference. 
Conversely, the page-long Figure 2 could be reduced or removed to fit the content.

Overall, the work is quite interesting and seems to be a perfect fit for the conference. Given that an extended version is publicly available, I do not think that the above comments are really important.

Pros:
-- a natural extension of the previous model which achieves respectable results on standard benchmarks (though results are not included in the submissions)
Cons:
-- a little more information about the model and its performance could be included even in a 3-page workshop paper.