Asymptotically Optimal Quickest Change Detection in Distributed Sensor Systems

Abstract

In the standard formulation of the quickest change-point detection problem, a sequence of observations, whose distribution changes at some unknown point in time, is available to a decision maker, and the goal is to detect this change as quickly as possible, subject to false alarm constraints. In this paper, we study the quickest change detection problem in the setting where the information available for decision-making is distributed across a set of geographically separated sensors, and only a compressed version of observations in sensors may be used for final decision-making due to communication bandwidth constraints. We consider the minimax, uniform, and Bayesian versions of the optimization problem, and we present asymptotically optimal decentralized quickest change detection procedures for two scenarios. In the first scenario, the sensors send quantized versions of their observations to a fusion center where the change detection is performed based on all the sensor messages. In the second scenario, the sensors perform local change detection and send their final decisions to the fusion center for combining. We show that our decentralized procedures for the latter scenario have the same first-order asymptotic performance as the corresponding centralized procedures that have access to all of the sensor observations. We also present simulation results for examples involving Gaussian and Poisson observations. These examples show that although the procedures with local decisions are globally asymptotically optimal as the false alarm rate (or probability) goes to zero, they perform worse than the corresponding decentralized procedures with binary quantization at the sensors, unless the false alarm rate (or probability) is unreasonably small.     

Asymptotically Optimal Methods of Early Change-Point Detection

Abstract

Based on the excellent review and numerical study presented by Professor T. N. Sriram and Professor R. Iaci, another sequential problem for autoregressive processes is discussed.     

Detection of Changes of a Multinomial Process Where the Probability Structure Before and After the Change Is Unknown

Abstract

We look at a multinomial distribution where the probabilities of landing in each category change at some unknown integer. We assume that the probability structure both before and after the change is unknown, and the problem is to find the probability that the probability structure has changed. For a loss function consisting of the cost of late detection and a penalty for early stopping, we develop, using dynamic programming, the one- and two-step look-ahead Bayesian stopping rules. We provide some numerical results to illustrate the effectiveness of the detection procedures.     

U-Statistics in Sequential Tests and Change Detection

Abstract

Research on U-statistics within the general framework of sequential and change-point literature is surveyed. Some recent developments are discussed and extended. New sequential testing strategies based on Wiener process approximations are proposed, and empirical studies explore the finite sample performance of these tests. It allows users to choose one that is appropriate for their application.     

Sequential Change-Point Detection Procedures That are Nearly Optimal and Computationally Simple

Abstract

Sequential schemes for detecting a change in distribution often require that all of the observations be stored in memory. Lai (1995 Lai , T. L. ( 1995 ). Sequential Changepoint Detection in Quality Control and Dynamical Systems , Journal of Royal Statistical Society, Series B 57 : 613 – 658 . [Google Scholar], Journal of Royal Statistical Society, Series B 57: 613–658) proposed a class of detection schemes that enable one to retain a finite window of the most recent observations, yet promise first-order optimality. The asymptotics are such that the window size is asymptotically unbounded. We argue that what's of computational importance isn't having a finite window of observations, but rather making do with a finite number of registers. We illustrate in the context of detecting a change in the parameter of an exponential family that one can achieve eventually even second-order asymptotic optimality through using only three registers for storing information of the past. We propose a very simple procedure, and show by simulation that it is highly efficient for typical applications.     

Detection of Changes of Multiple Poisson Processes Monitored at Discrete Time Points Where the Arrival Rates are Unknown

Abstract

We observe a Poisson process in several categories where the arrival rates in each category change at some unknown integer. For some of these categories the arrival rates increase, whereas in other categores the arrival rates decrease. The point at which the process changes may be different for each category. We assume that both the arrival rates for each category as well as the change-point are unknown. We develop procedures for detecting when a change has occurred in at least one of these categories. We provide some numerical results to illustrate the effectiveness of the detection procedures.     

Bayesian Detection of Changes of a Poisson Process Monitored at Discrete Time Points Where the Arrival Rates are Unknown

Abstract

We look at a Poisson process where the arrival rate changes at some unknown integer. At each integer, we count the number of arrivals that happened in that time interval. We assume that the arrival rates before and after the change are unknown. For a loss function consisting of the cost of late detection and a penalty for early stopping, we develop, using dynamic programming, the one- and two-step look-ahead Bayesian stopping rules. We provide some numerical results to illustrate the effectiveness of the detection procedures.     

A Comparison of 2-CUSUM Stopping Rules for Quickest Detection of Two-Sided Alternatives in a Brownian Motion Model

Abstract

This work compares the performance of all existing 2-CUSUM stopping rules used in the problem of sequential detection of a change in the drift of a Brownian motion in the case of two-sided alternatives. As a performance measure, an extended Lorden criterion is used. According to this criterion, the optimal stopping rule is an equalizer rule. This paper compares the performance of the modified drift harmonic mean 2-CUSUM equalizer rules with the performance of the best classical 2-CUSUM equalizer rule whose threshold parameters are chosen so that equalization is achieved. This comparison is made possible through the derivation of a closed-form formula for the expected value of a general classical 2-CUSUM stopping rule.     

Sequential Detection of Change-Points in Linear Models

Abstract

A new method for sequential detection of change-points in multivariate linear models is proposed. The main performance characteristics of this method are analyzed theoretically for finite sample volumes. Comparison with other well known methods for sequential detection of structural changes in linear models is carried out via Monte Carlo tests. Practical applications for the analysis of stability of the German quarterly model of demand for money (1961–1995) and the Russian monthly model of inflation (1994–2005) are considered.     

Optimal two-sided group sequential tests

We derive two-sided group sequential tests for normal responses with known variance which minimise expected sample size; minimisation is at a single value of the normal mean or integrated with respect to a normal density. In deriving these tests we use a method analogous to that used by Eales and Jennison (1992) to compute optimal one-sided tests. We present a comparison of our optimal tests with existing tests.     

Asymptotically optimal procedures in multivariate Bayesian sequential estimation

In this article, we consider the problem of multivariate Bayesian sequential estimation of the unknown mean vector. We propose a robust sequential procedure without using the prior information or any auxiliary data, which is similar to multivariate non-Bayesian sequential estimation by M. Ghosh et al. (1976 Ghosh, M., Sinha, B. K., and Mukhopadhyay, N. (1976). Multivariate Sequential Point Estimation, Journal of Multivariate Analysis 6: 281–294.[Crossref], [Web of Science ®] , [Google Scholar]). The proposed procedure, depending only on the present data but not on its distribution, is shown to be asymptotically as well as or better than the optimal fixed-sample-size procedures for the arbitrary distributions and asymptotically pointwise optimal and asymptotically optimal for multivariate exponential family with a large class of prior distributions.     

Off-Line Detection of Multiple Change Points by the Filtered Derivative with p-Value Method

Abstract

This article deals with off-line detection of change points, for time series of independent observations, when the number of change points is unknown. We propose a sequential analysis method with linear time and memory complexity. Our method is based, on a filtered derivative method that detects the right change points as well as false ones. We improve the filtered derivative method by adding a second step in which we compute the p-values associated to every single potential change point. Then, we eliminate false alarms; that is, the change points that have p-values smaller than a given critical level. Next, we apply our method and penalized least squares criterion procedure to detect change points on simulated data sets and then we compare them. Eventually, we apply the filtered derivative with p-value method to the segmentation of heartbeat time series, and the detection of change points in the average daily volume of financial time series.     

Change-Point Detection in Binomial Thinning Processes,with Applications in Epidemiology

Abstract

Most of the classical change-point detection schemes are designed for the sequences of independent and identically distributed (i.i.d.) random variables. In this article, motivated by the outbreak of 2009 H1N1 pandemic influenza, we develop change-point detection procedures for the susceptible–infected–recovered (SIR) epidemic model, where a change-point in the infection rate parameter signifies either the beginning or the end of an epidemic trend.

The considered model falls into a general class of binomial thinning processes, which is a Markov chain. The cumulative sum (CUSUM) change-point detection procedure is developed for this class, and its performance is evaluated. Apparently, the CUSUM stopping rule is no longer optimal for this non-i.i.d. case. It can be improved by introducing a non constant adaptive threshold. The resulting modified scheme attains a shorter mean delay and at the same time a longer expected time of a false alarm, given that a false alarm eventually occurs.

Proposed detection procedures are applied to the 2001–2012 influenza data published by the Centers for Disease Control and Prevention.     

Detection of Stationary Errors in Multiple Regressions with Integrated Regressors and Cointegration

Abstract

This article studies the problem of detecting sequentially stationary error terms in a multiple regression model with a difference-stationary multivariate I(1)-regressor. The detection of cointegration is covered as a special case. We provide the asymptotic distribution theory for a monitoring procedure that is related to a well-known nonparametric unit root test statistic calculated from sequentially updated least squares residuals. Functional limit theorems for the corresponding sequential processes and central limit theorems for the detectors used to raise an alarm are established under the no-change null hypothesis as well as under change-point models covering a change to I(0)-errors and a change of the regression coefficients as well. We also discuss extensions to the case that continuous time processes are discretely sampled to obtain the data allowing to apply the procedures to high-frequency data as well. Our results show that we can handle the infill asymptotics assuming that nonstationary continuous-time processes such as semimartingales are discretely observed, by virtue of the general assumptions that we impose. The finite sample properties are investigated by a simulation study.     

Detection of Multiple Blockages in Parallelized Microreactors

In a plant consisting of parallelized microreactors (MRs), the product quality is lowered because of a lack of flow uniformity among them when blockage occurs. It is not practical to install sensors in every MR from the viewpoint of cost when detecting the blocked MRs. In the previous study, the multiple blockage detection (MBD) method using a small number of sensors was proposed, but its performance became low when the number of sensors decreased. Here, the conventional algorithm for MBD is improved by considering the process behavior on blockage occurrence, and the effectiveness of the improved algorithm is demonstrated through a numerical case study. The effects of flow distributor types and sensor types on the MBD performance are numerically investigated.     

Kullback-Leibler Approach to CUSUM Quickest Detection Rule for Markovian Time Series

Abstract

Optimality properties of decision procedures are studied for the quickest detection of a change-point of parameters in autoregressive and other Markov type sequences. The limit of the normalized conditional log-likelihood ratios is shown to exist for Markov chains satisfying the ergodic theorem of information theory. Then closed-form expressions for this limit are derived by making use of the time average rate of Kullback-Leibler divergence. The good properties of the detection procedures based on a sequential analysis approach are proven to hold thanks to geometric ergodicity properties of the observation processes. In particular, the window-limited CUSUM rule is shown to be optimal for detecting the disruption point in autoregressive models. Sparre Andersen models are specifically studied.     

Sequential detection of three-dimensional signals under dependent noise

We study detection methods for multivariable signals under dependent noise. The main focus is on three-dimensional signals; that is, on signals in the space–time domain. Examples for such signals are multifaceted. They include geographic and climatic data as well as image data that are observed over a fixed time horizon. We assume that the signal is observed as a finite block of noisy samples whereby we are interested in detecting changes from a given reference signal. Our detector statistic is based on a sequential partial sum process, related to classical signal decomposition and reconstruction approaches applied to the sampled signal. We show that this detector process converges weakly under the no change null hypothesis that the signal coincides with the reference signal, provided that the spatial–temporal partial sum process associated with the random field of the noise terms disturbing the sampled signal converges to a Brownian motion. More generally, we also establish the limiting distribution under a wide class of local alternatives that allows for smooth as well as discontinuous changes. Our results also cover extensions to the case in which the reference signal is unknown. We conclude with an extensive simulation study of the detection algorithm.     

Construction of an Optimal Sequential Plan for Testing a Treatment for an Adverse Effect

Abstract

Classical sequential procedures that collect a single observation at a time are often found impractical, expensive, and time consuming. Sequentially planned procedures, or simply sequential plans, extend and generalize the concepts of sequential analysis by allowing observations to be collected in groups of variable sizes. After every group, all of the previously collected data are used to determine the next course of action. An optimal (Bayes) sequential plan minimizes the (Bayes) risk function that combines the decision loss, observation (variable) cost, and group (fixed) cost. In general, determining the optimal sequential plan remains an open and challenging problem mainly because it requires risk optimization over a huge and rather unstructured set of all sequential plans. This article demonstrates how to obtain the optimal solution for a particular class of problems that may arise in testing a treatment for a rare but severe adverse effect. This solution is obtained by studying a number of properties of the Bayes sequential plan such as transitivity and monotonicity. This allows one to reduce the search to a small, manageable set of sequential plans within which the optimal plan can be calculated.     

Tests for Change in a Mean Function when the Data are Dependent

Detecting changes in the mean of a stochastic process is important in many areas, including quality control. We develop powerful omnibus tests for the null hypothesis that the underlying mean is constant. The proposed tests can be applied to test for any kind of change, whether it be abrupt, smooth or cyclical. Nonparametric function estimation techniques are used in deriving these tests. The test statistics are derived from a Fourier series smoother that minimizes an estimate of mean integrated squared error.
An important example of correlated data is that arising from a stationary time series. To obtain a valid test of mean constancy, it is necessary to estimate the spectrum of the error process, and we consider various methods of doing this. We have found that, in the case of an AR(1) model, the spectrum is well estimated if local linear smoothing is used in conjunction with generalized least squares. A power study of the proposed tests is done by simulation when the errors follow an AR(1) model, and the tests are applied to a set of astronomy data.     

Data-Efficient Minimax Quickest Change Detection in a Decentralized System

Abstract

A sensor network is considered where a sequence of random variables is observed at each sensor. At each time step, a processed version of the observations is transmitted from the sensors to a common node called the fusion center. At some unknown point in time the distribution of the observations at all of the sensor nodes changes. The objective is to detect this change in distribution as quickly as possible, subject to constraints on the false alarm rate and the cost of observations taken at each sensor. Minimax problem formulations are proposed for the above problem. A data-efficient algorithm is proposed in which an adaptive sampling strategy is used at each sensor to control the cost of observations used before change. To conserve the cost of communication an occasional binary digit is transmitted from each sensor to the fusion center. It is shown that the proposed algorithm is globally asymptotically optimal for the proposed formulations, as the false alarm rate goes to zero.