Changepoint Detection

Changepoint detection operates in two primary modes. Online detection analyzes data in real-time as it arrives, aiming to identify a changepoint with minimal delay after it occurs. This is critical for monitoring live systems like financial trading or server metrics. Offline detection (or retrospective detection) analyzes a complete historical dataset to identify all changepoints, providing a more accurate and complete picture for post-mortem analysis or model retraining decisions. The choice impacts algorithm selection and computational complexity.

Algorithms are categorized by their assumptions about the data's underlying distribution. Parametric methods (e.g., Bayesian changepoint models, CUSUM for mean shifts) assume the data follows a known probability distribution (like Gaussian) before and after the change. They are powerful and efficient when the assumption holds. Non-parametric methods (e.g., Kernel-based change detection, EDIV) make no strong distributional assumptions, relying instead on statistics like ranks or empirical distributions. They are more robust to unknown or complex data distributions but can be less statistically powerful.

The problem scope defines the algorithm's search strategy. Single changepoint detection seeks the one most significant break in a dataset, often using methods like maximum likelihood estimation. Multiple changepoint detection identifies an unknown number of change points, which is the more common and challenging real-world scenario. Algorithms for this, such as PELT (Pruned Exact Linear Time) or Binary Segmentation, must efficiently search the combinatorial space of possible segmentations, balancing detection accuracy with computational cost.

Changepoints signify shifts in different statistical properties of the data generating process. Key types include:

• Mean Shift: A sudden change in the average value of the signal (e.g., server CPU usage jumps from 40% to 80%).
• Variance Shift: A change in the volatility or spread of the data (e.g., sensor readings become noisier).
• Trend Change: An alteration in the underlying slope or direction of the time series.
• Distribution Change: A shift in the entire probability distribution of the data, which encompasses changes in mean, variance, and shape.
• Covariate Shift: A change in the feature distribution for machine learning models, distinct from concept drift which affects the target relationship.

Several foundational statistical and computational strategies are employed:

• Cost Function & Search Methods: Algorithms define a cost (e.g., negative log-likelihood) for each data segment and use search methods (optimal, greedy, or approximate) to find the segmentation that minimizes the total cost plus a penalty for adding changepoints.
• Likelihood-Ratio Tests: For parametric models, these test the hypothesis of a change in model parameters at each point.
• Bayesian Methods: These treat the number and location of changepoints as random variables, using prior distributions and computing posterior probabilities to infer the most likely segmentation.
• Kernel-Based Methods: These map data into a high-dimensional space and detect changes in the mean of the mapped data, enabling non-parametric detection of complex changes.

Performance is measured by the accuracy of detected changepoint locations and the control of errors. Key metrics include:

• Detection Delay: The time lag between a true changepoint and its detection (critical for online methods).
• Precision & Recall: The proportion of detected changepoints that are true, and the proportion of true changepoints that are detected.
• Mean Squared Error (MSE) of Locations: The average squared distance between estimated and true changepoint indices.

Primary challenges include distinguishing a true structural break from a large outlier, setting the sensitivity penalty to avoid over- or under-fitting, and handling seasonality or autocorrelation that can obscure changes.

Anomaly detection is the general process of identifying rare items, events, or observations that deviate significantly from the majority of data. While changepoint detection identifies shifts in the generating process of data, anomaly detection focuses on individual data points or patterns that are unusual.

• Key Distinction: A changepoint marks a permanent or semi-permanent shift in the system's state (e.g., a new mean), whereas an anomaly is often a temporary deviation from the current state.
• Example: In server metrics, a changepoint might indicate a permanent upgrade that doubles baseline CPU usage, while an anomaly would be a sudden, brief 100% CPU spike.

Concept drift refers to changes in the statistical properties of the target variable a machine learning model is trying to predict, relative to the input features. It is a primary cause of model performance degradation in production.

• Relation to Changepoints: Concept drift often manifests as a changepoint in a model's performance metrics (e.g., accuracy, F1-score). Detecting such changepoints is critical for triggering model retraining or adaptation.
• Types: Includes sudden drift (abrupt change, akin to a changepoint), gradual drift, and recurring concepts.

CUSUM is a foundational sequential analysis algorithm for online changepoint detection. It monitors the cumulative sum of deviations between observations and a target value (often the historical mean).

• Mechanism: It is sensitive to small, persistent shifts. The cumulative sum resets after a detected change.
• Use Case: Extensively used in statistical process control (SPC) for manufacturing and monitoring system metrics for small mean shifts that might be missed by simple thresholding.
• Formula: The CUSUM statistic is defined as (S_t = \max(0, S_{t-1} + x_t - \mu - k)), where (\mu) is the target mean and (k) is a sensitivity parameter.

STL (Seasonal-Trend decomposition using Loess) is a robust time-series filtering method that decomposes a series into Seasonal, Trend, and Remainder components.

• Role in Changepoint Analysis: Changepoint detection is often performed on the Trend component to identify shifts in the underlying progression, or on the Remainder to detect anomalies once seasonality and trend are removed.
• Advantage: Handles complex seasonality and is robust to outliers, which prevents anomalous points from corrupting the trend estimation used for changepoint detection.

Statistical Process Control is a method of quality control that uses statistical methods to monitor and control a process. Control charts, a key SPC tool, are directly related to changepoint detection.

• Control Charts: Tools like Shewhart charts (for detecting large shifts) and CUSUM/EWMA charts (for detecting smaller, sustained shifts) are classic changepoint detection algorithms applied in industrial settings.
• Application to Data Pipelines: SPC principles are applied in Data Reliability Engineering to monitor data quality metrics (e.g., row counts, null rates) for changepoints indicating pipeline breaks.

This is a probabilistic approach to detecting changepoints in streaming data. It maintains a distribution over the run length—the time since the last changepoint—and updates it recursively with each new data point.

• Core Idea: Computes the probability that a changepoint occurred at each time step, given the prior distribution and the likelihood of the data under the current and new models.
• Advantages: Provides a principled measure of uncertainty (a probability of change) and can incorporate complex underlying models. It is inherently online and computationally efficient.
• Contrast: Unlike offline methods that analyze a complete dataset, this method processes data points sequentially, making it ideal for real-time monitoring systems.