EAGER: Characterizing Regime Shifts in Data Streams using Computational Topology - the Mathematics of Shape

University Of Colorado At Boulder, Boulder CO

Investigators

Abstract

Time-series data arise in a wide array of engineered systems, including network traffic, vibration sensors on machine tools, acoustic sensors on reactor containment vessels, and many other examples. The development of efficient and effective methods to characterize the patterns in such data has widespread utility in engineering, commerce and other fields. Methods for characterizing patterns in these streams could be used to detect malware attacks on a network, a lathe bearing that is degrading, or an impending containment failure in a reactor. Common challenges include observability - situations when sensors are expensive or difficult to deploy, or when they perturb the behavior under examination - as well as high information content, noise, and rapid regime shifts. The ultimate goal of this EArly-Grant for Exploratory Research (EAGER) project is to use computational topology, the fundamental mathematics of shape, to deal with these challenges. Shape is perhaps the roughest notion of structure and can be particularly robust to contamination of the signal. The specific goal of this study is to develop new methods for identifying and categorizing the temporal patterns associated with the regime shifts a stream of data. A topological approach to time series analysis is distinct from standard methods of the machine learning and stream-mining communities, which typically use probabilistic approaches and often implicitly assume linearity. This project seeks to extract nonlinear structure not necessarily visible in a regresssion or spectral approach. Indeed, a regime shift need not correspond to a change in the frequency content of a signal, but could nevertheless be represented as a shift in the homology (e.g., Betti numbers) of the embedded signal. A goal is to develop techniques useful to engineers and scientists for the detection of incipient system failure or rapid evaluation of state changes from hidden causes. Existing algorithms of computational topology often require lengthy computations, especially for large data sets in many dimensions. However, since not all of those variables may be observable, one may have to reconstruct the full dynamics from partial measurements--e.g., using the process called delay-coordinate embedding. This project seeks rapid evaluation of Betti numbers based on incomplete, partial embeddings. A novel aspect is that the dynamics gives rise to a multivalued map on a simplicial complex, a "witness map." Selection of multiple parameters in the algorithms will be based on persistent homology, previously developed only for the analysis of static data sets and for a single parameter. The ultimate goal is robust and rapid regime detection for a limited data stream from a "black-box" source.