Bayesian Online Changepoint Detection

A latency metric has sat near 120 ms for three weeks, and the newest reading is four standard deviations high. Is that an outlier, or the first point of a new regime? No rule applied to one observation can say. What can be said is how probable each explanation is given everything seen so far, and how that should move when the next point arrives. Adams and MacKay turned that into a recursion cheap enough to run online (Adams & MacKay, 2007, Bayesian Online Changepoint Detection, arXiv:0710.3742).

Where CUSUM, covered in its own concept, accumulates evidence for a shift of a size chosen in advance, this method maintains a full distribution over when the current regime began, and forecasts from it.

The run length

The model assumes data arrive in segments. Within a segment, observations are i.i.d. from a distribution with parameters \(\theta\); at a changepoint, a fresh \(\theta\) is drawn from a prior, independent of the old one. Define the run length \(r_t\) as the number of observations since the last changepoint. It either grows by one or resets to zero:

\(H\) is the hazard function, the probability that a segment ends at a given length. If segment lengths are geometric with mean \(\lambda\), the process is memoryless and \(H = 1/\lambda\) everywhere. That two-way branching keeps the algorithm tractable.

The recursion

Write \(x_t^{(r)}\) for the observations belonging to a run of length \(r\), and \(\pi_t^{(r)} = P(x_t \mid r_{t-1}, x_t^{(r)})\) for the predictive probability of the new point under that run's posterior. The joint distribution of run length and data updates as

which splits into a growth term, \(P(r_{t-1}, x_{1:t-1})\,\pi_t^{(r)}\,(1 - H)\) for each existing run, and a changepoint term that sums \(P(r_{t-1}, x_{1:t-1})\,\pi_t^{(r)}\,H\) over all of them. Dividing by the evidence \(P(x_{1:t}) = \sum_{r_t} P(r_t, x_{1:t})\) gives the posterior \(P(r_t \mid x_{1:t})\), and the forecast mixes each run's predictive by its posterior weight:

With a conjugate exponential-family model, each run's posterior is a handful of sufficient statistics, such as the count and sum for a Normal with unknown mean. Extending a run adds the new observation's statistics, and a new run starts from the prior. Nothing is refitted.

One consequence is easy to miss. Both branches score \(x_t\) with the old runs' predictives, so with constant hazard the posterior mass on \(r_t = 0\) always equals \(H\). Evidence that a change happened shows up one step later, as mass on short run lengths. Anyone thresholding \(P(r_t = 0 \mid x_{1:t})\) directly will never see it move.

A worked example

Simplify to two hypotheses: the old segment continues, with known mean 0 and standard deviation 1, or a new segment began at the suspicious point, with its mean drawn from a \(\mathcal{N}(0, 5^2)\) prior and the same noise. Take \(H = 1/250\), the rate used in the paper's well-log experiment, so prior odds of a change are \(1/249\).

A point at 4 has density 0.000134 under the old segment and 0.0575 under the new-segment prior predictive, a likelihood ratio of about 430. Posterior odds are \(430/249 \approx 1.73\), so the probability of a change is 0.63. Genuinely ambiguous.

If the next point is also 4, the new segment's predictive has tightened around 3.85 and assigns it density 0.283, while the old segment again gives 0.000134. The cumulative ratio passes 900,000 and the change probability exceeds 0.999. If instead the next point returns to 0, the ratio collapses to about 7 and the change probability to 0.03: an outlier, not a regime. The method waits for the second observation as a careful analyst would, and quantifies the wait.

Cost, and a parallel development

The run-length vector grows by one entry per step, so time and memory per step are linear in the data seen so far. The paper's remedy is pruning: discard run lengths whose total posterior mass falls below a threshold such as \(10^{-4}\), giving average cost on the order of the expected run length, though the worst case stays linear. Fearnhead and Liu, the same year, controlled the same growth by resampling (Fearnhead & Liu, 2007, On-line inference for multiple changepoint problems, JRSS B 69(4)).

When it breaks

Misspecified likelihoods create false changes. Under a Gaussian model, one heavy-tailed outlier is so improbable under the current run that a new segment explains it better, and the detector declares a change. Knoblauch, Jewson and Damoulas replaced the likelihood with a robust β-divergence update for exactly this reason (Knoblauch, Jewson & Damoulas, 2018, Doubly Robust Bayesian Inference for Non-Stationary Streaming Data with β-Divergences, NeurIPS, arXiv:1806.02261). There is real disagreement about whether robustness belongs in the likelihood, in the hazard, or in post-hoc filtering of detections.

The hazard and prior are not neutral. A constant hazard says segments have no memory, which is false for many processes; a vague prior on segment parameters inflates the new-segment predictive and makes changes easier to declare. Both are usually set by hand, and detections are sensitive to both.

Within-segment i.i.d. is rarely true. Autocorrelated or seasonal data violate it, and the model reads ordinary seasonal swings as regime changes unless it is applied to residuals or given a time-series likelihood per segment.

Probability is not a decision. Turning a posterior into alerts still requires a threshold, a delay tolerance and a false-alarm budget. Pruning also discards long run lengths that later evidence might have favoured.