Abstract
Changepoints are abrupt variations in the generative parameters of a data sequence. Online detection of changepoints is useful in modelling and prediction of time series in application areas such as finance, biometrics, and robotics. While frequentist methods have yielded online filtering and prediction techniques, most Bayesian papers have focused on the retrospective segmentation problem. Here we examine the case where the model parameters before and after the changepoint are independent and we derive an online algorithm for exact inference of the most recent changepoint. We compute the probability distribution of the length of the current "run," or time since the last changepoint, using a simple message-passing algorithm. Our implementation is highly modular so that the algorithm may be applied to a variety of types of data. We illustrate this modularity by demonstrating the algorithm on three different real-world data sets.
Introduction
In many real-world scenarios, the underlying process generating data changes suddenly—a robot moving between different floor types or a financial market shifting due to policy changes. These "changepoints" are critical for accurate modeling. While frequentist statistics offer online tools, most Bayesian approaches have historically been retrospective, segmenting completed datasets. This paper introduces a modular Bayesian framework for detecting these abrupt changes as they happen. By tracking the "run length"—the time elapsed since the last changepoint—the algorithm provides exact probabilistic inference and improved predictive accuracy with a computational cost that can be kept constant over time.
Methods: The Run Length Perspective
The core innovation is shifting the perspective from "where are the changepoints?" to "how long has the current regime lasted?" This duration is defined as the run length ($r_t$).
The algorithm employs several key strategies:
- Recursive Estimation: Using a message-passing approach, the run length $r_t$ at each time step $t$ has only two possibilities: it either increases by one ($r_t = r_{t-1} + 1$) or a changepoint occurs and it resets to zero ($r_t = 0$).
- The Hazard Function: A "hazard function" models the prior probability of a change. For instance, a constant hazard function represents changes occurring at a constant rate, similar to a Poisson process.
- Conjugate-Exponential Models: The framework is "pluggable." For data following exponential family distributions (e.g., Gaussian, Poisson) with conjugate priors, the math remains exact. Only a small set of "sufficient statistics" needs updating at each step.
- Computational Efficiency: Although the number of possible run lengths grows linearly ($O(t)$), "pruning" low-probability run lengths allows for a constant computational cost ($O(1)$) without significant loss in accuracy.
Applications and Key Results
The authors demonstrate the algorithm's modularity across three distinct real-world datasets: well-log data (nuclear magnetic response), Dow Jones returns (volatility detection), and coal mine disaster records (frequency shifts).
In the Well-Log and Coal Mine data, the algorithm's "drops to zero" in run length probability aligned closely with known historical shifts and physical strata changes. On the Dow Jones data, the model successfully identified increased volatility surrounding events like the resignation of President Nixon. Unlike approximate methods like particle filters, this algorithm provides the exact posterior distribution for the run length.
Discussion
A major advantage of this method is its focus on predictive filtering. By knowing the probability of the current run length, the model determines how much past data remains relevant for future predictions. This leads to automatic uncertainty adjustment: immediately after a detected changepoint, predictive variance spikes as the model recognizes it has little data about the "new" regime, becoming appropriately cautious.
However, the model currently assumes that parameters before and after a changepoint are completely independent. Furthermore, its efficiency relies on conjugate-exponential models; non-conjugate models would require approximations like MCMC. Future work could also explore automated ways to tune hyperparameters, such as the hazard function, online.
Summary updated