Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models

Evan Sidrow, Nancy Heckman, Alexandre Bouchard-Côté, Sarah M. E. Fortune, Andrew W. Trites, Marie Auger-MéthéJ. Comput. Graph. Stat 2025 · OpenReview

TL;DR

This paper introduces a novel optimization algorithm that significantly speeds up the process of fitting Hidden Markov Models (HMMs) to large datasets. By combining a partial Expectation-Maximization (EM) step with variance-reduced stochastic optimization, the algorithm achieves faster convergence and better results compared to existing methods, making complex HMMs more accessible for real-world applications.

What Problem Does This Paper Address?

Hidden Markov Models (HMMs) are powerful tools for analyzing sequential data, finding applications in fields ranging from speech recognition to animal behavior. However, a major bottleneck in using HMMs, especially with the ever-increasing size of datasets, is the computational cost of parameter estimation. Traditional methods, like the Baum-Welch algorithm, require iterating through the entire dataset for each parameter update, making them prohibitively slow for large-scale problems. This paper addresses this challenge by developing a more efficient inference algorithm that avoids this full data pass, enabling the analysis of more complex HMMs on larger datasets.

Methods

The core of the paper's contribution lies in a novel optimization algorithm that modifies the standard Expectation-Maximization (EM) algorithm for HMMs. The key innovations are:

  • Variance-Reduced Stochastic Optimization (VRSO): Instead of using the full dataset in the maximization (M) step of EM, the authors employ variance-reduced stochastic optimization techniques like SAGA and SVRG. These methods use random subsets of the data to estimate gradients, significantly reducing computation per update.
  • Partial E-step: To further accelerate the process, they introduce a "partial E-step" within the M-step. This means that instead of recalculating all conditional probabilities (which is computationally intensive) for every stochastic update, they only update a subset of these probabilities. This is inspired by belief propagation techniques and aims to balance computational cost with accuracy.
  • Combined Algorithm (EM-VRSO): The paper integrates these ideas into a new algorithm, EM-VRSO, which performs a full E-step periodically and then uses the partial E-step within the VRSO-based M-step for parameter updates.

Datasets

The authors evaluated their algorithm on two types of datasets:

  • Simulated Data: They generated synthetic HMM data with varying lengths of observation sequences (T), numbers of hidden states (N), and observation dimensions (d). This allowed for controlled experiments to compare performance across different scenarios.
  • Real-World Data: A case study involved analyzing kinematic data from eight northern resident killer whales. This dataset comprised over 5000 dives and 80000 depth readings, representing a large and complex real-world application.

Key Insights and Ideas

  • Stochasticity is Key for Scale: The paper strongly demonstrates that leveraging stochastic optimization is crucial for handling the massive datasets now common in many scientific fields. The proposed VRSO approach effectively bridges the gap between the speed of stochastic methods and the convergence guarantees of full-batch methods.
  • Partial E-step: A Smart Compromise: The partial E-step is a clever way to reduce the computational burden of the E-step without sacrificing too much accuracy, especially in the early stages of optimization when parameters are rapidly changing. This insight is particularly valuable for complex models where the full E-step is a significant bottleneck.
  • HMMs for Complex Behaviors: The killer whale case study highlights the applicability of HMMs to model intricate animal behaviors, such as dive phases and types. The success of their optimized inference method suggests that more sophisticated HMMs can now be applied to such biological datasets.

Key Results

  • Significant Speedup: The proposed EM-VRSO algorithm, particularly with SAGA and SVRG, consistently converged in fewer epochs compared to standard optimization techniques (BFGS, conjugate gradient, and full-batch gradient descent) across both simulated and real-world datasets. In simulations with T=10^5, the algorithm often converged in about half the epochs.
  • Improved Likelihood: The algorithm not only converged faster but also tended to reach regions of higher log-likelihood, indicating better parameter estimates.
  • Effectiveness of Partial E-step: The partial E-step variant (P=True) showed particular advantages early in the optimization process, leading to faster initial progress.
  • Scalability: The method's performance on large datasets (T=10^5) suggests its suitability for modern, high-frequency data collection.

Limitations and Future Work

  • Theoretical Guarantees: While the paper provides theoretical convergence guarantees for certain conditions, the analysis for the partial E-step variant is more complex.
  • Step Size Selection: Stochastic optimization methods can be sensitive to step size selection. The paper discusses adaptive step size strategies but acknowledges that Lipschitz constants are often unknown in practice.
  • Future Work: The authors suggest exploring other variance-reduced stochastic optimization algorithms (e.g., SARAH, SPIDER) and integrating them into their framework. They also envision applying their method to more complex HMMs with larger latent spaces across various disciplines.

Summary updated

BibTeX
@article{sidrow2025variance,
  author = {Evan Sidrow and Nancy Heckman and Alexandre Bouchard-Côté and Sarah M. E. Fortune and Andrew W. Trites and Marie Auger-Méthé},
  title = {{Variance-Reduced Stochastic Optimization for Efficient Inference of Hidden Markov Models}},
  journal = {J. Comput. Graph. Stat.},
  year = {2025},
  url = {https://openreview.net/forum?id=mQi16qOnzW},
}
Figure