Overfitting hidden Markov models with an unknown number of states

Zoé van Havre, Judith Rousseau, Nicole White, Kerrie MengersenarXiv 2016 · DOI · arXiv

Abstract

Determining the number of states in a Hidden Markov Model (HMM) is a fundamental challenge in Bayesian statistics. This paper proposes a method of intentional overfitting, where a model is fitted with more states than necessary, and specific prior configurations are used to induce "posterior emptying" of redundant states. By employing asymmetric Dirichlet priors and an adapted Prior Parallel Tempering (PPT) algorithm, the authors demonstrate that the true number of states can be identified without the need for trans-dimensional MCMC moves. Theoretical asymptotic convergence is established, and the approach is validated through extensive simulation studies comparing different prior structures.

Introduction

Hidden Markov Models (HMMs) are essential tools for modeling time-series data where transitions occur between unobserved latent states. However, selecting the correct number of states, $K^*$, remains a significant hurdle. Traditional model selection techniques, such as Reversible Jump Markov Chain Monte Carlo (RJMCMC), are often computationally prohibitive and difficult to implement. Conversely, non-parametric Bayesian approaches, like the Infinite Hidden Markov Model, frequently over-estimate the state count.

This research explores an alternative: fitting an overfitted HMM with $K > K^*$ states and designing the prior such that the posterior distribution concentrates on the true $K^*$ states. This process, known as "emptying" the extra states, allows for a fixed-dimensional parameter space while effectively performing model selection.

Methodology and Prior Configurations

The core of the proposed method lies in the choice of the prior for the transition matrix $Q$. The authors investigate three specific Dirichlet prior configurations designed to handle the non-identifiability of overfitted models:

  1. Column Prior ($\pi_c$): This prior favors a structure where transitions are concentrated into a small subset of "active" states. By "starving" redundant states of incoming transitions, the model forces their posterior weight toward zero.
  2. Diagonal Prior ($\pi_d$): Often used in applications like genomics to model state persistence ("stickiness"), this prior favors high self-transition probabilities.
  3. Mixture Prior ($\pi_m$): A 50/50 combination of the Column and Diagonal priors, intended to capture the benefits of both.

A critical theoretical requirement identified by the authors is that the prior must maintain the ergodicity of the hidden Markov chain. Even as states are emptied, the chain must remain capable of reaching all active states to ensure consistent estimation.

Computational Challenges: Prior Parallel Tempering

Overfitted posteriors are characterized by complex, multi-modal landscapes. In these models, "empty" states create regions of low probability that act as barriers, trapping standard Gibbs samplers in sub-optimal configurations where extra states remain active but redundant.

To overcome this, the authors extend the Prior Parallel Tempering (PPT) approach. PPT runs multiple MCMC chains in parallel, each with varying prior strengths. This allows the sampler to "tunnel" through low-probability regions, facilitating efficient movement between overfitted and emptied states. Without PPT, the authors found that the sampler frequently failed to identify the true $K^*$, leading to biased results.

Theoretical and Empirical Results

The paper provides a rigorous theoretical foundation, proving that under specific constraints on the Dirichlet hyperparameters ($\alpha$), the posterior probability of extra states being occupied converges to zero as the sample size $n$ approaches infinity.

Large-Sample Validation

In simulations with $n = 10,000$ observations from a 2-state Gaussian HMM (fitted with $K=4$), the model achieved a 100% success rate in identifying the correct number of states. This confirmed the asymptotic theory and the effectiveness of the Column prior in inducing sparsity.

Small-Sample Performance

The researchers also tested the model on smaller datasets ($n=100$ and $n=500$). Key findings include:

  • The $1/n$ Rule: While theoretical bounds for hyperparameters can be high, setting the "small" hyperparameter $\alpha = 1/n$ proved to be a robust practical choice for inducing sparsity in finite samples.
  • Prior Comparison: The Column Prior consistently outperformed the Diagonal Prior in emptying redundant states. The Diagonal Prior, while useful for modeling persistence, occasionally led to "merged" states where two model states split the observations of a single true state.

Discussion and Limitations

The study highlights that while intentional overfitting is a powerful tool, it is sensitive to certain model specifications. Specifically, the simulations primarily utilized known emission variances ($\sigma^2=1$). Preliminary investigations into unknown variances revealed a "trap" where the model might prefer a single state with an inflated variance over multiple well-defined states. Addressing this will likely require more informative priors on the variance parameters.

Furthermore, the choice of hyperparameters involves a trade-off. In very small samples, the high hyperparameter values suggested by asymptotic theory might overwhelm the data. Future work will focus on refining these "sweet spots" for various data complexities.

Conclusion

By combining asymmetric Dirichlet priors with Prior Parallel Tempering, this research provides a viable framework for Bayesian state estimation in HMMs without the need for trans-dimensional moves. The Column Prior emerges as the superior choice for inducing posterior sparsity, offering a theoretically grounded and practically effective solution to the problem of unknown state counts in Hidden Markov Models.

Summary updated

Abstract

This paper presents new theory and methodology for the Bayesian estimation of overfitted hidden Markov models, with finite state space. The goal is then to achieve posterior emptying of extra states. A prior configuration is constructed which favours configurations where the hidden Markov chain remains ergodic although it empties out some of the states. Asymptotic posterior convergence rates are proven theoretically, and demonstrated with a large sample simulation. The problem of overfitted HMMs is then considered in the context of smaller sample sizes, and due to computational and mixing issues two alternative prior structures are studied, one commonly used in practice, and a mixture of the two priors. The Prior Parallel Tempering approach of van Havre (2015) is also extended to HMMs to allow MCMC estimation of the complex posterior space. A replicate simulation study and an in-depth exploration is performed to compare the three priors with hyperparameters chosen according to the asymptotic constraints alongside less informative alternatives.
BibTeX
@misc{havre2016overfitting,
  author = {Zoé van Havre and Judith Rousseau and Nicole White and Kerrie Mengersen},
  title = {{Overfitting hidden Markov models with an unknown number of states}},
  year = {2016},
  eprint = {1602.02466},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/1602.02466},
}
Figure