Stochastic Variational Inference for the HDP-HMM

Aonan Zhang, San Gultekin, John W. PaisleyAISTATS 2016 · OpenReview

Abstract

We derive a variational inference algorithm for the Hierarchical Dirichlet Process Hidden Markov Model (HDP-HMM) based on a two-level stick-breaking construction. This approach overcomes the scalability limitations of traditional Markov Chain Monte Carlo (MCMC) methods by leveraging a novel local lower bound and stochastic variational inference (SVI). Our method enables closed-form parameter updates and scales to massive datasets, such as the Million Song Dataset, while maintaining the ability to learn the appropriate number of hidden states from sequential data.

Introduction

Hidden Markov Models (HMMs) are fundamental tools for sequential data analysis. However, a significant limitation is the requirement to pre-specify the number of hidden states. The Hierarchical Dirichlet Process HMM (HDP-HMM) addresses this by allowing for an "infinite" number of states, enabling the model to adapt its complexity based on the observed data.

Comparison of standard HMM (left) and HDP-HMM (right) structures, highlighting the hierarchical stick-breaking process.

Despite their flexibility, HDP-HMMs are computationally demanding. Traditional MCMC methods, such as beam sampling, are slow and do not scale well to large datasets. While Variational Inference (VI) has proven effective for other HDP-based models like topic models, its application to HDP-HMMs is complicated by sequential dependencies, which break the exchangeability assumptions typically used in VI. In an HMM, the state at time $t$ depends on $t-1$, breaking the mathematical symmetries that standard VI relies on.

Methodology

This paper presents a scalable variational inference algorithm for the HDP-HMM utilizing a two-level stick-breaking construction. This approach offers several innovations:

  1. Closed-Form Updates: The method provides closed-form variational updates for all parameters, improving efficiency over previous numerical optimization techniques.
  2. Local Lower Bounding: To address sequential dependencies, the authors introduce auxiliary "stick indicator" variables ($s_{d,i}$). These variables allow for a local lower bound on the objective function, making the inference tractable without sacrificing accuracy.
  3. Stochastic Extension (SVI): By employing natural gradients, the batch algorithm is extended to a stochastic version. This allows the model to process data in mini-batches, making it possible to train on millions of sequences.
  4. Forward-Backward Integration: The classic forward-backward algorithm structure is maintained within the variational framework to efficiently compute state probabilities.
Detailed HDP-HMM stick-breaking construction showing the mapping of sticks to states via auxiliary variables.

Experimental Evaluation

The algorithm was evaluated across three distinct datasets:

  • Artificial Data: Synthetic sequences from four-state HMMs were used to verify the recovery of the "ground truth" number of states.
  • Alice’s Adventures in Wonderland: Sequential text analysis where 12 chapters were treated as sequences of characters (27 possible symbols).
  • Million Song Dataset: A large-scale task involving discretized audio features from 371,000 songs, representing a massive jump in scale for HDP-HMM applications.

Results and Discussion

The variational approach demonstrated significant improvements in efficiency and scalability. On synthetic data, the VI method converged in under 2.5 seconds, compared to 40 seconds for beam sampling to reach the same number of inferred states. In the "Alice" text experiments, the HDP-HMM consistently outperformed standard HMMs, successfully learning the ideal number of states for each chapter (ranging from 21 to 26) without manual tuning.

Crucially, the stochastic version (oHDPHMM-sb) was the only HDP-based method capable of efficiently processing the Million Song Dataset. It outperformed both parametric HMMs and previous "direct assignment" stochastic HDP-HMMs in terms of predictive log-likelihood. The two-level stick-breaking construction also proved more stable and provided better predictive performance than standard mean-field approximations, which tend to overestimate the number of required states.

Conclusion

The proposed stochastic variational inference framework for the HDP-HMM enables the application of infinite state-space models to massive sequential datasets. By leveraging stick-breaking representations and novel local lower bounds, the authors bridge the gap between the flexibility of Bayesian nonparametrics and the scalability required for modern data science. While the model still utilizes truncation levels for computation, it remains far less restrictive than standard HMMs and offers a robust path for extending HDPs to complex sequential tasks.

Summary updated

Abstract

We derive a variational inference algorithm for the HDP-HMM based on the two-level stick breaking construction. This construction has previously been applied to the hierarchical Dirichlet processes...
BibTeX
@inproceedings{zhang2016stochastic,
  author = {Aonan Zhang and San Gultekin and John W. Paisley},
  title = {{Stochastic Variational Inference for the HDP-HMM}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2016},
  url = {https://openreview.net/forum?id=SCeExJ5Uqwz},
}
Figure