Variational Markov chain mixtures with automatic component selection

Abstract

Markov state modeling has gained popularity in various scientific fields since it reduces complex time-series data sets into transitions between a few states. Yet common Markov state modeling frameworks assume a single Markov chain describes the data, so they suffer from an inability to discern heterogeneities. As an alternative, this paper models time-series data using a mixture of Markov chains, and it automatically determines the number of mixture components using the variational expectation-maximization algorithm.Variational EM simultaneously identifies the number of Markov chains and the dynamics of each chain without expensive model comparisons or posterior sampling. As a theoretical contribution, this paper identifies the natural limits of Markov state mixture modeling by proving a lower bound on the classification error. It then presents numerical experiments where variational EM achieves performance consistent with the theoretically optimal error scaling. The experiments are based on synthetic and observational data sets including Last.fm music listening, ultramarathon running, and gene expression. In each of the three data sets, variational EM leads to the identification of meaningful heterogeneities.

v2: changed title, streamlined early sections

References in corpus (7)

• Projected and Hidden Markov Models for calculating kinetics and metastable states of complex molecules
• Model-based clustering based on sparse finite Gaussian mixtures
• Reaction coordinates for the flipping of genetic switches
• Rare-Event Sampling of Epigenetic Landscapes and Phenotype Transitions
• Agnostic detection of large-scale weather patterns in the northern hemisphere: from blockings to teleconnections
• Clustering sequence data with mixture Markov chains with covariates using multiple simplex constrained optimization routine (MSiCOR)
• Asymptotics for Markov chain mixture detection