A recursive estimate for the predictive likelihood in a topic model

James Scott, Jason BaldridgeAISTATS 2013 · OpenReview

Abstract: We consider the problem of evaluating the predictive log likelihood of a previously unseen document under a topic model. This task arises when cross-validating for a model hyperparameter, when testing the fit of a model, or when comparing different models. We propose a recursive estimate of the predictive likelihood that is fast to compute and has low variance. Our method is based on a filtering approximation to the posterior distribution of the topic assignments for the words in the document. We show that our method is more accurate than standard importance sampling and much faster than the left-to-right algorithm.

Introduction

In natural language processing, topic models like Latent Dirichlet Allocation (LDA) are standard tools for discovering latent thematic structures in text. A critical task in using these models is evaluating the "predictive likelihood" (or perplexity) of held-out data. This metric quantifies how well a trained model generalizes to new documents, serving as the primary benchmark for model selection and hyperparameter tuning.

However, calculating this likelihood is computationally demanding. It involves marginalizing over all possible topic assignments for every word in a document— a high-dimensional integral that is analytically intractable. Existing approaches typically force a trade-off between speed and accuracy. Simple approximations are often biased, while more accurate methods, such as the "left-to-right" (L2R) Gibbs sampler, exhibit quadratic computational complexity ($O(N^2)$) relative to document length. This makes large-scale evaluation prohibitively expensive.

The Filtering Approach

This paper introduces a fast, deterministic filtering algorithm to estimate predictive likelihood. The method is derived from Particle Learning (PL), a sequential Monte Carlo technique that treats a document as a sequence of words arriving one by one.

Instead of maintaining a computationally expensive "cloud" of particles to represent the posterior, the authors propose a deterministic version. This algorithm tracks the expected topic assignments using a single-particle approach. By employing Rao-Blackwellization—using expected counts rather than hard sampled assignments—the algorithm significantly reduces variance. This shift from sampling to deterministic filtering reduces computational complexity from $O(MN^2)$ to $O(N)$, where $N$ is the document length and $M$ is the number of particles.

Sources of Uncertainty in Estimation

A key insight of the research is the hierarchy of noise in likelihood estimation. The authors found that the variation introduced by the specific word order (permuting words in a document) or the particular posterior draw of model parameters often exceeds the variation between different estimation algorithms.

Impact of posterior draws and word order on likelihood estimates across different methods.

As shown in the figure above, the "within-method" variability is substantial. This suggests that pursuing an "exact" but slow sampling method is often unnecessary for practical applications, as the errors of a fast deterministic approximation are negligible compared to other inherent sources of uncertainty in the text-processing pipeline.

Empirical Performance

The filtering method was evaluated against six diverse English corpora, including the New York Times (nyt), 20 Newsgroups (20news), and Project Gutenberg.

Comparison of filtering and L2R methods across different topic counts and their high correlation in simulated corpora.

Key results include:

  • Efficiency: The proposed filtering method operates at approximately 1% of the computational cost of the standard 100-particle L2R algorithm.
  • Accuracy: In simulations, the filtering estimates were nearly indistinguishable from full Particle Learning and highly correlated with the more expensive L2R implementation in the Mallet toolkit.
  • Scalability: The linear scaling ($O(N)$) allows for the evaluation of massive datasets that were previously computationally inaccessible for high-quality likelihood estimation.

Conclusion and Future Work

Deterministic filtering provides a robust and efficient alternative for evaluating topic models. While the authors note that bias might increase for extremely short documents (where the number of words is much smaller than the number of topics), the method generally provides a "good enough" estimate for most real-world applications. Future research may explore the impact of stop-word filtering, which currently introduces a bias that likely outweighs the inaccuracies of any specific estimation technique.

Summary updated

Abstract

We consider the problem of evaluating the predictive log likelihood of a previously un- seen document under a topic model. This task arises when cross-validating for a model hyperparameter, when te...
BibTeX
@inproceedings{scott2013recursive,
  author = {James Scott and Jason Baldridge},
  title = {{A recursive estimate for the predictive likelihood in a topic model}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2013},
  url = {https://openreview.net/forum?id=wdeG6YtemA},
}

Loading related content...

Figure