Change-point detection (CUSUM, BOCPD)

"A single high reading, I ignore; that is just noise doing its job. But when the noise stops averaging back to where it used to live, I know the world underneath it moved, and I say so."

A Vigilant AI Agent

The problem: a shift hiding under noise

What we are detecting is a change point: a time \(\tau\) before which the samples follow one distribution and after which they follow another. Formally, \(x_t \sim p_0\) for \(t < \tau\) and \(x_t \sim p_1\) for \(t \ge \tau\), with \(\tau\) unknown. Why this is not solved by the thresholds of Section 12.3 is a matter of magnitude versus persistence. A shift of half a standard deviation is buried inside the per-sample noise: any threshold loose enough to ignore normal jitter will also ignore the shift, and any threshold tight enough to catch it will fire constantly on noise alone. The signal is not in any one sample; it is in the fact that many consecutive samples all lean the same way. How every method here works is by turning that persistence into an accumulating statistic, so that a small but consistent bias grows without bound while zero-mean noise cancels itself out. When you reach for these tools is exactly when the interesting events are regime shifts rather than spikes: sensor recalibration drift, fault onset, activity transitions, mode changes in a controller.

CUSUM: accumulate the log-likelihood ratio

CUSUM (cumulative sum) is the sequential test that detects a shift with the smallest average delay for a fixed false-alarm rate; that optimality (Page, 1954; Lorden, 1971) is why it has survived seventy years in production. The idea is to score each sample by how much more consistent it is with the post-change distribution \(p_1\) than with the pre-change \(p_0\), using the log-likelihood ratio \(s_t = \log \frac{p_1(x_t)}{p_0(x_t)}\). Under normal operation \(s_t\) is negative on average; after the change it turns positive on average. The one-sided CUSUM statistic accumulates these scores but refuses to go below zero, so quiet periods reset it rather than digging an ever-deeper hole:

For the common case of detecting a mean shift of size \(\delta\) in Gaussian noise of standard deviation \(\sigma\), the score simplifies to \(s_t = \frac{\delta}{\sigma^2}\big(x_t - \mu_0 - \tfrac{\delta}{2}\big)\), which is just the residual minus half the shift you are hunting for. That is the whole algorithm: subtract a slack, add it up, clamp at zero, alarm at a threshold \(h\). The threshold trades the two quantities you actually care about, the mean time between false alarms and the detection delay, and both have closed-form approximations you can solve for a target alarm budget rather than guess.

import numpy as np

def cusum(x, mu0, sigma, delta, h):
    """One-sided CUSUM for an upward mean shift of size `delta`.
    Returns the first index where the accumulated evidence crosses h, else None."""
    k = delta / 2.0                       # reference 'slack': half the target shift
    g = 0.0
    for t, xt in enumerate(x):
        s = (delta / sigma**2) * (xt - mu0 - k)   # log-likelihood-ratio score
        g = max(0.0, g + s)               # accumulate, but never below zero
        if g > h:
            return t                      # change declared here
    return None

rng = np.random.default_rng(0)
stream = np.concatenate([rng.normal(0.0, 1.0, 200),      # in-control
                         rng.normal(0.6, 1.0, 200)])     # +0.6 sigma shift at t=200
print(cusum(stream, mu0=0.0, sigma=1.0, delta=0.6, h=5.0))   # -> ~223, a short delay

Code 12.4.1 shows why CUSUM catches what thresholds miss: at \(t = 200\) the mean moves by only 0.6 standard deviations, so every individual sample still looks plausible, yet within roughly twenty steps the accumulated score crosses \(h\). Run the same stream through a fixed three-sigma limit and it never fires. Two practical notes matter. First, one-sided CUSUM detects shifts in one direction; run two in parallel (one for up, one for down) to catch both. Second, CUSUM assumes it knows \(\mu_0\) and \(\sigma\), so it pairs naturally with the robust baseline estimation of Section 12.3 to supply those in-control parameters.

BOCPD: a posterior over "time since the last change"

CUSUM is superb when you know the shift you are hunting and the noise is stationary. Real sensor streams often violate both: the shift size is unknown, the pre-change parameters themselves drift, and you would like a probability rather than a binary alarm to feed a risk-weighted decision. Bayesian online change-point detection (Adams and MacKay, 2007) answers this by tracking a distribution over the run length \(r_t\), the number of steps since the most recent change point. At every step it does two things: it grows each run length by one with probability \(1 - H\) (no change) or resets it to zero with hazard probability \(H\) (a change just happened), and it weights each hypothesis by how well the recent data, modeled by that run's sufficient statistics, predicts the new sample. The recursion over the joint of run length and data is

and normalizing gives \(p(r_t \mid x_{1:t})\), a full posterior you can read at any instant. A change point is signalled when probability mass suddenly collapses onto \(r_t = 0\). The payoff over CUSUM is threefold: BOCPD needs no known shift size (a conjugate prior, typically Normal-Gamma for Gaussian data, integrates over all possible new means and variances), it reports calibrated uncertainty that composes cleanly with the conformal and calibration machinery of Chapter 18, and it can retrospectively refine where the change occurred, not merely that one did. The cost is more computation per step and a hazard rate \(H\) you must set, encoding how often you a priori expect changes.

Choosing between them, and what they share

How you choose comes down to three questions. Do you know the shift you are hunting? If yes, CUSUM detects it with provably minimal delay and almost no compute, which is why it dominates on microcontrollers and in the streaming edge budgets of Chapter 60. Do you need a calibrated probability, an unknown or multiple shift sizes, or retrospective localization? Then BOCPD earns its extra cost. Do you have the whole recording and want the single best set of segment boundaries offline? Then neither online method is ideal; a dynamic-programming segmenter (PELT, Binary Segmentation) is the right tool. What all of them share is the defining move of this section: they convert persistence into accumulated evidence, so that a change too small to see in any one sample becomes unmistakable once summed. That is also their shared failure mode. A slow drift with no sharp onset (a gyro bias creeping over hours) has no single \(\tau\) to find, and both methods will either lag badly or fragment it into many spurious points; for those, the state-augmentation approach of Chapter 9, estimating the drift as a hidden state, fits better than declaring change points.

What's Next

In Section 12.5, we leave the world of univariate, one-parameter-at-a-time detection and move to methods that learn the shape of "normal" directly from unlabeled data. Isolation Forest, Local Outlier Factor, and one-class SVM each carve out a region of feature space that ordinary sensor behavior occupies, then flag whatever falls outside it, giving us anomaly detectors that need no explicit distribution and no known shift size at all.