NEWMA: a new method for scalable model-free online change-point detection
We consider the problem of detecting abrupt changes in the distribution of a multi-dimensional time series, with limited computing power and memory. In this paper, we propose a new, simple method for model-free online change-point detection that relies only on fast and light recursive statistics, inspired by the classical Exponential Weighted Moving Average algorithm (EWMA). The proposed idea is to compute two EWMA statistics on the stream of data with different forgetting factors, and to compare them. By doing so, we show that we implicitly compare recent samples with older ones, without the need to explicitly store them. Additionally, we leverage Random Features (RFs) to efficiently use the Maximum Mean Discrepancy as a distance between distributions, furthermore exploiting recent optical hardware to compute high-dimensional RFs in near constant time. We show that our method is significantly faster than usual non-parametric methods for a given accuracy.
Code (1)
Tasks
Change Point DetectionTime SeriesTime Series AnalysisSimilar Papers 제목 키워드 기반
Online Change Point Detection in Molecular Dynamics With Optical Random Features
Proteins are made of atoms constantly fluctuating, but can occasionally undergo large-scale changes. Such transitions are of biological interest, linking the structure of a protein to its function with a cell. Atomic-lev…
Change Point DetectionTime SeriesTime Series AnalysisRobust and Scalable Bayesian Online Changepoint Detection
This paper proposes an online, provably robust, and scalable Bayesian approach for changepoint detection. The resulting algorithm has key advantages over previous work: it provides provable robustness by leveraging the g…
Memory-free Online Change-point Detection: A Novel Neural Network Approach
Change-point detection (CPD), which detects abrupt changes in the data distribution, is recognized as one of the most significant tasks in time series analysis. Despite the extensive literature on offline CPD, unsupervis…
Change Point DetectionTime SeriesTime Series AnalysisA Distributed Hybrid Community Detection Methodology for Social Networks
Nowadays, the amount of digitally available information has tremendously grown, with real-world data graphs outreaching the millions or even billions of vertices. Hence, community detection, where groups of vertices are …
Community DetectionMarketingSociologyOnlineSTL: Scaling Time Series Decomposition by 100x
Decomposing a complex time series into trend, seasonality, and remainder components is an important primitive that facilitates time series anomaly detection, change point detection, and forecasting. Although numerous bat…
Anomaly DetectionChange Point DetectionTime SeriesTime Series Analysis+1