Blei et al Latent Dirichlet Allocation

Citation

author = {Blei, David M. and Ng, Andrew Y. and Jordan, Michael I.},
title = {Latent dirichlet allocation},
journal = {J. Mach. Learn. Res.},
issue_date = {3/1/2003},
volume = {3},
month = mar,
year = {2003},
issn = {1532-4435},
pages = {993--1022},
numpages = {30},
url = {http://dl.acm.org/citation.cfm?id=944919.944937},
acmid = {944937},
publisher = {JMLR.org}

Online Version

Latent Dirichlet Allocation

Summary

This paper addresses the problem of document modeling

LDA

LDA is a generative probabilistic model for discrete data such as text corpora. It is a Bayesian model that consists of three hierarchies. Each item of the collection is modeled as a finite mixture i.e. modeled as being generated by an underlying (latent) set of topics, where each topic is characterized by a distribution over words. Each document $d$ in the corpus is assumed to be generated using the following process:

1. The author chooses the number of words $N_{d}$ in the document by drawing from a Poisson($\xi$) distribution. 
2. He then tosses a Dirichlet hypergenerator Dirichlet($\alpha$) to get a $\theta _{d,n}$ which is used to generate a Multinomial($\theta _{d,n}$) topiv generator
3. For each word $w_{d,n}$ from the $N_{d}$ words
  a. A topic $z_{d,n}$ is chosen from a Multinomial($\theta _{d,n}$) distribution
  b. A topic specific word generator parametrized by $z_{d,n}$ and $\beta$ is then tossed to get the word

The parameters $\alpha$ and $\beta$ are corpus level parameters and are sampled only once in the process of generating a corpus. The variables $\theta _{d,n}$ are sampled once per document. Finally, the variables $z_{d,n}$ and $w_{d,n}$ are word-level variables and are sampled once for each word in each document. What makes LDA unique is that it consists of three levels, and notably the topic node is sampled repeatedly within a document. This allows documents to be associated with multiple topics rather than just one.

Inference

The posterior distribution of the hidden variables given a document is, in general, intractable. However, many efficient approximate inference techniques can be used to estimate the posterior. The paper describes a convexity-based variational method involving EM algorithm for Bayes parameter estimation.

The basic idea is to obtain a lower bound on the log likelihood parametrized by the variational parameters using the Jensen’s inequality. The variational parameters are chosen by an optimization procedure that attempts to find the tightest possible lower bound. The authors show that this requires choosing the parameters to minimize the KL divergence between the distribution under the variational parameters and the true posterior. This leads to a pair of interdependent update equations which can be solved via an iterative fixed-point method.

Parameter Estimation

We now need to estimate the parameters $\alpha$ and $\beta$ of the LDA model. An empirical Bayes method for parameter estimation is provided. Given a corpus of documents D, we wish to find parameters $\alpha$ and $\beta$ that maximize the (marginal) log likelihood of the data:

$l(\alpha ,\beta )=\sum _{d\in D}log(p(d|\alpha ,\beta )$

This is again not directly solvable. However, variational inference technique provides a tractable lower bound on the log likelihood/ which can be maximized with respect to $\alpha$ and $\beta$. Thus an alternating variational EM procedure can be used to solve the above:

1. E step: For each document, find the optimizing values of the variational parameters
2. M step: For fixed values of variational parameters, maximize resulting lower bound on the log likelihood with respect to the model parameters $\alpha ,\beta$

Experiments

LDA is empirically evaluated in several problem domains -- document modeling, document classification, and collaborative filtering.

• Document Modeling

The model is evaluated by computing, what the authors call, perplexity of a test set on the trained model. Perplexity is a measure of how surprised the trained model is on seeing a new document. Thus a lower perplexity score is better. Datasets used were Elegans scientific corpus and a subset of the TREC AP corpus. LDA is compared against smoothed unigram (every word from the same multinomial), smoothed mixture of unigrams (a topic chosen for the document and each word selected conditioned on the chosen topic) and Hoffman's pLSI model. LDA performs better than each of the above. These models also suffer from overfitting while the LDA does not.

• Document classification

The authors conducted binary classification experiments on the Reuters-21578 dataset. The parameters of an LDA model were estimated on all the documents, without their true class label. A SVM was then trained on the low-dimensional representations provided by LDA and was compared to an SVM trained on all the word features.

• Collaborative filtering

A model is trained on a fully observed set of users. Then, for each unobserved user, all but one of the movies preferred by that user are shown and the task is to predict what the held-out movie is. The different algorithms are evaluated according to the likelihood they assign to the held-out movie. The EachMovie collaborative filtering data was used.

Study Plan

• Probabilistic Latent Semantic Indexing
  • Mixture models
• Variational Bayesian Methods
  • Variational Inference lecture pdf by Blei
• KL divergence