Sequential Analysis for Faster Drift Detection

While basic statistical tests applied to fixed batches of data can identify drift, they often introduce significant latency. By the time a batch is collected and analyzed, a model might have already been operating on drifted data for some time, potentially impacting business outcomes. For applications requiring quicker responses, such as high-frequency trading, real-time bidding, or critical control systems, waiting for a full batch is often unacceptable. Sequential analysis methods offer an alternative by analyzing data points as they arrive, aiming to detect changes much faster.

The fundamental idea is to make a decision (drift detected or not) after each new data point or small mini-batch, rather than waiting for a predetermined, larger batch size. This allows for potentially much earlier warnings when a distribution starts to shift.

Contrasting Sequential and Batch Approaches

Imagine monitoring the average transaction value for fraud detection.

• Batch Approach: You might collect data for an entire day, calculate the average transaction value, and compare it to the average from the previous day or a reference window using a t-test or KS-test. A significant difference triggers an alert. The detection latency is at least one day (the batch window).
• Sequential Approach: You update a statistical measure with each new transaction. If this measure crosses a predefined threshold, an alert is triggered immediately. Detection can happen within minutes or hours of the drift starting, depending on the magnitude of the change and the test's sensitivity.

This speed comes with considerations. Sequential tests are often designed around specific assumptions about the data distribution and the nature of the change you expect. They typically involve setting parameters that balance the rate of false alarms when no drift has occurred against the speed of detection when drift has occurred.

Concepts in Sequential Analysis

Sequential analysis for drift detection is essentially a form of sequential hypothesis testing. We continuously test:

• $H_0$: The data generating process has not changed (no drift).
• $H_1$: The data generating process has changed (drift).

Unlike classical fixed-sample tests where you collect $N$ samples and then decide, sequential tests evaluate the evidence after each sample (or small group) and decide whether to:

1. Accept $H_0$ (conclude no drift for now).
2. Accept $H_1$ (signal drift).
3. Continue sampling (not enough evidence yet).

Two important performance metrics for sequential tests are:

• Average Run Length to False Alarm (ARL$_0$): The average number of observations processed before the test incorrectly signals drift when $H_0$ is true. You want this to be large.
• Average Run Length to Detection (ARL$_1$): The average number of observations processed after a true drift occurs until the test signals it. You want this to be small.

The design of a sequential test involves choosing parameters to achieve a desired (low) ARL$_1$ while maintaining an acceptably high ARL$_0$.

Sequential Probability Ratio Test (SPRT)

One of the earliest and most foundational methods is Wald's Sequential Probability Ratio Test (SPRT). It's particularly powerful when you can specify the data distribution under both the null hypothesis ($H_0$, no drift) and an alternative hypothesis ($H_1$, drift).

Let $f_0(x)$ be the probability density (or mass) function under $H_0$ and $f_1(x)$ be the density under $H_1$. After observing $n$ data points $x_1, x_2, ..., x_n$, the likelihood ratio is:

$$L_n = \frac{\prod_{i=1}^n f_1(x_i)}{\prod_{i=1}^n f_0(x_i)}$$

SPRT uses two thresholds, $A$ and $B$, typically defined based on the desired Type I error rate $\alpha$ (probability of false alarm) and Type II error rate $\beta$ (probability of missed detection):

• $A \approx (1-\beta)/\alpha$
• $B \approx \beta/(1-\alpha)$

The decision rule at step $n$ is:

• If $L_n \ge A$: Stop and accept $H_1$ (signal drift).
• If $L_n \le B$: Stop and accept $H_0$ (conclude no drift).
• If $B < L_n < A$: Continue to the next observation $x_{n+1}$.

Example: Suppose we monitor the mean $\mu$ of a normally distributed feature $X \sim N(\mu, \sigma^2)$ where $\sigma^2$ is known.

• $H_0: \mu = \mu_0$ (e.g., the mean observed during training)
• $H_1: \mu = \mu_1$ (e.g., a specific shifted mean we want to detect quickly)

The likelihood ratio $L_n$ can be calculated, and often its logarithm $\log L_n$ is used for computational stability, leading to additive updates rather than multiplicative ones.

SPRT Advantages: SPRT is mathematically optimal in the sense that it minimizes the expected sample size (ARL$_0$ and ARL$_1$) among all tests with the same or lower error rates ($\alpha, \beta$).

SPRT Challenges: Its main drawback is the need to precisely specify both $f_0$ and $f_1$. Defining a single, representative "drifted" distribution $f_1$ can be difficult in practice, as drift might manifest in various ways.

Cumulative Sum (CUSUM) Control Charts

CUSUM charts are widely used in statistical process control and adapt well to drift detection. They are effective at detecting small, persistent shifts in a process parameter (like the mean or proportion).

The core idea is to accumulate deviations from a target value. Let $X_i$ be the observation at time $i$, and $\mu_0$ be the target mean (under $H_0$). A one-sided CUSUM statistic $S_n$ for detecting an increase in the mean can be calculated recursively:

$$S_n = \max(0, S_{n-1} + (X_n - (\mu_0 + k)))$$

where $S_0 = 0$.

• $X_n$: The observed value at step $n$ (or a summary statistic like the average of a mini-batch).
• $\mu_0$: The target mean under $H_0$.
• $k$: A "slack" or "allowance" parameter, often chosen as half the magnitude of the shift you want to detect quickly (e.g., $k = |\mu_1 - \mu_0| / 2$). It helps prevent the CUSUM from accumulating noise when the process is in control.
• $S_n$: The CUSUM statistic at step $n$. It accumulates deviations above the adjusted target $(\mu_0 + k)$. The $\max(0, ...)$ ensures it resets to zero if deviations fall below the target, preventing past negative deviations from masking a current positive shift.

Drift (an upward shift) is signaled if $S_n$ exceeds a predefined decision threshold $h$. The parameters $k$ and $h$ are chosen to balance ARL$_0$ and ARL$_1$. Similar formulas exist for detecting decreases or two-sided changes.

Example CUSUM statistic over time. The process mean shifts upwards around time step 50. The CUSUM statistic remains near zero initially, then starts accumulating positively after the shift, crossing the detection threshold $h=8$ around time step 67, signaling drift.

CUSUM Advantages: Generally easier to implement than SPRT as it doesn't require specifying a full distribution for $H_1$. It's quite effective for detecting small, sustained shifts.

CUSUM Challenges: Requires careful tuning of $k$ and $h$. Performance depends on the shift magnitude relative to $k$. May be slower than SPRT for detecting very large, abrupt shifts if $k$ is optimized for small shifts.

Advantages and Trade-offs

The primary advantage of sequential methods like SPRT and CUSUM is their potential for significantly faster detection compared to fixed-batch methods, especially for moderate or small shifts. They examine evidence as it becomes available, minimizing the delay between the onset of drift and its detection. This timeliness is invaluable in many production ML systems.

However, this speed comes with complexities:

1. Parameter Tuning: Selecting appropriate thresholds ($A, B, h$) and parameters ($k$, specific $H_1$) requires careful consideration, often involving simulation or analysis to understand the trade-off between ARL$_0$ and ARL$_1$. Poor tuning can lead to excessive false alarms or slow detection.
2. Assumptions: SPRT requires well-defined hypotheses, while CUSUM assumes a specific type of shift (e.g., in the mean). Performance can degrade if the actual drift pattern differs significantly from assumptions.
3. Multivariate Data: Applying these methods directly to high-dimensional data is often impractical. Common approaches involve applying sequential tests to:
   • Individual features.
   • A univariate summary statistic derived from multivariate data (e.g., the output of a dimensionality reduction technique, or a metric like prediction probability).
   • The output of a univariate drift metric calculated on multivariate data (e.g., applying CUSUM to the Mahalanobis distance).

Sequential analysis provides a powerful set of tools for rapid drift detection, particularly valuable in streaming contexts. They act as efficient early warning systems. When a sequential test signals potential drift, it can trigger more comprehensive, potentially computationally heavier, investigations using multivariate methods (discussed in other sections) or initiate automated responses like model retraining.