How to Find Breaks in a Data Stream ✎

Original: "Multiple Change Point Analysis: Fast Implementation And Strong Consistency"
· Jie Ding, Yu Xiang, Lu Shen, Vahid Tarokh
arXiv:1605.00346 · 2016-05-02 · arXiv non-exclusive · independent analysis · 2 min
Scientists have figured out how to quickly spot moments when a time series changes behavior, even when the data points are correlated.

The ice cover on a river looks solid, but beneath it lie cracks that alter the flow. So too with a time series: behind the smooth surface of numbers hide moments when the rules of the game change. These moments are called change points, and finding them is like tapping the ice to locate weak spots.

The temperature in the eastern United States over 120 years changed its regime only five times, and these shifts coincide with phases of the Atlantic Multidecadal Oscillation, which lasts 20–40 years.

Classical methods look for cracks by assuming the ice is homogeneous, meaning the data are independent. But in reality, neighboring values in a series are connected, like adjacent ice floes: today's temperature depends on yesterday's. The authors proposed splitting the series into windows, estimating autoregressive coefficients (the dependence on the past) within each window, and then obtaining a sequence of nearly independent points. Fast change-point algorithms can then be applied to these points.

To determine how many cracks truly exist rather than how many are imagined, a penalized criterion is used. It acts like a judge who fines you for every extra crack: the sum of squared losses within segments plus a penalty for each change point. The authors proved that if the penalty grows as the logarithm of the logarithm of the sample size, the method almost surely selects the true number of change points. On real data, the method worked precisely: in eastern U.S. temperatures, it found change points in 1901, 1929, 1944, 2009, and 2012, and in the El Niño index, a shift around 1979. The ice cracked exactly where climatologists expected.

Eastern U.S. temperatures over the last 120 years have changed their regime only five times, and these shifts coincide with phases of the Atlantic Multidecadal Oscillation, which lasts 20 to 40 years.

\hat{M} = \arg\min_{k=0,\ldots,M} (\hat{e}_k + k f(N))
The number of change points is chosen to minimize the sum of within-segment losses plus a penalty for each point.
\mathrm{Loss}_q(x_{\ell_{j-1}+1},\ldots,x_{\ell_j}) = \sum_{n=\ell_{j-1}+1}^{\ell_j} |x_n - \bar{x}|^2
The loss equals the sum of squared deviations of the segment points from their mean.
Concepts
information criterion linear regression random forest autoregressive model reanalysis IRI Dynamical Systems stochastic processes principal component analysis seasonal cycle independent component analysis statistical method prediction accuracy benchmark linear inverse model retrospective forecast probabilistic forecast cross validation climate Stochastic modeling