High dimensional change-point detection: a complete graph approach

• URL: http://arxiv.org/abs/2203.08709v1
• Date: Wed, 16 Mar 2022 15:59:20 GMT
• Title: High dimensional change-point detection: a complete graph approach
• Authors: Yang-Wen Sun, Katerina Papagiannouli, Vladimir Spokoiny
• Abstract summary: We propose a complete graph-based, change-point detection algorithm to detect change of mean and variance from low to high-dimensional online data. Inspired by complete graph structure, we introduce graph-spanning ratios to map high-dimensional data into metrics. Our approach has high detection power with small and multiple scanning window, which allows timely detection of change-point in the online setting.
• Score: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: The aim of online change-point detection is for a accurate, timely discovery of structural breaks. As data dimension outgrows the number of data in observation, online detection becomes challenging. Existing methods typically test only the change of mean, which omit the practical aspect of change of variance. We propose a complete graph-based, change-point detection algorithm to detect change of mean and variance from low to high-dimensional online data with a variable scanning window. Inspired by complete graph structure, we introduce graph-spanning ratios to map high-dimensional data into metrics, and then test statistically if a change of mean or change of variance occurs. Theoretical study shows that our approach has the desirable pivotal property and is powerful with prescribed error probabilities. We demonstrate that this framework outperforms other methods in terms of detection power. Our approach has high detection power with small and multiple scanning window, which allows timely detection of change-point in the online setting. Finally, we applied the method to financial data to detect change-points in S&P 500 stocks.

Related papers

• Online Change Points Detection for Linear Dynamical Systems with Finite Sample Guarantees [1.6026317505839445]
  We study the online change point detection problem for linear dynamical systems with unknown dynamics. We develop a data-dependent threshold that can be used in our test that allows one to achieve a pre-specified upper bound on the probability of making a false alarm.
  arXiv  Detail & Related papers  (2023-11-30T18:08:16Z)
• Greedy online change point detection [0.0]
  Greedy Online Change Point Detection (GOCPD) is a computationally appealing method which finds change points by maximizing the probability of the data coming from the (temporal) concatenation of two independent models. We show that, for time series with a single change point, this objective is unimodal and thus CPD can be accelerated via ternary search with logarithmic complexity.
  arXiv  Detail & Related papers  (2023-08-14T08:59:59Z)
• 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)
• Deep learning model solves change point detection for multiple change types [69.77452691994712]
  A change points detection aims to catch an abrupt disorder in data distribution. We propose an approach that works in the multiple-distributions scenario.
  arXiv  Detail & Related papers  (2022-04-15T09:44:21Z)
• WATCH: Wasserstein Change Point Detection for High-Dimensional Time Series Data [4.228718402877829]
  Change point detection methods have the ability to discover changes in an unsupervised fashion. We propose WATCH, a novel Wasserstein distance-based change point detection approach. An extensive evaluation shows that WATCH is capable of accurately identifying change points and outperforming state-of-the-art methods.
  arXiv  Detail & Related papers  (2022-01-18T16:55:29Z)
• 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)
• Weakly Supervised Change Detection Using Guided Anisotropic Difusion [97.43170678509478]
  We propose original ideas that help us to leverage such datasets in the context of change detection. First, we propose the guided anisotropic diffusion (GAD) algorithm, which improves semantic segmentation results. We then show its potential in two weakly-supervised learning strategies tailored for change detection.
  arXiv  Detail & Related papers  (2021-12-31T10:03:47Z)
• Fast and Accurate Anomaly Detection in Dynamic Graphs with a Two-Pronged Approach [49.25767340466445]
  We propose AnomRank, an online algorithm for anomaly detection in dynamic graphs. AnomRank uses a two-pronged approach defining two novel metrics for anomalousness. We show theoretically and experimentally that the two-pronged approach successfully detects two common types of anomalies.
  arXiv  Detail & Related papers  (2020-11-26T01:38:27Z)
• Partially Observable Online Change Detection via Smooth-Sparse Decomposition [16.8028358824706]
  We consider online change detection of high dimensional data streams with sparse changes, where only a subset of data streams can be observed at each sensing time point due to limited sensing capacities. On the one hand, the detection scheme should be able to deal with partially observable data and meanwhile have efficient detection power for sparse changes. In this paper, we propose a novel detection scheme called CDSSD. In particular, it describes the structure of high dimensional data with sparse changes by smooth-sparse decomposition.
  arXiv  Detail & Related papers  (2020-09-22T16:03:04Z)
• 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)
• Offline detection of change-points in the mean for stationary graph signals [55.98760097296213]
  We propose an offline method that relies on the concept of graph signal stationarity. Our detector comes with a proof of a non-asymptotic inequality oracle.
  arXiv  Detail & Related papers  (2020-06-18T15:51:38Z)

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.