Source
Blei, Griffiths and Jordan (2010), Journal of the ACM 57(2), LIT-1542, read in full in NOTE-1176 from arXiv 0710.0845v3. The model is the paper’s §3 (the nCRP) and §4 (hLDA). The single-path restriction is stated in §6.3: “a document can only access the topics that lie along a single path in the tree.” The derivations below are the record’s.
What was actually shown
hLDA’s generative process (§4): every node k of an infinite tree carries a topic βₖ ~ Dirichlet(η). Document d draws a path cᵈ ~ nCRP(γ), level proportions θᵈ ~ GEM(m, π), and then, for each word, a level z ~ Mult(θᵈ) and the word from the topic at level z of cᵈ.
Nested partitions. Let the path’s node at depth ℓ be cᵈ[ℓ]. Two documents are in the same depth-ℓ block when cᵈ[ℓ] = cᵉ[ℓ]. Since a node at depth ℓ has exactly one parent, cᵈ[ℓ] = cᵉ[ℓ] implies cᵈ[ℓ′] = cᵉ[ℓ′] for every ℓ′ < ℓ. So the depth-(ℓ + 1) partition refines the depth-ℓ one, and the tree is the nested sequence the paper describes (“A tree can be viewed as a nested sequence of partitions”).
Overlap is nested. The topics document d can use are exactly those on cᵈ. Two documents share the topic at node k iff both paths pass through k, and then they share every topic above k. If d shares node k with e and node k′ with f, with k and k′ siblings, then cᵈ passes through two nodes of the same depth, which a path cannot do. So no document draws on two sibling subtrees, and the sets of topics documents can use form a chain under inclusion along each path. Which of a path’s topics a given document actually uses is set by θᵈ and its words. That is the only freedom within a path.
Exchangeability. At each node the choice among children is a CRP over the documents passing through it, and the CRP’s probability of a seating does not depend on arrival order (§3, citing Pitman). The probability of a set of paths is the product, over nodes, of the CRP probabilities of the induced seatings, so it does not depend on the order of the documents either. Re-checked by enumeration: five depth-two paths, with two documents sharing a full path and two sharing only the root’s child, give the same probability, 1.12 × 10⁻³ at γ = 1.3, in all 120 orders.
What could have failed: a path-based prior could have allowed a document to branch, as the multiple-path variant the paper names in §4 would. It does not, and the paper says so.
What this does not say
- Not that the inferred tree is identified. This is a property of the model’s support. Whether the sampler’s tree is the only one the data support is THEORY-1010’s question, and the paper has no theorem.
- Not that a document’s topics are all used. θᵈ may put almost no mass on some levels, so a document’s effective topics may be fewer than its path’s.
- Not that hierarchy in data must be nested. The model imposes the nesting. A corpus whose documents mix sibling themes is still fitted, by assigning each document one path, and the misfit shows only in likelihood.
- Not about the nested HDP. LIT-002’s model (NOTE-023) gives each word its own path and removes the restriction.
Connections
- QUESTION-276, condition 2. If documents are members’ activity, hLDA can express overlapping participation only as shared ancestry, which is a partition at every level. That is the restriction T21 noted, and the reason it turned to the nested HDP.
- CLAIM-454. A path is a position in a hierarchy of word distributions. Whether members on the same path form a perspective is the question the claim says such an allocation leaves open.
- The author–topic model and the mixed membership blockmodel (THEORY-972, THEORY-993) give overlap of another kind: memberships on a simplex, with no nesting.