Bayesian Online Changepoint Detection

By Ryan P. Adams, David John Cameron MacKay. 2007

889 citations recorded by the source corpus.

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.

Subfields: Artificial Intelligence, Statistics and Probability, Probabilistic & Bayesian Methods

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Statistics and Probability

In Probabilistic & Bayesian Methods

Citations in the corpus

Causal Discovery from Heterogeneous/Nonstationary Data (2019, methodology): “Regarding Problem 3, traditionally, one may use Bayesian change point detection to detect change points of observed time series (Adams and MacKay, 2007) or use sliding windows and then estimate the causal model within each segment separately.”
Causal Discovery from Nonstationary/Heterogeneous Data: Skeleton Estimation and Orientation Determination (2017, methodology): “Improved versions include the online changepoint detection method [ Adams and Mackay, 2007 ] , the online undirected graph learning [Talih and Hengartner, 2005], the locally stationary structure tracker algorithm [Kummerfeld and Danks, 2013], and the regime aware learning algorithm to learn a…”
Benchmark for Skill Learning from Demonstration: Impact of User Experience, Task Complexity, and Start Configuration on Performance (2019, methodology): “Specifically, we created another variation of the task dataset by passing the demonstrations through a motion segmentation routine [28], which divided each trajectory into two segments.”
Continuous Meta-Learning without Tasks (2019, methodology): “The Bayesian online changepoint framework of Adams & MacKay (2007) (which we leverage in this paper) and the similar, simultaneous work of Fearnhead & Liu (2007) have generated a substantial body of follow-on work since their publication.”
Continual Learning in Practice (2019, methodology): “…but non-transient, then the problem is usually called change-point detection (for a recent survey see [27]), with a divide between parametric methods that build a model of p S ( x ) [28] and non-parametric approaches based on estimating the ratio between the densities p S ( x ) and p T ( x ) .”
DCdetector: Dual Attention Contrastive Representation Learning for Time Series Anomaly Detection (2023, methodology): “[32], CL-MPPCA [67]; the density-estimation models: LOF [10], MPPCACD [76], DAGMM [92]; the clustering-based methods: DeepSVDD [60], THOC [64], ITAD [65]; the classic methods: OCSVM [68], OCSVM-based subsequence clustering (OCSVM*), IForest [46], IForest-based subsequence clustering (IForest*), Grad”
Sparse Multi-Output Gaussian Processes for Medical Time Series Prediction (2017, background): “Some possible approaches to explore include incorporating state-space models or change point detection (Adams and MacKay, 2007; Saatçi et al., 2010), and extending those methods to work on multivariate scenarios.”
Causal Discovery and Inference: Concepts and Recent Methodological Advances (2016, methodology): “There exist some methods aiming to detect the changes [Talih and Hengartner (2005); Adams and Mackay 2007); Kummerfeld and Danks 2013)] or directly model time-varying causal relations (see, e.g., Huang et al. (2015)) in a dynamic manner.”
Change-Point Detection in Time-Series Data by Relative Density-Ratio Estimation (2012, methodology): “Depending on the delay of detection, change-point detection methods can be classiﬁed into two categories: Real-time detection (Adams and MacKay, 2007; Garnett et al., 2009; Paquet, 2007) and retrospective detection (Basseville and Nikiforov, 1993; Takeuchi and Yamanishi, 2006; Moskvina and…”
Explicit-Duration Markov Switching Models (2014, background): “More recent Bayesian approaches define a distribution on the number and positions of changepoints through a segmentduration distribution [Fearnhead, 2006, Fearnhead and Liu, 2007, Adams and MacKay, 2007, Fearnhead and Vasileiou, 2009, Eckley et al., 2011].”
Anomaly Transformer: Time Series Anomaly Detection with Association Discrepancy (2021, methodology): “Thus, we also include the BOCPD (Adams & MacKay, 2007) and TS-CP2 (Deldari et al., 2021) from change point detection and UTime (Perslev et al., 2019) from time series segmentation for comparison.”
Unsupervised real-time anomaly detection for streaming data (2017, methodology): “The algorithms evaluated include HTM, Twitter’s Anomaly Detection, Etsy’s Skyline, Multinomial Relative Entropy [32] EXPoSE [23], Bayesian Online Changepoint detection [57], and a simple sliding threshold.”
Deep Reinforcement Learning amidst Lifelong Non-Stationarity (2020, background): “r the HM-MDP [8] assumption of infrequent, discrete, unobserved shifts in the task parameters. In particular, this notion of infrequent, discrete shifts underlies the changepoint detection literature [1, 13]. Previous work both within sequential decision making in changing environments [9, 21, 4] an”