Offline change detection under contamination

Sujay Bhatt, Guanhua Fang, Ping Li

Abstract

In this work, we propose a non-parametric and robust change detection algorithm to detect multiple change points in time series data under non-adversarial contamination. The algorithm is designed for the offline setting, where the objective is to detect changes when all data are received. We only make weak moment assumptions on the inliers (uncorrupted data) to handle a large class of distributions. The robust scan statistic in the change detection algorithm is fashioned using mean estimators based on influence functions. We establish the consistency of the estimated change point indexes as the number of samples increases, and provide empirical evidence to support the consistency results.

Introduction

Identifying "change points"—moments when the underlying data-generating process shifts—is a fundamental task in time series analysis. Whether it involves sensor failures, climate pattern shifts, or physiological changes in medical data, accurately pinpointing when the "old normal" becomes the "new normal" is critical.

However, real-world data is rarely clean. It is often contaminated by outliers, transmission errors, or heavy-tailed noise. Classical algorithms typically assume independent and identically distributed (i.i.d.) data following thin-tailed distributions like the Gaussian. These methods often fail when faced with dependent, heavy-tailed, or corrupted data. In this paper, we introduce RC-Cat (Robust Change Detection with Catoni), a non-parametric algorithm designed to find multiple change points even under significant contamination.

The RC-Cat Framework

RC-Cat addresses the limitations of existing methods by utilizing a robust scan statistic based on Catoni’s influence functions. This approach allows the algorithm to handle non-i.i.d. data and adversarial noise more effectively than current state-of-the-art methods.

Robust Scan Statistic

The core of the algorithm is a scan statistic, $S_w(j)$, which evaluates a sliding window of length $w$ across the dataset. Instead of a simple empirical mean, which is highly sensitive to outliers, RC-Cat employs a soft-truncation estimator. This estimator uses an influence function $\psi(x)$ that caps the impact of extreme values, making the mean estimation nearly immune to massive outliers while remaining sensitive to the underlying distribution shift.

Detection Procedure

  1. Scanning: The algorithm calculates the difference between the robust means of windows immediately preceding and following each point $j$.
  2. Local Maxima Identification: To avoid over-detecting multiple points for a single shift, the algorithm identifies local maximizers within a neighborhood defined by the window size.
  3. Thresholding: Change points are only identified where the jump $S_w(j)$ exceeds a predefined threshold $b$.
Figure 1: Change point detection on synthetic data with Student's t + Pareto (left) and Normal + Power (right) distributions at 15% contamination.

Experimental Validation

We evaluated RC-Cat against the Adversarially Robust Change point detection (ARC) algorithm using both synthetic and real-world datasets.

Synthetic Data and Robustness

Testing involved time series generated with heavy-tailed Student’s t-distributions and Pareto contamination. We examined scenarios including one-sided and two-sided arbitrary shifts. A key finding was RC-Cat's stability at high contamination rates. While competing methods showed significant error spikes as contamination approached 40%, RC-Cat maintained high accuracy.

Figure 3: Robust detection performance under higher contamination levels (η = 0.25) using Student's t + Pareto distribution.

Real-World Applications

  • Well-log Data: In this classic benchmark of nuclear magnetic response during drilling, RC-Cat successfully identified major stratigraphic shifts despite frequent "spiky" outliers.
  • PM2.5 Index: Analysis of air quality data from Hong Kong (2014–2022) demonstrated the algorithm's ability to handle natural fluctuations and seasonal shifts.

Conclusion

RC-Cat provides a robust, computationally efficient ($O(nw)$) solution for offline change point detection. By requiring only a bounded second moment, it applies to a wide range of heavy-tailed real-world phenomena without the need for data-wasting sample splitting. Future work will explore extending this framework to multivariate datasets and addressing fully adversarial scenarios.

Summary updated

Abstract

In this work, we propose a non-parametric and robust change detection algorithm to detect multiple change points in time series data under non-adversarial contamination. The algorithm is designed for the offline setting, where the objective is to detect changes when all data are received. We only make weak moment assumptions on the inliers (uncorrupted data) to handle a large class of distributions. The robust scan statistic in the change detection algorithm is fashioned using mean estimators based on influence functions. We establish the consistency of the estimated change point indexes as the number of samples increases, and provide empirical evidence to support the consistency results.
BibTeX
@inproceedings{bhatt2022offline,
  author = {Sujay Bhatt and Guanhua Fang and Ping Li},
  title = {{Offline change detection under contamination}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2022},
  url = {https://openreview.net/forum?id=sOi2jmvT7B},
}
Figure