An adaptive simulated annealing EM algorithm for inference on non-homogeneous hidden Markov models

Aliaksandr Hubin

This paper presents a pragmatic yet mathematically rigorous approach to a classic "needle in a haystack" problem in statistics: variable selection for Non-Homogeneous Hidden Markov Models (NHHMMs). By introducing the ASA-EM algorithm, the author provides a tool that can navigate massive model spaces to find the best predictors for complex, time-varying data.

TL;DR

The paper introduces ASA-EM, an algorithm that combines adaptive simulated annealing with Expectation-Maximization to perform joint model selection and parameter estimation in NHHMMs. It handles non-Gaussian data, scales to large sets of covariates, and outperforms industry-standard benchmarks like Facebook’s Prophet and Google’s CausalImpact in financial forecasting.

What Problem Does This Paper Address?

Hidden Markov Models (HMMs) are workhorses for modeling systems that flip between "hidden" states (e.g., a "bull" vs. "bear" market). In a standard HMM, the probability of switching states is constant. Non-Homogeneous HMMs (NHHMMs) are more realistic; they allow these transition probabilities—and the behavior within a state—to be influenced by external variables (covariates).

The challenge is variable selection. If you have $p$ potential covariates, and each can influence either the state transitions, the observations, both, or neither, you are faced with $4^p$ possible model configurations. For just 30 variables, that is over a quintillion ($10^{18}$) combinations. Existing methods (like MCMC or Variational Bayes) are often too computationally heavy, limited to Gaussian data, or lack accessible software implementations.

Methods

The author proposes the Adaptive Simulated Annealing Expectation Maximization (ASA-EM) algorithm. It breaks the problem into two nested loops:

  1. Simulated Annealing (SA) for Model Space: This "outer" loop explores the discrete space of model configurations (which variables to include). It uses a "cooling" schedule to move from broad exploration to fine-tuned exploitation.
  2. Expectation-Maximization (EM) for Parameters: For a given model structure chosen by the SA, the EM algorithm estimates the continuous parameters (the "weights" of the variables).
  3. The "Adaptive" Secret Sauce: Unlike standard SA, this version learns its own hyperparameters during the run. It uses Bayesian updates to tune the number of EM iterations, the size of the neighborhood it searches, and the probability of including specific variables based on "successful" previous moves.

Crucially, the algorithm is designed for the exponential family of distributions, meaning it works for binary, count, and continuous data, not just Gaussian noise.

Datasets

The paper evaluates the algorithm on two distinct real-world problems:

  • Epigenetics (Arabidopsis): 1,502 observations of DNA methylation with 17 covariates. This is a pattern recognition task using a Binomial distribution.
  • S&P 500 Stock Data: Predicting Amazon (AMZN) stock returns using 30 other stocks as covariates (1,258 daily observations). This is a prediction-driven task using a Gaussian NHHMM with three hidden states ("buy", "sell", "wait").

Key Insights and Ideas

  • Joint Optimization is Key: By nesting EM within SA, the algorithm optimizes the model structure and the parameters simultaneously, rather than treating them as separate steps.
  • Self-Tuning Hyperparameters: By making the algorithm adaptive, the user doesn't need to perfectly guess the right "temperature" or "step size" for the search; the algorithm learns these from the data's topology.
  • Parallelism as a Feature: Because the search space is so vast, the author suggests running multiple parallel "threads" of the algorithm. This isn't just for speed; it helps ensure the algorithm finds the global optimum rather than getting stuck in a local "trap."

Key Results

  • Superior Accuracy: In the S&P 500 experiment, the NHHMM selected by ASA-EM achieved a Root Mean Square Error (RMSE) of 78.6, significantly beating LASSO (92.2), SARIMAX (87.4), and Facebook’s Prophet (181.4).
  • Economic Utility: A simple trading strategy based on the model's hidden states turned \$1,000 into **\$1,915** during the training period and maintained profitability in a "blind" test period.
  • Biological Relevance: In the epigenetics study, the model identified specific genetic regions (CHG and CG) as the primary drivers of methylation, aligning with known biological theory while providing a more nuanced view than "naive" statistical approaches.

Limitations and Future Work

  • Local Optima: Despite the simulated annealing, the EM part is still "greedy" and can get stuck. The author mitigates this with parallel threads, but it remains a theoretical hurdle.
  • Linearity: The current model assumes linear relationships between covariates and the parameters. The author suggests that incorporating non-linear relations (like deep learning components) could be a fruitful next step.
  • Scalability: While it handles 30 variables well, the author notes that for truly massive "big data" sets, the EM part might need to be replaced with stochastic sub-sampling to remain computationally feasible.

Note: The author has released an R package, depmixS4pp, on GitHub to allow researchers to apply this method to their own datasets.

Summary updated

Abstract

Non-homogeneous hidden Markov models (NHHMM) are a subclass of dependent mixture models used for semi-supervised learning, where both transition probabilities between the latent states and the mean parameter of the probability distribution of the responses (for a given state) depend on the set of up to p covariates. A priori we do not know which (and how) covariates influence the transition probabilities and the mean parameters. This induces a complex combinatorial optimization problem for model selection with 4p potential configurations. To address the problem, in this article we propose an adaptive (A) simulated annealing (SA) expectation maximization (EM) algorithm (ASA-EM) for joint optimization of models and their parameters with respect to a criterion of interest.
BibTeX
@inproceedings{hubin2019adaptive,
  author = {Aliaksandr Hubin},
  title = {{An adaptive simulated annealing EM algorithm for inference on non-homogeneous hidden Markov models}},
  booktitle = {AIIPCC},
  year = {2019},
  url = {https://openreview.net/forum?id=M8Bs7LVART},
}

Loading related content...

Figure