Change points

Looking for regime changes in stochastic processes. a.k.a. Switching state space models

November 29, 2021 — April 1, 2022

Bayes
metrics
Monte Carlo
probabilistic algorithms
signal processing
state space models
statistics
stochastic processes
time series
Figure 1: Non-stationary dynamics turn out to be important in practice.

If our data is stationary, that is great, and we have good estimation theory. However, every non-stationary time series is non-stationary in its own way. A popular type of non-stationarity is change-point type, where we imagine locally stationary series are stapled together.

1 Piecewise wide-sense-stationary time series

Aminikhanghahi and Cook (2017) surveys many types of change-point methods, focusing on ones that use up-to-second-order statistics, i.e. piecewise wide-sense-stationary time series.

2 Online detection

Can we do online state filtering?

3 Online detection with system identification

Can we do online state filtering and identification?

4 Bayesian detection of change points

I am going to file the AdaptSpec methods here, even though they try to marginalize over possible change points, because change points end up being fundamental to these methods, and also I think they are cool (Bertolacci et al. 2020; Rosen, Wood, and Stoffer 2012). You might also imagine these to be probabilistic spectral methods.

I am typically more interested in online methods. A classic is Adams and MacKay (2007), which introduces an auxiliary run time variate that factorizes nicely. The basic algorithm only works for conditionally i.i.d. observations, though. Saatçi, Turner, and Rasmussen (2010) extends it to a Gaussian process time series.

5 Functional

Where the observations are themselves functions.

6 Switching State Space models

a.k.a. mixture filters (Fearnhead 2005, 2004; Fearnhead and Liu 2011, 2007; Fearnhead and Sherlock 2006; Fearnhead and Clifford 2003).

7 As anomaly detection

If we have a “typical” regime with constant coefficients and an “anomalous” one without constant coefficients, then we are in an anomaly detection setting.

8 References

Adams, and MacKay. 2007. Bayesian Online Changepoint Detection.” arXiv:0710.3742 [Stat].
Agudelo-España, Gomez-Gonzalez, Bauer, et al. 2020. Bayesian Online Prediction of Change Points.” In Proceedings of the 36th Conference on Uncertainty in Artificial Intelligence (UAI).
Ahmad, Lavin, Purdy, et al. 2017. Unsupervised Real-Time Anomaly Detection for Streaming Data.” Neurocomputing, Online Real-Time Learning Strategies for Data Streams,.
Aminikhanghahi, and Cook. 2017. A Survey of Methods for Time Series Change Point Detection.” Knowledge and Information Systems.
Aue, Gabrys, Horváth, et al. 2009. Estimation of a Change-Point in the Mean Function of Functional Data.” Journal of Multivariate Analysis.
Berkes, Gabrys, Horváth, et al. 2009. Detecting Changes in the Mean of Functional Observations.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Bertolacci, Rosen, Cripps, et al. 2020. AdaptSPEC-X: Covariate Dependent Spectral Modeling of Multiple Nonstationary Time Series.” arXiv:1908.06622 [Stat].
Detommaso, Hoitzing, Cui, et al. 2019. Stein Variational Online Changepoint Detection with Applications to Hawkes Processes and Neural Networks.” arXiv:1901.07987 [Cs, Stat].
Fearnhead. 2004. Particle Filters for Mixture Models with an Unknown Number of Components.” Statistics and Computing.
———. 2005. Direct Simulation for Discrete Mixture Distributions.” Statistics and Computing.
———. 2011. MCMC for State–Space Models.” In Handbook of Markov Chain Monte Carlo.
Fearnhead, and Clifford. 2003. Online Inference for Hidden Markov Models via Particle Filters.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Fearnhead, and Liu. 2007. Online Inference for Multiple Changepoint Problems.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
———. 2011. Efficient Bayesian Analysis of Multiple Changepoint Models with Dependence Across Segments.” Statistics and Computing.
Fearnhead, and Sherlock. 2006. An Exact Gibbs Sampler for the Markov-Modulated Poisson Process.” Journal of the Royal Statistical Society: Series B (Statistical Methodology).
Gundersen, Cai, Zhou, et al. 2021. Active Multi-Fidelity Bayesian Online Changepoint Detection.” In Proceedings of the Thirty-Seventh Conference on Uncertainty in Artificial Intelligence.
Horváth, Hušková, and Kokoszka. 2010. Testing the Stability of the Functional Autoregressive Process.” Journal of Multivariate Analysis, Statistical Methods and Problems in Infinite-dimensional Spaces,.
Nemeth, Fearnhead, and Mihaylova. 2014. Sequential Monte Carlo Methods for State and Parameter Estimation in Abruptly Changing Environments.” IEEE Transactions on Signal Processing.
Rosen, Wood, and Stoffer. 2012. AdaptSPEC: Adaptive Spectral Estimation for Nonstationary Time Series.” Journal of the American Statistical Association.
Saatçi, Turner, and Rasmussen. 2010. Gaussian Process Change Point Models.” In Proceedings of the 27th International Conference on International Conference on Machine Learning. ICML’10.
Turner, Bottone, and Stanek. 2013. Online Variational Approximations to Non-Exponential Family Change Point Models: With Application to Radar Tracking.” In Advances in Neural Information Processing Systems.
van Delft, Characiejus, and Dette. 2021. A Nonparametric Test for Stationarity in Functional Time Series.” Statistica Sinica.
Vogt, and Dette. 2015. Detecting Gradual Changes in Locally Stationary Processes.” The Annals of Statistics.
Wilson, Nassar, and Gold. 2010. Bayesian Online Learning of the Hazard Rate in Change-Point Problems.” Neural Computation.