PaperlayerView exact revision on arXiv

Source-linked AI summary

Bayesian Online Changepoint Detection

Ryan Prescott Adams, David J. C. MacKay

arXiv:0710.3742v1stat.ML

TL;DR

The paper tackles the limited use of Bayesian changepoint detection for online rather than retrospective inference. It develops an exact message-passing method for the posterior distribution of the current run length under independent segment parameters, and demonstrates it on three real-world datasets.

  • Problem

    Most Bayesian changepoint methods focus on retrospective segmentation, while online filtering is needed for causal prediction from sequential data.

  • Method

    The paper derives an exact Bayesian online algorithm that updates the posterior distribution of the current run length using message passing under independent segment parameters.

  • Results

    The algorithm is demonstrated on three real-world datasets with different modelling requirements: well-log means, Dow Jones return variances, and coal-mine disaster intervals.

  • Takeaways & Limitations

    The method provides a predictive, online interpretation of Bayesian changepoint detection and a simple exact calculation of the posterior probability of the current run length.

  • Takeaways & Limitations

    The model assumes observations are i.i.d. within each segment and segment parameters are i.i.d. across segments.

Abstract

from arXiv · show

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.

1 INTRODUCTION

The paper addresses the gap between online frequentist changepoint detection and predominantly retrospective Bayesian methods by developing an online Bayesian filtering approach. It models independent parameterized segments, tracks the current run length, and supports causal prediction from observed data.

  • Changepoint detection identifies abrupt changes in the generative parameters of sequential data and supports applications including process control, EEG analysis, DNA segmentation, econometrics, and disease demographics.
  • Frequentist methods provide online detectors, whereas most Bayesian approaches focus on retrospective segmentation and posterior sampling over changepoint locations.
  • The paper develops Bayesian online inference for causal predictive filtering, using only observed data to generate a distribution for the next unseen datum.
  • The model assumes independent non-overlapping segments whose observations are i.i.d. within each segment and whose segment parameters are i.i.d.; changepoint intervals follow Pgap(g).
  • Inference targets the posterior distribution of the current run length rt, defined as the time since the last changepoint, with associated observations x(r).
  • Figure 1 represents run-length hypotheses over time: run lengths grow along solid transitions and reset to zero along dotted changepoint transitions.

2 RECURSIVE RUN LENGTH ESTIMATION

The algorithm recursively updates the joint distribution of current run length and observed data using changepoint and predictive probabilities. It supports different initialization priors and exponential-family likelihoods through incrementally maintained sufficient statistics.

  • Recursive run length estimation: The posterior over current run length is obtained by integrating run-length-specific predictive distributions over the run-length posterior.The current run is the time since the last changepoint.
  • Recursive run length estimation: A message-passing recursion combines the prior transition for run length with the predictive probability of the newly observed datum.The predictive distribution depends only on observations since the last changepoint.
  • The changepoint prior: The run-length transition has nonzero probability only for continuation, rt = rt−1 + 1, or a changepoint, rt = 0.The transition probabilities are determined by the hazard function H(τ).
  • The changepoint prior: For a discrete exponential gap prior with timescale λ, the hazard is constant at H(τ) = 1/λ.This makes the changepoint process memoryless.
  • Boundary conditions: Initialization uses either P(r0 = 0) = 1 after a prior changepoint or a normalized survival function for an observed recent data subset.The initialization choice depends on how the sequence was first observed.
  • Conjugate-exponential models: Exponential-family likelihoods enable incremental inference using a finite number of sufficient statistics and compact hyperparameters ν and χ.Conjugate-exponential representations keep both prior and posterior in exponential-family form.

6. Calculate Evidence P(x1:t) =

The algorithm determines the run-length distribution by normalizing the joint probability of the current run length and all observations by the evidence P(x1:t).

  • 6. Calculate Evidence P(x1:t) =: The run-length distribution is computed as P(rt | x1:t) = P(rt, x1:t)/P(x1:t).The evidence P(x1:t) normalizes the joint distribution.

10. Return to Step 2

The implementation combines exact predictive distributions with a run-length recursion and can reduce computation by truncating negligible posterior tails. Figure 2 visualizes predictive uncertainty alongside posterior run-length probabilities for drilling data.

  • 10. Return to Step 2: The algorithm assumes exact predictive distributions parameterized by ν(r), while compact approximations may be used when exact distributions are unavailable.The paper addresses only the exact case.
  • 10. Return to Step 2: Figure 2 overlays drilling data with predictive means and 1-σ error bars, while darker pixels encode higher posterior probability for each current run length.The bottom plot uses a logarithmic color scale.
  • 10. Return to Step 2: Discarding run-length probabilities whose tail mass is below a threshold such as 10−4 yields constant average per-iteration complexity on the order of expected run length E[r].The untruncated algorithm has linear space and time complexity per timestep in the number of observations so far.

3 EXPERIMENTAL RESULTS

The algorithm is demonstrated on three real-world datasets using distinct probabilistic models, with run-length posteriors tracking abrupt changes in well-log means, financial volatility, and coal-mine disaster rates.

  • Three real-world examples use Gaussian mean changes, Gaussian variance changes in Dow Jones returns, and a Poisson model for coal-mine disaster intervals.Each example uses a discrete exponential prior over changepoint intervals.
  • 3.1 WELL-LOG DATA: The well-log analysis uses 4050 nuclear magnetic response measurements to interpret geophysical structure through changes in the data mean.The variations in mean reflect stratification of the earth’s crust.
  • 3.1 WELL-LOG DATA: Drops to zero run length correspond well with abrupt well-log mean changes, while predictive variance increases immediately after a changepoint.The analysis uses a univariate Gaussian model with µ = 1.15×10^5 and σ = 1×10^4, with λ_gap = 250.
  • 3.2 1972-75 DOW JONES RETURNS: Dow Jones daily returns from July 1972 to June 1975 are modeled with a zero-mean Gaussian distribution and piecewise-constant variance.The analysis uses a gamma prior on inverse variance with a = 1 and b = 10^-4, and marks three contemporaneous political and economic events.
  • 3.2 1972-75 DOW JONES RETURNS: Figure 3 displays daily returns with predictive volatility above and the posterior probability of current run length below on a logarithmic color scale.Darker pixels indicate higher run-length probability, and the time axis is in business days.
  • 3.3 COAL MINE DISASTER DATA: Coal-mine explosions killing at least ten people between 1851 and 1962 are modeled as a weekly Poisson process with a gamma prior on the rate.The Coal Mines Regulations Act’s introduction in 1887 is marked, corresponding to weeks 1868 to 1920.

4 DISCUSSION

The paper frames Bayesian changepoint detection as predictive online inference and provides an exact, modular method demonstrated across three real-world datasets.

  • The paper contributes a predictive online interpretation of Bayesian changepoint detection and a simple exact method for calculating current-run-length posteriors.
  • The algorithm is demonstrated on three real-world datasets with different modeling requirements.
  • Separating changepoint code from model implementation enables an object-oriented, pluggable architecture.
Loading 0710.3742v1…