Как найти переломы в потоке данных ✎

Оригинал: "Multiple Change Point Analysis: Fast Implementation And Strong Consistency"
arXiv:1605.00346 · 2016-05-02 · arXiv non-exclusive · собственный разбор · 1 мин
Учёные придумали, как быстро находить моменты, когда поведение временного ряда меняется, даже если данные связаны между собой.

Ледяной покров реки кажется цельным, но под ним есть трещины, которые меняют течение. Так и временной ряд: за ровной поверхностью чисел скрываются моменты, когда правила игры меняются. Эти моменты называют точками смены, и их поиск похож на простукивание льда в поисках слабых мест.

Температура востока США за 120 лет меняла свой режим всего пять раз, и эти смены совпадают с фазами Атлантической мультидекадной осцилляции, которая длится по 20–40 лет.

Классические методы ищут трещины, предполагая, что лёд однороден, то есть данные независимы. Но в реальности соседние значения ряда связаны, как соседние льдины: сегодняшняя температура зависит от вчерашней. Авторы предложили разбить ряд на окна, оценить в каждом окне коэффициенты авторегрессии (зависимости от прошлого), а затем получить последовательность почти независимых точек. На этих точках уже можно применять быстрые алгоритмы поиска переломов.

Чтобы понять, сколько трещин действительно есть, а не примерещилось, используют штрафной критерий. Он похож на судью, который штрафует за каждую лишнюю трещину: сумма квадратичных потерь внутри сегментов плюс штраф за каждую точку смены. Авторы доказали, что если штраф растёт как логарифм от логарифма размера выборки, то метод почти наверняка выбирает истинное число точек смены. На реальных данных метод сработал точно: в температуре востока США он нашёл точки смены в 1901, 1929, 1944, 2009 и 2012 годах, а в индексе Эль-Ниньо — сдвиг около 1979 года. Лёд треснул именно там, где ожидали климатологи.

Температура востока США за последние 120 лет меняла свой режим всего пять раз, и эти смены совпадают с фазами Атлантической мультидекадной осцилляции, которая длится по 20–40 лет.

\hat{M} = \arg\min_{k=0,\ldots,M} (\hat{e}_k + k f(N))
Число точек смены выбирается так, чтобы минимизировать сумму потерь внутри сегментов и штрафа за каждую точку.
\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
Потери равны сумме квадратов отклонений точек сегмента от их среднего.
Понятия
информационный критерий линейная регрессия случайный лес авторегрессионная модель реанализ IRI динамические системы стохастические процессы анализ главных компонент сезонный цикл анализ независимых компонент статистический метод точность предсказаний эталон линейная инверсная модель ретроспективный прогноз вероятностный прогноз перекрёстная проверка климат стохастическое моделирование