A message-passing algorithm for the smoothing problem of change point detection
Research and Development Department, GET Capital AG, Heinz-Nixdorf-Strasse 41179, Monchengladbach, Germany
In the framework of regime switching models, change point detection refers to the problem of identifying the time points that divide the time series into homogeneous segments characterized by the same generative parameters. Recently Adams and MacKay developped a Bayesian Online Change Point Detector that computes exactly and online the probability distribution of the current “running length” or time since the last change point by means of a message-passing algorithm.
In this study we address the smoothing problem of change point detection. That is, the estimation of the running length not just of the last but any intermediate point of the time series given the complete set of observations. The solution of the smoothing problem implies the adquisition of valuable information about the whole set of change points in the time series.
Here we present a method that uses a chain factorization of the joint probability distribution of the running lengths and observations to construct a message-passing algorithm that permits to calculate exactly the probability distribution of the running length for any time point. Most importantly, all expressions involved in such an algorithm are also calculated during an iterative evaluation of the Bayesian Online Change Point Detector. That is, the solution of the smoothing problem of change point detection appears without extra effort as a by-product of the sequential online inference of the “running length” of the last avaliable observation in a time series.