Change Point Detection for Data with Network Structure

网络结构数据变点检测

• 批准号: 2348640
• 负责人: George Michailidis
• 金额: $ 30万
• 依托单位: University of California-Los Angeles
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2023
• 资助国家: 美国
• 起止时间: 2023-01-15 至 2025-07-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2348640&HistoricalAwards=false
• 关键词: Change; Point; Detection; Data; Network

Detecting breaks and anomalies in a mechanism that drives the generation of data represents a critical task, due to numerous applications in high-impact areas including health, social, and engineering sciences. This project aims to advance the state of the art of change point analysis for big and complex data, by developing a simple to implement, yet powerful, scalable algorithmic framework, thus providing new tools to examine high-dimensional, long streams for events of interest. The potential application domains of this project include but not limited to occurrence of seizure in brain connectivity data sets, coordinated market and other systemic failures in economic and finance data, and identification of orchestrated malicious activities in computer network streams. The developed algorithms and methodology will be implemented in open-source software, while curated data sets will be made available to the community for use in change point analysis investigations. The project will offer multiple unique opportunities for interdisciplinary research training of the future generation of statisticians and for further enhancement of diversity in mathematical sciences.To achieve the stated goals, the project (i) develops a unified detection framework for change points in complex statistical models for network and high dimensional time streams and (ii) provides a rigorous theoretical analysis of their accuracy in the form of consistency, finite sample bounds, and asymptotic distributions for the change points and other model parameters. The framework leverages a simple, easy to implement two-step strategy, wherein the first step one selects windows of the time series of appropriate length and using a standard exhaustive search strategy identifies at most a single change point in each of them. In the second step, a second search based on a global information criterion is employed to eliminate spurious change points. The strategy exhibits linear complexity in time (and thus matches the fastest available in the literature), yet is simple to implement and theoretically analyze, in particular for complex statistical models that exhibit network and low rank structure. Further, the following issues are rigorously addressed: (i) conditions of identifiability of the model parameters and the change points and (ii) probabilistic guarantees and uncertainty quantification for them in the presence of high dimensionality, network structure, temporal dependence, as well as dependence across data streams.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.

由于健康、社会和工程科学等高影响领域的大量应用，检测驱动数据生成的机制中的故障和异常是一项关键任务。该项目旨在通过开发一个易于实现但功能强大、可扩展的算法框架来推进大而复杂数据的变点分析的最新技术，从而提供新的工具来检查高维、长流中感兴趣的事件。该项目的潜在应用领域包括但不限于大脑连接数据集中的癫痫发作、经济和金融数据中的协调市场和其他系统性故障，以及计算机网络流中精心策划的恶意活动的识别。开发的算法和方法将在开源软件中实施，同时精选的数据集将提供给社区用于变化点分析调查。该项目将为下一代统计学家的跨学科研究培训和进一步增强数学科学的多样性提供多种独特的机会。为了实现既定目标，该项目（i）为复杂统计模型中的变化点开发了统一的检测框架对于网络和高维时间流，并且 (ii) 以一致性、有限样本界限以及变化点和其他模型参数的渐近分布的形式对其准确性进行严格的理论分析。该框架利用简单、易于实现的两步策略，其中第一步选择适当长度的时间序列的窗口，并使用标准的穷举搜索策略识别每个窗口中的至多一个变化点。在第二步中，采用基于全局信息准则的第二次搜索来消除虚假变化点。该策略表现出时间上的线性复杂性（因此与文献中可用的最快策略相匹配），但易于实现和理论上分析，特别是对于表现出网络和低秩结构的复杂统计模型。此外，还严格解决了以下问题：（i）模型参数和变化点的可识别性条件，以及（ii）在存在高维、网络结构、时间依赖性以及该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。