Online Variational Inference for the Hierarchical Dirichlet Process

Chong Wang, John W. Paisley, David M. BleiAISTATS 2011 · OpenReview

Abstract

Topic modeling on massive document collections is a common task, often handled by Latent Dirichlet Allocation (LDA). However, LDA requires the number of topics to be specified upfront, which can lead to overfitting or underfitting. The Hierarchical Dirichlet Process (HDP) addresses this by automatically inferring the number of topics, but traditional inference methods are too slow for large-scale or streaming data. This paper introduces an online variational inference algorithm for the HDP that leverages Sethuraman’s stick-breaking construction and natural gradients. The proposed method is highly scalable, processes data in mini-batches, and outperforms online LDA while eliminating the need for manual topic count selection.

Introduction

The Hierarchical Dirichlet Process (HDP) is a powerful Bayesian nonparametric model for topic modeling. Unlike Latent Dirichlet Allocation (LDA), which requires a fixed number of topics ($K$), the HDP treats $K$ as a random variable to be inferred from the data. This flexibility prevents the common pitfalls of over-specifying or under-specifying the model's capacity.

Despite its theoretical advantages, the HDP has historically been limited by the computational complexity of its posterior inference. Traditional approximate inference algorithms, such as Markov Chain Monte Carlo (MCMC) or batch variational inference, require multiple passes over the entire dataset. This makes them impractical for massive archives or continuous data streams like news feeds. To address this, we present an online variational inference algorithm that allows the HDP to scale to millions of documents through single-pass processing.

Methodology

The primary challenge in developing an online algorithm for the HDP lies in the mathematical representation of the process. Previous variational methods relied on Teh's stick-breaking construction, which couples the top-level and bottom-level Dirichlet Processes in a way that prevents closed-form updates.

We overcome this by employing Sethuraman’s stick-breaking construction. This representation maintains full conjugacy between the levels of the hierarchy, enabling simple, closed-form coordinate-ascent updates for the variational parameters.

The hierarchical structure of the HDP using stick-breaking construction, showing the relationship between global atoms and document-specific weights.

The algorithm processes data in mini-batches using stochastic optimization with natural gradients. For each mini-batch, the algorithm computes optimal local (document-level) parameters and then updates the global (corpus-level) parameters. Because the coordinate-ascent updates in our construction correspond to the natural gradient of the variational objective, the algorithm achieves fast and stable convergence without the need to compute expensive second-order information.

Experimental Setup

The model was evaluated on two large-scale scientific corpora:

  • Nature: 352,549 documents spanning from 1869 to 2008, containing approximately 58 million tokens.
  • PNAS (Proceedings of the National Academy of Sciences): 82,519 documents from 1914 to 2004, containing approximately 46 million tokens.

Performance was measured using per-word log-likelihood on held-out data, comparing the online HDP (oHDP) against batch HDP (bHDP) and online LDA (oLDA) with various fixed topic counts.

Results and Discussion

The online HDP consistently outperformed both online LDA and batch HDP across all experiments.

Per-word log likelihood as a function of training time for the Nature dataset. oHDP reaches higher likelihood faster than batch HDP and outperforms oLDA across various topic counts.

Predictive Performance and Scalability

As shown in the results for the Nature dataset, oHDP achieves a higher per-word log-likelihood than oLDA, regardless of the number of topics chosen for the latter. Furthermore, oHDP is significantly more efficient than batch HDP. In our experiments, batch HDP could only process a small subset (20,000 documents) within a 6-hour window, whereas oHDP successfully processed the entire dataset of over 350,000 documents in the same timeframe.

Automatic Model Selection

A key advantage of the oHDP is its built-in regularization. While oLDA tends to use every available topic slot—often leading to overfitting if $K$ is set too high—the oHDP naturally prunes unnecessary topics. For example, when given a truncation limit of 150 topics on the Nature corpus, the oHDP utilized only approximately 110, effectively performing automatic model selection during the inference process.

Dynamic Topic Discovery

When applied to historical document streams, the oHDP demonstrates the ability to discover topics dynamically. It identifies stable, long-standing topics early in the stream while allowing new topics to emerge as relevant documents appear in later years. For instance, topics like astronomy solidify early, while others remain dormant until relevant scientific shifts occur decades later.

Conclusion

We have presented an online variational inference algorithm for the Hierarchical Dirichlet Process that is both scalable and robust. By utilizing a conjugate stick-breaking construction and natural gradients, the method provides a practical way to apply nonparametric Bayesian models to massive datasets. While the approach still requires a high-level truncation parameter, it is significantly less sensitive than the fixed topic count required by LDA. Future work will explore extending this framework to other nonparametric models, such as the Indian Buffet Process.

Summary updated

BibTeX
@inproceedings{wang2011online,
  author = {Chong Wang and John W. Paisley and David M. Blei},
  title = {{Online Variational Inference for the Hierarchical Dirichlet Process}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2011},
  url = {https://openreview.net/forum?id=BhCf7Z-oU4},
}
Figure