Multiple Change Point Analysis: Fast Implementation and Strong Consistency

Jie Ding, Yu Xiang, Lu Shen, Vahid Tarokh

Research output: Contribution to journalArticle

8 Scopus citations

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 multiwindow 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 like criterion gives a strongly consistent selection of the optimal number of change points, while an Akaike information criterion 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 U.S. temperature data and the El Nino data. The experiment leads to some interesting discoveries about temporal variability of the summer-time temperature over the Eastern U.S., and about the most dominant factor of ocean influence on climate, which were also discovered by environmental scientists.

Original languageEnglish (US)
Article number7938741
Pages (from-to)4495-4510
Number of pages16
JournalIEEE Transactions on Signal Processing
Volume65
Issue number17
DOIs
StatePublished - Sep 1 2017
Externally publishedYes

    Fingerprint

Keywords

  • Autoregression
  • change detection
  • information criteria
  • large deviation analysis
  • strong consistency
  • time series

Cite this