Evolving Markov Chains: Unsupervised Mode Discovery and Recognition from Data Streams
This addresses the need for efficient online mode discovery and recognition in non-stationary data streams, such as in activity tracking or industrial monitoring, though it appears incremental as it builds on Markov chain frameworks with novel updates.
The study tackled the problem of modeling live, real-world processes with behavior switches by proposing Evolving Markov Chains (EMCs), which adaptively track transition probabilities, automatically discover modes, and detect mode switches online, achieving geometric convergence of estimates and demonstrating versatility in applications like human activity recognition and EEG-based eye-state recognition.
Markov chains are simple yet powerful mathematical structures to model temporally dependent processes. They generally assume stationary data, i.e., fixed transition probabilities between observations/states. However, live, real-world processes, like in the context of activity tracking, biological time series, or industrial monitoring, often switch behavior over time. Such behavior switches can be modeled as transitions between higher-level \emph{modes} (e.g., running, walking, etc.). Yet all modes are usually not previously known, often exhibit vastly differing transition probabilities, and can switch unpredictably. Thus, to track behavior changes of live, real-world processes, this study proposes an online and efficient method to construct Evolving Markov chains (EMCs). EMCs adaptively track transition probabilities, automatically discover modes, and detect mode switches in an online manner. In contrast to previous work, EMCs are of arbitrary order, the proposed update scheme does not rely on tracking windows, only updates the relevant region of the probability tensor, and enjoys geometric convergence of the expected estimates. Our evaluation of synthetic data and real-world applications on human activity recognition, electric motor condition monitoring, and eye-state recognition from electroencephalography (EEG) measurements illustrates the versatility of the approach and points to the potential of EMCs to efficiently track, model, and understand live, real-world processes.