Deterministic Single-Pass Algorithm for LDA

Issei Sato, Kenichi Kurihara, Hiroshi NakagawaNeurIPS 2010

TL;DR

This paper introduces sREM-LDA, a deterministic, single-pass algorithm for Latent Dirichlet Allocation (LDA) designed for massive text streams. By treating the posterior of one document as the prior for the next, it achieves the accuracy of batch algorithms with significantly lower memory overhead and a 25x speedup over sampling-based online methods.

The Challenge of Streaming Text

Latent Dirichlet Allocation (LDA) is the "gold standard" for discovering hidden topics in large collections of text. However, traditional "batch" LDA algorithms require iterating over the entire dataset multiple times, which is impossible for continuous streams like news feeds or social media posts.

Existing "online" versions of LDA often rely on sampling methods (like Gibbs sampling or particle filters). While effective, these methods have two major drawbacks:

  1. Computational Cost: They require many samples to represent a posterior distribution accurately, making them slow.
  2. Memory Bloat: They often need to store old samples or "resample" old data, which defeats the purpose of a streaming algorithm.

The authors aim to create a deterministic (non-random) algorithm that processes each document exactly once and then discards it, without needing to store global statistics for every document ever seen.

Performance comparison of LDA algorithms

Proposed Methods: iREM-LDA and sREM-LDA

The authors propose two new algorithms based on the Reverse EM (REM) framework:

  1. iREM-LDA (Incremental): An incremental variant that updates parameters by replacing old "sufficient statistics" with new ones. While faster than batch processing, it still requires storing statistics for all data.
  2. sREM-LDA (Single-Pass): This is the core contribution. It is inspired by Bayesian sequential updates: the posterior distribution calculated for document $j$ becomes the prior distribution for document $j+1$.

Key Innovations: * Sequential Dirichlet Updates: Unlike previous methods that used batch updates for the Dirichlet parameter ($\alpha$), sREM-LDA uses a sequential update rule. This allows the model to adapt to a growing vocabulary in real-time. * No Manual Learning Rate: The algorithm's update rules naturally incorporate a "stepsize" (learning rate) derived from the model's hyperparameters. This stepsize automatically decreases as more documents are observed, ensuring mathematical convergence without manual tuning.

Datasets

The researchers evaluated their algorithms on two standard text corpora:

  • Associated Press (AP): 10,000 documents, ~67,000 unique words.
  • The Wall Street Journal (WSJ): 10,000 documents, ~56,000 unique words.

The documents were ordered chronologically to simulate a real-world time-series stream.

Key Insights

  • Deterministic > Sampling for Streams: By moving away from sampling (Particle Filters) to a deterministic variational approach, the authors eliminated the need for parallel processing and massive sample storage.
  • The "Prior as Posterior" Trick: The most elegant part of sREM-LDA is how it handles the "single-pass" constraint. By mathematically passing information forward through the Dirichlet priors, the model "remembers" what it learned from previous documents without needing to keep them in memory.
  • Automatic Convergence: The authors prove that their update weights satisfy the conditions for stochastic approximation (Robbins-Monro). This means the algorithm is theoretically guaranteed to stabilize as it processes more data.

Key Results

  • Speed: sREM-LDA is dramatically faster than existing online methods. For a model with 300 topics, sREM-LDA finished in ~1.2 hours, whereas a Particle Filter (PF) took over 28 hours on the same data.
  • Accuracy (Perplexity): Despite only seeing each document once, sREM-LDA achieved "test set perplexity" (a measure of how well the model predicts new text) comparable to batch algorithms (VB-LDA) and the more memory-intensive incremental algorithm (iREM-LDA).
Testset perplexity on the AP dataset across different topic counts
  • Memory Efficiency: sREM-LDA does not need to store old statistics for all data, making its memory footprint $O(T \times V)$ (Topics $\times$ Vocabulary), whereas other methods scale with the number of processes or samples.

Limitations and Future Work

  • Hyperparameter Sensitivity: While the "stepsize" is automatic, it is still tied to the initial choice of hyperparameters, which might require some initial tuning for different types of text.
  • Convergence Proofs: While the authors provide a theorem regarding the update weights, they note that a full, rigorous convergence analysis using super-martingale theory is "future work."
  • Short Documents: The paper notes that sREM-LDA's performance depends on the length of the document; extremely short documents (like tweets) might require more internal iterations ($l$) to provide a stable update.

Summary updated

BibTeX
@inproceedings{sato2010deterministic,
  author = {Issei Sato and Kenichi Kurihara and Hiroshi Nakagawa},
  title = {{Deterministic Single-Pass Algorithm for LDA}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2010},
}
Figure