Abstract
The Infinite Hidden Markov Model (IHMM) extends hidden Markov models to have a countably infinite number of hidden states (Beal et al., 2002; Teh et al., 2006). We present a generalization of this model, the Block Diagonal Infinite Hidden Markov Model (BD-IHMM), which automatically groups hidden states into "blocks" that represent distinct sub-behaviors. This allows the model to perform unsupervised segmentation and classification of complex time-series data—like identifying different gestures in a video or recurring themes in a song—without knowing the number of states or behaviors in advance.
Introduction
Hidden Markov Models (HMMs) are fundamental tools for time-series analysis. However, standard HMMs and their infinite variants (HDP-HMMs) typically assume a flat structure for the transition matrix. In contrast, many real-world processes are hierarchical, composed of distinct "sub-processes" or "regimes." For example, a complex physical activity consists of sequences of movements; transitions within a movement are highly probable, while transitions between different movements are rare. This behavioral pattern manifests as a block-diagonal transition matrix. The BD-IHMM is designed to learn this latent block structure automatically, preventing the "conflation" of states that often plagues standard models.
Methodology: The Block Innovation
The BD-IHMM builds upon the Infinite Hidden Markov Model by introducing an additional layer to the hierarchy. It partitions the infinite set of hidden states into an infinite set of "blocks" using a stick-breaking process.
A critical component of this model is the hyperparameter $\xi$. This parameter acts as a bias term that scales transition probabilities: a high $\xi$ value strongly encourages transitions between states within the same block. To perform inference, the authors utilize a direct assignment Gibbs sampler. To overcome the common issue of samplers getting stuck in local optima during clustering, they adapted the Swendsen-Wang algorithm from statistical physics. This allows the model to update block labels for multiple states simultaneously, significantly accelerating convergence.
Experimental Evaluation
The authors validated the BD-IHMM across several diverse domains:
- Synthetic Data: On 100 artificial datasets with 2–4 sub-behaviors, the BD-IHMM achieved an Adjusted Rand Index (ARI) exceeding 0.95 in over half the trials, significantly outperforming the standard IHMM.
- Gesture Classification: The model successfully segmented video data of a person performing four distinct gestures (batting, boxing, pitching, and tennis), providing clean behavioral labels where standard models failed.
- Music Analysis: Applied to the song "Shine" by Collective Soul, the model identified the underlying verse-chorus structure despite minimal repetitions.
- Commute Patterns: Using U.S. Census data for Pennsylvania, the model identified 55 clusters of municipalities. These clusters were found to be geographically localized (e.g., Greater Pittsburgh), demonstrating the model's ability to perform graph partitioning based on edge weights (commute counts) without spatial priors.
Key Insights and Discussion
A central insight of this work is that a single "behavior" is often too complex for a single HMM state. By grouping states into blocks, the BD-IHMM captures internal dynamics while maintaining a high-level behavioral unit for classification. Furthermore, the model's ability to discover the "natural" granularity of data makes it a powerful tool for unsupervised discovery.
Limitations
The computational cost of evaluating block assignments scales at $O(M^2)$ relative to the number of visited states $M$, which may limit scalability for massive datasets. Additionally, the model requires a minimum threshold of repetition to reliably identify sub-behaviors. Future research will focus on online learning implementations and extending the block-diagonal prior to more general relational data structures.
This summary is based on the research paper "The Block Diagonal Infinite Hidden Markov Model."
Summary updated