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

EAGER：使用计算拓扑表征数据流中的政权转变 - 形状数学

• 批准号: 1447440
• 负责人: Elizabeth Bradley
• 金额: $ 6.15万
• 依托单位: University of Colorado at Boulder
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2014
• 资助国家: 美国
• 起止时间: 2014-08-01 至 2016-07-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1447440&HistoricalAwards=false
• 关键词: EAGER; Characterizing; Regime; Shifts; Data

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.

时间序列数据出现在广泛的工程系统中，包括网络流量、机床上的振动传感器、反应堆安全壳上的声学传感器以及许多其他示例。开发高效的方法来描述这些数据中的模式在工程、商业和其他领域具有广泛的用途。表征这些流模式的方法可用于检测网络上的恶意软件攻击、正在退化的车床轴承或反应堆中即将发生的安全壳故障。常见的挑战包括可观测性——当传感器昂贵或难以部署时，或者当它们干扰被检查的行为时——以及高信息含量、噪声和快速的状态变化。这个探索性研究早期拨款（EAGER）项目的最终目标是使用计算拓扑，即形状的基础数学，来应对这些挑战。形状可能是最粗略的结构概念，对信号的污染尤其可靠。本研究的具体目标是开发新的方法来识别和分类与数据流的政权转移相关的时间模式。时间序列分析的拓扑方法不同于机器学习和流挖掘社区的标准方法，后者通常使用概率方法，并且通常隐含地假设线性。这个项目试图提取非线性结构，不一定是在回归或光谱方法中可见的。事实上，一个状态的移动并不需要对应于信号的频率内容的变化，但是可以被表示为嵌入信号的同源性（例如，贝蒂数）的移动。目标是开发对工程师和科学家有用的技术，用于检测早期系统故障或快速评估隐藏原因导致的状态变化。现有的计算拓扑算法往往需要长时间的计算，特别是对于多维的大型数据集。然而，由于并非所有这些变量都可以观察到，人们可能不得不从部分测量中重建完整的动力学。，使用称为延迟坐标嵌入的过程。该项目寻求基于不完整、部分嵌入的贝蒂数的快速评估。一个新颖的方面是，动力学在一个简单复合体上产生了一个多值映射，一个“见证映射”。算法中多个参数的选择将基于持久同源性，以前仅为分析静态数据集和单个参数而开发。最终目标是对来自“黑箱”源的有限数据流进行鲁棒和快速的状态检测。