Restarted Bayesian online change-point detector achieves optimal detection delay
Article No.: 21, Pages 211 - 221
Abstract
In this paper, we consider the problem of sequential change-point detection where both the changepoints and the distributions before and after the change are assumed to be unknown. For this problem of primary importance in statistical and sequential learning theory, we derive a variant of the Bayesian Online Change Point Detector proposed by (Fearnhead & Liu, 2007) which is easier to analyze than the original version while keeping its powerful message-passing algorithm. We provide a non-asymptotic analysis of the false-alarm rate and the detection delay that matches the existing lower-bound. We further provide the first explicit high-probability control of the detection delay for such approach. Experiments on synthetic and realworld data show that this proposal outperforms the state-of-art change-point detection strategy, namely the Improved Generalized Likelihood Ratio (Improved GLR) while compares favorably with the original Bayesian Online Change Point Detection strategy.
Supplementary Material
Supplemental material.
- Download
- 314.00 KB
References
[1]
Adams, R. P. and MacKay, D. J. Bayesian online change-point detection. arXiv preprint arXiv:0710.3742, 2007.
[2]
Alami, R., Maillard, O., and Féraud, R. Memory bandits: a bayesian approach for the switching bandit problem. In Neural Information Processing Systems: Bayesian Optimization Workshop., 2016.
[3]
Aminikhanghahi, S. and Cook, D. J. A survey of methods for time series change point detection. Knowledge and Information Systems, 51(2):339-367, May 2017. ISSN 0219-3116.
[4]
Basseville, M., Nikiforov, I. V., et al. Detection of abrupt changes: theory and application, volume 104. Prentice Hall Englewood Cliffs, 1993.
[5]
Biswas, R., Limketkai, B., Sanner, S., and Thrun, S. Towards object mapping in non-stationary environments with mobile robots. In IEEE/RSJ international conference on intelligent robots and systems, volume 1, pp. 1014-1019. IEEE, 2002.
[6]
Brodsky, E. and Darkhovsky, B. S. Nonparametric Methods in Change-Point Problems, volume 243. Springer, 1993.
[7]
Caron, F., Doucet, A., and Gottardo, R. On-line changepoint detection and parameter estimation with application to genomic data. Statistics and Computing, 22(2):579-595, 2012.
[8]
Cerqueira, A. and Leonardi, F. Strong consistency of krichevsky-trofimov estimator for the number of communities in the stochastic block model. arXiv preprint arXiv:1804.03509, 2018.
[9]
Cesa-Bianchi, N. and Lugosi, G. Prediction, learning, and games. Cambridge university press, 2006.
[10]
Csörgö, M. and Horváth, L. Limit theorems in change-point analysis, volume 18. John Wiley & Sons Inc, 1997.
[11]
Dakdouk, H., Tarazona, E., Alami, R., Féraud, R., Papadopoulos, G. Z., and Maillé, P. Reinforcement learning techniques for optimized channel hopping in ieee 802.15.4-tsch networks. In Proceedings of the 21st ACM International Conference on Modeling, Analysis and Simulation of Wireless and Mobile Systems, MSWIM '18, pp. 99-107, New York, NY, USA, 2018. ACM. ISBN 978-1-4503-5960-3.
[12]
Fearnhead, P. and Clifford, P. On-line inference for hidden markov models via particle filters. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 65 (4):887-899, 2003.
[13]
Fearnhead, P. and Liu, Z. On-line inference for multiple changepoint problems. Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(4):589- 605, 2007.
[14]
Goldberg, D. and Matarić, M. J. Maximizing reward in a non-stationary mobile robot environment. Autonomous Agents and Multi-Agent Systems, 6(3):287-316, 2003.
[15]
Grzegorczyk, M. and Husmeier, D. Non-stationary continuous dynamic bayesian networks. In Advances in Neural Information Processing Systems, pp. 682-690, 2009.
[16]
Jie, C. and Gupta, A. Parametric statistical change point analysis. Birkh User, 2000.
[17]
Kerkouche, R., Alami, R., Féraud, R., Varsier, N., and Maillé, P. Node-based optimization of lora transmissions with multi-armed bandit algorithms. In 2018 25th International Conference on Telecommunications (ICT), pp. 521-526, June 2018.
[18]
Knoblauch, J. and Damoulas, T. Spatio-temporal bayesian on-line changepoint detection with model selection. arXiv preprint arXiv:1805.05383, 2018.
[19]
Knoblauch, J., Jewson, J. E., and Damoulas, T. Doubly robust bayesian inference for non-stationary streaming data with beta-divergences. In Advances in Neural Information Processing Systems, pp. 64-75, 2018.
[20]
Konidaris, G., Kuindersma, S., Grupen, R., and Barto, A. G. Constructing skill trees for reinforcement learning agents from demonstration trajectories. In Advances in neural information processing systems, pp. 1162-1170, 2010.
[21]
Lai, T. L. and Xing, H. Sequential change-point detection when the pre-and post-change parameters are unknown. Sequential analysis, 29(2):162-175, 2010.
[22]
Maillard, O.-A. Sequential change-point detection: Laplace concentration of scan statistics and non-asymptotic delay bounds. In Algorithmic Learning Theory, pp. 610-632, 2019.
[23]
Mellor, J. and Shapiro, J. Thompson sampling in switching environments with bayesian online change detection. In Artificial Intelligence and Statistics, pp. 442-450, 2013.
[24]
Nandhini, V. and Devasena, M. G. Predictive analytics for climate change detection and disease diagnosis. In 2019 5th International Conference on Advanced Computing & Communication Systems (ICACCS), pp. 1152-1155. IEEE, 2019.
[25]
Niekum, S., Osentoski, S., Atkeson, C. G., and Barto, A. G. Champ: Changepoint detection using approximate model parameters. Technical report, CARNEGIE-MELLON UNIV PITTSBURGH PA ROBOTICS INST, 2014.
[26]
Page, E. S. Continuous inspection schemes. Biometrika, 41 (1/2):100-115, 1954.
[27]
Panda, S. P. and Nayak, A. K. Automatic speech segmentation in syllable centric speech recognition system. International Journal of Speech Technology, 19(1):9-18, 2016.
[28]
Polunchenko, A. S., Tartakovsky, A. G., and Mukhopadhyay, N. Nearly optimal change-point detection with an application to cybersecurity. Sequential Analysis, 31(3): 409-435, 2012.
[29]
Ruggieri, E. and Antonellis, M. An exact approach to bayesian sequential change point detection. Computational Statistics & Data Analysis, 97:71-86, 2016.
[30]
Saatçi, Y., Turner, R. D., and Rasmussen, C. E. Gaussian process change point models. In ICML, pp. 927-934, 2010.
[31]
Schmitt, T. A., Chetalova, D., Schäfer, R., and Guhr, T. Nonstationarity in financial time series: Generic features and tail behavior. EPL (Europhysics Letters), 103(5):58003, 2013.
[32]
Tartakovsky, A. Sequential methods in the theory of information systems, 1991.
[33]
Turner, R., Saatci, Y., and Rasmussen, C. E. Adaptive sequential bayesian change point detection. In Temporal Segmentation Workshop at NIPS, pp. 1-4, 2009.
[34]
Turner, R. D., Bottone, S., and Stanek, C. J. Online variational approximations to non-exponential family change point models: with application to radar tracking. In Advances in Neural Information Processing Systems, pp. 306-314, 2013.
[35]
Wilson, R. C., Nassar, M. R., and Gold, J. I. Bayesian online learning of the hazard rate in change-point problems. Neural computation, 22(9):2452-2476, 2010.
[36]
Wu, Y. Inference for change point and post change means after a CUSUM test, volume 180. Springer, Lecture Notes in Statistics, 2007.
[37]
Xuan, X. and Murphy, K. Modeling changing dependency structure in multivariate time series. In Proceedings of the 24th international conference on Machine learning, pp. 1055-1062, 2007.
Recommendations
BARO: Robust Root Cause Analysis for Microservices via Multivariate Bayesian Online Change Point Detection
Detecting failures and identifying their root causes promptly and accurately is crucial for ensuring the availability of microservice systems. A typical failure troubleshooting pipeline for microservices consists of two phases: anomaly detection and root ...
Online Change-Point Detection of Linear Regression Models
In this paper, we consider the problem of quickly detecting an abrupt change in linear regression models. Specifically, an observer sequentially obtains a sequence of observations, whose underlying linear model changes at an unknown time. Moreover, the ...
Multi-stage change-point detection scheme for large-scale simultaneous events
Change-point detection schemes, which represent one type of anomaly detection schemes, are a promising approach for detecting network anomalies, such as attacks and epidemics by unknown viruses and worms. These events are detected as change-points. ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Copyright © 2020.
Publisher
JMLR.org
Publication History
Published: 13 July 2020
Qualifiers
- Research-article
- Research
- Refereed limited
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 106Total Downloads
- Downloads (Last 12 months)86
- Downloads (Last 6 weeks)7
Reflects downloads up to 03 Jan 2025
Other Metrics
Citations
View Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in