Algorithm detects changes quickly despite unknown post-change models
Robust Quickest Change Detection with Cost-Efficient Experiment Design and Unknown Post-Change Model
Information Theory
Summary
Detecting sudden changes as quickly as possible is important but hard when the exact change is unknown. This paper looks at a situation where multiple ways to test for change exist, but only one can be used at a time. The authors propose a method that works well even under the worst-case scenario within a range of possible changes. Their approach makes the detection process both efficient and reliable while controlling false alarms.
What this means in practice
- •For quality control engineers: Use the method to quickly detect defects or shifts in manufacturing processes when the exact defect patterns are not fully known.
- •For network monitoring teams: Implement the algorithm to promptly identify performance degradations or cyber attacks despite uncertain attack patterns.
Authors
Patrick Vincent Lubenia, Taposh Banerjee
Abstract
A quickest change detection problem is studied where the decision-maker has access to multiple experiments, but can choose only one experiment at a time to detect the change. The true post-change distribution under each experiment is unknown, but known to belong to a family of distributions. It is assumed that each of these families of distributions has an element that is least favorable in a well-defined sense. An algorithm is proposed that is designed using the least favorable distributions. It is shown that the algorithm is first-order asymptotically optimal, as the rate of false alarms goes to zero. This algorithm minimizes the worst-case average detection delay over all post-change distributions within the assumed families, subject to a constraint on the average run length to false alarm and constraints on the average fraction of time each experiment is performed before change.