The Hierarchical Dirichlet Process Hidden Semi-Markov Model

Matthew J. Johnson, Alan S. WillskyUAI 2010

TL;DR

This paper introduces the Hierarchical Dirichlet Process Hidden Semi-Markov Model (HDP-HSMM), a flexible Bayesian nonparametric model that extends the popular HDP-HMM by allowing for non-geometric state durations. This new model offers more expressive power for sequential data and is accompanied by efficient sampling inference algorithms that demonstrate faster convergence than existing methods on tasks like speaker diarization and Morse code analysis.

What Problem Does This Paper Address?

Many real-world sequential data problems, such as analyzing speech, DNA, or user behavior, involve identifying underlying states and understanding how long these states persist. Traditional Hidden Markov Models (HMMs) are limited because they assume state durations follow a geometric distribution, which is often unrealistic. While the Hierarchical Dirichlet Process HMM (HDP-HMM) addresses the issue of inferring an unknown number of states in a Bayesian way, it still inherits the geometric duration limitation. This can lead to models that are overly complex or exhibit unrealistic rapid switching dynamics. The paper aims to bridge this gap by developing a model that combines the Bayesian nonparametric advantages of the HDP-HMM with the flexibility of semi-Markovian models, allowing for arbitrary state duration distributions.

Methods

The core contribution is the Hierarchical Dirichlet Process Hidden Semi-Markov Model (HDP-HSMM). This model augments the HDP-HMM by incorporating explicit duration distributions for each state. Instead of a strict Markovian transition, when a state is entered, a duration is sampled from a state-specific distribution, and the state remains constant for that duration before transitioning.

To handle inference in this more complex model, the authors develop two novel sampling algorithms:

  • Direct-Assignment Sampler: This approach leverages the HDP-HMM's direct-assignment sampler. It treats segments of observations as atomic units and samples the super-state sequence first, then efficiently resamples the segmentation boundaries. A key technique here is "latent history sampling" to allow for the sampling of super-state transitions while effectively outlawing self-transitions.
  • Weak-Limit Sampler: This method builds upon the weak-limit approximation used for HDP-HMMs. It creates a finite approximation to the HDP transitions, enabling block sampling of the hidden state chain and thus accelerating mixing. This approach is particularly useful for non-geometric duration distributions.

Datasets

The paper evaluates the HDP-HSMM on:

  • Synthetic Data: Generated from both HSMMs (with Poisson durations) and HMMs to test the model's ability to recover underlying structure and parameters.
  • Morse Code Data: Spectrogram data of Morse code audio was used to demonstrate how duration information can disambiguate states (e.g., distinguishing between short and long tones).
  • NIST Rich Transcription Database: A standard dataset for speaker diarization, used to showcase the practical benefits of the HDP-HSMM's faster mixing inference algorithms compared to existing methods.

Key Insights and Ideas

  • Non-geometric durations are crucial: The paper strongly argues that real-world sequential data often exhibits state durations that are not geometric. Models that can capture these more flexible duration patterns are more expressive and can lead to better interpretations and performance.
  • HDP-HSMM offers a principled way to combine Bayesian nonparametrics and semi-Markovianity: It inherits the HDP-HMM's ability to infer the number of states while adding the flexibility of semi-Markovian duration modeling.
  • Faster inference is achievable: The developed sampling algorithms, particularly the weak-limit sampler, demonstrate significantly faster convergence ("burn-in") compared to existing methods like the Sticky HDP-HMM, making the model more practical for large datasets.
  • Explicit duration modeling can prevent superfluous states: The HDP-HMM, lacking explicit duration modeling, can create unnecessary extra states to mimic non-geometric behavior. The HDP-HSMM avoids this by directly modeling durations.

Key Results

  • Synthetic Data: The HDP-HSMM successfully captured the proper duration statistics and reduced posterior uncertainty when applied to data generated from a Poisson-HSMM, outperforming the HDP-HMM which struggled with duration modeling and state identification. When learning from HMM data, the HDP-HSMM (with a negative binomial duration class) quickly concentrated on geometric durations (r=1), showing only a slight loss in mixing time compared to the HDP-HMM.
  • Morse Code: The HDP-HSMM correctly disambiguated three states (short tone, long tone, silence) from Morse code data, whereas the HDP-HMM only identified two. The learned duration parameters for the tone states closely matched the pulse widths.
  • Speaker Diarization: On the NIST Rich Transcription Database, the HDP-HSMM sampler achieved approximately 0.4 normalized Hamming error in under 200 iterations, a significant speedup compared to the Sticky HDP-HMM which required 5000-30000 iterations for similar performance. This faster mixing makes the HDP-HSMM more practical for large-scale diarization tasks.

Limitations and Future Work

  • Computational Cost: While the HDP-HSMM offers faster convergence, the message-passing algorithm for HSMMs is inherently more computationally expensive than for HMMs (O(T²N + TN²) vs. O(TN²)). However, truncating segment lengths (dmax) can reduce this to O(Tdmax N²).
  • Self-Transitions: The paper adopts the convention of ruling out self-transitions in HSMMs, which simplifies inference but might be a limitation in certain applications.
  • Future Work: The authors suggest that the developed sampling algorithms could also provide new approaches for inference in the original HDP-HMM, potentially addressing its mixing issues. Further exploration of different duration distribution classes and their impact on inference and model performance is also implied.

Summary updated

BibTeX
@inproceedings{johnson2010hierarchical,
  author = {Matthew J. Johnson and Alan S. Willsky},
  title = {{The Hierarchical Dirichlet Process Hidden Semi-Markov Model}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2010},
}
Figure