Tag Archives: Change Detection

Reducing outliers in time series with singular spectrum analysis and use of deep learning for change detection

November 10, 2023 09:22 ,

Muktesh Gupta, Rajesh Wadhvani, Akhtar Rasool, Real-time Change-Point Detection: A deep neural network-based adaptive approach for detecting changes in multivariate time series data, Expert Systems with Applications, Volume 209, 2022 DOI: 10.1016/j.eswa.2022.118260.

The behavior of a time series may be affected by various factors. Changes in mean, variance, frequency, and auto-correlation are the most common. Change-Point Detection (CPD) aims to track down abrupt statistical characteristic changes in time series that can benefit many applications in different domains. As demonstrated in recently introduced CPD methodologies, deep learning approaches have the potential to identify more subtle changes. However, due to improper handling of data and insufficient training, these methodologies generate more false alarms and are not efficient enough in detecting change-points. In real-time CPD algorithms, preprocessed data plays a vital role in increasing the algorithm\u2019s efficiency and minimizing false alarm rates. Therefore, preprocessing of data should be a part of the algorithm, but in the existing methods, preprocessing of data is done initially, and then the whole dataset is passed to the CPD algorithm. A new three-phase architecture is proposed to address this issue, in which all phases, from preprocessing to CPD, work in an adaptive manner. The phases are integrated into a pipeline, allowing the algorithm to work in real-time. Our proposed strategy performs optimally and consistently based on performance metrics resulting from experiments on real-world datasets and artifacts. This work effectively addresses the issue of non-stationary data normalization using deep learning approaches. To reduce noise and outliers from the data, a recursive version of singular spectrum analysis is introduced. It is demonstrated that the method\u2019s performance has significantly improved by combining adaptive preprocessing with deep learning CPD techniques.

NOTE: See also C. Ma, L. Zhang, W. Pedrycz and W. Lu, “The Long-Term Prediction of Time Series: A Granular Computing-Based Design Approach,” in IEEE Transactions on Systems, Man, and Cybernetics: Systems, vol. 52, no. 10, pp. 6326-6338, Oct. 2022, doi: 10.1109/TSMC.2022.3144395.

See also https://babel.isa.uma.es/kipr/?p=1548

Posted in: Probability and statistics , Tagged: , ,

A particular application of quick detection of changes in a signal: detecting changes of voltage regimes in the electric distribution network

September 3, 2021 11:25 ,

D. Macii and D. Petri, Rapid Voltage Change Detection: Limits of the IEC Standard Approach and Possible Solutions, IEEE Transactions on Instrumentation and Measurement, vol. 69, no. 2, pp. 382-392, Feb. 2020, DOI: 10.1109/TIM.2019.2903617.

Rapid voltage changes (RVCs) are power quality (PQ) events characterized by small and fast transitions between two steady-state root-mean-square (rms) voltage levels. RVCs occur quite often at the distribution level and are expected to be even more frequent in the future due to the increasing penetration of dynamic loads and renewable-based generators in the smart grid. Unlike other PQ events, RVCs are less critical, but also more difficult to detect than dips/sags and swells, due to their smaller voltage variations. Nevertheless, they can be harmful to generators’ control systems and electronic equipment in general. Moreover, they strongly affect flicker. The IEC Standard 61000-4-3:2015 clearly describes an algorithm for RVC detection. However, this approach is poorly characterized in the scientific literature. In fact, it suffers from some drawbacks. In this paper, some of them (e.g., rate-dependent detection limits and detection delays) are analyzed in depth. In addition, an alternative approach based on the estimation of the rate of change of rms voltage is proposed. Multiple simulation results show that the approach considered is more sensitive to noise, but also faster, especially when not so fast RVCs occur. Moreover, it allows measuring the rate of change of rms voltage, which is currently disregarded in the IEC Standard.

Posted in: Electronics, Probability and statistics , Tagged:

Nice related work on change-point detection and a novel algorithm for off-line detection of abrupt changes in multivariate signals

October 23, 2020 16:09 ,

Charles Truong; Laurent Oudre; Nicolas Vayatis, Greedy Kernel Change-Point Detection, IEEE Transactions on Signal Processing ( Volume: 67, Issue: 24, Dec.15, 15 2019), DOI: 10.1109/TSP.2019.2953670.

We consider the problem of detecting abrupt changes in the underlying stochastic structure of multivariate signals. A novel non-parametric and model-free off-line change-point detection method based on a kernel mapping is presented. This approach is sequential and alternates between two steps: a greedy detection to estimate a new breakpoint and a projection to remove its contribution to the signal. The resulting algorithm is able to segment time series for which no accurate model is available: it is computationally more efficient than exact kernel change-point detection and more precise than window-based approximations. The proposed method also offers some theoretical consistency properties. For the special case of a linear kernel, an even faster implementation is provided. The proposed strategy is compared to standard parametric and non-parametric procedures on a real-world data set composed of 262 accelerometer recordings.

Posted in: Probability and statistics , Tagged: , ,

Detection of qualitative behaviours in signals

January 18, 2019 11:44 ,

Ying Tang, Alessio Franci, Romain Postoyan, On-line detection of qualitative dynamical changes in nonlinear systems: The resting-oscillation case, Automatica, Volume 100, 2019, Pages 17-28, DOI: 10.1016/j.automatica.2018.10.058.

Motivated by neuroscience applications, we introduce the concept of qualitative detection, that is, the problem of determining on-line the current qualitative dynamical behavior (e.g., resting, oscillating, bursting, spiking etc.) of a nonlinear system. The approach is thought for systems characterized by i) large parameter variability and redundancy, ii) a small number of possible robust, qualitatively different dynamical behaviors and, iii) the presence of sharply different characteristic timescales. These properties are omnipresent in neurosciences and hamper quantitative modeling and fitting of experimental data. As a result, novel control theoretical strategies are needed to face neuroscience challenges like on-line epileptic seizure detection. The proposed approach aims at detecting the current dynamical behavior of the system and whether a qualitative change is likely to occur without quantitatively fitting any model nor asymptotically estimating any parameter. We talk of qualitative detection. We rely on the qualitative properties of the system dynamics, extracted via singularity and singular perturbation theories, to design low dimensional qualitative detectors. We introduce this concept on a general class of singularly perturbed systems and then solve the problem for an analytically tractable class of two-dimensional systems with a single unknown sigmoidal nonlinearity and two sharply separated timescales. Numerical results are provided to show the performance of the designed qualitative detector.

Posted in: Systems and Signals , Tagged:

Modelling ECGs with sums of gaussians and estimating them through switching Kalman Filters and the likelihood of each mode

September 30, 2015 18:32 ,

Oster, J.; Behar, J.; Sayadi, O.; Nemati, S.; Johnson, A.E.W.; Clifford, G.D., Semisupervised ECG Ventricular Beat Classification With Novelty Detection Based on Switching Kalman Filters, in Biomedical Engineering, IEEE Transactions on , vol.62, no.9, pp.2125-2134, Sept. 2015, DOI: 10.1109/TBME.2015.2402236.

Automatic processing and accurate diagnosis of pathological electrocardiogram (ECG) signals remains a challenge. As long-term ECG recordings continue to increase in prevalence, driven partly by the ease of remote monitoring technology usage, the need to automate ECG analysis continues to grow. In previous studies, a model-based ECG filtering approach to ECG data from healthy subjects has been applied to facilitate accurate online filtering and analysis of physiological signals. We propose an extension of this approach, which models not only normal and ventricular heartbeats, but also morphologies not previously encountered. A switching Kalman filter approach is introduced to enable the automatic selection of the most likely mode (beat type), while simultaneously filtering the signal using appropriate prior knowledge. Novelty detection is also made possible by incorporating a third mode for the detection of unknown (not previously observed) morphologies, and denoted as X-factor. This new approach is compared to state-of-the-art techniques for the ventricular heartbeat classification in the MIT-BIH arrhythmia and Incart databases. F1 scores of 98.3% and 99.5% were found on each database, respectively, which are superior to other published algorithms’ results reported on the same databases. Only 3% of all the beats were discarded as X-factor, and the majority of these beats contained high levels of noise. The proposed technique demonstrates accurate beat classification in the presence of previously unseen (and unlearned) morphologies and noise, and provides an automated method for morphological analysis of arbitrary (unknown) ECG leads.

Posted in: Bayesian filtering , Tagged: , , ,

On quickest change detection when the process is modelled with HMMs

September 29, 2015 09:09 ,

Cheng-Der Fuh; Yajun Mei, Quickest Change Detection and Kullback-Leibler Divergence for Two-State Hidden Markov Models, in Signal Processing, IEEE Transactions on , vol.63, no.18, pp.4866-4878, Sept.15, 2015 DOI: 10.1109/TSP.2015.2447506

In this paper, the quickest change detection problem is studied in two-state hidden Markov models (HMM), where the vector parameter θ of the HMM changes from θ0 to θ1 at some unknown time, and one wants to detect the true change as quickly as possible while controlling the false alarm rate. It turns out that the generalized likelihood ratio (GLR) scheme, while theoretically straightforward, is generally computationally infeasible for the HMM. To develop efficient but computationally simple schemes for the HMM, we first discuss a subtlety in the recursive form of the generalized likelihood ratio (GLR) scheme for the HMM. Then we show that the recursive CUSUM scheme proposed in Fuh (Ann. Statist., 2003) can be regarded as a quasi-GLR scheme for pseudo post-change hypotheses with certain dependence structure between pre- and postchange observations. Next, we extend the quasi-GLR idea to propose recursive score schemes in the scenario when the postchange parameter θ1 of the HMM involves a real-valued nuisance parameter. Finally, the Kullback-Leibler (KL) divergence plays an essential role in the quickest change detection problem and many other fields, however it is rather challenging to numerically compute it in HMMs. Here we develop a non-Monte Carlo method that computes the KL divergence of two-state HMMs via the underlying invariant probability measure, which is characterized by the Fredholm integral equation. Numerical study demonstrates an unusual property of the KL divergence for HMM that implies the severe effects of misspecifying the postchange parameter for the HMM.

Posted in: Probability and statistics , Tagged: , , , ,

The problem of monitoring events that can only be predicted stochastically, applied to mobile sensors for monitoring

July 17, 2015 12:18 ,

Jingjin Yu; Karaman, S.; Rus, D., Persistent Monitoring of Events With Stochastic Arrivals at Multiple Stations, Robotics, IEEE Transactions on , vol.31, no.3, pp.521,535, June 2015, DOI: 10.1109/TRO.2015.2409453.

This paper introduces a new mobile sensor scheduling problem involving a single robot tasked to monitor several events of interest that are occurring at different locations (stations). Of particular interest is the monitoring of transient events of a stochastic nature, with applications ranging from natural phenomena (e.g., monitoring abnormal seismic activity around a volcano using a ground robot) to urban activities (e.g., monitoring early formations of traffic congestion using an aerial robot). Motivated by examples like these, this paper focuses on problems in which the precise occurrence times of the events are unknown apriori, but statistics for their interarrival times are available. In monitoring such events, the robot seeks to: (1) maximize the number of events observed and (2) minimize the delay between two consecutive observations of events occurring at the same location. This paper considers the case when a robot is tasked with optimizing the event observations in a balanced manner, following a cyclic patrolling route. To tackle this problem, first, assuming that the cyclic ordering of stations is known, we prove the existence and uniqueness of the optimal solution and show that the solution has desirable convergence rate and robustness. Our constructive proof also yields an efficient algorithm for computing the unique optimal solution with O(n) time complexity, in which n is the number of stations, with O(log n) time complexity for incrementally adding or removing stations. Except for the algorithm, our analysis remains valid when the cyclic order is unknown. We then provide a polynomial-time approximation scheme that computes for any ε > 0 a (1 + ε)-optimal solution for this more general, NP-hard problem.

Posted in: Real-Time Systems, Robot sensors, Task scheduling , Tagged:

Estimating the bandwidth of a communication channel for adjusting the bitrate in high-definition video streaming, using Pareto and Gamma distributions (that are conjugate) in a bayesian estimation framework

December 9, 2014 17:48 ,

Javadtalab, A.; Semsarzadeh, M.; Khanchi, A.; Shirmohammadi, S.; Yassine, A., Continuous One-Way Detection of Available Bandwidth Changes for Video Streaming Over Best-Effort Networks, Instrumentation and Measurement, IEEE Transactions on , vol.64, no.1, pp.190,203, Jan. 2015. DOI: 10.1109/TIM.2014.2331423

Video streaming over best-effort networks, such as the Internet, is now a significant application used by most Internet users. However, best-effort networks are characterized by dynamic and unpredictable changes in the available bandwidth, which adversely affect the quality of video. As such, it is important to have real-time detection mechanisms of bandwidth changes to ensure that video is adapted to the available bandwidth and transmitted at the highest quality. In this paper, we propose a Bayesian instantaneous end-to-end bandwidth change prediction model and method to detect and predict one-way bandwidth changes at the receiver. Unlike existing congestion detection mechanisms, which use network parameters such as packet loss probability, round trip time (RTT), or jitter, our approach uses weighted interarrival time of video packets at the receiver side. Furthermore, our approach is continuous, since it measures available bandwidth changes with each incoming video packet, and therefore detects congestion occurrence in <200 ms, on average, which is significantly faster than existing approaches. In addition, it is a one-way scheme, since it only takes into account the characteristics of the incoming path and not the outgoing path, as opposed to other approaches, which use RTT and are hence less accurate. In this paper, we provide extensive experimental simulations and real-world network implementation. Our results indicate that the proposed detection method is superior to existing solutions.

Posted in: QoS in networked telerobots , Tagged: , ,