Online Inference of Topics with Latent Dirichlet Allocation

Kevin Robert Canini, Lei Shi, Thomas L. GriffithsAISTATS 2009 · OpenReview

Abstract

Inference algorithms for topic models are typically designed to be run over an entire collection of documents after they have been observed. However, in many applications, document collections arrive in a continuous stream. This paper introduces efficient online inference algorithms for Latent Dirichlet Allocation (LDA), employing Rao-Blackwellized particle filters and incremental Gibbs sampling. These methods achieve near-batch-level accuracy with the speed and flexibility required for streaming data like news feeds or communication logs.

Introduction

Standard topic modeling via LDA typically relies on "batch" algorithms, such as Gibbs sampling or variational inference. These require the entire collection of documents to be available upfront and often involve multiple passes over the data to converge. In real-world scenarios, data often arrives in a continuous stream. Re-running a batch algorithm every time a new document is published is computationally wasteful and eventually impossible as the dataset grows.

Previous "online" attempts, such as o-LDA, were fast but suffered from a major flaw: they never "revisited" old decisions. If the model made a poor topic assignment early on, it was stuck with it forever. The challenge is to create an algorithm that can process data one document at a time while still being able to "rejuvenate" or correct past inferences without the overhead of a full batch process.

Methods

The authors propose two primary approaches based on collapsed (Rao-Blackwellized) sampling, where the topic-word and document-topic distributions are analytically integrated out to simplify the state space:

  1. Incremental Gibbs Sampler: This algorithm processes new words as they arrive but includes a "rejuvenation" step. After sampling topics for a new document, it selects a small subset of previously seen words and resamples their topics. This allows the model to adapt its understanding of topics as more data provides a clearer picture.
  2. Particle Filter: This is a Sequential Monte Carlo approach that maintains multiple "particles," each representing a potential state of topic assignments. It uses importance sampling to weight these particles based on how well they explain new data.
Directed tree of hashtables for efficient state representation in particle filters.

A major technical contribution is the "directed tree of hashtables." Normally, a particle filter would need to copy the entire history of topic assignments for every particle, leading to quadratic time complexity. The authors developed a tree structure where child particles only store changes from their parents in a hashtable, allowing for linear-time updates and significantly lower memory usage.

Results

The algorithms were evaluated on several document collections, including subsets of the 20 Newsgroups dataset (diff-3, rel-3, sim-3, and subset-20) and news articles from Slashdot (slash-6 and slash-7).

Performance comparison (nMI) of online inference algorithms against batch Gibbs sampling across various datasets.

Key Insights

  • The Power of "Looking Back": The results confirm that simply processing data once (o-LDA) leads to significantly lower accuracy. Periodically resampling even a small fraction of the past (rejuvenation) is essential for maintaining high-quality topics. Both the Incremental Gibbs Sampler and the Particle Filter consistently outperformed standard o-LDA across all datasets, often approaching the performance of the "gold standard" batch Gibbs sampler.
  • State Sharing is Essential: Without the tree-based hashtable implementation, particle filters would be too slow for online use. This data structure allows the algorithm to exploit the high degree of redundancy between different particles.
  • Early Information Dominance: Interestingly, the performance of the models didn't change drastically after the first 10% of the training data. This suggests that the core structure of the topics is often captured early, and subsequent data serves to refine rather than redefine them.

While the proposed online methods are roughly 6 times slower than the bare-bones o-LDA due to the rejuvenation steps, they remain computationally feasible for streaming applications. Furthermore, the particle filter's shared representation allowed it to use significantly less memory than maintaining independent samples.

Conclusion

This research demonstrates that online inference for LDA can achieve high accuracy through rejuvenation and efficient state representation. Future work may involve automating the tuning of rejuvenation schedules and extending the framework to non-parametric models like the Hierarchical Dirichlet Process (HDP), where the number of topics can grow automatically as more data is observed. Additionally, the natural parallelizability of particle filters offers a promising avenue for scaling in multi-processor environments.

Summary updated

Abstract

Inference algorithms for topic models are typically designed to be run over an entire collection of documents after they have been observed. However, in many applications of these models, the colle...
BibTeX
@inproceedings{canini2009online,
  author = {Kevin Robert Canini and Lei Shi and Thomas L. Griffiths},
  title = {{Online Inference of Topics with Latent Dirichlet Allocation}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2009},
  url = {https://openreview.net/forum?id=P0JZ3VCTo_D},
}
Figure