intermediate text-mining 35 min read

Topic Models: Latent Dirichlet Allocation

Documents as points in a polytope of topics: when the topics can be recovered, the two classical ways to infer them, and what a topic model finds in filings whose generator plants seven vocabularies but only six identifiable topics.

Part of the Text Mining track · View full curriculum →

Prerequisites: Distributional Semantics: PPMI and Truncated SVD

Overview & Motivation

The distributional semantics topic ended on a matrix. It took the finance corpus’s frequent content nouns, counted which ones share a document, and found that the ratio matrix drops to the level of noise after its fifth singular value, as a mixture of six sector vocabularies predicts. It closed by observing that a topic model would find this structure more easily than an embedding would. This page takes that up.

A topic model treats a document as a bag of words drawn from a few distributions over the vocabulary, its topics, mixed in proportions of its own. Picture the set of all distributions over $V$ words, a simplex with one corner per word. Each topic is a point in it, and so is each document’s word distribution, which is a weighted average of the topic points and so lies inside their convex hull. Fitting a topic model means finding a few corners that hold the documents’ points, and reading each document’s proportions off its position.

That picture organizes the page.

The generative model. Latent Dirichlet allocation, the polytope its documents live in, and fitting a document’s proportions as a projection.
Identifiability and anchor words. When the corners are determined by the documents, and how the corners can be found by convex geometry alone.
Collapsed Gibbs sampling and mean-field variational inference, the two classical ways to fit the model.
Evaluation. Why held-out likelihood is hard to estimate, and how to compare models anyway.

Then the finance case study. The corpus’s generator plants seven vocabularies, one per sector and one shared, and every filing draws about half its content nouns from its sector’s vocabulary and half from the shared one. We will see that only six of the seven can be recovered, and that the obstacles to recovering those six are optimizers rather than the model.

The generative model

Fix a vocabulary of $V$ words and write $\Delta^{V-1}$ for the simplex of distributions over it. A topic is a point $\varphi_k \in \Delta^{V-1}$ , and we stack $K$ of them as the rows of a $K \times V$ matrix $\Phi$ .

Definition 1 (Latent Dirichlet allocation).

Given $\alpha \in \mathbb R_{\gt 0}^K$ and $\beta \gt 0$ , draw each topic $\varphi_k \sim \mathrm{Dir}(\beta \mathbf 1_V)$ . For each document $d$ , draw its topic proportions $\theta_d \sim \mathrm{Dir}(\alpha)$ , and for each position $n = 1, \dots, n_d$ draw a topic $z_{dn} \sim \mathrm{Cat}(\theta_d)$ and then a word $w_{dn} \sim \mathrm{Cat}(\varphi_{z_{dn}})$ . The probabilistic latent semantic indexing model (pLSI) is the same model with $\theta_d$ and $\Phi$ treated as free parameters, with no priors.

The Dirichlet distribution and its moments are covered on formalStatistics (Multivariate Distributions, Theorems 5 and 6). A small $\alpha$ puts most of its mass near the corners of $\Delta^{K-1}$ , so documents concentrate on few topics; a large one puts it near the center.

Definition 2 (Topic polytope).

The topic polytope of $\Phi$ is the convex hull $T(\Phi) = \operatorname{conv}\lbrace \varphi_1, \dots, \varphi_K \rbrace \subseteq \Delta^{V-1}$ .

Proposition 1 (Documents live in the polytope).

Given $\theta_d$ and $\Phi$ , the words of document $d$ are independent and identically distributed with distribution

p_d = \Phi^\top \theta_d \in T(\Phi),

so its count vector $x_d$ satisfies $\mathbb E[x_d \mid \theta_d] = n_d\, p_d$ . Stacking documents, the matrix of their word distributions is $P = \Theta \Phi$ , a product of nonnegative matrices with inner dimension $K$ .

Proof.

Summing out the topic of one position, $P(w_{dn} = w \mid \theta_d) = \sum_k \theta_{dk}\, \varphi_k(w) = (\Phi^\top\theta_d)_w$ . Given $\theta_d$ the pairs $(z_{dn}, w_{dn})$ are independent across positions, so the words are too. Since $\theta_d$ is a probability vector, $p_d$ is a convex combination of the rows of $\Phi$ .

∎

Only the expected distribution $p_d$ lies in the polytope. The observed frequencies $\hat p_d = x_d / n_d$ scatter around it, often outside. In the lab’s Topic simplex tab the vocabulary has three words, so the word simplex is a triangle, and three topics span a smaller triangle inside it. With $\alpha = 1$ and documents of $10$ words, $0.613$ of the documents’ observed frequencies fall outside the topic triangle; at $160$ words, $0.150$ do. At $\alpha = 0.1$ the documents crowd the corners, where a little noise carries them out: $0.662$ are still outside at $160$ words.

How do we place an observed document back in the polytope? By maximum likelihood, and the answer is a projection.

Proposition 2 (Fitting a document's proportions is a KL projection).

Fix $\Phi$ and a document with counts $x$ , length $n$ , and frequencies $\hat p = x/n$ . For every $\theta \in \Delta^{K-1}$ ,

\sum_w x_w \log\, (\Phi^\top\theta)_w = -n \left[ H(\hat p) + \mathrm{KL}\big(\hat p \,\Vert\, \Phi^\top\theta\big) \right],

where $H$ is the entropy. So the maximum-likelihood $\theta$ places $\Phi^\top\theta$ at a point of $T(\Phi)$ nearest to $\hat p$ in KL divergence. If some point of $T(\Phi)$ gives every word of the document positive probability, a nearest point exists, and its probabilities on the document’s words are unique.

Proof.

With $q = \Phi^\top\theta$ , $\sum_w x_w \log q_w = n \sum_w \hat p_w \log \hat p_w - n \sum_w \hat p_w \log(\hat p_w / q_w)$ , which is the identity. Maximizing the left side over $\theta$ therefore minimizes $\mathrm{KL}(\hat p \,\Vert\, q)$ over $q \in T(\Phi)$ , which is nonnegative by Gibbs’ inequality (formalML, KL Divergence, Proposition 2). The function $q \mapsto -\sum_{w : \hat p_w \gt 0} \hat p_w \log q_w$ is continuous where it is finite and tends to $+\infty$ as any $q_w$ with $\hat p_w \gt 0$ tends to $0$ ; on the compact set $T(\Phi)$ , where it is finite somewhere, it attains its minimum. It is strictly convex in the coordinates $(q_w)_{\hat p_w \gt 0}$ , so two minimizers agree on them.

∎

The projection is computed by an EM iteration in which each step raises the likelihood. pLSI fits $\Phi$ too, minimizing the total $\sum_d n_d\, \mathrm{KL}(\hat p_d \,\Vert\, T(\Phi))$ jointly. Hofmann (1999) described the aspect model’s sub-simplex and its KL reading for the joint table of documents and words, and Gaussier and Goutte (2005) showed that pLSI solves non-negative matrix factorization under the generalized KL divergence.

Remark.

LSA’s projection is Euclidean and signed. The distributional semantics topic’s truncated SVD (its Definition 3) projects the rows of a document–word matrix onto a $d$ -dimensional subspace in Euclidean norm. A subspace of dimension $d \ge K$ has room for the polytope, but its coordinates take both signs. On the finance documents’ word frequencies, LSA’s rank- $6$ reconstruction has $0.283$ of its entries negative, which no mixture of distributions can produce. LDA keeps the simplex: a document’s coordinates are proportions.

Identifiability and anchor words

A factorization $P = \Theta\Phi$ is useful only if the documents determine it. They do not, in three ways.

Proposition 3 (The factorization is not unique).

(a) For every permutation matrix $\Pi$ , the topics $\Pi\Phi$ with proportions $\Theta\Pi^\top$ give the same documents, and under a symmetric prior the same posterior density. The posterior therefore has $K!$ symmetric modes. (b) The polytope itself need not be determined. With $V = 3$ , $K = 2$ , $\varphi_1 = (0.6, 0.3, 0.1)$ , $\varphi_2 = (0.1, 0.3, 0.6)$ , and $t = 0.1$ , the stretched topics

\varphi_1' = \varphi_1 + t(\varphi_1 - \varphi_2), \qquad \varphi_2' = \varphi_2 + t(\varphi_2 - \varphi_1)

lie in the simplex, and every document of $(\Phi, \Theta)$ has proportions $\theta' = M^\top\theta \ge 0$ under them, with the same $p_d$ , where $M = \frac{1}{1 + 2t}\begin{pmatrix} 1 + t & t \\ t & 1 + t \end{pmatrix}$ .

Proof.

(a) Relabeling topics is a bijection of the assignments $z$ that preserves the joint density of every quantity in Definition 1 when $\alpha$ is symmetric. (b) Solving the two definitions for $\varphi_1$ and $\varphi_2$ gives $\Phi = M\Phi'$ , so $\Theta\Phi = (\Theta M)\Phi'$ . The rows of $\Theta M$ are nonnegative and sum to one because $M$ is nonnegative with rows summing to one, and $\Phi' \ge 0$ for $t = 0.1$ by direct computation: $\varphi_1' = (0.65, 0.3, 0.05)$ .

∎

Part (a) means that topics are compared only after matching them, which the harness does by the assignment of least total $L^1$ distance. Part (b) means that some condition on $\Phi$ is needed. A third failure is the one the finance corpus has.

Proposition 4 (A topic every document shares at one weight is unidentifiable).

Suppose every document’s proportions put weight $c \in (0, 1)$ on a shared topic $\varphi_0$ and $1 - c$ on one topic $\varphi_{s(d)}$ of its own, $s(d) \in \lbrace 1, \dots, S \rbrace$ . Then each document’s words are i.i.d. from

\psi_s = (1 - c)\,\varphi_s + c\,\varphi_0 ,

the same distribution as a single-membership model, a mixture of unigrams with $S$ topics. For every $c' \in [0, c]$ , the shared topic $\varphi_0$ with weight $c'$ and the own topics $\varphi_s' = (\psi_s - c'\varphi_0)/(1 - c')$ give the same documents, and the topic–topic matrix $R = \mathbb E[\theta\theta^\top]$ , of size $S + 1$ , has rank at most $S$ .

Proof.

By Proposition 1 a document’s words are i.i.d. from $\Phi^\top\theta_d = \psi_{s(d)}$ , which depends on the topics only through the $\psi_s$ . For $c' \le c$ , $\varphi_s' = \big((1 - c)\varphi_s + (c - c')\varphi_0\big)/(1 - c')$ is a probability vector and $(1 - c')\varphi_s' + c'\varphi_0 = \psi_s$ . Every $\theta_d$ is one of the $S$ vectors $v_s = (1 - c)e_s + c\, e_0$ , so $R = \sum_s P(s(d) = s)\, v_s v_s^\top$ is a sum of $S$ rank-one matrices.

∎

The cure for (b) is a condition borrowed from non-negative matrix factorization (Donoho and Stodden 2003).

Definition 3 (Separability and anchor words).

$\Phi$ is separable if every topic $k$ has an anchor word $a_k$ with $\varphi_k(a_k) \gt 0$ and $\varphi_j(a_k) = 0$ for $j \ne k$ .

An anchor word is evidence of its topic and of nothing else. Anchors are found in a matrix the distributional semantics topic already built, the document-level co-occurrence matrix, provided it is estimated without counting a word with itself.

Proposition 5 (The co-occurrence estimator is unbiased).

For a document with $n_d \ge 2$ , let

\hat Q_d = \frac{x_d x_d^\top - \operatorname{diag}(x_d)}{n_d(n_d - 1)} .

Then $\mathbb E[\hat Q_d \mid \theta_d] = \Phi^\top\theta_d\theta_d^\top\Phi$ , and averaged over documents, $\mathbb E[\hat Q] = \Phi^\top R\, \Phi$ with $R = \mathbb E[\theta\theta^\top]$ .

Proof.

$x_d x_d^\top - \operatorname{diag}(x_d) = \sum_{i \ne j} e_{w_{di}} e_{w_{dj}}^\top$ counts the $n_d(n_d - 1)$ ordered pairs of distinct positions. Given $\theta_d$ the words at two distinct positions are independent with distribution $p_d$ (Proposition 1), so each pair has expectation $p_d p_d^\top = \Phi^\top\theta_d\theta_d^\top\Phi$ . Averaging over $\theta_d$ gives $\Phi^\top R\,\Phi$ .

∎

So $Q = \Phi^\top R\,\Phi$ is the joint distribution of the words at two distinct positions of a random document. Let $p = Q\mathbf 1$ be its word marginal and $\bar Q = \operatorname{diag}(p)^{-1} Q$ , whose row $\bar Q_w$ is the distribution of the second word given that the first is $w$ .

Theorem 1 (Anchor rows are the vertices).

Let $\Phi$ be separable with anchors $a_1, \dots, a_K$ , and let $\pi = R\mathbf 1$ be the topics’ marginal probabilities. For every word with $p(w) \gt 0$ ,

\bar Q_w = \sum_k C_{wk}\, \bar Q_{a_k}, \qquad C_{wk} = P(z_1 = k \mid w_1 = w) = \frac{\varphi_k(w)\, \pi_k}{p(w)} ,

so every row of $\bar Q$ lies in $\operatorname{conv}\lbrace \bar Q_{a_1}, \dots, \bar Q_{a_K} \rbrace$ . If $R$ is nonsingular, the anchor rows are affinely independent, they are the vertices of the convex hull of all rows, a word’s row is a vertex only if the word is an anchor, and $\Phi$ is recovered from $C$ and $p$ :

\varphi_k(w) = \frac{C_{wk}\, p(w)}{\sum_{u} C_{uk}\, p(u)} .

Proof.

Let $z_1$ be the topic of the first position. Given $z_1$ , the first word is independent of $\theta$ , so $p(\theta \mid z_1, w_1) = p(\theta \mid z_1)$ and the second word is independent of the first given $z_1$ . Hence

\bar Q_w = \sum_k P(z_1 = k \mid w_1 = w)\; g_k, \qquad g_k = P(w_2 = \cdot \mid z_1 = k),

and Bayes’ rule gives $C_{wk} = \varphi_k(w)\pi_k / p(w)$ . For an anchor, $C_{a_k k} = 1$ , so $\bar Q_{a_k} = g_k$ . This proves the first claim, since each row $C_w$ is a probability vector.

Now $g_k = \sum_j P(z_2 = j \mid z_1 = k)\, \varphi_j$ , that is, $g = \bar R \Phi$ with $\bar R = \operatorname{diag}(\pi)^{-1} R$ . If $R$ is nonsingular then $\pi \gt 0$ and $\bar R$ is nonsingular. Separability makes the rows of $\Phi$ linearly independent, since its anchor columns form a diagonal matrix with positive diagonal. If $\sum_k \lambda_k g_k = 0$ , then $\lambda^\top \bar R \Phi = 0$ , so $\lambda^\top \bar R = 0$ and $\lambda = 0$ . The $g_k$ are therefore linearly, hence affinely, independent, and their hull is a simplex with vertices $g_k$ . Barycentric coordinates in a simplex are unique, so $\bar Q_w = g_k$ forces $C_w = e_k$ , which means $\varphi_j(w) = 0$ for $j \ne k$ : $w$ is an anchor of $k$ . Finally $\sum_u C_{uk}\, p(u) = \pi_k$ , so the last display is $C_{wk}p(w)/\pi_k = \varphi_k(w)$ .

∎

Arora, Ge, and Moitra (2012) introduced anchor words and proved polynomial-time recovery from finitely many documents (their Theorem 1.4) under a lower bound on the $\ell_1$ condition number of $R$ , which implies nonsingularity. Arora et al. (2013, Section 3) gave the convex-combination form above. Theorem 1 is the exact, population-level core of those results, and nonsingularity is not a technicality. In Proposition 4’s world, the shared topic’s anchor row lies in the hull of the others: in the harness’s four-topic example its linear-programming distance to that hull is $0$ , and the anchor search below picks a non-anchor in its place.

Algorithm 1 (Anchor finding and recovery).

Estimate $\hat Q$ by Proposition 5 and normalize its rows to $\bar Q$ .
FastAnchorWords. Among candidate words that appear in at least $5\%$ of the documents, take the row of $\bar Q$ farthest from the origin; then, $K - 1$ times, take the row farthest from the affine span of the rows chosen so far (Gram–Schmidt on differences).
RecoverL2. For every word, find the probability vector $C_w$ minimizing $\lVert \bar Q_w - C_w^\top \bar Q_S \rVert^2$ , where $\bar Q_S$ holds the anchor rows.
Set $\varphi_k(w) \propto C_{wk}\, \hat p(w)$ , as in Theorem 1.

FastAnchorWords is Arora et al.’s Algorithm 4, and RecoverL2 is defined in their Section 3. The candidate threshold matters: with a fixed minimum count, rare words, whose sampled rows are mostly noise, win the farthest-point search. The lab’s Anchors tab draws the rows of a three-topic world in the anchors’ triangle, where Theorem 1 puts the population rows exactly, and the sampled rows scatter and tighten as the corpus grows. In a separable world of $400$ words and $5$ topics, the mean $L^1$ error per topic falls from $0.542$ at $250$ documents to $0.065$ at $16{,}000$ , and the planted anchors are found from $4{,}000$ documents on. Without anchors the error stops at $0.190$ , above the population floor of $0.169$ that no amount of data removes. (The topics there are dense, $\mathrm{Dir}(\mathbf 1)$ off the anchors. Sparse topics are already nearly separable: their frequent words carry almost all their mass in one topic, and the contrast disappears.)

Collapsed Gibbs sampling

The posterior $p(z, \theta, \Phi \mid w)$ has no closed form, but conjugacy lets us integrate out everything except the assignments.

Lemma 1 (The Dirichlet–multinomial marginal).

For $\theta \sim \mathrm{Dir}(a)$ and counts $n \in \mathbb N^K$ ,

\mathbb E\Big[ \prod_k \theta_k^{n_k} \Big] = \frac{B(a + n)}{B(a)}, \qquad B(a) = \frac{\prod_k \Gamma(a_k)}{\Gamma\big(\sum_k a_k\big)} .

Proof.

The integrand $\prod_k \theta_k^{n_k} \cdot \prod_k \theta_k^{a_k - 1}/B(a)$ is $B(a + n)/B(a)$ times the $\mathrm{Dir}(a + n)$ density, which integrates to one. This is the normalizing-constant step of the conjugacy in formalStatistics, Multivariate Distributions, Theorem 6.

∎

Write $n_{dk}$ for the number of tokens of document $d$ assigned to topic $k$ , $n_{kw}$ for the number of tokens of word $w$ assigned to $k$ , and $n_k = \sum_w n_{kw}$ . Applying Lemma 1 to every document and every topic,

p(w, z) = \prod_d \frac{B(\alpha + n_{d\cdot})}{B(\alpha)} \prod_k \frac{B(\beta\mathbf 1 + n_{k\cdot})}{B(\beta\mathbf 1)} .

Theorem 2 (The collapsed full conditional).

For token $i$ of document $d$ , with word $w$ , and with every count computed without token $i$ (marked $^{-i}$ ),

P(z_i = k \mid z_{-i}, w) \;\propto\; \big(n_{dk}^{-i} + \alpha_k\big)\, \frac{n_{kw}^{-i} + \beta}{n_k^{-i} + V\beta} .

Proof.

Setting $z_i = k$ changes only two counts, each by one: the count of topic $k$ in document $d$ , and the count of word $w$ in topic $k$ . Every other factor of $p(w, z)$ is the same for all $k$ , so $P(z_i = k \mid z_{-i}, w)$ is proportional to

\frac{B(\alpha + n_{d\cdot}^{-i} + e_k)}{B(\alpha + n_{d\cdot}^{-i})} \cdot \frac{B(\beta\mathbf 1 + n_{k\cdot}^{-i} + e_w)}{B(\beta\mathbf 1 + n_{k\cdot}^{-i})} .

For any $a$ , $B(a + e_k)/B(a) = a_k / \sum_j a_j$ , by $\Gamma(x + 1) = x\Gamma(x)$ applied in the numerator and in the denominator. The first ratio is $(n_{dk}^{-i} + \alpha_k)/(n_d - 1 + \sum_j\alpha_j)$ , whose denominator does not depend on $k$ ; the second is $(n_{kw}^{-i} + \beta)/(n_k^{-i} + V\beta)$ .

∎

Griffiths and Steyvers (2004, Eq. 5) wrote the conditional with the document’s denominator $n_d - 1 + K\alpha$ , which we drop as a constant.

Algorithm 2 (Collapsed Gibbs sampling).

Assign every token a topic uniformly at random and tabulate the counts. Then sweep: for each token in turn, remove it from the counts, draw its new topic from Theorem 2’s conditional, and add it back. After the sweeps, estimate the topics and proportions by Proposition 6.

Corollary 1 (The posterior is the sampler's limit).

Each step of Algorithm 2 leaves $p(z \mid w)$ invariant. If $\alpha, \beta \gt 0$ , one sweep can move from any assignment to any other with positive probability, so the chain is irreducible and aperiodic on its finite state space, and the distribution of $z$ after $t$ sweeps converges to $p(z \mid w)$ .

Proof.

A step that redraws one coordinate from its exact conditional is a Metropolis–Hastings step that always accepts, so it leaves the target invariant (formalStatistics, Bayesian Computation and MCMC, Theorem 2), and so does a composition of such steps. Every factor of Theorem 2’s conditional is positive, so each step can set its token to any topic, and a sweep can reach any assignment in one pass. A finite chain whose transition matrix is entrywise positive converges to its unique invariant distribution (ibid., Theorem 5).

∎

The harness checks Corollary 1 exactly on a corpus of two documents and seven tokens, small enough to enumerate all $2^7 = 128$ assignments. The product of the seven single-token kernels is entrywise positive, and its invariant vector equals the enumerated posterior to $10^{-12}$ ; the sampler itself, run for $40{,}000$ sweeps, matches every token’s posterior marginal to $0.01$ .

Proposition 6 (Point estimates from one sample).

Given an assignment $z$ ,

\mathbb E[\varphi_k(w) \mid z, w] = \frac{n_{kw} + \beta}{n_k + V\beta}, \qquad \mathbb E[\theta_{dk} \mid z] = \frac{n_{dk} + \alpha_k}{n_d + \sum_j\alpha_j} .

Proof.

Given $z$ and $w$ , the topic $\varphi_k$ is $\mathrm{Dir}(\beta\mathbf 1 + n_{k\cdot})$ and $\theta_d$ is $\mathrm{Dir}(\alpha + n_{d\cdot})$ , by conjugacy; these are their means.

∎

These are the Dirichlet-smoothed estimates of formalRAG’s query-likelihood topic (its Theorem 1). Averaging them over the sweeps of one run is safe; averaging across runs is not, because of Proposition 3(a).

Mean-field variational inference

The other classical engine replaces the posterior with the closest member of a factorized family and climbs a lower bound on $\log p(w)$ , the ELBO (formalML, Variational Inference, Definition 1). Its updates need one expectation.

Lemma 2 (The Dirichlet log-moment).

If $\theta \sim \mathrm{Dir}(\gamma)$ , then $\mathbb E[\log\theta_k] = \psi(\gamma_k) - \psi\big(\sum_j\gamma_j\big)$ , where $\psi = \Gamma'/\Gamma$ is the digamma function.

Proof.

$B(\gamma) = \int_{\Delta^{K-1}} \prod_j \theta_j^{\gamma_j - 1}\, d\theta$ . Differentiating under the integral in $\gamma_k$ , which dominated convergence permits on a neighborhood of $\gamma$ where $\gamma_k \gt 0$ , gives $\partial_k B(\gamma) = \int \log\theta_k \prod_j \theta_j^{\gamma_j - 1}\, d\theta$ , so

\mathbb E[\log\theta_k] = \partial_k \log B(\gamma) = \psi(\gamma_k) - \psi\Big(\sum_j\gamma_j\Big).

This is the Dirichlet case, with sufficient statistic $\log\theta$ , of the identity formalStatistics proves for one-parameter families (Exponential Families, Theorem 1), and Blei, Ng, and Jordan (2003, Appendix A.1) derive it the same way.

∎

Theorem 3 (Coordinate ascent for LDA).

Under the mean-field family in which the topics, each document’s proportions, and each token’s topic are independent,

q = \prod_k \mathrm{Dir}(\varphi_k; \lambda_k) \prod_d \Big[ \mathrm{Dir}(\theta_d; \gamma_d) \prod_n \mathrm{Cat}(z_{dn}; r_{dn}) \Big],

the ELBO’s optimal coordinate updates are

r_{dnk} \propto \exp\big( \mathbb E_q\log\theta_{dk} + \mathbb E_q\log\varphi_k(w_{dn}) \big), \qquad \gamma_d = \alpha + \sum_n r_{dn},

\lambda_{kw} = \beta + \sum_{d, n} r_{dnk}\, \mathbf 1[w_{dn} = w],

with both expectations given by Lemma 2.

Proof.

formalML’s Theorem 2 says the optimal factor for one block is proportional to the exponential of the expected log of that block’s complete conditional. Given everything else, $\log p(z_{dn} = k \mid \cdot) = \log\theta_{dk} + \log\varphi_k(w_{dn}) + \text{const}$ , which gives $r$ . The complete conditional of $\theta_d$ is $\mathrm{Dir}(\alpha + \sum_n e_{z_{dn}})$ and that of $\varphi_k$ is $\mathrm{Dir}(\beta\mathbf 1 + \sum_{d,n} \mathbf 1[z_{dn} = k]\, e_{w_{dn}})$ , both conjugate, so by formalML’s Proposition 1 the optimal factors are Dirichlet with the expected natural parameters, which are $\gamma_d$ and $\lambda_k$ .

∎

These are Blei, Ng, and Jordan’s Eqs. 6–8, derived in their Appendix A.3, with the Dirichlet prior on the topics of their smoothed model (Section 5.4).

Corollary 2 (The ELBO never decreases).

Each update of Theorem 3 maximizes the ELBO over its block, so alternating them never lowers it, and since the ELBO is bounded above by $\log p(w)$ , its values converge.

Proof.

Each update is the exact maximizer in its block (formalML, Theorem 2), so the ELBO after it is at least the ELBO before it; a monotone sequence bounded above converges.

∎

The harness records the ELBO after every update of every run and checks that it never falls, and checks our closed form for the bound against scikit-learn’s to $10^{-8}$ relative. Corollary 2 promises convergence of the ELBO’s values, not to the best optimum, and the finance case study shows how far apart those can be.

Remark.

CVB0. Replacing Theorem 2’s counts with their expectations under $q$ turns the sampler’s conditional into a deterministic update, CVB0 (Asuncion et al. 2009, Eq. 13; Teh, Newman, and Welling 2006 for the collapsed bound). Asuncion et al. found that the main differences between inference algorithms are attributable to the amount of smoothing, and largely vanish once the hyperparameters are tuned.

The lab’s Gibbs vs. VI tab shows their point on one world. With the topic prior the world was drawn from, $\beta = 1$ , collapsed Gibbs recovers the topics best, at mean $L^1$ error $0.293$ against $0.452$ for coordinate ascent and $0.439$ for the anchors. With a sparse, misspecified $\beta = 0.01$ the order reverses: $0.787$ for Gibbs and $0.461$ for coordinate ascent.

Evaluating a topic model

The natural score is the probability of held-out documents, but $p(w) = \sum_z p(w, z)$ sums over $K^N$ assignments.

Definition 4 (Held-out likelihood and document completion).

The held-out log-likelihood per token of documents $w$ is $\frac{1}{N} \log p(w \mid \hat\Phi, \alpha)$ , where $N$ is their number of tokens. Plug-in document completion splits each held-out document into its even and odd positions, estimates $\hat\theta_d$ from the even positions with $\hat\Phi$ fixed, and scores the odd positions by their mean of $\log \sum_k \hat\theta_{dk}\, \hat\varphi_k(w)$ .

Completion needs no marginal likelihood, and it scores a single-membership model by the same rule, with $\hat\theta_d$ its posterior over clusters. Estimating $p(w)$ itself is a trap.

Theorem 4 (The harmonic-mean estimator).

Let $z^{(1)}, \dots, z^{(S)}$ be draws from $p(z \mid w)$ and $\hat p_{\mathrm{HM}} = \big( \frac1S \sum_s 1/p(w \mid z^{(s)}) \big)^{-1}$ .

(a) $\mathbb E_{p(z \mid w)}\big[ 1/p(w \mid z) \big] = 1/p(w)$ , so $\hat p_{\mathrm{HM}}$ is consistent.

(b) $\mathbb E[\hat p_{\mathrm{HM}}] \ge p(w)$ : it overestimates in expectation.

(c) With $\Phi$ fixed and the proportions $\theta$ continuous, the variance of $1/p(w \mid \theta)$ under $p(\theta \mid w)$ is finite if and only if $\int p(\theta)/p(w \mid \theta)\, d\theta \lt \infty$ . If $\Phi$ is separable and the document holds $c \ge \alpha_k$ tokens of anchor words of topic $k$ , the integral diverges and the variance is infinite.

Proof.

(a) $\sum_z p(z \mid w)/p(w \mid z) = \sum_z p(z)/p(w) = 1/p(w)$ , and the average of the $1/p(w \mid z^{(s)})$ converges to it. (b) $x \mapsto 1/x$ is convex, so by Jensen’s inequality $\mathbb E[\hat p_{\mathrm{HM}}] \ge 1/\mathbb E[\frac1S\sum_s 1/p(w \mid z^{(s)})] = p(w)$ . (c) The second moment is

\int \frac{p(\theta \mid w)}{p(w \mid \theta)^2}\, d\theta = \frac{1}{p(w)} \int \frac{p(\theta)}{p(w \mid \theta)}\, d\theta .

Every factor of $p(w \mid \theta) = \prod_n (\Phi^\top\theta)_{w_n}$ is at most one, and an anchor token of topic $k$ contributes $(\Phi^\top\theta)_{a} = \theta_k\, \varphi_k(a)$ . So $p(w \mid \theta) \le C\, \theta_k^{\,c}$ for a constant $C$ , and the integral is at least $C^{-1}\, \mathbb E[\theta_k^{-c}]$ , where $\theta_k \sim \mathrm{Beta}(\alpha_k, \alpha_0 - \alpha_k)$ with $\alpha_0 = \sum_j \alpha_j$ . That expectation is $\int_0^1 t^{\alpha_k - c - 1}(1 - t)^{\alpha_0 - \alpha_k - 1}\, dt / B(\alpha_k, \alpha_0 - \alpha_k)$ , which diverges at $0$ when $c \ge \alpha_k$ .

∎

With the common choice $\alpha_k = 0.1$ , a single anchor token makes the variance infinite. Newton and Raftery (1994) proposed the estimator, Neal (2008) called it the worst Monte Carlo method ever because its infinite variance can hide behind a small sample variance, and Wallach et al. (2009, Section 6.2) found that it wildly overestimated topic models’ held-out likelihood. The harness checks (a) exactly on the seven-token corpus ( $\log p(w) = -9.015$ ), (b) by $4{,}000$ replicates of $20$ exact posterior draws, and (c) on a one-anchor document, whose tail integral over $[\varepsilon, 1]$ grows tenfold each time $\varepsilon$ shrinks a hundredfold, like $\varepsilon^{-1/2}$ .

Proposition 7 (Importance sampling from the prior is unbiased).

For draws $z^{(s)} \sim p(z)$ , the average $\frac1S \sum_s p(w \mid z^{(s)})$ is an unbiased estimator of $p(w)$ with finite variance, and its logarithm underestimates $\log p(w)$ in expectation.

Proof.

$\mathbb E_{p(z)}[p(w \mid z)] = \sum_z p(z)\, p(w \mid z) = p(w)$ , and $p(w \mid z) \le 1$ bounds the variance. Jensen’s inequality for the concave logarithm gives the last claim.

∎

Unbiased is not the same as useful. On one-document corpora of $4$ , $8$ , and $12$ tokens, a prior draw’s relative variance is $0.387$ , $3.033$ , and $17.424$ , growing quickly with length (measured, not proved), while the harmonic mean’s is $0.250$ , $0.613$ , and $1.015$ . On a finite collapsed state space the harmonic mean’s variance is finite, and smaller; its defects are the bias of (b) and, with continuous proportions, the infinite variance of (c). Wallach et al. recommend Chib-style and left-to-right estimators (their Algorithms 2 and 3); we compare models by document completion instead.

Definition 5 (Topic coherence).

For a topic’s top words $v_1, \dots, v_M$ and document frequencies $D(\cdot)$ , the UMass coherence is

\sum_{m = 2}^{M} \sum_{l = 1}^{m - 1} \log \frac{D(v_m, v_l) + 1}{D(v_l)} ,

and the NPMI coherence is the mean over pairs of $\log\frac{P(v, v')}{P(v)P(v')} \big/ \big(-\log P(v, v')\big)$ , with document-level probabilities.

UMass coherence is Mimno et al.’s (2011) Eq. 1, and the PMI form is Newman et al.’s (2010), here normalized to $[-1, 1]$ ; unnormalized, it is the distributional semantics topic’s PMI (its Definition 2) between words. Coherence asks whether a topic’s words occur together, which held-out likelihood does not: Chang et al. (2009) found models with better held-out likelihood whose topics people found less meaningful.

Finance case study

§ Finance case study: seven planted vocabularies, six identifiable topics

The training text is the corpus of the distributional semantics topic, generate_corpus(300, 0), rebuilt from its own generator so that the vocabulary every content noun was drawn from is visible, and run on for $100$ more documents that continue the same vocabularies, which we hold out. The generator seats content nouns in Pitman–Yor restaurants, six for the sectors and one shared, and draws each noun from the document’s sector restaurant with probability $\frac12$ and from the shared one otherwise. We keep the $2{,}908$ words seated in exactly one restaurant: $13{,}382$ tokens in the training documents and $3{,}735$ in the held-out ones. Industrials covers $142$ of the $300$ training documents, technology $52$ , banking $40$ , retail $27$ , energy $20$ , and healthcare $19$ . All models use $\alpha = \beta = 0.1$ .

Seven restaurants, six topics. Every document is Proposition 4’s mixture with $c = \frac12$ : the median share of a document’s tokens from the shared restaurant is $0.489$ . The identifiable truth is therefore six topics $\psi_s$ , each the word distribution of one sector’s documents, and the harness scores every model against them. The anchor search agrees. Asked for six anchors, FastAnchorWords returns one per sector: outlevy (industrials), power (energy), merchandise (retail), cloud (technology), royaltyside (banking), and patients (healthcare). Asked for seven, its seventh pick is freight, a second industrials word, and never a word of the shared vocabulary, as Theorem 1 leads us to expect when $R$ is singular. The pseudo-words are the generator’s: past its seed nouns, each restaurant invents new ones.

The engines. With $K = 6$ and three seeds each, mean $L^1$ error against the six $\psi_s$ , plug-in completion on the held-out documents in nats per token, and the normalized mutual information between each document’s dominant topic and its sector:

method	$L^1$	completion	NMI
collapsed Gibbs	$0.548$	$-5.794$	$0.967$
coordinate ascent from noise	$1.033$	$-6.185$	$0.186$
coordinate ascent from Gibbs’s counts	$0.576$	$-5.840$	$0.963$
anchors (Algorithm 1)	$0.590$
mixture of unigrams, best of 20 starts	$0.985$	$-6.157$	$0.270$
mixture of unigrams from the sectors	$0.279$	$-5.734$	$1.000$

The obstacle is the optimizer, not the model. Collapsed Gibbs finds the sectors on every seed, with NMI from $0.944$ to $1.000$ . Coordinate ascent started from scikit-learn’s Gamma noise does not, and it is not because its bound prefers another answer. Started from Gibbs’s topic counts, the same updates reach an ELBO averaging $-88{,}822$ , while from noise they stop at $-93{,}556$ , about $4{,}700$ nats lower. scikit-learn’s own fit stops in between, at $-90{,}353$ and NMI $0.652$ . The single-membership model, a mixture of unigrams, tells the same story more sharply. By Proposition 4 it is the correctly specified model here, and started at the gold sectors its EM keeps them and scores the best completion of all, $-5.734$ . From $20$ random starts, the best run reaches a training log-likelihood of $-80{,}675$ , against $-77{,}168$ for the run started at the sectors. Both deterministic coordinate-ascent methods stall at optima their own objectives rank far below the sectors, and the stochastic sampler escapes.

Anchors need no optimizer. Algorithm 1, one co-occurrence matrix and one convex fit, recovers the six topics to $0.590$ , close to the sampler’s $0.548$ .

What the templates do. The analysis above keeps only the planted content nouns. Run on every word, a six-topic model gives one topic to the function words and keys the rest on company names, which carry the sector: NMI $0.943$ with the sector, $0.012$ with the document type (earnings call, MD&A, or 8-K), and $0.011$ with the tone. Restricted to words in $3$ to $90$ of the $300$ documents, $0.709$ , $0.023$ , and $0.015$ . Tone and document type are carried by templates every document shares, and a topic model, which sees only which words occur together, never finds them.

The capstone’s stage. topic_mixtures folds any filing’s content nouns into the headline Gibbs fit, whose topics are matched to the sectors, and returns its six proportions. On the $100$ held-out documents its dominant topic is the document’s sector $0.930$ of the time. On a fresh generator run its pseudo-words carry this run’s sectors, so the capstone folds in only the 80 seeded nouns.

Documents live in the topic triangle only in expectation

prior α

words per document n_d

show

topics φ_k and their triangleexpected p_d = Φᵀθ_dobserved frequencies p̂_dKL projection onto the triangle

observed documents outside the topic triangle

0.613

80 documents per setting; the same θ_d at every length, so only the sampling noise changes. Small α piles documents at the topics; short documents scatter their observed frequencies outside, and Proposition 2 maps each back to the nearest point in KL divergence.

Where this sits

The distributional semantics topic found the corpus’s sectors in the spectrum of a co-occurrence matrix. This page found them as the corners of a polytope. Documents live in the polytope of their topics (Proposition 1), and fitting a document’s proportions is a KL projection onto it (Proposition 2). The corners are determined only up to relabeling, not at all in general, and not for a topic every document shares at one weight (Propositions 3 and 4). Under separability, and with a nonsingular topic–topic matrix, the anchor words are the corners of the co-occurrence rows and give the topics by convex geometry (Theorem 1). Conjugacy collapses the posterior to one conditional in three counts (Theorem 2), and the digamma identity gives the mean-field updates (Theorem 3). The harmonic-mean estimator is the wrong way to compare the results (Theorem 4).

The capstone imports topic_mixtures as its topic stage, beside the Loughran–McDonald lexicon for tone and the knowledge-graph embeddings for the facts. Its topics are sectors, which every filing already declares; on real filings, without a planted answer, the structure a topic model finds is harder to name.

Honest caveats

⚠ Rigor flag

Proved and checked. Lemmas 1–2, Theorems 1–4, Corollaries 1–2, and Propositions 1–7 are proved here in full; the KL-NMF equivalence after Proposition 2 and the finite-sample rates of anchor recovery are cited. The harness checks Theorem 1, Propositions 3–5, and Corollary 1 exactly; Theorem 2 against ratios of the enumerated joint; Lemma 2 by quadrature and central differences; Theorem 3 against scikit-learn; Corollary 2 on every update of a run; and Theorem 4 by enumeration, simulation, and quadrature.
One planted vocabulary is unrecoverable. The generator’s shared restaurant enters every document at weight one half, so the topic–topic matrix is singular and Theorem 1’s hypothesis fails. No amount of data recovers seven topics, and the page scores six.
Optimizers, not models. Coordinate ascent and EM stop at local optima that their own objectives rank far below the sectors. The ranking of engines also moves with the topic prior. The comparisons measure fitted runs at one setting, with three seeds.
Estimated likelihoods. Held-out likelihood can only be estimated. We compare by plug-in document completion, which scores an estimate of $\theta$ rather than integrating over it.
Interpretability is not likelihood. Chang et al. (2009) found the two can disagree. On the finance corpus the topics are sectors; on real filings there is no planted answer to check them against.

Implementation

The companion notebook (notebookPath) imports the topic’s Python module, which owns every number on this page. It imports the distributional semantics topic’s module for the corpus’s generator and the linear text classifiers’ module for its rounding, and through them the finance corpus. The collapsed sampler is pure Python, a few hundredths of a second per sweep over the corpus’s $63{,}000$ tokens; coordinate ascent is NumPy, with every document’s E-step done at once on scikit-learn’s schedule. Its harness checks:

Theorem 2 and Corollary 1 by enumerating every assignment of a seven-token corpus, and the sampler against that posterior;
Theorem 1 at the population level, with and without a singular topic–topic matrix, and Algorithm 1 on sampled corpora;
Lemma 2, Theorem 3, and Corollary 2 against quadrature, scikit-learn, and every update of a run;
Theorem 4 and Proposition 7 exactly and by simulation, and every comparison this page states.

The laboratory reads its data from a JSON file that one of the harness’s tests requires to equal the module’s viz_payload() exactly, so the figure cannot drift from the code.

Connections

Document completion scores held-out tokens by their mean log-probability, the negative of that topic's cross-entropy, so −5.794 nats per token is a perplexity of about 328 over the content-noun vocabulary. perplexity-cross-entropy
The mixture of unigrams is that topic's multinomial naive Bayes with the class unobserved; started at the gold sectors, its EM keeps the supervised solution, and from random starts it stalls far below it. linear-text-classifiers
The finance corpus seats its content nouns in Pitman–Yor restaurants, the process that topic connects to Kneser–Ney; Proposition 6's point estimates are the same add-beta Dirichlet posterior means as its additive smoothing. n-gram-models-smoothing

References & Further Reading

paper Latent Dirichlet Allocation — David M. Blei, Andrew Y. Ng, and Michael I. Jordan (2003) Journal of Machine Learning Research 3: 993–1022. Section 4.3: pLSI; Section 4.4 and Figure 4: the topic simplex embedded in the word simplex; Section 5.2, Eqs. 6–8: the variational updates, derived in Appendix A.3; Appendix A.1: E[log θ_i] = Ψ(α_i) − Ψ(Σα_j) (an unnumbered display); Section 5.4 and Figure 7: smoothed LDA, with a Dirichlet prior on the topics
paper Finding Scientific Topics — Thomas L. Griffiths and Mark Steyvers (2004) Proceedings of the National Academy of Sciences 101, suppl. 1: 5228–35. Eq. 5: the collapsed full conditional, written with the document-length denominator that Theorem 2 drops as a constant
paper Probabilistic Latent Semantic Analysis — Thomas Hofmann (1999) Proceedings of UAI 1999, 289–96. Section 3.3 and Figure 2: the aspect model's sub-simplex, and maximum likelihood as minimizing the KL divergence from the empirical distribution
paper Probabilistic Latent Semantic Indexing — Thomas Hofmann (1999) Proceedings of SIGIR 1999, 50–57 (cited from its metadata)
paper Learning Topic Models—Going beyond SVD — Sanjeev Arora, Rong Ge, and Ankur Moitra (2012) Proceedings of FOCS 2012, 1–10 (full version arXiv 1204.1956). Definition 1.1: p-separable topic matrices (anchor words are introduced in Section 1's prose); Definition 1.3: the topic–topic matrix R; Theorem 1.4: polynomial-time recovery under a lower bound on R's ℓ1 condition number (Definition 2.1)
paper A Practical Algorithm for Topic Modeling with Provable Guarantees — Sanjeev Arora, Rong Ge, Yoni Halpern, David Mimno, Ankur Moitra, David Sontag, Yichen Wu, and Michael Zhu (2013) Proceedings of ICML 2013, PMLR 28 (2): 280–88. Section 3, Eqs. 1–2 and the text after them: the rows of the normalized co-occurrence matrix as convex combinations of the anchor rows with coefficients p(z = k | w); Algorithm 4: FastAnchorWords; RecoverL2 is defined in Section 3's prose; Appendix D.1 of the full version (arXiv 1212.4777): the unbiased per-document co-occurrence estimator
paper When Does Non-Negative Matrix Factorization Give a Correct Decomposition into Parts? — David Donoho and Victoria Stodden (2003) Advances in Neural Information Processing Systems 16. Section 5: the separability condition [R2] (Eq. 5) and Theorem 1, uniqueness of the factorization
paper Relation between PLSA and NMF and Implications — Eric Gaussier and Cyril Goutte (2005) Proceedings of SIGIR 2005, 601–2. PLSA solves non-negative matrix factorization under the generalized KL divergence (cited from its metadata; the publisher's page refused our request)
paper Evaluation Methods for Topic Models — Hanna M. Wallach, Iain Murray, Ruslan Salakhutdinov, and David Mimno (2009) Proceedings of ICML 2009, 1105–12. Section 4.2, Eq. 14: the harmonic mean method; Section 6.2: it wildly overestimated held-out likelihood; Algorithm 2: the Chib-style estimator; Algorithm 3: left-to-right evaluation
paper Approximate Bayesian Inference with the Weighted Likelihood Bootstrap — Michael A. Newton and Adrian E. Raftery (1994) Journal of the Royal Statistical Society, Series B 56 (1): 3–26. The harmonic-mean estimator of the marginal likelihood (Section 7, by Neal's discussion; the article itself is behind a paywall)
blog The Harmonic Mean of the Likelihood: Worst Monte Carlo Method Ever — Radford M. Neal (2008) The estimator's infinite variance, which may go undetected because the sample variance stays small
paper Reading Tea Leaves: How Humans Interpret Topic Models — Jonathan Chang, Jordan Boyd-Graber, Sean Gerrish, Chong Wang, and David M. Blei (2009) Advances in Neural Information Processing Systems 22. Models that score better on held-out likelihood can infer less semantically meaningful topics (word and topic intrusion)
paper Optimizing Semantic Coherence in Topic Models — David Mimno, Hanna M. Wallach, Edmund Talley, Miriam Leenders, and Andrew McCallum (2011) Proceedings of EMNLP 2011, 262–72. Section 4.2, Eq. 1: the coherence score from document co-occurrence counts
paper Automatic Evaluation of Topic Coherence — David Newman, Jey Han Lau, Karl Grieser, and Timothy Baldwin (2010) Proceedings of NAACL-HLT 2010, 100–108. PMI between a topic's top words, from co-occurrence in an external corpus
paper Rethinking LDA: Why Priors Matter — Hanna M. Wallach, David Mimno, and Andrew McCallum (2009) Advances in Neural Information Processing Systems 22. An asymmetric prior on the documents' proportions helps; an asymmetric prior on the topics does not
paper A Collapsed Variational Bayesian Inference Algorithm for Latent Dirichlet Allocation — Yee Whye Teh, David Newman, and Max Welling (2006) Advances in Neural Information Processing Systems 19 (MIT Press, 2007)
paper On Smoothing and Inference for Topic Models — Arthur Asuncion, Max Welling, Padhraic Smyth, and Yee Whye Teh (2009) Proceedings of UAI 2009, 27–34. Eq. 13: the CVB0 update, the collapsed sampler's conditional applied to expected counts; the main differences between inference algorithms are attributable to the amount of smoothing
paper The Structure of Economic News — Leland Bybee, Bryan Kelly, Asaf Manela, and Dacheng Xiu (2020) NBER Working Paper 26648. LDA fitted to the Wall Street Journal; published as 'Business News and Business Cycles,' Journal of Finance 79 (5): 3105–47 (2024), doi 10.1111/jofi.13377