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.     

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.     

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.     

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.     

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.     

Sequential detection/isolation of abrupt changes

The quickest multidecision change detection/isolation problem is the generalization of the quickest changepoint detection problem 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. Both the rate of false alarms and the misidentification (false isolation) rate should be controlled by given levels. Several detection/isolation procedures that asymptotically minimize the tradeoff between the expected detection delay and the false alarm/false isolation rates in the worst-case scenario are discussed.     

Sequential Anomaly Detection in Wireless Sensor Networks and Effects of Long-Range Dependent Data

Abstract

Anomaly detection is important for the correct functioning of wireless sensor networks. Recent studies have shown that node mobility along with spatial correlation of the monitored phenomenon in sensor networks can lead to observation data that have long range dependency, which could significantly increase the difficulty of anomaly detection. In this article, we develop an anomaly detection scheme based on multiscale analysis of the long-range dependent traffic to address this challenge. In this proposed detection scheme, the discrete wavelet transform is used to approximately de-correlate the traffic data and capture data characteristics in different timescales. The remaining dependencies are then captured by a multilevel hidden Markov model in the wavelet domain. To estimate the model parameters, we develop an online discounting expectation maximization (EM) algorithm, which also tracks variations of the estimated models over time. Network anomalies are detected as abrupt changes in the tracked model variation scores. Statistical properties of our detection scheme are evaluated numerically using long-range dependent time series. We also evaluate our detection scheme in malicious scenarios simulated using the NS-2 network simulator.     

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.     

Online Change Detection for a Poisson Process with a Phase-Type Change-Time Prior Distribution

Abstract

We consider a change detection problem in which the arrival rate of a Poisson process changes suddenly at some unknown and unobservable disorder time. It is assumed that the prior distribution of the disorder time is known. The objective is to detect the disorder time with an online detection rule (a stopping time) in a way that balances the frequency of false alarms and detection delay. So far in the study of this problem, the prior distribution of the disorder time is taken to be exponential distribution for analytical tractability. Here, we will take the prior distribution to be a phase-type distribution, which is the distribution of the absorption time of a continuous time Markov chain with a finite state space. We find an optimal stopping rule for this general case. We illustrate our findings on two numerical examples.     

Bayesian Quickest Detection in Sensor Arrays

Abstract

We study Bayesian quickest detection problems with sensor arrays. An underlying signal is assumed to gradually propagate through a network of several sensors, triggering a cascade of interdependent change-points. The aim of the decision maker is to centrally fuse all available information to find an optimal detection rule that minimizes Bayes risk. We develop a tractable continuous-time formulation of this problem focusing on the case of sensors collecting point process observations and monitoring the resulting changes in intensity and type of observed events. Our approach uses methods of nonlinear filtering and optimal stopping and lends itself to an efficient numerical scheme that combines particle filtering with a Monte Carlo–based approach to dynamic programming. The developed models and algorithms are illustrated with plenty of numerical examples.     

Temperature control during microwave heating process by sliding mode neural network

In microwave heating applications, Lambert’s law is a common way to calculate power distribution. However, because of the complex application environment, Lambert’s law is not precise for the unknown power distribution on material surfaces. During the microwave heating process, the system process parameters can only be partly known by experience. Therefore, for such situations, to make the entire heating process safe, a sliding mode combined with a neural network algorithm is proposed. The algorithm is designed to calculate the suitable input power at each control period to make the material temperature follow the reference trajectory, which is determined by experience. The simulation and actual application results demonstrate that the proposed algorithm can commendably control the heating process. The difference between the reference trajectory and the material sampling temperature may exceed 1°C initially. However, as time progresses, the difference gradually decreases. Nonetheless, due to the low conduction coefficient, a single microwave heating process may take a long time. Therefore, many actual applications combine convective heat transfer with microwave. This article also discusses the control method of multiple inputs including microwave power and convective heat transfer with unknown model parameters. Another neural network is constructed to identify the unknown parameters. The algorithm is designed to obtain the suitable input power and input convective heat transfer at each control period. The simulation results show that the control algorithm can work well under multiple inputs. The material temperature on both the surfaces and the interior can follow the reference trajectory with a satisfactory difference, and suitable inputs can be obtained with few fluctuations during the learning process.     

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.     

Quickest Detection of Changes in the Generating Mechanism of a Time Series via the ε-Complexity of Continuous Functions

Abstract

A novel methodology for the quickest detection of abrupt changes in the generating mechanisms (stochastic, deterministic, or mixed) of a time series, without any prior knowledge about them, is developed. This methodology has two components: the first is a novel concept of the ε-complexity and the second is a method for the quickest change point detection (Darkhovsky, 2013 Darkhovsky , B. S. ( 2013 ). Detection of Changes in Random Sequence with Minimum Priori Information, Theory of Probability and Its Applications 58:585–590. (in Russian)  [Google Scholar]). The ε-complexity of a continuous function given on a compact segment is defined. The expression for the ε-complexity of functions with the same modulus of continuity is derived. It is found that, for the Hölder class of functions, there exists an effective characterization of the ε-complexity. The conjecture that the ε-complexity of an individual function from the Hölder class has a similar characterization is formulated. The algorithm for the estimation of the ε-complexity coefficients via finite samples of function values is described. The second conjecture that a change of the generating mechanism of a time series leads to a change in the mean of the complexity coefficients, is formulated. Simulations to support our conjectures and verify the efficiency of our quickest change point detection algorithm are performed.     

Classifying Acoustic Signatures Using the Sequential Probability Ratio Test

Abstract

Acoustic sensors can provide real time information about moving targets. The acoustic information is typically processed sequentially, allowing the sequential probability ratio test (SPRT) to be used as the basis to solve the target identification problem. The SPRT keeps gathering observations only as long as the statistical test has a value between the upper stopping boundary and the lower stopping boundary. When the test goes above the upper boundary or below the lower boundary, the system can make a decision. The desired false alarm error rate and the desired missed detection error rate determine the upper and lower stopping boundaries. We present extensions to the sequential probability ratio test to handle problems of dependence, contamination, and the unknown class. We also present results for using the SPRT for target identification using acoustic information.     

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.     

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.     

Bayesian sequential joint detection and estimation

Abstract

Joint detection and estimation refers to deciding between two or more hypotheses and, depending on the test outcome, simultaneously estimating the unknown parameters of the underlying distribution. This problem is investigated in a sequential framework under mild assumptions on the underlying random process. We formulate an unconstrained sequential decision problem, whose cost function is the weighted sum of the expected run-length and the detection/estimation errors. Then, a strong connection between the derivatives of the cost function with respect to the weights, which can be interpreted as Lagrange multipliers, and the detection/estimation errors of the underlying scheme is shown. This property is used to characterize the solution of a closely related sequential decision problem, whose objective function is the expected run-length under constraints on the average detection/estimation errors. We show that the solution of the constrained problem coincides with the solution of the unconstrained problem with suitably chosen weights. These weights are characterized as the solution of a linear program, which can be solved using efficient off-the-shelf solvers. The theoretical results are illustrated with two example problems, for which optimal sequential schemes are designed numerically and whose performance is validated via Monte Carlo simulations.     

基于LSTM时间序列重建的生产装置异常检测

工业生产装置通常设置传感器报警阈值进行报警，但是对处于报警阈值以下的时间序列异常难以及时捕捉。基于统计的传统检测方法在解决时间序列异常检测上存在很大挑战，因此提出基于long short term memory (LSTM)时间序列重建的方法进行生产装置的异常检测。该算法首先引入一层LSTM网络对传感器数据的时间序列进行向量表示，采用另一层LSTM网络对时间序列进行逆序重建，然后利用重建值与实际值之间的误差，通过极大似然估计方法对该段序列进行异常概率估计，最终通过学习异常报警阈值实现时间序列异常检测。采用ECG测试数据、能源数据与危险品储罐传感器数据进行了仿真实验，验证了所提方法在不同长度的数据上的有效性。     

Optimization‐Based Nonlinear Centralized Controller Tuning of Liquid‐Liquid Extraction Processes

Abstract

The control problem of an agitated contactor is considered in this work. A Scheibel extraction column is modeled using the non‐equilibrium backflow mixing cell model. Model dynamic analysis shows that this process is highly nonlinear, thus the control problem solution of such a system needs to tackle the process nonlinearity efficiently. The control problem of this process is solved by developing a multivariable nonlinear control system implemented in MATLAB?. In this control methodology, a new controller tuning method is adopted, in which the time‐domain control parameter‐tuning problem is solved as a constrained optimization problem. A MIMO (multi‐input multi‐output) PI controller structure is used in this strategy. The centralized controller uses a 2×2 transfer function and accounts for loops interaction. The controller parameters are tuned using an optimization‐based algorithm with constraints imposed on the process variables reference trajectories. Incremental tuning procedure is performed until the extractor output variables transient response satisfies a preset uncertainty which bounds around the reference trajectory. A decentralized model‐based IMC (internal model control) control strategy is compared with the newly developed centralized MIMO PI control one. Stability and robustness tests are applied to the two algorithms. The performance of the MIMO PI controller is found to be superior to that of the conventional IMC controller in terms of stability, robustness, loops interaction handling, and step‐change tracking characteristics.     

Power of the MOSUM test for online detection of a transient change in mean

Abstract

In this article we discuss an online moving sum (MOSUM) test for detection of a transient change in the mean of a sequence of independent and identically distributed (i.i.d.) normal random variables. By using a well-developed theory for continuous time Gaussian processes and subsequently correcting the results for discrete time, we provide accurate approximations for the average run length (ARL) and power of the test. We check theoretical results against simulations, compare the power of the MOSUM test with that of the cumulative sum (CUSUM), and briefly consider the cases of nonnormal random variables and weighted sums.