Change Point Detection for Data with Network Structure

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

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.