A0406
Title: A fast Bayesian online changepoint detection algorithm
Authors: Ziyang Yang - STOR-i Doctoral Training Centre, Lancaster University (United Kingdom) [presenting]
Paul Fearnhead - Lancaster University (United Kingdom)
Idris Eckley - Lancaster University (United Kingdom)
Abstract: Changepoint detection is crucial for online monitoring in many fields, i.e., finance and environment. While frequentist algorithms excel at quickly detecting changes in real-time, there is often a need for more information, such as quantifying the uncertainty of a change or its location. Bayesian changepoint algorithms address this need by providing a posterior distribution. This posterior can be calculated analytically if independence between models is assumed before and after a changepoint and conjugate priors are used. However, the computational complexity of these approaches grows linearly over time, resulting in quadratic time complexity. To overcome this challenge, a fast Bayesian online changepoint detection algorithm is proposed. The quadratic time complexity can be reduced to a constant level by merging potential locations of changes with similar posterior distributions on the post-change parameter. The resulting posterior distribution, which has fewer support points, can still be used for inference. In simulations, the algorithm has a similar speed but higher accuracy compared to a benchmark pruning approach, which only prunes the candidate with the lowest posterior probability. Moreover, the proposed method can also be applied to a range of different models, i.e., detecting changes in slope or slope with seasonality.
