Bayesian Online Changepoint Detection

University of Cambridge, Cambridge, UK (2007)
arXiv:0710.3742 [stat.ML] | PDF | Google Doc | Code | Data | Google Scholar | BibTex | EndNote

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.

Keywords:

changepoint detection, graphical models, online learning, time series

Notes:

MATLAB Code

I know I promised Python code in the paper, but I've never been happy with the reusability of the Python code, and I haven't really worked in Python quite some time. Most of my work is now in MATLAB. Also, the numeric libraries for Python seem to be in a great deal of flux. So, what I'm putting up here is an example implementation of the changepoint detection algorithm for a univariate Gaussian with unknown mean and variance. You will need Tom Minka's Lightspeed Toolbox.

There are basically three files:

  • gaussdemo.m: This is a heavily-commented demonstration.
  • constant_hazard.m: This is an example hazard function that just does a constant changepoint rate.
  • studentpdf.m: With conjugate priors, the predictive distribution for the Gaussian inference case has a Student T distribution. This implements it.

If you run the code, you should get an image like this:

I generated this using exportfig in MATLAB. You might not have this tool, however, and should comment this line out. The top show the data, with red x's for the changepoints. The bottom shows the log probability of the run length, and the red line is the maximum.


Data

There are two data sets used in the paper.