Multiple Change Point Analysis: Fast Implementation And Strong Consistency
arXiv:1605.00346 · doi:10.1109/TSP.2017.2711558
Abstract
One of the main challenges in identifying structural changes in stochastic processes is to carry out analysis for time series with dependency structure in a computationally tractable way. Another challenge is that the number of true change points is usually unknown, requiring a suitable model selection criterion to arrive at informative conclusions. To address the first challenge, we model the data generating process as a segment-wise autoregression, which is composed of several segments (time epochs), each of which modeled by an autoregressive model. We propose a multi-window method that is both effective and efficient for discovering the structural changes. The proposed approach was motivated by transforming a segment-wise autoregression into a multivariate time series that is asymptotically segment-wise independent and identically distributed. To address the second challenge, we derive theoretical guarantees for (almost surely) selecting the true number of change points of segment-wise independent multivariate time series. Specifically, under mild assumptions, we show that a Bayesian Information Criterion (BIC)-like criterion gives a strongly consistent selection of the optimal number of change points, while an Akaike Information Criterion (AIC)-like criterion cannot. Finally, we demonstrate the theory and strength of the proposed algorithms by experiments on both synthetic and real-world data, including the Eastern US temperature data and the El Nino data from 1854 to 2015. The experiment leads to some interesting discoveries about temporal variability of the summer-time temperature over the Eastern US, and about the most dominant factor of ocean influence on climate.
arXiv commentA preliminary version of this work was presented in ICML 2016 Anomaly Detection Workshop
References in corpus (5)
- An Algorithm for Optimal Partitioning of Data on an Interval
- Consistencies and rates of convergence of jump-penalized least squares estimators
- A pruned dynamic programming algorithm to recover the best segmentations with to change-points
- Recursive Sparse Point Process Regression with Application to Spectrotemporal Receptive Field Plasticity Analysis
- Learning the Number of Autoregressive Mixtures in Time Series Using the Gap Statistics