This paper by Alexander Y. Shestopaloff and Radford M. Neal introduces a significant upgrade to the embedded Hidden Markov Model (HMM) method for Markov Chain Monte Carlo (MCMC) sampling. By moving from global to sequential, local pool state selection, the authors enable the method to handle high-dimensional latent states with linear computational complexity, while introducing a clever "mirroring" trick to navigate multimodal distributions.
TL;DR
The authors propose a sequential pool state selection scheme that allows the embedded HMM method to scale to high-dimensional state space models. This new approach reduces computational complexity from quadratic to linear in the number of pool states and introduces "mirroring" to efficiently sample from multimodal posterior distributions.
What Problem Does This Paper Address?
State space models (SSMs) are essential for modeling time-series data where an unobserved "latent" process drives observed measurements. However, when these models are non-linear or non-Gaussian, inferring the latent states is notoriously difficult.
Standard MCMC methods like single-state Metropolis-Hastings often struggle because temporal dependencies make the posterior distribution highly concentrated, leading to "stuck" chains. While "block" update methods like Particle Gibbs with Backward Sampling (PGBS) and the original embedded HMM method exist, they have drawbacks:
- Dimensionality: The original embedded HMM used "global" pool states, which rarely land in high-probability regions as the state space dimension increases.
- Complexity: The original method had a computational cost of $O(L^2n)$ (where $L$ is the number of pool states and $n$ is the sequence length), making it expensive for large $L$.
- Multimodality: Local sampling schemes often get trapped in a single mode of the posterior distribution.
Methods
The core innovation is a sequential pool state selection scheme. Instead of picking pool states independently at each time step, the authors generate them sequentially (either forward or backward in time).
- Local Pool States: By using Markov transitions (like autoregressive or Metropolis updates) to generate pool states near the current state, the sampler stays within high-probability regions even in high dimensions.
- Linear Complexity: By treating the pool state densities as marginals and using an auxiliary variable approach (similar to an auxiliary particle filter), they reduce the cost of the forward-backward pass from $O(L^2n)$ to $O(Ln)$. This makes the method computationally competitive with Particle Gibbs.
- Mirroring (Flip Updates): To handle models where the posterior has multiple modes (e.g., when observations depend on the absolute value of the state), the authors introduce "flip updates." This involves adding negated versions of pool states to the "pool," allowing the HMM to "flip" large segments of the sequence between modes in a single step.
Datasets
The authors evaluated their method using two synthetic non-linear, non-Gaussian state space models:
- Model 1 (Unimodal): A 10-dimensional latent state with a sequence length of $n=250$. It uses a Gaussian latent process and Poisson observations.
- Model 2 (Multimodal): A more challenging 15-dimensional latent state with $n=500$. The observations depend on the absolute value of the state, creating a posterior with many well-separated modes.
Key Insights and Ideas
- Locality is Key for High Dimensions: Global sampling fails in high dimensions because the "volume" of high-probability space is tiny. By anchoring pool states to the current state, the embedded HMM remains effective as dimensionality grows.
- HMMs as "Super-Metropolis" Proposals: The embedded HMM essentially constructs a temporary, finite-state HMM that approximates the true model. This allows for complex, coordinated moves across the entire time sequence that a simple Metropolis sampler could never achieve.
- The Power of Symmetry: The "mirroring" technique shows that if you know your distribution has specific symmetries (like sign invariance), you can bake that knowledge directly into the pool state generation to solve multimodality issues that would otherwise require massive computational effort.
Key Results
- Efficiency: For the unimodal Model 1, the new embedded HMM performed similarly to a well-tuned combination of PGBS and Metropolis updates.
- Superior Multimodal Exploration: For Model 2, the embedded HMM with flip updates significantly outperformed the baseline (PGBS + Metropolis). While the baseline sampler tended to get stuck in single modes, the flip-enabled HMM explored well-separated modes efficiently.
- Scaling: The reduction to $O(Ln)$ complexity was verified, allowing the use of larger pools without the quadratic performance hit of the original method.
Limitations and Future Work
- Fixed Parameters: The paper assumes model parameters ($\theta$) are known. A natural next step is to integrate this into a Gibbs sampler that alternates between updating states and updating parameters.
- Information Lag: The forward pool state generation doesn't use "future" data, which might lead to over-dispersed pool states in some scenarios. The authors suggest that slowing down the Markov chain used for pool generation might help control this dispersion.
- Implementation Sensitivity: The authors noted that performance can be sensitive to implementation details, such as how well the code is vectorized in environments like MATLAB.
Summary updated