FlowHMM: Flow-based continuous hidden Markov models

Pawel Lorek, Rafal Nowak, Tomasz Trzcinski, Maciej ZiebaNeurIPS 2022 · OpenReview

Introduction

Hidden Markov Models (HMMs) are the workhorses of time-series analysis, used in everything from speech recognition to financial forecasting. However, standard continuous HMMs have a "Gaussian problem." They typically assume that observations for any given state follow a Gaussian distribution or a mixture of Gaussians (GMMs).

Real-world data is rarely that polite. It can be skewed, multimodal, or have sharp boundaries that a smooth Gaussian curve simply cannot capture. Furthermore, the standard way to train these models—the Baum-Welch algorithm—is computationally expensive for very long sequences, scaling linearly with the number of time steps. FlowHMM introduces a novel class of continuous HMMs that swap out restrictive Gaussian emission distributions for flexible, deep Normalizing Flows, aiming to break both the "Gaussian ceiling" of model flexibility and the "linear bottleneck" of training time.

Methodology: The FlowHMM Approach

The core innovation is FlowHMM, where the emission density of each hidden state is modeled by a Continuous Normalizing Flow (CNF). Normalizing flows work by taking a simple base distribution (like a standard normal) and "warping" it through a series of learnable, invertible transformations into a complex target distribution.

The concept of FlowHMM: each state uses a separate flow component to model complex, non-Gaussian emission distributions.

The paper proposes two distinct training flavors:

  1. $\mathcal{F}^{ML}$ (Maximum Likelihood): A standard gradient-based approach that optimizes the log-likelihood directly. It is highly flexible but, like Baum-Welch, its computational cost grows with the sequence length.
  2. $\mathcal{F}^Q$ (Co-occurrence based): This is the "secret sauce" for efficiency. The authors discretize the continuous observations onto a grid and compute a co-occurrence matrix $\hat{Q}$, which tracks how often pairs of values appear consecutively. They then train the FlowHMM to minimize the KL divergence between the model's predicted joint distribution and this empirical matrix.

Experimental Setup

The authors evaluated FlowHMM across a mix of synthetic and real-world scenarios:

  • 1D Synthetic Sequences: Data generated from mixtures of Gaussians, Uniform, and Beta distributions to test the model's ability to recover non-standard shapes.
  • 2D Synthetic Sequences: The "Two Moons" dataset and geometric Brownian motion.
  • Financial Data: S&P 500 and Dow Jones stock indices (daily differences).
  • Environmental Data: A 6-dimensional real-world dataset containing air pressure and humidity metrics from Papua New Guinea.

Key Findings and Insights

  • Beyond the Bell Curve: By using flows, FlowHMM can fit "weird" distributions—like the flat top of a Uniform distribution or the sharp peaks of a Beta distribution—that GMMs struggle to approximate without an excessive number of components.
  • The Efficiency of $\hat{Q}$: The $\mathcal{F}^Q$ method is a game-changer for big data. Once the co-occurrence matrix is calculated (a one-time pass over the data), the actual optimization time is the same whether you have 10,000 or 10,000,000 observations.
  • Stationarity as a Feature: The co-occurrence method assumes the underlying Markov chain is stationary. While this is a constraint, it allows the model to aggregate global statistics of the time series into a compact matrix, making it highly robust for long-term modeling.
Distributions learned by the two FlowHMM variants ($\mathcal{F}^{ML}$ and $\mathcal{F}^Q$) compared to the ground truth. Both effectively capture non-Gaussian peaks and valleys.

In almost all synthetic tests, FlowHMM achieved higher log-likelihoods and lower Total Variation distance to the true distribution compared to Gaussian baselines. It also showed higher accuracy in predicting the underlying hidden states, particularly when the transition matrices were complex. On real-world financial and environmental data, FlowHMM significantly outperformed standard HMMs. For example, on the 6D air pressure dataset, the flow-based model provided a massive jump in normalized log-likelihood (-571.08 for FlowHMM vs. -1097.49 for a standard Gaussian HMM).

Limitations and Future Work

  • The Grid Constraint: The $\mathcal{F}^Q$ method requires discretizing data onto a grid. In very high dimensions, the number of cells in this grid grows exponentially (the "curse of dimensionality"), making the co-occurrence matrix approach difficult to scale beyond a few dimensions without cleverer discretization.
  • Stationarity Assumption: The efficiency of the co-occurrence approach relies on the process being stationary. If the "rules" of the time series change over time, the model might struggle.
  • Future Directions: The authors suggest exploring "temporally stationary" co-occurrence matrices that could be re-computed during training to handle non-stationary data, as well as more sophisticated grid search methods for high-dimensional observations.

Summary updated

Abstract

Continuous hidden Markov models (HMMs) assume that observations are generated from a mixture of Gaussian densities, limiting their ability to model more complex distributions. In this work, we address this shortcoming and propose novel continuous HMM models, dubbed FlowHMMs, that enable learning general continuous observation densities without constraining them to follow a Gaussian distribution or their mixtures. To that end, we leverage deep flow-based architectures that model complex, non-Gaussian functions and propose two variants of training a FlowHMM model. The first one, based on gradient-based technique, can be applied directly to continuous multidimensional data, yet its application to larger data sequences remains computationally expensive. Therefore, we also present a second approach to training our FlowHMM that relies on the co-occurrence matrix of discretized observations and considers the joint distribution of pairs of co-observed values, hence rendering the training time independent of the training sequence length. As a result, we obtain a model that can be flexibly adapted to the characteristics and dimensionality of the data. We perform a variety of experiments in which we compare both training strategies with a baseline of Gaussian mixture models. We show, that in terms of quality of the recovered probability distribution, accuracy of prediction of hidden states, and likelihood of unseen data, our approach outperforms the standard Gaussian methods.
BibTeX
@inproceedings{lorek2022flowhmm,
  author = {Pawel Lorek and Rafal Nowak and Tomasz Trzcinski and Maciej Zieba},
  title = {{FlowHMM: Flow-based continuous hidden Markov models}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=wanujhLxQ7},
}
Figure