Collaborative Research: Optimal Changepoint Detection and Identification Algorithms with Applications

协作研究：最优变点检测和识别算法及其应用

• 批准号: 0830169
• 负责人: Venugopal Veeravalli
• 金额: $ 30.6万
• 依托单位: University of Illinois at Urbana-Champaign
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2008
• 资助国家: 美国
• 起止时间: 2008-09-01 至 2013-05-31
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=0830169&HistoricalAwards=false
• 关键词: Collaborative; Research; Optimal; Changepoint; Detection

Changepoint problems deal with detecting anomalies or more generally changes in patterns. In the sequential setting, as long as the behavior of observations is consistent with the ``normal state," one is content to let the process continue. If the state changes, then one is interested in detecting that a change is in effect, usually as quickly as possible. Any detection policy may give rise to false alarms and attempting to avoid false alarms too strenuously will lead to a long delay between the time of occurrence of the change and its detection. The gist of the changepoint problem is to produce a detection policy that minimizes the average detection delay subject to a bound on the false alarm rate. While the quickest changepoint detection problem has been studied for over fifty years, there has been remarkably little prior work on theoretical extensions to general stochastic models that go beyond independent and identically distributed observations in the pre- and post-change modes, and to the distributed sensor setting. The goal of this project is to investigate the properties of known changepoint detection procedures and to develop novel procedures for change detection and classification under general system models that are relevant in practical applications, as well as to provide an analytical framework to predict their performance. The usefulness of the theoretical advances will be demonstrated through two key application areas: (a) the rapid detection of intrusions and disruptions in computer networks, and (b) the efficient monitoring of critical infrastructures. In both cases, the distributions of the noisy observations change, and this change occurs at an a priori unknown point in time. Also, in both cases, the detection should be performed in a timely manner, while keeping the false alarm rate at an acceptable level. Our results will be validated using simulations as well as real data (to the extent possible).

变更点问题处理检测异常或更普遍的模式更改。在顺序设置中，只要观察到的行为与“正常状态”一致，人们就会满足于让这个过程继续下去。如果状态发生了变化，那么人们就有兴趣检测变化是否有效，通常是尽可能快地检测。任何检测策略都可能产生假警报，过于努力地避免假警报将导致变化发生时间和检测时间之间的长时间延迟。变更点问题的要点是产生一种检测策略，使受虚警率约束的平均检测延迟最小化。虽然最快的变化点检测问题已经研究了50多年，但对于一般随机模型的理论扩展，除了在变化前和变化后模式下的独立和同分布观测之外，以及分布式传感器设置，先前的工作非常少。这个项目的目标是调查已知的变更点检测程序的特性，并在实际应用中相关的一般系统模型下开发新的变更检测和分类程序，以及提供一个分析框架来预测它们的性能。理论进展的有用性将通过两个关键应用领域得到证明：(a)快速检测计算机网络的入侵和中断，以及(b)有效监测关键基础设施。在这两种情况下，噪声观测值的分布都发生了变化，这种变化发生在一个先验的未知时间点。此外，在这两种情况下，都应及时进行检测，同时将虚警率保持在可接受的水平。我们的结果将使用模拟和真实数据进行验证（尽可能）。