The problem of robust quickest change detection (QCD) in non-stationary processes under a multi-stream setting is studied. In classical QCD theory, optimal solutions are developed to detect a sudden change in the distribution of stationary data. Most studies have focused on single-stream data. In non-stationary processes, the data distribution both before and after a change varies with time and is not precisely known. The multi-stream or multi-dimensional nature of the data further complicates the issue. It is shown that if the non-stationary family for each dimension or stream has a least favorable law (LFL) or distribution in a well-defined sense, then the algorithm designed using the LFLs is robust optimal. The notion of LFL defined in this work differs from the classical definitions due to the dependence of the post-change model on the change point. Examples of multi-stream non-stationary processes encountered in public health monitoring and aviation applications are provided. Our robust algorithm is applied to simulated and real data to show its effectiveness.

Methods in the field of quickest change detection rapidly detect in real-time a change in the data-generating distribution of an online data stream. Existing methods have been able to detect this change point when the densities of the pre-and post-change distributions are known. Recent work has extended these results to the case where the pre-and post-change distributions are known only by their score functions. This work considers the case where the pre-and post-change score functions are known only to correspond to distributions in two disjoint sets. This work selects a pair of least-favorable distributions from these sets to robustify the existing score-based quickest change detection algorithm, the properties of which are studied. This paper calculates the least-favorable distributions for specific model classes and provides methods of estimating the leastfavorable distributions for common constructions. Simulation results are provided demonstrating the performance of our robust change detection algorithm.

Classical quickest change detection algorithms require modeling pre-change and post-change distributions. Such an approach may not be feasible for various machine learning models because of the complexity of computing the explicit distributions. Additionally, these methods may suffer from a lack of robustness to model mismatch and noise. This paper develops a new variant of the classical Cumulative Sum (CUSUM) algorithm for the quickest change detection. This variant is based on Fisher divergence and the Hyvärinen score and is called the Hyvärinen score-based CUSUM (SCUSUM) algorithm. The SCUSUM algorithm allows the applications of change detection for unnormalized statistical models, i.e., models for which the probability density function contains an unknown normalization constant. The asymptotic optimality of the proposed algorithm is investigated by deriving expressions for average detection delay and the mean running time to a false alarm. Numerical results are provided to demonstrate the performance of the proposed algorithm.

Classical change detection algorithms typically require modeling pre-change and post-change distributions. The calculations may not be feasible for various machine learning models because of the complexity of computing the partition functions and normalized distributions. Additionally, these methods may suffer from a lack of robustness to model mismatch and noise. In this paper, we develop a new variant of the classical Cumulative Sum (CUSUM) change detection, namely Score-based CUSUM (SCUSUM), based on Fisher divergence and the Hyvärinen score. Our method allows the applications of the quickest change detection for unnormalized distributions. We provide a theoretical analysis of the detection delay given the constraints on false alarms. We prove the asymptotic optimality of the proposed method in some particular cases. We also provide numerical experiments to demonstrate our method’s computation, performance, and robustness advantages.

Detecting an abrupt and persistent change in the underlying distribution of online data streams is an important problem in many applications. This paper proposes a new robust score-based algorithm called RSCUSUM, which can be applied to unnormalized models and addresses the issue of unknown post-change distributions. RSCUSUM replaces the Kullback-Leibler divergence with the Fisher divergence between pre- and post-change distributions for computational efficiency in unnormalized statistical models and introduces a notion of the “least favorable” distribution for robust change detection. The algorithm and its theoretical analysis are demonstrated through simulation studies.

This paper investigates the practical engineering problem of traffic sensors placement on stretched highways with ramps. Since it is virtually impossible to install bulky traffic sensors on each highway segment, it is crucial to find placements that result in optimized network-wide, traffic observability. Consequently, this results in accurate traffic density estimates on segments where sensors arenotinstalled. The substantial contribution of this paper is the utilization of control-theoretic observability analysis—jointly with integer programming—to determine traffic sensor locations based on the nonlinear dynamics and parameters of traffic networks. In particular, the celebrated asymmetric cell transmission model is used to guide the placement strategy jointly with observability analysis of nonlinear dynamic systems through Gramians. Thorough numerical case studies are presented to corroborate the proposed theoretical methods and various computational research questions are posed and addressed. The presented approach can also be extended to other models of traffic dynamics.

An algorithm is proposed to detect and classify a change in the distribution of a stochastic process that has periodic statistical behavior. The problem is posed in the framework of independent and periodically identically distributed (i.p.i.d.) processes, a recently introduced class of processes to model statistically periodic data. It is shown that the proposed algorithm is asymptotically optimal as the rate of false alarms and the probability of misclassification goes to zero. This problem has applications in anomaly detection in traffic data, social network data, ECG data, and neural data, where periodic statistical behavior has been observed. The effectiveness of the algorithm is demonstrated by application to real and simulated data.

The problem of detecting a change in the distribution of a statistically periodic process is investigated. The problem is posed in the framework of independent and periodically identically distributed (i.p.i.d.) processes, a recently introduced class of processes to model statistically periodic data. An algorithm is proposed that is shown to be robust against an uncertainty in the post-change law. The motivation for the problem comes from event detection problems in traffic data, social network data, electrocardiogram data, and neural data, where periodic statistical behavior has been observed.

A new class of stochastic processes called independent and periodically identically distributed (i.p.i.d.) processes is defined to capture periodically varying statistical behavior. A novel Bayesian theory is developed for detecting a change in the distribution of an i.p.i.d. process. It is shown that the Bayesian change point problem can be expressed as an optimal control problem of a Markov decision process (MDP) with periodic transition and cost structures. An optimal control theory is developed for periodic MDPs for discounted and undiscounted total cost criteria. A fixed-point equation is obtained that is satisfied by the optimal cost function. It is shown that a nonstationary but periodic policy is optimal. A value iteration algorithm is obtained to compute the optimal cost function. The results from the MDP theory are then applied to detect a change in the distribution of an i.p.i.d. process. It is shown that while a stopping rule based on a periodic sequence of thresholds is exactly optimal, a single-threshold policy is asymptotically optimal, as the probability of false alarm goes to zero. Numerical results are provided to demonstrate that the asymptotically optimal policy is not strictly optimal.

A new class of stochastic processes called episodic processes is introduced to model the statistical regularity of data observed in several applications in cyberphysical systems, neuroscience, and medicine. Algorithms are proposed to detect a change in the distribution of episodic processes. The algorithms can be computed recursively using finite memory and are shown to be asymptotically optimal for well-defined Bayesian or minimax stochastic optimization formulations. The application of the developed algorithms to detect a change in waveform patterns is also discussed.

Mixture-based algorithms are proposed for detecting a change in the distribution of a statistically periodic process in multislot and multistream settings. In the multislot change detection problem, the distribution of the observed process can change in any subset of time slots in each period. In the multistream change detection problem, there are parallel streams of observations, and the change can affect an arbitrary subset of streams. It is shown that the algorithms are asymptotically optimal in a Bayesian setting.

A new class of stochastic processes called independent and periodically identically distributed (i.p.i.d.) processes is defined to capture periodically varying statistical behavior. Algorithms are proposed to detect changes in such i.p.i.d. processes. It is shown that the algorithms can be computed recursively and are asymptotically optimal. This problem has applications in anomaly detection in traffic data, social network data, and neural data, where periodic statistical behavior has been observed.

Bayesian optimality theory is developed for quickest change detection in a class of stochastic processes called independent and periodically identically distributed (i.p.i.d.) processes. This class of processes can be used to model periodically varying statistical behavior. An algorithm called the periodic-Shiryaev algorithm is proposed and is shown to asymptotically minimize the average detection delay subject to a constraint on the probability of false alarm. It is also shown that the statistic for this algorithm can be computed recursively and using a finite amount of memory. This problem has applications in anomaly detection problems in cyber-physical systems and biology, where periodic statistical behavior has been observed.

The problem of sequential detection of anomalies in multimodal data is considered. The objective is to observe physical sensor data from CCTV cameras, and social media data from Twitter and Instagram to detect anomalous behaviors or events. Data from each modality is transformed to discrete time count data by using an artificial neural network to obtain counts of objects in CCTV images and by counting the number of tweets or Instagram posts in a geographical area. The anomaly detection problem is then formulated as a problem of quickest detection of changes in count statistics. The quickest detection problem is then solved using the framework of partially observable Markov decision processes (POMDP), and structural results on the optimal policy are obtained. The resulting optimal policy is then applied to real multimodal data collected from New York City around a 5K race to detect the race. The count data both before and after the change is found to be nonstationary in nature. The proposed mathematical approach to this problem provides a framework for event detection in such nonstationary environments and across multiple data modalities.

A macaque monkey is trained to perform two different kinds of tasks, memory aided and visually aided. In each task, the monkey saccades to eight possible target locations. A classifier is proposed for direction decoding and task decoding based on local field potentials (LFP) collected from the prefrontal cortex. The LFP time-series data is modeled in a nonparametric regression framework, as a function corrupted by Gaussian noise. It is shown that if the function belongs to Besov bodies, then the proposed wavelet shrinkage and thresholding based classifier is robust and consistent. The classifier is then applied to the LFP data to achieve high decoding performance. The proposed classifier is also quite general and can be applied for the classification of other types of time-series data as well, not necessarily brain data.

The problem of quickest detection of a change in the distribution of a n × p random matrix based on a sequence of observations having a single unknown change point is considered. The forms of the pre- and post-change distributions of the rows of the matrices are assumed to belong to the family of elliptically contoured densities with sparse dispersion matrices but are otherwise unknown. We propose a non-parametric stopping rule that is based on a novel summary statistic related to k-nearest neighbor correlation between columns of each observed random matrix. In the large scale regime of p → ∞ and n fixed we show that, among all functions of the proposed summary statistic, the proposed stopping rule is asymptotically optimal under a minimax quickest change detection (QCD) model.

The problem of quickest change detection is studied, where there is an additional constraint on the cost of observations used before the change point and where the post-change distribution is composite. Minimax formulations are proposed for this problem. It is assumed that the post-change family of distributions has a member which is least favorable in a well-defined sense. An algorithm is proposed in which ON-OFF observation control is employed using the least favorable distribution, and a generalized likelihood ratio-based approach is used for change detection. Under additional conditions on the post-change family of distributions, it is shown that the proposed algorithm is asymptotically optimal, uniformly for all possible post-change distributions.

A method to detect and isolate power system transmission line outages in near real-time is proposed. In particular, a linearized power system model is presented and a statistical model for line outage detection and isolation is developed using this model. To detect and isolate the line outage quickly, algorithms based on statistical quickest change detection are employed.

The problem of quickest change detection is studied, where there is an additional constraint on the cost of observations used before the change point and where the post-change distribution is unknown. An algorithm is proposed for the case where there are finite number of possibilities for the unknown post-change distribution. It is shown that if the post-change family of distributions satisfies some additional conditions, then the proposed algorithm is asymptotically optimal uniformly for all possible post-change distributions.

A distributed or multi-channel system consisting of multiple sensors is considered. At each sensor a sequence of observations is taken, and at each time step, a summary of available information is sent to a central decision maker, called the fusion center. At some point of time, the distribution of observations at an unknown subset of the sensor nodes changes. The objective is to detect this change as quickly as possible, subject to constraints on the false alarm rate, the cost of observations taken at the sensors and the cost of communication between the sensors and the fusion center. Minimax formulations are proposed for this problem. An algorithm called DE-Censor-Sum is proposed, and is shown to be asymptotically optimal for the proposed formulations, for each possible post-change scenario, as the false alarm rate goes to zero. It is also shown, via numerical studies, that the DE-Censor-Sum algorithm performs significantly better than the approach of fractional sampling, where the cost constraints are met based on the outcome of a sequence of biased coin tosses, independent of the observation process.

The problem of decentralized quickest change detection is studied with an additional constraint on the cost of observations used at each sensor. Minimax problem formulations are proposed for the problem. A distributed algorithm called the DE-All algorithm is proposed in which on-off observation control is employed locally at each sensor. It is shown that the proposed algorithm is asymptotically optimal up to first order for the proposed formulations.

The classical problem of quickest change detection is studied with an additional constraint on the cost of observations used in the detection process. The change point is modeled as an unknown constant, and minimax formulations are proposed for the problem. The objective in these formulations is to find a stopping time and an ON-OFF observation control policy for the observation sequence, to minimize a version of the worst possible average delay, subject to constraints on the false alarm rate and the fraction of time observations are taken before change. An algorithm called DE-CuSum is proposed and is shown to be asymptotically optimal for the proposed formulations, as the false alarm rate goes to zero. Numerical results are used to show that the DE-CuSum algorithm has good tradeoff curves and performs significantly better than the approach of fractional sampling, in which the observations are skipped using the outcome of a sequence of coin tosses, independent of the observation process. This study is guided by the insights gained from an earlier study of a Bayesian version of this problem.

In [1], a Bayesian two-threshold algorithm was obtained for quickest detection of a change in the distribution of a sequence of random variables, subject to constraints of probability of false alarm and observation cost. This algorithm was shown to be asymptotically optimal and to have good trade-off curves. In this paper, the results in [1] are extended to the more practically relevant minimax setting. Motivated by the structure of the algorithm developed in [1], a CUSUM based algorithm, called DE-CUSUM is proposed, which can be used for on-off observation control and to detect change as quickly as possible subject to a false alarm constraint. It is shown that the DE-CUSUM algorithm inherits the good qualities of the algorithm in [1], i.e., it is also asymptotically optimal and has good trade-off curves. Numerical results show that the DE-CUSUM algorithm provides a substantial savings in the observation cost over the naive approach of fractional sampling.

We propose an energy efficient distributed cooperative Change Detection scheme called DualCUSUM based on Page's CUSUM algorithm. In the algorithm, each sensor runs a CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a Multiple Access Channel (MAC) corrupted with noise. The fusion center performs another CUSUM to detect the change. The algorithm performs better than several existing schemes when energy is at a premium. We generalize the algorithm to also include nonparametric CUSUM and provide a unified analysis. Our results show that while the false alarm probability is smaller for observation distribution with a lighter tail, the detection delay is asymptotically the same for any distribution. Consequently, we provide a new viewpoint on why parametric CUSUM performs better than nonparametric CUSUM. In the process, we also develop new results on a reflected random walk which can be of independent interest.

An energy efficient distributed Change Detection scheme based on Page's CUSUM algorithm was presented in [2]. In this paper we consider a nonparametric version of this algorithm. In the algorithm in [2], each sensor runs CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a Multiple Access Channel (MAC) corrupted with noise. The fusion center performs another CUSUM to detect the change. In this paper, we generalize the algorithm to also include nonparametric CUSUM and provide a unified analysis.

We propose a simple and energy efficient distributed change detection scheme for sensor networks based on Page's parametric CUSUM algorithm. The sensor observations are IID over time and across the sensors conditioned on the change variable. Each sensor runs CUSUM and transmits only when the CUSUM is above some threshold. The transmissions from the sensors are fused at the physical layer. The channel is modeled as a multiple access channel (MAC) corrupted with IID noise. The fusion center which is the global decision maker, performs another CUSUM to detect the change. We provide the analysis and simulation results for our scheme and compare the performance with an existing scheme which ensures energy efficiency via optimal power selection.