Где ломается лёд: как найти переломы в случайном потоке ✎

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

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

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

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

Ключевая идея: превратить зависимые данные в почти независимые, не потеряв информацию о структуре ряда.

Чтобы понять, сколько трещин действительно есть, а не примерещилось, используют штрафной критерий. Он похож на судью, который штрафует за каждую лишнюю трещину: сумма квадратичных потерь внутри сегментов плюс штраф за каждую точку смены. Авторы доказали, что если штраф растёт как логарифм от логарифма размера выборки, то метод почти наверняка выбирает истинное число точек смены. А вот критерий типа AIC с постоянным штрафом всегда даёт ненулевую вероятность переобучения, то есть находит лишние трещины.

На реальных данных метод сработал точно. В температуре востока США за 1895–2015 годы он нашёл точки смены в 1901, 1929, 1944, 2009 и 2012 годах, совпадающие с фазами Атлантической мультидекадной осцилляции. В индексе Эль-Ниньо за 1854–2015 годы обнаружен сдвиг около 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 динамические системы стохастические процессы анализ главных компонент сезонный цикл анализ независимых компонент статистический метод точность предсказаний эталон линейная инверсная модель ретроспективный прогноз вероятностный прогноз перекрёстная проверка климат стохастическое моделирование