Blei 2003 - LDA Generative Model and Exchangeability

Summary

Terminology: words (vocabulary items $\mathrm{1..}V$ as unit-basis vectors), documents (sequences of $N$ words), corpora ($M$ documents). LDA draws $\theta \sim \text{Dir}(\alpha )$ per document, a topic $z_n\sim \text{Mult}(\theta )$ per word, then $w_n\sim \text{Mult}({\beta }_{z_n})$. Exchangeability of words and topics within a document plus de Finetti’s theorem motivates the mixture form.

Main Content

Notation. A word is $w$ with $w^v=1$ and $w^u=0$ ($u\ne v$); a document $\mathbf{w}=(w_1,\dots ,w_N)$; a corpus $D=\{{\mathbf{w}}_1,\dots ,{\mathbf{w}}_M\}$. The model is not tied to text (collaborative filtering, image retrieval, bioinformatics).

LDA generative process (Sec. 3)

For each document: (1) $N\sim \text{Poisson}(\xi )$; (2) $\theta \sim \text{Dir}(\alpha )$; (3) for each of $N$ words: $z_n\sim \text{Multinomial}(\theta )$ and $w_n\sim p(w_n\mid z_n,\beta )$, a multinomial with ${\beta }_{ij}=p(w^j=1\mid z^i=1)$ ($\beta$ is $k\times V$). Simplifying assumptions: $k$ fixed and known; $\beta$ a fixed quantity to estimate; the Poisson length is ancillary and ignored.

Dirichlet density (Eq. 1)

$p(\theta \mid \alpha )=\frac{\Gamma ({\sum }_i{\alpha }_i)}{{\prod }_i\Gamma ({\alpha }_i)}{\theta }_1^{{\alpha }_1-1}\cdots {\theta }_k^{{\alpha }_k-1}$ on the $(k-1)$-simplex; exponential family, conjugate to the multinomial.

Joint, document and corpus likelihood (Eqs. 2-3)

$$p(\theta ,\mathbf{z},\mathbf{w}\mid \alpha ,\beta )=p(\theta \mid \alpha )\prod _{n=1}^{N}p(z_n\mid \theta )p(w_n\mid z_n,\beta ),$$ $$p(\mathbf{w}\mid \alpha ,\beta )=\int p(\theta \mid \alpha )(\prod _{n=1}^N\sum _{z_n}p(z_n\mid \theta )p(w_n\mid z_n,\beta ))d\theta ,p(D\mid \alpha ,\beta )=\prod _{d=1}^{M}p({\mathbf{w}}_d\mid \alpha ,\beta ).$$

Three levels: $\alpha ,\beta$ corpus-level (sampled once), ${\theta }_d$ document-level, $z_{dn},w_{dn}$ word-level. This differs from a Dirichlet-multinomial clustering model, which samples the cluster once per document: in LDA the topic node is resampled within the document, so a document can exhibit multiple topics. The structure is a conditionally independent hierarchical model (Kass and Steffey 1989), and $\alpha ,\beta$ are estimated by parametric empirical Bayes in the simple implementation.

Exchangeability and the continuous mixture of unigrams (Secs. 3.1-3.2)

Words and topics are assumed infinitely exchangeable within a document; by de Finetti, $p(\mathbf{w},\mathbf{z})=\int p(\theta ){\prod }_{n}p(z_n\mid \theta )p(w_n\mid z_n)d\theta$. Marginalising $z$: $p(w\mid \theta ,\beta )={\sum }_{z}p(w\mid z,\beta )p(z\mid \theta )$, so LDA is a continuous mixture of unigrams $p(\mathbf{w}\mid \alpha ,\beta )=\int p(\theta \mid \alpha ){\prod }_{n}p(w_n\mid \theta ,\beta )d\theta$, with only $k+kV$ parameters but a multimodal density on the word simplex (Fig. 2).

Examples

Marginalising the topics

Take $k=3,V=6$. For a 5-word document the likelihood given $\theta$ and $\beta$ is ${\prod }_n({\theta }^T\beta {)}_{w_n}$, the product of mixture word probabilities; summing over all $3^5$ topic assignments gives exactly the same number. This is the identity used to “sum out token topics” in gradient-based samplers (see Blei 2003 - LDA Beyond Text Baskets and Sessions).

import numpy as np
rng = np.random.default_rng(0)
K, V, N = 3, 6, 5
phi = rng.dirichlet(np.ones(V) * .5, K); th = rng.dirichlet(np.ones(K) * .5)
w = rng.integers(0, V, N)
explicit = np.prod([sum(th[k] * phi[k, wn] for k in range(K)) for wn in w])
print(explicit, np.prod((th @ phi)[w]))      # equal

Connections

Hierarchical Models for the shared-hyperparameter structure. Compare with DP-based clustering: Teh 2010 - DP Mixture Models and Applications.

See Also

Blei 2003 - Latent Dirichlet Allocation - Overview