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 mean parameter of the probability distribution of the responses (for a given state) depend on the set of $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 $4^p$ 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.
Introduction
Hidden Markov Models (HMMs) are fundamental tools for modeling systems that transition between unobserved states, such as market regimes or biological phases. Standard HMMs assume constant state transition probabilities. However, Non-Homogeneous HMMs (NHHMMs) offer a more sophisticated framework where transition probabilities and state-dependent observations are influenced by external covariates.
The primary challenge in NHHMMs is variable selection. With $p$ potential covariates, each capable of influencing transitions, observations, both, or neither, the search space expands to $4^p$ configurations. For 30 variables, this results in over $10^{18}$ combinations, rendering traditional MCMC or Variational Bayes methods computationally prohibitive or overly restrictive.
Methodology: The ASA-EM Algorithm
To navigate this vast model space, we introduce the Adaptive Simulated Annealing Expectation Maximization (ASA-EM) algorithm. This approach integrates two nested optimization loops:
- Simulated Annealing (SA) for Model Selection: The outer loop explores the discrete space of model configurations. It employs a cooling schedule to transition from global exploration to local exploitation.
- Expectation-Maximization (EM) for Parameter Estimation: For each model structure proposed by the SA, the EM algorithm estimates the continuous parameters (variable weights).
- Adaptive Hyperparameter Tuning: Unlike standard SA, ASA-EM utilizes Bayesian updates to tune its own hyperparameters during execution. It dynamically adjusts the number of EM iterations, neighborhood search size, and variable inclusion probabilities based on the success of previous iterations.
The algorithm is designed for the exponential family of distributions, supporting binary, count, and continuous data. To avoid local optima, the algorithm utilizes parallel "threads," ensuring a more robust search for the global optimum.
Experimental Evaluation
The ASA-EM algorithm was evaluated on two distinct real-world datasets:
Epigenetics (Arabidopsis)
This task involved pattern recognition in DNA methylation using 1,502 observations and 17 covariates, modeled with a Binomial distribution. The NHHMM successfully identified specific genetic regions (CHG and CG) as primary drivers of methylation, providing a nuanced view consistent with biological theory.
Financial Forecasting (S&P 500)
The algorithm was used to predict Amazon (AMZN) stock returns using 30 other stocks as covariates over 1,258 daily observations. A Gaussian NHHMM with three hidden states ("buy", "sell", "wait") was employed.
Key Results
- Forecasting Accuracy: In the S&P 500 experiment, ASA-EM achieved a Root Mean Square Error (RMSE) of 78.6, significantly outperforming LASSO (92.2), SARIMAX (87.4), and Facebook’s Prophet (181.4).
- Economic Utility: A trading strategy derived from the model's hidden states demonstrated significant profitability, nearly doubling an initial investment during the training period and maintaining performance in blind tests.
- Joint Optimization: The nesting of EM within SA allows for the simultaneous optimization of model structure and parameters, a key advantage over sequential methods.
Discussion and Limitations
While ASA-EM provides a powerful framework for NHHMM inference, certain limitations remain. The EM component is inherently greedy and susceptible to local optima, though parallel threading mitigates this risk. Additionally, the current model assumes linear relationships between covariates and parameters; future work could explore non-linear components, such as deep learning architectures. Finally, for extremely large datasets, the EM step may require stochastic sub-sampling to maintain computational efficiency.
The implementation of this method is available via the R package depmixS4pp on GitHub.
Summary updated