NOTE-1176: Blei, Griffiths and Jordan — The nested Chinese restaurant process and hLDA

Contribution

It defines the nested Chinese restaurant process (nCRP), a prior on trees of unbounded depth and branching, and uses it as the prior of hierarchical LDA (hLDA), a topic model whose topics are arranged in a tree that is inferred, not fixed. It gives a collapsed Gibbs sampler that resamples each document’s path as a block, and each word’s level, including new branches and new levels. The finite-depth model was introduced earlier, in Blei, Griffiths, Jordan and Tenenbaum (NIPS 2003). This paper gives the infinite-depth version, hyperparameter inference, and the empirical comparison with LDA.

Key insight

A tree is a nested sequence of partitions, so a CRP at every node gives a distribution on trees with the CRP’s preferential attachment and exchangeability. If a document is a path, and the root lies on every path, the posterior pushes words that every document uses toward the root and words that a few documents share toward deeper nodes. Abstraction is not defined. It is read off where in the tree a word’s usage is shared: “the internal nodes are not summaries of their children. Rather, the internal nodes reflect the shared terminology of the documents assigned to the paths that contain them.” The cost of this is that a document is one path, so “a document can only access the topics that lie along a single path in the tree.”

Assumptions

• Bag of words: each document is a multiset of word tokens over a fixed vocabulary.
• nCRP(γ). At each node a document picks an existing child with probability nᵢ/(γ + n − 1) and a new child with γ/(γ + n − 1), where n counts the documents through that node before it (Eq. 1 applied at every level). Each node carries a topic βₖ ~ Dirichlet(η).
• One path per document. cᵈ ~ nCRP(γ); every word of document d is drawn from a topic on cᵈ.
• Levels. θᵈ ~ GEM(m, π), the stick-breaking distribution with sticks Vᵢ ~ Beta(mπ, (1 − m)π), m ∈ (0, 1), π > 0 (§2.4); each word takes level zᵈ,ₙ ~ Mult(θᵈ), then w ~ Mult(β at that level of cᵈ).
• Hyperparameters either fixed (§6.2) or given priors m ~ Beta, π ~ Exponential, γ ~ Gamma, η ~ Exponential and sampled by Metropolis–Hastings steps between Gibbs sweeps (§5.4).
• In §6.1 and §6.2 the levels are truncated at three, with a Dirichlet on the three proportions instead of the GEM. §6.3 uses the infinite-depth model.

Key results

• The prior. After M documents the paths form a random subtree “with a branching factor of at most M at all nodes”. The CRP’s exchangeability carries over: the probability of a set of paths does not depend on the order in which the documents arrived (§3). Re-checked here for five depth-two paths: all 120 orders give the same probability.
• The sampler (§5). Collapsed Gibbs over paths cᵈ and levels zᵈ,ₙ, with topics and level proportions integrated out. The path conditional (Eq. 4) is the nCRP prior times a ratio of Dirichlet normalizers, over existing leaves and new branches at every internal node, drawn as a block. Levels deeper than any in use are reached by a sequence of Bernoulli steps. No convergence-rate result: “it is difficult to say something more definitive about the speed of the algorithm”. The mode is approximated by the sampled state of highest log joint probability (Eq. 5), and restarts choose among local modes.
• Simulated data (§6.1, Fig. 6). Ten corpora drawn from hLDA itself, each 100 documents of 250 words, vocabulary 100, η = 0.005, γ = 1, three levels. “We exactly recover the correct hierarchies, with only two errors”: in one, a single wrongly allocated path; in the other, “the inferred mode has higher posterior probability than the true tree structure (due to finite data)”.
• Real corpora (§6.2). With η = (2.0, 1.0, 0.5) by level, γ = 1.0, and the GEM parameters “fixed at m = 100 and π = 0.5”: JACM, 536 abstracts 1987–2004, 68K words, a 25-topic tree (Fig. 1) with function words at the root and subfields at level two; Psychological Review, 1,272 abstracts 1967–2003, a 52-topic tree (Fig. 7); PNAS, 12,913 abstracts 1991–2001, 2.3M words, 56 topics with a smaller γ (Fig. 8). Judged by inspection only. The Gibbs sampler took about 0.001 s per document per iteration for JACM and Psychological Review, 0.006 s for PNAS.
• Against LDA (§6.3, Fig. 9). On JACM, five-fold cross-validation, all hyperparameters integrated out, held-out likelihood approximated by the harmonic mean of 800 inner samples for each of 100 outer samples. The posterior over hLDA’s topic count has its mode near 140. At every LDA topic count in the bracketing range, hLDA’s held-out likelihood was higher. The authors expect the reverse for large topic counts: “we eventually expect LDA to dominate hLDA for large numbers of topics.”

Claims

id	claim	strength	support
C1	The nCRP is a distribution on infinitely deep, infinitely branching trees, exchangeable in its customers, with posterior inference by collapsed Gibbs sampling	strong	construction in §3 from the CRP; sampler in §5
C2	In hLDA a document draws its words from the topics on one root-to-leaf path, so topics are shared only through shared ancestry	strong	the generative process of §4; stated in §6.3
C3	The posterior places general topics near the root and specialized ones near the leaves	moderate	argued in §4 from the root lying on every path and the GEM’s bias to small levels; shown in Figs. 1, 7, 8
C4	The sampler recovers the generating tree from data simulated under the model, with occasional errors	moderate	ten simulated corpora, eight exact (§6.1)
C5	Near hLDA’s own posterior topic count, the hierarchy predicts held-out JACM abstracts better than LDA at any fixed topic count in that range	moderate	Fig. 9; one corpus; harmonic-mean estimator
C6	”If interpretability is the goal, then there are strong reasons to prefer hLDA to LDA”	weak	ten randomly chosen LDA topics (Fig. 10) set against the hLDA trees, judged by eye
C7	The nonparametric prior lets the data choose the tree’s size and shape	moderate, with a caveat the paper itself gives	§§4–5. The paper adds that the tree’s “size, shape, and character will be affected by the settings of the hyperparameters”, and §6.2 tunes them for readability

Concepts

• Nested CRP: an infinite collection of CRPs, one per node, each table pointing to a child restaurant; a customer’s path is the sequence of tables chosen on successive nights.
• Path cᵈ: the root-to-leaf sequence of nodes a document visits.
• Level allocation zᵈ,ₙ: which node on the document’s path generated word n.
• GEM(m, π): two-parameter stick-breaking with sticks Beta(mπ, (1 − m)π), so that m sets the mean stick and π how tightly documents keep to it.
• Abstraction: not defined formally; “a statistical procedure that allows a system designer to capture notions of abstraction that are reflected in usage patterns of the specific corpus at hand”.

Connections

It builds on the CRP (Aldous), stick-breaking and the GEM distribution (Pitman; Sethuraman), and the Dirichlet process mixture (Antoniak; Ferguson), and extends LDA (Blei, Ng and Jordan 2003) and its collapsed Gibbs sampler (Griffiths and Steyvers 2004). It contrasts itself with hierarchical clustering, whose internal nodes summarize their children, and with supervised placement of documents into a given hierarchy. It names as open the variant in which “each document exhibits multiple paths through the tree”, which the nested HDP of LIT-002 (NOTE-023) supplies. It names the author-topic model (LIT-1546) as adaptable to a flexible hierarchy, and cites the mixed membership blockmodel (LIT-1553) among flat mixed-membership models of non-text data. It mentions the Indian buffet process (Griffiths and Ghahramani 2006) as the parallel line of “multiple binary features rather than clusters”.

Bearing on the record

• QUESTION-276, condition 2 (overlap). T21 said that “classical hLDA assigns each document one path through a tree”, and the paper confirms it in its own words (THEORY-969). If a document is a member’s activity, hLDA can place a member under several topics only as a chain of ever more specific ones. A member who takes part in two sibling branches cannot be represented. That is a partition at every level, not an overlap. T21’s move to the nested HDP (LIT-002) is the paper’s own §4 suggestion.
• QUESTION-276, “without their number being fixed in advance”. The nCRP does leave the number of topics open, but the paper is plain that the hyperparameters shape the tree, and its readable trees use hyperparameters chosen for readability (§6.2). Leaving the number open moves the choice into γ, η and the GEM, and does not remove it. That bears on CLAIM-188’s price of naming a recovered unit.
• QUESTION-276, “What would not answer it”. §6.1 is exactly the test that the question sets aside: recovering the prior’s structure from data generated under that prior. Eight of ten trees came back exactly (THEORY-1010). That shows the sampler can invert the model. It says nothing about whether a tree is in data the model did not generate. The one failure “due to finite data”, a wrong tree with higher posterior than the true one, is a small-sample identifiability failure, and the authors’ own caveat names the condition: “how identifiable the topics are”. The paper has no identifiability theorem for trees or topics. CLAIM-135’s second step is not reached for hLDA by anything in it.
• QUESTION-276, T21’s “allow the hierarchy to lose”. §6.3 is the paper’s own test of whether the hierarchy earns its constraint, and it passes only in a range: near its own topic count on one corpus, with an estimator now known to be unreliable (THEORY-989, Proposed). The authors expect a flat model to win when the topic count is free. A hierarchy over members’ messages would need its own such test against a flat mixed-membership model, which is what T21 asked for.
• CLAIM-454. An hLDA topic is a distribution over words and nothing more. The paper’s “abstraction” is shared usage, by definition. A tree of what members say is at most a constituent in that claim’s sense, and the paper itself claims no more. T21’s falsification test (two organizations with identical messages and different authorization pathways) follows from the likelihood: hLDA’s depends only on the words, so it must give both organizations the same posterior.
• CASE-166. Its analyzer fixed the number of factors. hLDA does not, but the trees of §6.2 were read by eye. The same objection that CLAIM-427 makes to recovering modes in the framework’s own terms applies to reading a tree’s levels as levels of an organization.

No instruction for machine-learning practice; nothing for the anthology.

Limitations

• §5.1 does not match §2.4. §2.4 defines GEM(m, π) with sticks Vᵢ ~ Beta(mπ, (1 − m)π), so E[Vᵢ] = m. §5.1’s conditional for a level k ≤ max(zᵈ,₋ₙ) is printed with factors ((1 − m)π + #[z = k])/(π + #[z ≥ k]) and (mπ + #[z > j])/(π + #[z ≥ j]). That is the posterior predictive for sticks Beta((1 − m)π, mπ). With §2.4’s sticks the factors are (mπ + #[z = k])/(π + #[z ≥ k]) and ((1 − m)π + #[z > j])/(π + #[z ≥ j]). Checked by Monte Carlo at m = 0.3, π = 4 with seven observed levels: the corrected form gives 0.473, 0.241, 0.126, 0.048 for the first four levels, against Monte Carlo 0.473, 0.240, 0.126, 0.048, and the printed form gives 0.618, 0.262, 0.091, 0.020. The stop probability for new levels, printed as (1 − m) times the word likelihood, follows the printed convention too.
• Hyperparameters out of range. §6.2 fixes “m = 100 and π = 0.5”, though §2.4 requires m ∈ (0, 1). The text before it says “If we set π to be large (e.g., π = 0.5)” and “Setting m to be large (e.g., m = 100)”, which reads as m and π swapped. The likely intent (mean stick 0.5, concentration 100) is the reader’s guess. The JACM text may differ.
• No identifiability result. Neither for the tree nor for the topics. §6.1’s success is on sparse, well-separated topics (η = 0.005), and the authors say trees “will not be as easy to identify in data sets which exhibit polysemy and similarity between topics.”
• No mixing guarantee. The mode is the best of the sampled states, and the authors defend local modes as useful representations: “a local mode of the posterior found by Gibbs sampling often provides such a representation.”
• The harmonic-mean estimator. §6.3’s held-out likelihoods use it (Kass and Raftery). It is known to be unstable and biased, and it can have infinite variance, so the margin in Fig. 9 is less secure than it looks. One corpus only.
• Interpretability by eye. C6 rests on ten LDA topics against the hLDA trees, with no protocol, and LDA was run without removing function words.
• Not the typeset paper. The arXiv v3 text was read; the JACM version was not compared.

Open questions

• Under what conditions on the topics and the data are an hLDA tree and its topics identifiable, up to relabelling of siblings? The paper supplies a condition in words (separation of topics, enough data) and no result.
• Does a multiple-path model (the nested HDP) keep §6.3’s predictive advantage over a flat model when the topic count is free? LIT-002’s reading (NOTE-023) has the variational comparison, not this one.
• With a reliable estimator of held-out likelihood, does the JACM ordering in Fig. 9 survive?