Data-efficient quickest change detection

Quickest Change Detection;Observation Control;Asymptotic Optimality;Bayesian;Minimax;Generalized Likelihood Ratio Test (GLRT);Sensor Networks;Multi-Channel Systems

Banerjee, Taposh

关键词: Quickest Change Detection;    Observation Control;    Asymptotic Optimality;    Bayesian;    Minimax;    Generalized Likelihood Ratio Test (GLRT);    Sensor Networks;    Multi-Channel Systems;   

Others  :  https://www.ideals.illinois.edu/bitstream/handle/2142/72864/Taposh_Banerjee.pdf?sequence=1&isAllowed=y

美国|英语

来源: The Illinois Digital Environment for Access to Learning and Scholarship

【 摘 要 】

In the classical problem of quickest change detection, a decision maker observes a sequence of random variables. At some point of time, the distribution of the random variables changes abruptly. The objective is to detect this change in distribution with minimum possible delay, subject to a constraint on the false alarm rate.In many applications of quickest change detection, changes are rare and there is a cost associated with taking observations or acquiring data. For such applications, the classical quickest change detection model is no longer applicable. In this dissertation we extend the classical formulations by adding anadditional penalty on the cost of observations used before the change point. The objective is to find a causal on-off observation control policy and a stopping time, to minimize the detection delay, subject to constraints on the falsealarm rate and the cost of observations used before the change point. We show that two-threshold generalizations of the classicalsingle-threshold tests are asymptotically optimal for the proposed formulations. The nature of optimality is strong in the sense that the false alarm rates of the two-threshold tests are at least as good as the false alarm rates of their classical counterparts. Also, the delays of the two-threshold tests are within a constant of the delays of their classical counterparts. These results indicate that an arbitrary but fixed fraction of observations can be skipped before change without any loss in asymptoticperformance. A detailed performance analysis of these algorithms is provided, and guidelines are given for the design of the proposed tests, on the basis of the performance analysis. An important result obtained through this analysis is that the two constraints, on the false alarm rate and the cost of observations used before the change, can be met independent of each other. Numerical studies of these two-threshold algorithms also reveal that they have good trade-off curves, and perform significantly better than the approach of fractional sampling, where classical single threshold tests are used and the constraint on the cost of observations is met by skipping observations randomly.We first study the problem in Bayesian and minimax settings and then extend the results to more general quickest change detection models, namely, model withunknown post-change distribution,a sensor network model, and a multi-channel model.