Fast Online Changepoint Detection via Functional Pruning CUSUM statistics

• URL: http://arxiv.org/abs/2110.08205v1
• Date: Fri, 15 Oct 2021 17:08:06 GMT
• Title: Fast Online Changepoint Detection via Functional Pruning CUSUM statistics
• Authors: Gaetano Romano, Idris Eckley, Paul Fearnhead, Guillem Rigaill
• Abstract summary: Functional Online CuSUM (FOCuS) is equivalent to running earlier methods simultaneously for all sizes of window, or all possible values for the size of change. We show how FOCuS can be applied to a number of different change in mean scenarios, and demonstrate its practical utility.
• Score: 2.867517731896504
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Many modern applications of online changepoint detection require the ability to process high-frequency observations, sometimes with limited available computational resources. Online algorithms for detecting a change in mean often involve using a moving window, or specifying the expected size of change. Such choices affect which changes the algorithms have most power to detect. We introduce an algorithm, Functional Online CuSUM (FOCuS), which is equivalent to running these earlier methods simultaneously for all sizes of window, or all possible values for the size of change. Our theoretical results give tight bounds on the expected computational cost per iteration of FOCuS, with this being logarithmic in the number of observations. We show how FOCuS can be applied to a number of different change in mean scenarios, and demonstrate its practical utility through its state-of-the art performance at detecting anomalous behaviour in computer server data.

Related papers

• Low-rank extended Kalman filtering for online learning of neural networks from streaming data [71.97861600347959]
  We propose an efficient online approximate Bayesian inference algorithm for estimating the parameters of a nonlinear function from a potentially non-stationary data stream. The method is based on the extended Kalman filter (EKF), but uses a novel low-rank plus diagonal decomposition of the posterior matrix. In contrast to methods based on variational inference, our method is fully deterministic, and does not require step-size tuning.
  arXiv  Detail & Related papers  (2023-05-31T03:48:49Z)
• A Log-Linear Non-Parametric Online Changepoint Detection Algorithm based on Functional Pruning [5.202524136984542]
  We build a flexible nonparametric approach to detect a change in the distribution of a sequence. Thanks to functional pruning ideas, NP-FOCuS has a computational cost that is log-linear in the number of observations. In terms of detection power, NP-FOCuS is seen to outperform current nonparametric online changepoint techniques in a variety of settings.
  arXiv  Detail & Related papers  (2023-02-06T11:50:02Z)
• Online Kernel CUSUM for Change-Point Detection [12.383181837411469]
  We present a computationally efficient online kernel Cumulative Sum (CUSUM) method for change-point detection. Our approach exhibits increased sensitivity to small changes compared to existing kernel-based change-point detection methods.
  arXiv  Detail & Related papers  (2022-11-28T05:08:30Z)
• Fast Exploration of the Impact of Precision Reduction on Spiking Neural Networks [63.614519238823206]
  Spiking Neural Networks (SNNs) are a practical choice when the target hardware reaches the edge of computing. We employ an Interval Arithmetic (IA) model to develop an exploration methodology that takes advantage of the capability of such a model to propagate the approximation error.
  arXiv  Detail & Related papers  (2022-11-22T15:08:05Z)
• E-detectors: a nonparametric framework for sequential change detection [86.15115654324488]
  We develop a fundamentally new and general framework for sequential change detection. Our procedures come with clean, nonasymptotic bounds on the average run length. We show how to design their mixtures in order to achieve both statistical and computational efficiency.
  arXiv  Detail & Related papers  (2022-03-07T17:25:02Z)
• Online Changepoint Detection on a Budget [5.077509096253692]
  Changepoints are abrupt variations in the underlying distribution of data. We propose an online changepoint detection algorithm which compares favorably with offline changepoint detection algorithms.
  arXiv  Detail & Related papers  (2022-01-11T00:20:33Z)
• DeepTimeAnomalyViz: A Tool for Visualizing and Post-processing Deep Learning Anomaly Detection Results for Industrial Time-Series [88.12892448747291]
  We introduce the DeTAVIZ interface, which is a web browser based visualization tool for quick exploration and assessment of feasibility of DL based anomaly detection in a given problem. DeTAVIZ allows the user to easily and quickly iterate through multiple post processing options and compare different models, and allows for manual optimisation towards a chosen metric.
  arXiv  Detail & Related papers  (2021-09-21T10:38:26Z)
• Optimal Sequential Detection of Signals with Unknown Appearance and Disappearance Points in Time [64.26593350748401]
  The paper addresses a sequential changepoint detection problem, assuming that the duration of change may be finite and unknown. We focus on a reliable maximin change detection criterion of maximizing the minimal probability of detection in a given time (or space) window. The FMA algorithm is applied to detecting faint streaks of satellites in optical images.
  arXiv  Detail & Related papers  (2021-02-02T04:58:57Z)
• Online Neural Networks for Change-Point Detection [0.6015898117103069]
  We present two online change-point detection approaches based on neural networks. We compare them with the best known algorithms on various synthetic and real world data sets.
  arXiv  Detail & Related papers  (2020-10-03T16:55:59Z)
• Change Point Detection in Time Series Data using Autoencoders with a Time-Invariant Representation [69.34035527763916]
  Change point detection (CPD) aims to locate abrupt property changes in time series data. Recent CPD methods demonstrated the potential of using deep learning techniques, but often lack the ability to identify more subtle changes in the autocorrelation statistics of the signal. We employ an autoencoder-based methodology with a novel loss function, through which the used autoencoders learn a partially time-invariant representation that is tailored for CPD.
  arXiv  Detail & Related papers  (2020-08-21T15:03:21Z)
• High-dimensional, multiscale online changepoint detection [7.502070498889449]
  We introduce a new method for high-dimensional, online changepoint detection in settings where a $p$- Gaussian data stream may undergo a change in mean. The algorithm is online in the sense that both its storage requirements and worst-case computational complexity per new observation are independent of the number of previous observations. Simulations confirm the practical effectiveness of our proposal, which is implemented in the R package 'ocd', and we also demonstrate its utility on a seismology data set.
  arXiv  Detail & Related papers  (2020-03-07T21:54:09Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.