Latent Dirichlet Allocation

Finding short descriptions of the members of a collection (e.g. documents in a corpus) that enable efficient processing while preserving the statistical relationships useful for classification, novelty detection, summarization and similarity judgments.

tf-idf reduces documents to fixed-length vectors but compresses little and reveals little inter- or intra-document structure. LSI (an SVD of the term-document matrix) compresses well, but it is not a generative probabilistic model, so it’s unclear why to use it rather than fitting a model directly.

It has no generative model at the document level: each training document’s topic mixture is a list of free parameters. So (1) the number of parameters grows linearly with the corpus (\(kV + kM\)), causing overfitting, and (2) there is no natural way to assign probability to a document outside the training set.

Random variables are exchangeable if their joint distribution is invariant to permutation; the bag-of-words assumption is exchangeability of words (and of documents in a corpus). De Finetti: an infinitely exchangeable sequence is distributed as if a random parameter were drawn and the variables were then i.i.d. given it, i.e. a mixture. Exchangeable is “conditionally i.i.d.”, not i.i.d.

(1) Choose length \(N \sim \text{Poisson}(\xi)\) (not essential). (2) Choose topic proportions \(\theta \sim \text{Dir}(\alpha)\). (3) For each of the \(N\) words: choose a topic \(z_n \sim \text{Multinomial}(\theta)\), then a word \(w_n\) from \(p(w_n \mid z_n, \beta)\), where \(\beta\) is a \(k \times V\) matrix with \(\beta_{ij} = p(w^j = 1 \mid z^i = 1)\).

A density on the \((k-1)\)-simplex: \(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}\), with \(\alpha_i > 0\). It is in the exponential family, has finite-dimensional sufficient statistics, and is conjugate to the multinomial.

\(p(\mathbf{w} \mid \alpha, \beta) = \int p(\theta \mid \alpha) \Big(\prod_{n=1}^{N} \sum_{z_n} p(z_n \mid \theta)\, p(w_n \mid z_n, \beta)\Big) d\theta\); a corpus’s probability is the product over documents.

Corpus level: \(\alpha\), \(\beta\), sampled once. Document level: \(\theta_d\), once per document. Word level: \(z_{dn}\), \(w_{dn}\), once per word. A clustering model picks one cluster per document; in LDA the topic is resampled for every word, so a document can exhibit multiple topics.

Marginalizing out \(z\) gives a word distribution \(p(w \mid \theta, \beta) = \sum_z p(w \mid z, \beta)\, p(z \mid \theta)\) that depends on the random \(\theta\). So \(p(\mathbf{w} \mid \alpha, \beta) = \int p(\theta \mid \alpha) \prod_n p(w_n \mid \theta, \beta)\, d\theta\): a continuous mixture of unigram models with mixture weights \(p(\theta \mid \alpha)\), using only \(k + kV\) parameters.

A mixture of unigrams draws one topic \(z\) per document and all words from \(p(w \mid z)\): each document exhibits exactly one topic, often too limiting. LDA lets documents mix topics in different proportions at the cost of one extra parameter: \(k\) for \(p(\theta \mid \alpha)\) vs \(k - 1\) for \(p(z)\).

\(p(d, w_n) = p(d) \sum_z p(w_n \mid z)\, p(z \mid d)\): a document index \(d\) and a word are independent given a topic. But \(d\) is a dummy index over training documents, so \(p(z \mid d)\) exists only for them. LDA instead treats topic proportions as a \(k\)-parameter hidden random variable, so parameters don’t grow with the corpus.

All work on the word simplex (distributions over words); \(k\) topics span a topic simplex inside it. Unigram: one point for all words. Mixture of unigrams: each document at one corner of the topic simplex. pLSI: an empirical distribution with one point per training document. LDA: a smooth distribution over the topic simplex, sampled once per document.

The posterior \(p(\theta, \mathbf{z} \mid \mathbf{w}, \alpha, \beta)\) needs the normalizer \(p(\mathbf{w} \mid \alpha, \beta)\), which couples \(\theta\) and \(\beta\) in the sum over latent topics inside the integral. Approximations include Laplace, variational methods and MCMC.

Drop the edges between \(\theta\), \(z\) and \(w\) and the \(w\) nodes: \(q(\theta, \mathbf{z} \mid \gamma, \phi) = q(\theta \mid \gamma) \prod_{n=1}^{N} q(z_n \mid \phi_n)\), with a free Dirichlet parameter \(\gamma\) and free multinomials \(\phi_n\), chosen to minimize \(\text{KL}(q \,\|\, p(\theta, \mathbf{z} \mid \mathbf{w}, \alpha, \beta))\), which tightens a Jensen lower bound on the log likelihood.

\(\phi_{ni} \propto \beta_{i w_n} \exp\{\Psi(\gamma_i) - \Psi(\sum_j \gamma_j)\}\) and \(\gamma_i = \alpha_i + \sum_{n=1}^{N} \phi_{ni}\), where \(\Psi\) is the digamma function. The \(\gamma\) update is a posterior Dirichlet given expected topic counts; the \(\phi\) update is Bayes’ rule with \(p(z_n)\) approximated by the exponentiated expected log of \(\theta\). Iterate to convergence.

It is document-specific: a representation of the document in the topic simplex, and \(\gamma_i - \alpha_i\) is the expected number of words generated by topic \(i\). Each iteration costs \(O((N+1)k)\), and about \(N\) iterations are needed, so roughly \(N^2 k\) operations per document.

Empirical Bayes by variational EM, maximizing the variational lower bound on \(\sum_d \log p(\mathbf{w}_d \mid \alpha, \beta)\). E-step: fit \(\gamma_d^*\), \(\phi_d^*\) for every document. M-step: \(\beta_{ij} \propto \sum_d \sum_n \phi^*_{dni} w^j_{dn}\), and \(\alpha\) by Newton–Raphson with a Hessian invertible in linear time.

Maximum likelihood gives unseen words zero probability, and Laplace smoothing isn’t justified as MAP in a mixture model. Instead each row \(\beta_i\) gets an exchangeable Dirichlet prior with parameter \(\eta\) and is treated as random, with variational posterior \(\text{Dir}(\lambda_i)\), \(\lambda_{ij} = \eta + \sum_d \sum_n \phi^*_{dni} w^j_{dn}\): a fuller Bayesian treatment.

Topics such as Arts, Budgets, Children and Education emerged as word distributions. For a held-out article about a foundation’s grants to arts and education institutions, four topics had \(\gamma_i - \alpha_i \ge 1\), and per-word \(\phi_n\) showed which topic generated each word.

The bag-of-words assumption lets words that belong together, like “William Randolph Hearst Foundation”, be allocated to different topics; fixing this requires relaxing exchangeability, e.g. partial exchangeability or Markovian word sequences.

Held-out perplexity \(\exp\big(-\sum_d \log p(\mathbf{w}_d) / \sum_d N_d\big)\) on C. elegans abstracts and TREC AP news, against unigram, mixture-of-unigrams and pLSI models. Latent variable models beat the unigram model, and LDA was consistently best across numbers of topics.

Mixture of unigrams: peaked posteriors cluster training documents almost deterministically, so a new document has words with tiny probability in its best cluster (AP perplexity reached \(10^{264}\) at 200 topics). pLSI: a new document must reuse topic proportions seen in training. Folding-in refits \(p(z \mid d_{\text{new}})\), an unfair advantage. LDA infers new proportions for any document.

On Reuters-21578 binary tasks (EARN, GRAIN), an SVM on the 50 \(\gamma^*\) features of a 50-topic LDA model (a 99.6% feature reduction) lost little accuracy compared with all word features, and was better in almost all cases.

Users are documents and their preferred movies are words (EachMovie). Shown all but one of a test user’s movies, the model predicts the held-out one: \(p(w \mid \mathbf{w}_{\text{obs}}) = \int \sum_z p(w \mid z)\, p(z \mid \theta)\, p(\theta \mid \mathbf{w}_{\text{obs}})\, d\theta\). LDA had the best predictive perplexity.

Modularity and extensibility: LDA can be embedded in larger models (e.g. images with captions), unlike LSI. Extensions: other emission distributions (e.g. Gaussian), mixtures of Dirichlets, topics in a time series or conditioned on exogenous variables. Inference alternatives include expectation propagation and MCMC (Griffiths and Steyvers 2002).