Blei 2003 - Smoothed LDA, Examples and Experiments

Summary

Smoothed LDA places an exchangeable $\text{Dir}(\eta )$ prior on each row of $\beta$ and adds the update ${\lambda }_{ij}=\eta +{\sum }_d{\sum }_n{\varphi }_{dni}^{\ast }{w}_{dn}^j$. Experiments: perplexity on C. Elegans and AP, SVM classification on Reuters-21578 with 50 LDA features, and collaborative filtering on EachMovie, where LDA is best.

Main Content

Smoothing (5.4, Fig. 7). Maximum likelihood assigns zero probability to unseen words. Laplace smoothing is not a MAP justification in mixture models. LDA treats ${\beta }_i\sim \text{Dir}(\eta )$ and uses a separable variational family $q({\beta }_{1:k},{\mathbf{z}}_{1:M},{\theta }_{1:M}\mid \lambda ,\varphi ,\gamma )={\prod }_i\text{Dir}({\beta }_i\mid {\lambda }_i){\prod }_d{q}_d({\theta }_d,{\mathbf{z}}_d\mid {\varphi }_d,{\gamma }_d)$ with the same $\varphi ,\gamma$ updates and ${\lambda }_{ij}=\eta +{\sum }_d{\sum }_n{\varphi }_{dni}^{\ast }{w}_{dn}^j$. $\eta$ and $\alpha$ by approximate empirical Bayes.

Example (Sec. 6, Fig. 8). 16,000 TREC AP documents, 100-topic LDA, stop words removed. Top words for four topics: “Arts” (new, film, show, music, movie, play), “Budgets” (million, tax, program, budget, billion, federal), “Children” (children, women, people, child, years, families), “Education” (school, students, schools, education, teachers). Posterior inference on a held-out article (Hearst Foundation grants to Lincoln Center, the Metropolitan Opera, New York Philharmonic, Juilliard) loads on arts, budgets, children and education: words are coloured by their most likely topic.

Perplexity (7.1)

For a held-out set of $M$ documents, $\text{perplexity}=\exp \{-{\sum }_{d=1}^M\log p({\mathbf{w}}_d)/{\sum }_{d=1}^M{N}_d\}$: the inverse geometric mean per-word likelihood; lower is better.

7.1 Document modelling. Corpora: C. Elegans abstracts (5,225 documents, 28,414 unique terms) and TREC AP subset (16,333 articles, 23,075 unique terms); 10% held out; 50 stop words removed (AP: also words seen once). Models trained by EM with stopping rule: average change in expected log-likelihood below 0.001%. Compared: unigram, mixture of unigrams, pLSI (folding-in), LDA (smoothed where noted).

Table 1 (AP) shows the overfitting of the unsmoothed models:

Topics $k$	Perplexity, mixture of unigrams	Perplexity, pLSI
2	22,266	7,052
5	$2.20\times 10^8$	17,588
10	$1.93\times 10^{17}$	63,800
20	$1.20\times 10^{22}$	$2.52\times 10^5$
50	$4.19\times 10^{106}$	$5.04\times 10^6$
100	$2.39\times 10^{150}$	$1.72\times 10^7$
200	$3.51\times 10^{264}$	$1.31\times 10^7$

Interpretation: perplexity explodes with $k$ because test documents contain words that have tiny probability in the sharp components. After smoothing / folding-in correction, Fig. 9 shows LDA with the lowest perplexity at every $k$ on both corpora; latent variable models beat the smoothed unigram.

7.2 Classification (Fig. 10). Reuters-21578 (8,000 documents, 15,818 words), two binary tasks (EARN vs not, GRAIN vs not). An SVM (SVMLight) on 50 LDA features ${\gamma }^{\ast }(\mathbf{w})$ (99.6% feature reduction) shows little reduction in accuracy relative to an SVM on all word features and in almost all cases improves it, across training proportions (the authors note the results need further substantiation and suggest LDA as a fast feature-selection filter).

7.3 Collaborative filtering (Fig. 11). EachMovie; users with at least 100 positively rated movies (rating at least 4 of 5): 3,300 training users, 390 test users, vocabulary 1,600 movies. Predictive perplexity $\exp \{-{\sum }_d\log p(w_{d,N_d}\mid w_{d,1:N_d-1})/M\}$ for the held-out movie; LDA predicts via $p(w\mid w_{obs})=\int {\sum }_{z}p(w\mid z)p(z\mid \theta )p(\theta \mid w_{obs})d\theta$, a linear combination of $k$ Dirichlet expectations. LDA obtains the best predictive perplexity (mixture of unigrams and pLSI corrected for overfitting).

8 Discussion. Extensions listed: Laplace and higher-order variational (Leisink and Kappen 2002), expectation propagation (Minka and Lafferty 2002), MCMC (Griffiths and Steyvers 2002), $n$-gram / paragraph mixtures via partial exchangeability, and generalised exchangeability results (Diaconis 1988).

Examples

Reading the perplexity blow-up

A test word with per-component probability $10^{-6}$ in the document’s assigned component contributes $\log 10^{-6}=-13.8$ to the log-likelihood; across hundreds of words and $k=200$ components this accumulates into the astronomically large values in Table 1. Smoothing with $\eta$ lifts every word above zero.

Connections

Posterior Predictive Checking and held-out likelihood as validation tools; yardsticks beyond perplexity: Concept - Topic Model Evaluation and Stability.

See Also

Blei 2003 - Latent Dirichlet Allocation - Overview