Change Point Detection

Change point detection is categorized by its operational mode. Online detection processes data sequentially in real-time, aiming to identify a change as soon as possible after it occurs. Algorithms like CUSUM and Page-Hinkley are designed for this streaming context. In contrast, offline (or retrospective) detection analyzes a complete dataset after collection, identifying all change points simultaneously. This is common in historical data analysis using methods like binary segmentation or pruned exact linear time (PELT).

These methods assume the data follows a known probability distribution before and after the change. The Cumulative Sum (CUSUM) algorithm monitors the cumulative sum of deviations from a target mean, flagging a change when the sum exceeds a threshold. The Generalized Likelihood Ratio (GLR) test is more flexible, comparing the likelihood of data under a no-change hypothesis versus a change hypothesis at an unknown point. These are highly sensitive but require strong distributional assumptions.

For data where distributional form is unknown, non-parametric methods are essential. Kernel-based tests, like those using Maximum Mean Discrepancy (MMD), compare samples by mapping them into a high-dimensional feature space. Rank-based statistics or tests comparing empirical cumulative distribution functions (ECDFs), such as the Kolmogorov-Smirnov test, are also common. These methods trade some statistical power for robustness to a wider range of data types.

This probabilistic framework treats the change point as a latent variable and computes its posterior distribution given the observed data. It naturally incorporates prior beliefs about the frequency of changes and provides uncertainty estimates (e.g., the probability a change occurred at each time point). Methods often rely on computational techniques like Markov Chain Monte Carlo (MCMC) or particle filtering for online inference. This approach is powerful but computationally more intensive than frequentist methods.

These methods frame change point detection as a cost minimization problem. The goal is to partition the time series into segments such that the total cost (e.g., negative log-likelihood) within each segment is minimized, penalized by the number of change points. The Pruned Exact Linear Time (PELT) algorithm solves this efficiently, providing an exact solution with linear computational complexity under certain conditions. It's a standard for accurate offline detection.

Supervised and unsupervised ML models can be adapted for change detection. Unsupervised methods might use clustering to identify shifts in feature representations over time. Supervised methods can be trained to predict whether a new batch of data comes from the same distribution as a reference set, treating it as a classification problem. Deep learning models, such as recurrent neural networks (RNNs) or transformers, can also learn complex temporal dependencies to predict or flag anomalous shifts.

Classical change point detection relies on statistical hypothesis testing and control charts to identify shifts in data properties.

• CUSUM (Cumulative Sum): Accumulates deviations from a target mean to detect small, persistent shifts.
• Page-Hinkley Test: A sequential analysis technique monitoring the cumulative difference between observations and their running mean.
• ADWIN (Adaptive Windowing): Dynamically adjusts the size of a data window, dropping old data when a change is inferred. These methods are often parameter-light and form the basis for many online monitoring systems.

Modern techniques use machine learning to detect more complex, multivariate changes.

• Bayesian Change Point Detection: Models the data as a piecewise stationary process and uses inference to estimate change point probabilities.
• Kernel-Based Methods: Use metrics like Maximum Mean Discrepancy (MMD) to compare distributions of data in different windows in a high-dimensional feature space.
• Deep Learning Models: Recurrent or convolutional neural networks can be trained to learn temporal representations and predict change points, useful for high-dimensional signals like sensor data or video.

The detection paradigm is defined by when analysis occurs relative to data arrival.

• Online (Real-Time) Detection: Analyzes data points sequentially as they arrive. Essential for live monitoring and triggering immediate model adaptation (e.g., CUSUM, ADWIN). Minimizes detection delay but is susceptible to noise.
• Offline (Retrospective) Detection: Analyzes a complete dataset after collection. Allows for more accurate detection of multiple change points and is less sensitive to transient fluctuations. Used for forensic analysis and model diagnosis.

A primary use case is within MLOps pipelines to safeguard model performance.

• Triggering Retraining: A detected change point in feature distributions (data drift) or prediction error (concept drift) can automatically initiate a triggered retraining pipeline.
• Segmenting Reference Data: Helps define clean reference windows of stable data for comparison, improving the accuracy of metrics like Population Stability Index (PSI).
• Root Cause Analysis: By localizing change points to specific time windows, engineers can correlate them with external events (e.g., a policy change, data pipeline bug).

Change point detection is a broader statistical field that underpins specific drift detection methods.

• Drift Detection is a specialized application focused on changes that degrade model performance. It often uses change point algorithms on model-centric signals (error rate, prediction distributions).
• Key Difference: Change point detection identifies when a change occurred. Drift localization seeks to explain what changed (e.g., which features).
• Synergy: Methods like the Drift Detection Method (DDM) are built on statistical process control, a form of change point analysis.

Implementing effective detection requires balancing sensitivity, latency, and false alarms.

• False Positive Rate: Tuning detection thresholds to avoid unnecessary retraining cycles.
• Detection Delay: The lag between a real change and its alert, which can impact model performance.
• Multivariate Changes: Detecting coordinated shifts across many correlated features is more complex than univariate detection.
• Gradual vs. Abrupt Change: Many algorithms are optimized for abrupt shifts; detecting slow, gradual drift requires different techniques or larger test windows.

Concept drift is a change in the statistical relationship between the input features (X) and the target variable (Y) that a model aims to predict. This means the mapping P(Y|X) learned during training is no longer valid, directly degrading predictive accuracy. Change point detection is often used to identify the moment this relationship shifts.

• Real vs. Virtual Drift: Real drift affects P(Y|X), while virtual drift only affects P(X) (data drift).
• Causes: Include non-stationary environments, evolving user behavior, or sensor degradation.
• Detection Challenge: Requires monitoring model error rates or prediction distributions, not just input data.

Data drift, specifically covariate shift, occurs when the distribution of the input features P(X) changes between the training and production environments, while the true relationship P(Y|X) remains stable. This is a primary target for unsupervised change point detection methods.

• Common Cause: Shifts in population demographics, seasonal effects, or changes in data collection sensors.
• Impact: A model can become biased or inaccurate because it encounters feature values outside its training domain.
• Detection: Methods like Population Stability Index (PSI), Kolmogorov-Smirnov tests, and distribution distance metrics (e.g., Wasserstein Distance) are applied to feature distributions to find change points.

Change point detection operates in two primary modes defined by data arrival and decision latency.

• Online Detection: Processes data points sequentially in real-time, making a decision at each time step. Algorithms like CUSUM, Page-Hinkley, and ADWIN are designed for this low-latency environment. They are essential for high-velocity streams like financial trading or IoT sensor monitoring.
• Batch Detection: Analyzes fixed, collected batches of data (e.g., daily logs). Techniques like two-sample hypothesis testing (K-S test, MMD) compare a recent batch to a historical reference window. This is common in weekly model performance reviews.
• Trade-off: Online methods minimize detection delay but can be sensitive to noise; batch methods are more statistically robust but introduce latency.

Statistical Process Control (SPC) is a foundational quality control methodology adapted for machine learning monitoring. It uses control charts to distinguish common-cause variation from special-cause variation (drift).

• Core Tool: The Control Chart plots a metric (e.g., prediction error, feature mean) over time with statistically derived upper and lower control limits.
• Application: A data point or trend breaching these limits signals a potential change point requiring investigation. The CUSUM chart is a direct SPC technique for detecting small, persistent shifts in the process mean.
• Philosophy: Provides a framework for defining normal operation and triggering alerts for abnormal states, forming the basis for triggered retraining systems.

Two-sample hypothesis testing is the statistical backbone of batch-based change point and drift detection. It formally tests whether two datasets (a reference window and a test window) are drawn from the same underlying distribution.

• Null Hypothesis (H0): The two samples are from the same distribution (no drift).
• Common Tests:
  • Kolmogorov-Smirnov Test: Compares empirical cumulative distribution functions (ECDFs).
  • Maximum Mean Discrepancy (MMD): A kernel-based test powerful for high-dimensional data.
  • Wasserstein Distance: Measures the minimal "work" to transform one distribution into another.
• Output: A p-value. A low p-value (e.g., <0.05) leads to rejecting H0, indicating a statistically significant change point between the windows.

These are the critical performance metrics for evaluating any change point detection system in production.

• Detection Delay: The time lag between the actual onset of a distributional shift and the algorithm's alert. Minimizing delay is crucial for rapid model adaptation. Online algorithms are explicitly designed to optimize this.
• False Positive Rate: The probability that the system incorrectly triggers a drift alert when no real change has occurred. A high false positive rate leads to alert fatigue and unnecessary retraining costs.
• Trade-off: There is an inherent trade-off between a low detection delay (sensitivity) and a low false positive rate (specificity). Tuning detection thresholds (e.g., control limits in CUSUM) manages this balance.