Author's response

This article contains the author's responses to the five discussion papers commenting on the results presented in Nikiforov (2016 Nikiforov, I. V. (2016). Sequential Detection/Isolation of Abrupt Changes, Sequential Analysis 35: 268–301.[Taylor &; Francis Online] , [Google Scholar]). The quickest detection/isolation of abrupt changes is the generalization of the quickest detection of abrupt changes to the case of M post-change hypotheses. It is necessary to detect the change in distribution as soon as possible and to indicate which hypothesis is true after a change occurs.     

Multidecision Quickest Change-Point Detection: Previous Achievements and Open Problems

Abstract

The following multidecision quickest detection problem, which is of importance for a variety of applications, is considered. There are N populations that are either statistically identical or where the change occurs in one of them at an unknown point in time. Alternatively, there may be N “isolated” points/hypotheses associated with a change. It is necessary to detect the change in distribution as soon as possible and indicate which population is “corrupted” or which hypothesis is true after a change occurs. Both the false alarm rate and misidentification rate should be controlled by given (usually low) levels. We discuss performance of natural multihypothesis/multipopulation generalizations of the Page and Shiryaev-Roberts procedures, including certain asymptotically optimal properties of these tests when both the false alarm and the misidentification rates are low. Specifically, we show that under certain conditions the proposed multihypothesis detection-identification procedures asymptotically minimize the trade-off between any positive moment of the detection lag and the false alarm/misclassification rates in the worst-case scenario. At the same time, the corresponding sequential detection-identification procedures are computationally simple and can be easily implemented online in a variety of applications such as rapid detection of intrusions in large-scale distributed computer networks, target detection in cluttered environment, and detection of terrorist' malicious activity. Limitations of the existing and proposed solutions to this challenging problem are also discussed.     

Is Average Run Length to False Alarm Always an Informative Criterion?

Abstract

Apart from Bayesian approaches, the average run length (ARL) to false alarm has always been seen as the natural performance criterion for quantifying the propensity of a detection scheme to make false alarms, and no researchers seem to have questioned this on grounds that it does not always apply. In this article, we show that in the change-point problem with mixture prechange models, detection schemes with finite detection delays can have infinite ARLs to false alarm. We also discuss the implication of our results on the change-point problem with either exchangeable prechange models or hidden Markov models. Alternative minimax formulations with different false alarm criteria are proposed.     

Author's Responses

Abstract

In this rejoinder I briefly summarize my thoughts on appropriate measures of performance for evaluating change-point detection schemes, particularly the false alarm criterion. Then I address some specific issues in the light of the discussion pieces from eight experts in this field.     

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.     

Discussion on “Quickest Detection Problems: Fifty Years Later” by Albert N. Shiryaev

Abstract

Quickest detection is a fascinating area of sequential analysis that spans across various branches of science and engineering. It is a pleasure to welcome Professor Albert Shiryaev's article, which provides a comprehensive overview (both scientific and historic) of this area. In this discussion, we expand on some of the issues raised in the article that we believe require further elaboration.     

Discussion on “Sequential detection/isolation of abrupt changes” by Igor V. Nikiforov

Professor Nikiforov gave an excellent introduction to the modern theory and applications of detection/isolation. We discuss possible consequences of the “ultra-minimax” (working against the worst-worst-worst case) approach as well as some extensions and modifications of the problem.     

Sequential algorithms for moving anomaly detection in networks

Abstract

The problem of quickest moving anomaly detection in networks is studied. Initially, the observations are generated according to a prechange distribution. At some unknown but deterministic time, an anomaly emerges in the network. At each time instant, one node is affected by the anomaly and receives data from a post-change distribution. The anomaly moves across the network, and the node that it affects changes with time. However, the trajectory of the moving anomaly is assumed to be unknown. A discrete-time Markov chain is employed to model the unknown trajectory of the moving anomaly in the network. A windowed generalized likelihood ratio–based test is constructed and is shown to be asymptotically optimal. Other detection algorithms including the dynamic Shiryaev-Roberts test, a quickest change detection algorithm with recursive change point estimation, and a mixture cumulative sum (CUSUM) algorithm are also developed for this problem. Lower bounds on the mean time to false alarm are developed. Numerical results are further provided to compare their performances.     

Data-Efficient Quickest Change Detection with On–Off Observation Control

Abstract

In this article we extend Shiryaev's quickest change detection formulation by also accounting for the cost of observations used before the change point. The observation cost is captured through the average number of observations used in the detection process before the change occurs. The objective is to select an on–off observation control policy that decides whether or not to take a given observation, along with the stopping time at which the change is declared, to minimize the average detection delay, subject to constraints on both the probability of false alarm and the observation cost. By considering a Lagrangian relaxation of the constraint problem and using dynamic programming arguments, we obtain an a posteriori probability-based two-threshold algorithm that is a generalized version of the classical Shiryaev algorithm. We provide an asymptotic analysis of the two-threshold algorithm and show that the algorithm is asymptotically optimal—that is, the performance of the two-threshold algorithm approaches that of the Shiryaev algorithm—for a fixed observation cost, as the probability of false alarm goes to zero. We also show, using simulations, that the two-threshold algorithm has good observation cost-delay trade-off curves and provides significant reduction in observation cost compared to the naïve approach of fractional sampling, where samples are skipped randomly. Our analysis reveals that, for practical choices of constraints, the two thresholds can be set independent of each other: one based on the constraint of false alarm and another based on the observation cost constraint alone.     

Quickest detection of an accumulated state-dependent change point

Abstract

Motivated by the practical investigation of a state-dependent quickest detection problem in continuous time, especially for Brownian observations, we propose an asymptotic scheme in discrete time called a quickest detection scheme of an accumulated state-dependent change point. Here the state-dependent means that the priori probability of the change point depends on the current state. We reduce the problem to finding an optimal stopping time of a vector-valued Markov process. We illustrate the scheme via a numerical example.     

Quickest Detection with Discretely Controlled Observations

Abstract

We study a continuous-time Bayesian quickest detection problem in which observation times are a scarce resource. The agent, limited to making a finite number of discrete observations, must adaptively decide his observation strategy to minimize detection delay and the probability of false alarm. Under two different models of observation rights, we establish the existence of optimal strategies and formulate an algorithmic approach to the problem via jump operators. We describe algorithms for these problems and illustrate them with some numerical results. As the number of observation rights tends to infinity, we also show convergence to the classical continuous observation problem of Shiryaev.     

Sequential Detection of Transient Changes

Abstract

This article addresses the transient change detection problem. It is assumed that a change occurs at an unknown (but nonrandom) change-point and the duration of post-change period is finite and known. A latent detection—that is, a detection that occurs after signal disappearance—is considered as a missed detection. A new optimality criterion adapted to the detection of transient changes involves the minimization of the worst-case probability of missed detection under constraint on the false alarm rate for a given period. A suboptimal sequential transient change detection algorithm is proposed. It is based on a window-limited cumulative sum (CUSUM) test. An upper bound for the worst-case probability of missed detection and a lower and an upper bound for the false alarm rate are proposed. Based on these bounds, the window-limited CUSUM test is optimized with respect to the proposed criterion. The developed algorithm and theoretical findings are applied to drinking water distribution network monitoring.     

A time-varying process monitoring approach based on iterative-updated semi-supervised nonnegative matrix factorizations

This paper proposes a new time-varying process monitoring approach based on iterative-updated semi-supervised nonnegative matrix factorizations (ISNMFs). ISNMFs are a type of semi-supervised model that constructs a semi-nonnegative matrix factorization (SNMF) model of a process using both labelled and unlabelled samples. Compared with the existing nonnegative matrix factorizations (NMFs) where NMFs are referred to as matrix factorization algorithms that factorize a nonnegative matrix into two low-rank nonnegative matrices whose product can well approximate the original nonnegative matrix, ISNMFs have advantages in terms of the model update and the use of labelled samples. The ISNMFs-based process monitoring approach concerns fault detection and isolation and updates an SNMF model iteratively using the latest samples to capture the change of statistical property of time-varying processes. Moreover, the proposed fault detection and isolation approach is supported by the k-means algorithm in theory. At last, we demonstrate the superiority of ISNMFs over the existing NMFs in terms of fault detection and isolation through a case study on the penicillin fermentation process.     

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.     

Nonparametric change-point detection for two populations

Suppose F and G are unknow continuous distributions and one can observe sequential a series of independent random vectors (X₁,Y₁),(X₂,Y₂),...such that (X_i,Y_i)'s initially have distribution F×F and at some unknow time their distribution may become F×G. Namely,a change in the distribution of the Y observations may occur for some reason, while the X observation maintain their distribution. We coinsider the case where the X observation maintain their distribution We consider the case where the post-change distribution is a Lehmann alternative of F, i.e.., G = F^δ for some δ > 0. The problem is to detect the change as soon as possible after its occurrence, subject to constriant on the rate of false alarms Let Aⁿ _k denote the likehood ratio of the ranks of the combined data(X₁,...,X_n,Y₁,...,Y_n) for the test of no change versus na change to a Lehmann alternative at k+1 in the Y sequence. We consider the nonparmetric Shiryaev-Roberts stopping rule based on Aⁿ _k and compute its average run length to dectection by decoupling method     

Design and assessment of delay timer alarm systems for nonlinear chemical processes

In process and manufacturing industries, alarm systems play a critical role in ensuring safe and efficient operations. The objective of a standard industrial alarm system is to detect undesirable deviations in process variables as soon as they occur. Fault detection and diagnosis systems often need to be alerted by an industrial alarm system; however, poorly designed alarms often lead to alarm flooding and other undesirable events. In this article, we consider the problem of industrial alarm design for processes represented by stochastic nonlinear time‐series models. The alarm design for such complex processes faces three important challenges: (1) industrial processes exhibit highly nonlinear behavior; (2) state variables are not precisely known (modeling error); and (3) process signals are not necessarily Gaussian, stationary or uncorrelated. In this article, a procedure for designing a delay timer alarm configuration is proposed for the process states. The proposed design is based on minimization of the rate of false and missed alarm rates—two common performance measures for alarm systems. To ensure the alarm design is robust to any non‐stationary process behavior, an expected‐case and a worst‐case alarm designs are proposed. Finally, the efficacy of the proposed alarm design is illustrated on a non‐stationary chemical reactor problem. © 2017 American Institute of Chemical Engineers AIChE J, 63: 77–90, 2018     

An Accurate Method for Determining the Pre-Change Run Length Distribution of the Generalized Shiryaev-Roberts Detection Procedure

Abstract

Change-of-measure is a powerful technique in wide use across statistics, probability, and analysis. Particularly known as Wald's likelihood ratio identity, the technique enabled the proof of a number of exact and asymptotic optimality results pertaining to the problem of quickest change-point detection. Within the latter problem's context we apply the technique to develop a numerical method to compute the generalized Shiryaev–Roberts (GSR) detection procedure's pre-change run length distribution. Specifically, the method is based on the integral equations approach and uses the collocation framework with the basis functions chosen to exploit a certain change-of-measure identity and a specific martingale property of the GSR procedure's detection statistic. As a result, the method's accuracy and robustness improve substantially, even though the method's theoretical rate of convergence is shown to be merely quadratic. A tight upper bound on the method's error is supplied as well. The method is not restricted to a particular data distribution or to a specific value of the GSR detection statistic's head start. To conclude, we offer a case study to demonstrate the proposed method at work, drawing particular attention to the method's accuracy and its robustness with respect to three factors: (1) partition size (rough vs. fine), (2) change magnitude (faint vs. contrast), and (3) average run length (ARL) to false alarm level (low vs. high). Specifically, assuming independent standard Gaussian observations undergoing a surge in the mean, we employ the method to study the GSR procedure's run length's pre-change distribution, its average (i.e., the usual ARL to false alarm), and its standard deviation. As expected from the theoretical analysis, the method's high accuracy and robustness with respect to the foregoing three factors are confirmed experimentally. We also comment on extending the method to handle other performance measures and other procedures.     

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.