Where Ice Breaks: Finding Change Points in a Random Flow ✎

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
Mathematicians have found a fast and reliable way to identify moments when the behavior of a time series changes, even when the data points are dependent on each other.

The ice cover of a river looks solid, but beneath it lie cracks that alter the flow. So it is 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.

Eastern US temperatures over 120 years changed regime only five times, and these shifts coincide with phases of the Atlantic Multidecadal Oscillation, which lasts 20–40 years.

Classical methods search for cracks by assuming the ice is homogeneous, meaning the data are independent. But in reality, neighboring values in a series are linked, like adjacent ice floes: today's temperature depends on yesterday's. The authors proposed a different approach: they split the series into windows, estimate autoregressive coefficients (dependence on the past) within each window, and then obtain a sequence of nearly independent multivariate points. On these points, fast change-point detection algorithms can be applied.

Key idea: turn dependent data into nearly independent data without losing information about the series structure.

To determine how many cracks truly exist, rather than being imagined, a penalty criterion is used. It acts like a judge who penalizes each extra crack: the sum of quadratic 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. In contrast, an AIC-type criterion with a constant penalty always has a nonzero probability of overfitting, meaning it finds spurious cracks.

On real data, the method worked accurately. In eastern US temperatures from 1895 to 2015, it found change points in 1901, 1929, 1944, 2009, and 2012, coinciding with phases of the Atlantic Multidecadal Oscillation. In the El Niño index from 1854 to 2015, a shift around 1979 was detected, linked to the Pacific Decadal Oscillation. The ice cracked exactly where climatologists expected.

Today, the method can be used in climatology to detect shifts in climate regimes, in finance to spot changes in volatility, and in network security to identify traffic anomalies. Fast and reliable ice tapping saves time and allows you to notice a crack before it becomes a polynya.

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