Stein Variational Online Changepoint Detection with Applications to Hawkes Processes and Neural Networks

arXiv.org Machine Learning

Bayesian online changepoint detection (BOCPD) (Adams & MacKay, 2007) offers a rigorous and viable way to identity changepoints in complex systems. In this work, we introduce a Stein variational online changepoint detection (SVOCD) method to provide a computationally tractable generalization of BOCPD beyond the exponential family of probability distributions. We integrate the recently developed Stein variational Newton (SVN) method (Detommaso et al., 2018) and BOCPD to offer a full online Bayesian treatment for a large number of situations with significant importance in practice. We apply the resulting method to two challenging and novel applications: Hawkes processes and long short-term memory (LSTM) neural networks. In both cases, we successfully demonstrate the efficacy of our method on real data.


Lagged Exact Bayesian Online Changepoint Detection

arXiv.org Machine Learning

Identifying changes in the generative process of sequential data, known as changepoint detection, has become an increasingly important topic for a wide variety of fields. A recently developed approach, which we call EXact Online Bayesian Changepoint Detection (EXO), has shown reasonable results with efficient computation for real time updates. However, when the changes are relatively small, EXO starts to have difficulty in detecting changepoints accurately. We propose a new algorithm called $\ell$-Lag EXact Online Bayesian Changepoint Detection (LEXO-$\ell$), which improves the accuracy of the detection by incorporating $\ell$ time lags in the inference. We prove that LEXO-1 finds the exact posterior distribution for the current run length and can be computed efficiently, with extension to arbitrary lag. Additionally, we show that LEXO-1 performs better than EXO in an extensive simulation study; this study is extended to higher order lags to illustrate the performance of the generalized methodology. Lastly, we illustrate applicability with two real world data examples comparing EXO and LEXO-1.


M-Statistic for Kernel Change-Point Detection

Neural Information Processing Systems

Detecting the emergence of an abrupt change-point is a classic problem in statistics and machine learning. Kernel-based nonparametric statistics have been proposed for this task which make fewer assumptions on the distributions than traditional parametric approach. However, none of the existing kernel statistics has provided a computationally efficient way to characterize the extremal behavior of the statistic. Such characterization is crucial for setting the detection threshold, to control the significance level in the offline case as well as the average run length in the online case. In this paper we propose two related computationally efficient M-statistics for kernel-based change-point detection when the amount of background data is large.


Spatio-temporal Bayesian On-line Changepoint Detection with Model Selection

arXiv.org Machine Learning

Bayesian On-line Changepoint Detection is extended to on-line model selection and non-stationary spatio-temporal processes. We propose spatially structured Vector Autoregressions (VARs) for modelling the process between changepoints (CPs) and give an upper bound on the approximation error of such models. The resulting algorithm performs prediction, model selection and CP detection on-line. Its time complexity is linear and its space complexity constant, and thus it is two orders of magnitudes faster than its closest competitor. In addition, it outperforms the state of the art for multivariate data.


A Review of Changepoint Detection Models

arXiv.org Machine Learning

Detecting abrupt changes in time-series data has attracted rese archers in the statistics and data mining communities for decades Basseville and Nikiforov ( 1993). Based on the instantaneousness of detection, changepoint detection algorithm s can be classified into two categories: online changepoint detection and offline changepoint de tection. While the online change detection targets on data that requires instantaneous r esponses, the offline detection algorithm often triggers delay, which leads to more accurate result s. This literature review mainly focuses on the online changepoint detection algorithms. There are plenty of changepoint detection algorithms that have be en proposed and proved pragmatic. The pioneering works Basseville and Nikiforov ( 1993) compared the probability distributions of time-series samples over the past and pr esent intervals. The algorithm demonstrates an abrupt change when two distributions a re significantly different.