Обнаружение критических точек на фондовом рынке

Размещено на http://www.allbest.ru/

Размещено на http://www.allbest.ru/

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ АВТОНОМНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ОБРАЗОВАНИЯ

«НАЦИОНАЛЬНЫЙ ИССЛЕДОВАТЕЛЬСКИЙ УНИВЕРСИТЕТ

«ВЫСШАЯ ШКОЛА ЭКОНОМИКИ»

Факультет экономических наук

Выпускная квалификационная работа

Обнаружение критических точек на фондовом рынке

Экономическое моделирование

Ткаченко Владислав Леонидович

Руководитель:

PhD, доцент Веретенникова М.А.

Москва 2019

Оглавление

Введение

Глава 1. Change point detection и его приложения в финансах

1.1 О применении CPD к анализу временных рядов

1.2 Некоторые приложения CPD-решений к финансам

Глава 2. Методы, используемые в исследовании

2.1 Оффлайн CPD

2.2 Facebook Prophet

2.3 Онлайн CPD

2.4 LSTM нейросеть

2.5 Математическая модель броуновского движения

Глава 3. Результаты исследования

3.1 Предсказывание критических точек с помощью комбинации оффлайн CPD и алгоритма Prophet

3.2 Применение онлайн CPD-алгоритмов

3.3 Краткосрочное предсказание колебаний фондового рынка с помощью LSTM-нейросети

3.4 Моделирование колебаний фондового рынка с помощью броуновского движения

Заключение

Список литературы

Введение

Фондовый рынок сегодня - ключевое звено финансового рынка, на котором сосредоточена огромная часть всего капитала человечества. Его роль настолько огромна, что без него невозможно представить современную рыночную экономику. Соответственно, важность исследований в этой области не нуждается в описании.

Историю таких исследований можно начать с «Гипотезы эффективного рынка» Юджин Фама, 1965, первые теоретические положения которой высказал Луи де Башелье в 1900 году. Основная мысль этой гипотезы в том, что вся значимая информация немедленно отражается на биржевых котировках, а значит, невозможно быть уверенным в получении спекулятивной прибыли сверх средней рыночной. Иными словами, невозможно «победить» финансовый рынок. К тому же, биржевые колебания имеют случайную природу и предсказать их крайне тяжело.

Однако, в 30-е годы XX века появилась «Волновая теория» Ральфа Эллиота, который утверждал, что поведение цен на фондовом рынке следует определенным шаблонам, в основе которых лежат числа Фибоначчи. Он заметил 13 таких шаблонов, которые так или иначе возникают в данных о биржевых котировках.

Мнение о «не совсем случайной» природе финансовых рядов было позднее поддержано «Теорией динамического хаоса» https://ru.wikipedia.org/wiki/Динамический_хаос. Согласно этой теории, поведение финансового ряда как нелинейной системы только выглядит случайным, когда на самом деле определяется некоторыми детерминистическими законами. Таким образом, котировки фондового рынка допускают краткосрочное прогнозирование.

Далее количество исследований в этой области стало стремительно расти, особенно с распространением вычислительной техники и развитием статистического моделирования. В настоящее время существует множество подходов к анализу финансовых рядов, один из них - задачи обнаружения критических точек, или change point detection (CPD).

Change point - это момент времени, в который у последовательности меняются статистические свойства Graham Laidler, Sequential Changepoint Detection, Lancaster University, 2017. Вовремя определяя такие точки, можно понять дальнейшее поведение ряда и, соответственно, принять решение об инвестиционной стратегии.

Сам по себе CPD - это целый отдельный раздел машинного обучения, делящийся, в свою очередь, на подразделы по отдельным задачам, для решения каждой из которых существует множество различных методик. Помимо финансов, этот подход к анализу последовательностей широко используется в таких областях как:

Медицина - мониторинг различных физиологических показателей пациента, например с помощью электроэнцефалограммы (ЭЭГ), электрокардиограммы (ЭКГ) и т. д.;

Исследования погоды - мониторинг изменения состава атмосферы и прочих факторов, влияющих на потенциальные климатические перемены;

Распознавание речи - мониторинг пауз, интонации и прочего для автоматического конвертирования речи в текст;

Анализ человеческого поведения - определение изменений в привычном поведении для контроля здоровья и безопасности, используется, например, умными домами;

И другие.

В данной работе применяется несколько подходов к определению критических точек в кризисных ситуациях различных финансовых рядов, рассматриваются онлайн и оффлайн CPD алгоритмы, а также решаются задачи краткосрочного предсказания поведения цены актива с помощью рекуррентной нейронной сети и моделирования ряда с помощью некоторых положений теории случайных процессов.

Цель работы заключается в оценке эффективности применения к финансовым рядам некоторых CPD-подходов, которые хорошо себя зарекомендовали во многих сферах, где уже сейчас активно применяются.

Для достижения поставленной цели, в работе решаются следующие задачи:

Предсказание критических точек с помощью комбинации оффлайн CPD-алгоритмов и алгоритма прогнозирования временных рядов;

Применение нескольких онлайн CPD-алгоритмов;

Краткосрочное предсказание временного ряда с помощью рекуррентной нейросети;

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

Объектом исследования являются финансовые ряды ежедневных цен закрытия индексов Dow Jones Industrial Average и Moex в различные кризисные периоды.

Предмет исследования - легитимность применения описываемых методик при построении инвестиционных стратегий.

Методологическая база исследования представляет из себя совокупность нескольких современных и популярных подходов к анализу и моделированию финансовых рядов. Среди них алгоритмы машинного обучения (CPD-алгоритмы и нейросеть для краткосрочного прогноза), аддитивная модель предсказывания временных рядов с нелинейными эффектами и математическая модель броуновского движения из теории случайных процессов. Для реализации практической части работы использован язык программирования Python версии 3.6.7.

Информационная база исследования включает в себя ежедневные данные о ценах закрытия индекса Dow Jones Industrial Average (DJIA) с 1914 по 2019 года и индекса Мосбиржи (Moex) с 1997 по 2019 года. Из этих данных выделены выборки докризисных и кризисных периодов, которые сосредоточены вокруг «Великой депрессии» 1929 года и «Черного понедельника» 1987 года для индекса DJIA, а также «Мирового финансового кризиса» 2008 года для индекса Мосбиржи. Данные взяты с сайта Мосбиржи https://www.moex.com/ и сайта Macrotrends https://www.macrotrends.net/.

Содержательная часть данной работы состоит из трех глав, введения и заключения. В первой главе будут рассмотрены семь статей, посвященных CPD-проблеме в целом и в финансах в частности. Вторая глава состоит из подробного описания всех используемых в работе алгоритмов и методов. В третьей главе представлены результаты решения поставленных задач и их анализ.

Глава 1. Change point detection и его приложения в финансах

1.1 О применении CPD к анализу временных рядов

Временные ряды - это последовательности каких-либо измерений за определенный период времени, которые описывают поведение каких-либо систем S. Aminikhanghahi, D.J. Cook «A survey of methods for time series change point detection», Springer, 2016. Анализ таких последовательностей очень важен для огромного количества самых разнообразных сфер деятельности - медицины, финансов, бизнеса, метеорологии, аэрокосмонавтики и многих других. Поведение временных рядов может со временем меняться в силу неожиданных внешних факторов или в силу систематических внутренних изменений в динамике последовательности. Таким образом, чтобы анализ временного ряда был качественным, возникает задача изучения возможных изменений последовательности. Эта задача называется Change point detection problem (CPD), формальное определение которой уже было дано во введении.

Для знакомства с CPD хорошо подходит статья S. Aminikhanghahi,

D. J. Cook «A survey of methods for time series change point detection», опубликованная в журнале Springer в 2016 году. Проведем небольшой обзор информации из этой статьи, которая поможет в понимании данного исследования.

Итак, допустим есть временной ряд, свойства которого менялись в силу тех или иных факторов. Периоды неизменности каждой группы свойств ряда будем называть состояниями, а точку, разделяющую два последовательно идущих состояния - критической точкой или change point`ом. Для наглядности рассмотрим график среднегодовой температуры в Шпицбергене с 1899 по 2010 годы:



Рис. 1. Пример временного ряда с разными состояниями.

Источник: S. Aminikhanghahi, D. J. Cook «A survey of methods for time series change point detection», Springer, 2016

На графике видно, что описываемый ряд находился в шести состояниях за указанный период. Рассмотрим следующее определение:

Пусть имеется временной ряд T фиксированной длины m, - наблюдение в момент времени t. Тогда матрица WM всех возможных подпоследовательностей длины k может быть построена путем перемещения скользящего окна длины k вдоль T и записывания подпоследовательности в p-й столбец матрицы WM. Результирующая матрица будет иметь размер (m-k+1) ? n.

Наглядное изображение таких «окон» можно увидеть на рисунке 2:

Рис. 2. Пример скользящих окон.

Источник: S. Aminikhanghahi, D. J. Cook «A survey of methods for time series change point detection», Springer, 2016

Теперь можно рассмотреть еще одно, более формальное с точки зрения математической статистики определение change point`а:

Пусть - последовательность наблюдений временного ряда. Задача обнаружения критической точки (CPD) может быть сформулирована как задача тестирования гипотезы с двумя альтернативами: нулевая гипотеза «Изменений не происходит» против альтернативной гипотезы

«Изменение происходит». При этом:

функция плотности вероятности скользящего окна, начинающего с точки , а - критическая точка (change point).

На этом моменте заметим, что представленное нами определение нельзя назвать общим описанием CPD-проблемы, так как его выполнение подразумевает единовременное наблюдение всей последовательности. В общем же, задача обнаружения критических точек подразделяется на онлайн или последовательный подход и оффлайн или ретроспективный подход.

Мы уже начали описание ретроспективного подхода (именно для него справедливо определение через альтернативные гипотезы) и продолжим расширением этой темы. Она подробно описана в статье A. Louise,

M. M. Shrцder «Methods for Change-Point Detection with Additional Interpretability», London School of Economics and Political Sciences, 2016.

Итак, при оффлайн-подходе для анализа доступен весь временной ряд . Задача такого подхода - определить количество и положение критических точек как можно более точно. При этом ретроспективный подход традиционно делится на задачу обнаружения единственной критической точки последовательности и задачу обнаружения нескольких таких точек.

В случае единственной точки важно заметить, что определение наличия критической точки и определение её положения - это две разные задачи. Тогда задача оффлайн-подхода формулируется как «определить, присутствует ли критическая точка в рассматриваемой последовательности и, если да, найти её наиболее вероятное местоположение». Однако, чаще всего обе задачи решаются вместе и раздельное их рассмотрение встречается на практике крайне редко. Тестирование на наличие критической точки отличается от классического тестирования гипотез тем, что здесь появляется задача множественного тестирования: каждая точка последовательности, кроме близких к граничным, является потенциальным change point`ом. Таким образом та точка, для которой тестовая статистика определит наибольшую вероятность статуса критической, и будет оценена как искомый change point.

В случае нескольких критических точек, задачи определения наличия и местоположения change point`ов также можно разделить на две, при этом основной проблемой является вычислительный ресурс: предположим наличие критических точек в последовательности

. Исследователя интересует количество этих точек и их местоположения . Таким образом, в идеале хотелось бы рассмотреть все возможные комбинации количества и локаций на всем временном промежутке . В результате все эти модели нужно будет сравнить с помощью какой-нибудь метрики качества, в то время как они сами должны быть экономичными в плане вычислительных затрат. Однако, сравнение всех возможных моделей невыполнимо даже для T больше нескольких сотен. В качестве доказательства, рассмотрим последовательность, в которой критические точки разделены каким-нибудь маленьким целым числом наблюдений . Тогда необходимо оценить T моделей с ровно одним предполагаемым change point`ом, моделей с двумя change point`ами и так далее. Поэтому существующие процедуры определения множества критических точек используют специальные критерии, исключающие те решения, которые проигрывают хотя бы одному другому в множестве рассматриваемых решений. Именно эти критерии и определяют экономичность таких процедур - чем более эффективно проходит процесс исключения, тем быстрее находится оптимальное решение. При этом вычислительные затраты все равно могут оказаться очень высокими, в таких ситуациях допускаются близкие к оптимальным решения для существенного увеличения экономичности.

При онлайн-подходе анализ производится последовательно с появлением каждого нового наблюдения. Подробное описание основ такого подхода можно найти в работе M. Basseville, I. V. Nikiforov «Detection of abrupt changes: theory and application», Prentice Hall Englewood Cliffs, 1993.

Итак, в базовом варианте, задача онлайн-обнаружения критических точек может быть сформулирована следующим образом:

Пусть ( - последовательность наблюдаемых случайных величин с условной плотностью . До неизвестного момента времени , в который наступает изменение последовательности, параметр и константен и равен . Затем, после наступления изменения, параметр и принимает значение . Задача заключается в обнаружении изменения как можно скорее, при этом с фиксированной долей так называемых «ложных сигналов тревоги» до момента . В базовом варианте не требуется оценка момента изменения и не требуется оценка параметров и . Ложным сигналом тревоги, как следует из самой формулировки, называется факт определения алгоритмом изменения, когда на самом деле его не произошло. Также предполагается, что в случае нескольких критических точек, каждое изменение последовательности определяется достаточно быстро, чтобы в каждый момент времени необходимо было учитывать только одну потенциальную критическую точку, и они определялись одна за другой. При онлайн-подходе обнаружение критической точки определяется так называемым «правилом остановки» (stopping rule), которое в базовом варианте выглядит следующим образом:

,

где л это порог, определяющий достаточное для статуса критической точки изменение, а - семейство функций из n координат. Сигнал тревоги - это момент времени, в который изменение последовательности было обнаружено. При этом, если , достаточно наблюдать последовательность до момента времени n, что объясняет название «последовательного» или «онлайн» подхода. Критерием качества онлайн CPD-алгоритмов является задержка обнаружения критической точки (в идеале алгоритм должен определять её сразу при появлении) и среднее время между ложными сигналами тревоги. Существует также и общий, объединенный критерий качества, суть которого в минимизации задержки обнаружения критической точки для фиксированного среднего времени между ложными сигналами тревоги.

На этом мы закончим общее описание проблемы обнаружения критических точек последовательности. В данной работе используются несколько оффлайн и онлайн CPD-процедур, каждая из которых подробно описана в разделе «Методы, применяемые в исследовании».

1.2 Некоторые приложения CPD-решений к финансам

Начнем рассмотрение CPD-приложений к финансам с двух работ, написанных одними из основоположников исследований проблемы критических точек на финансовых рядах - А. Н. Ширяевым,

М. В. Житлухиным и У. Т. Зиембой (Ширяев занимается исследованиями в этой области еще с 60-х годов XX века).

Первая из этих работ называется «When to sell Apple and the NASDAQ? Trading bubbles with a stochastic disorder model» A. N. Shiryaev, M. V. Zhitlukhin, W. T. Ziemba «When to sell Apple and the NASDAQ? Trading bubbles with a stochastic disorder model», 2013. В ней авторы применяют так называемую «модель стохастического процесса в непрерывном времени», разработанную Ширяевым и Житлухиным, для определения оптимальных моментов продажи акций в ситуации экономических пузырей https://ru.wikipedia.org/wiki/Экономический_пузырь. Модель тестируется на данных о ценах акций компании Apple в различные периоды с 2009 по 2012 года, с особым акцентом на период после локального спада

6 Марта 2009, а также на данных о ценах индекса NASDAQ-100, на котором очень успешный трейдер Джордж Сорос потерял деньги в 2000 году.

Модель Ширяева-Житлухина предполагает, что цены акций описываются геометрическим броуновским движением с разладкой (критической точкой), что является случайным процессом , определяемым дифференциальным уравнением

,

где или - константные параметры, - стандартное броуновское движение,

- неизвестный момент «разворота тренда», в который «коэффициент скольжения» процесса S меняет значение с на .

Цены наблюдаются в виде последовательности , которая изначально имеет положительный тренд, а затем в какой-то неизвестный момент времени тренд разворачивается. Также предполагается, что тренд развернется до заключительного момента времени N. Таким образом, выбрав начальный момент времени n < N, задача состоит в определении оптимального момента времени для закрытия позиции, при этом последовательность наблюдается онлайн. Случай изначального положительного тренда предполагает открытие длинной позиции в момент времени n, однако модель работает аналогичным образом и для коротких позиций - случая изначального негативного тренда.

Процесс происходит в непрерывном времени и авторы для удобства выбирают временную шкалу, в которой каждый день торгов имеет продолжительность . Тогда t = 0 соответствует времени входа на рынок, обозначаемому n, t = T соответствует заключительному моменту времени N (), а наблюдаемая в режиме реального времени цена соответствует значению процесса S в момент времени .

Что же касается интересующего нас момента времени и, для его определения авторы используют байесовский подход, согласно которому и предполагается случайной величиной с областью значений [0, T] и не зависящей от B. В силу трудности определения на практике специфики распределения и, авторы используют «худший» случай - предполагают, что и равномерно распределена на [0, T], так как равномерное распределение характеризуется максимальной энтропией на конечном интервале.

Момент закрытия позиции называется временем остановки , а задачу, в случае длинной позиции, открытой в момент времени n, теперь можно сформулировать как нахождение некоторого , максимизирующего среднюю цену акции. Аналогично для короткой позиции: нахождение , минимизирующего среднюю цену акции. В математических терминах эти задачи записываются как , .

Процедура нахождения оптимального основана на процессе

, который называется статистикой Ширяева-Робертса и определяется как

,

где

, а . Позиция закрывается в первый же момент времени , в который процесс пересекает некоторую зависящую от времени границу . Функция a(t) зависит от параметров и находится из определенного интегрального уравнения Shiryaev and Zhitlukhin, 2012b. Также эта функция является убывающей и a(T) = 0, то есть всегда пересекается с ней до момента времени T.

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

и , где .

Параметр выбирается субъективно из предположения о скорости падения цены после того, как «пузырь лопнет». Авторы используют значение

объясняя это тем, что несмотря на то, что цены в ситуациях с экономическими пузырями обычно падают быстрее, чем растут, изменение значения на более низкое не значимо влияет на результаты модели.

Применяя модель для акций Apple, авторы рассмотрели 8 различных дней открытия позиции: 30 июня 2009, 31 декабря 2009, 30 июня 2010, 31 декабря 2010, 30 июня 2011, 30 декабря 2011, 29 июня 2012 и 31 июля 2012. При этом пузырь, как уже было сказано ранее, начался с локального минимума цены 6 марта 2009. Таким образом, последовательность цен начиналась 6 марта 2009 и заканчивалась 31 декабря 2012, что насчитывает 962 торговых дня. Для всех восьми рассмотренных начальных позиций модель определила время остановки в моменты времени, когда цена соответствовала около 90% от максимального значения на всей последовательности. При этом ожидаемая прибыль составила от 13.83% до 59.07%, в зависимости от выбранного начального дня.

Что касается применения модели к торгам NASDAQ-100, также были выбраны 8 начальных дней в период с 1994 по 1999 года для случая длинной позиции, и результаты в терминах ожидаемой прибыли находятся в промежутке от 41.48% до 55.88%. Случай короткой позиции на данном индексе был рассмотрен для трех начальных дней: 31 января 2001, 29 июня 2001 и 28 февраля 2002. Ожидаемая прибыль соответственно составила 46.01%, 35.13% и 26.80%.

Вторая описываемая здесь работа этих же авторов называется «Exit strategies in bubble-like markets using a changepoint model» M. V. Zhitlukhin, W. T. Ziemba «Exit strategies in bubble-like markets using a changepoint model», 2016. В ней рассматривается применение стохастической CPD-модели к ситуациям обвала рынка в США 1929, 1987 и 2008 годов, а также к обвалу в Китае в 2015.

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

,

где - независимые стандартные нормальные случайные величины, и - константы.

Далее предпосылки модели во многом напоминают описанные в предыдущей статье: предполагается вход на рынок в момент времени n = 0 с параметрами и , оцененными по прошлым данным и выбирается момент времени N, в который в любом случае будет осуществлен уход с рынка. Критическая точка и может возникнуть в любой момент времени с одинаковыми вероятностями (напоминает равномерное распределение и из предыдущей статьи). То есть, и случайна и независима от , . Параметры p, N, , выбираются субъективно.

Задача также формулируется очень похоже с предыдущей:

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

, необходимые для исключения краевых решений и = 0 и и = N. Оптимальное время остановки, как и в предыдущей статье, находится с помощью статистики Ширяева-Робертса, однако здесь она определяется рекурсивно по следующему правилу:

.

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

. Функция b определяется из интегрального уравнения, детали можно увидеть в оригинале описываемой статьи.

Применяя данную модель к ситуации краха индекса DJIA в 1929 году, авторы оценили параметры по данным предыдущего года торгов для каждого из дней открытия позиции; вероятность возникновения критической точки p была взята в размере 75%, а выбранная функция полезности . Параметры тестировались в нескольких наборах, однако наилучшие результаты показал набор : для пяти разных начальных дней модель определила момент ухода, в который цена составляла от 84% до 90% от максимальной цены на всей рассмотренной последовательности. Результаты для ситуации краха S&P 500 в 1987 году с таким же набором параметров оказались даже лучше: от 89% до 92% от максимального значения цены для пяти рассмотренных начальных дней. В случае кризиса 2008 года и китайского обвала 2015 результаты также отличные - в среднем 89% и 87% соответственно.

Модели, рассмотренные в обеих статьях, конечно, очень впечатляют. Первая имеет преимущество над второй в плане отсутствия необходимости субъективного подбора вероятности наступления критической точки и меньшего количества гиперпараметров вообще, что делает её более применимой для ситуации неизвестного будущего, в которой удачно оценить вероятность краха может быть затруднительно. Однако, в случае успеха, вторая модель может показывать результаты, близкие к идеальным. В своей работе я использую несколько подходов к определению критических точек и проверяю их в ситуациях, близких к описанным авторами двух рассмотренных статей. Также я провожу аналогичную оценку эффективности рассматриваемых методов.

Далее рассмотрим статью О. Гоголевой и Е. Щербаковой «On-line change-point detection procedures for Initial Public Offerings» O. Gogoleva, E. Shcherbakova «On-line change-point detection procedures for Initial Public Offerings», Halmstad University, 2010. В данной статье рассматриваются акции, только что вышедшие на рынок, про которые известно, что цена изначально растет или падает до какого-то устойчивого уровня, после которого уже начинаются колебания. Момент перехода цен в устойчивое состояние определяется несколькими онлайн CPD-алгоритмами, которые сравниваются в эффективности. Авторы полагают, что цена описывается AR (1) процессом, при этом среднее значение сначала зависит от коэффициента наклона, а затем становится константным.

Итак, с учетом предпосылок авторов, процесс изменения цены переписывается в виде . Функция

- условное математическое ожидание наблюдаемого процесса, предположение о сдвиге в среднем описывается как , а безусловное математическое ожидание AR (1) процесса - . Далее рассуждения следующие: до момента времени и, в который предполагается сдвиг, справедливо равенство , в момент времени и: , после и: . Выразив из каждого равенства и соединив все три условия, получаем

.

При моделировании также используется свойство стационарности AR (1) процесса при .

Учитывая все вышеописанное, авторы применяют пять онлайн-процедур для определения момента времени и: метод Шеварта, метод кумулятивных сумм (CUSUM), метод Ширяева-Робертса, метод EWMA и метод отношения правдоподобий (Likelihood ratio). Все эти методы работают по принципу «правила остановки», которое можно в общем описать как

, где - функция тревоги, A - пороговое значение, определяющее точку как критическую. Модели сравниваются по критерию ожидаемой задержки, то есть ожидаемого времени тревоги при условии, что критическая точка уже была пройдена: . При этом сравнение происходит для случаев Пуассоновского, равномерного, биномиального и геометрического распределений критической точки и и значений параметра .

Таким образом, в случае Пуассоновского распределения и параметра , наименьшую ожидаемую задержку при раннем change point`е показал метод правдоподобия, а при более позднем - метод Шеварта; для , ранний change point быстрее всего определил метод Шеварта, а поздний - метод кумулятивных сумм. В случае геометрического распределения и , при ранней критической точке побеждает метод кумулятивных сумм, а при поздней - метод Ширяева-Робертса; для победители те же, но теперь метод Ширяева-Робертса лучше для ранних change point`ов, а метод кумулятивных сумм - для более поздних. Для обоих случаев равномерного распределения результаты точно такие же, как в случае геометрического распределения и , а для обоих случаев биномиального - как при геометрическом и .

Из результатов статьи можно сделать вывод, что методы кумулятивных сумм и Ширяева-Робертса показывают наилучшие результаты в большинстве случаев, однако необходимо принимать во внимание, что это справедливо в случае AR (1) процесса и не обязательно справедливо, если наблюдаемая последовательность моделируется иначе. В одной из частей своего исследования я использую метод кумулятивных сумм как представителя классических и эффективных онлайн CPD-алгоритмов и противопоставляю его байесовскому подходу к онлайн-определению критических точек.

Заключительная статья для рассмотрения - «Intelligent forecasting for financial time series subject to structural changes» J. J. Ahn, S. J. Lee, K. J. Oh, T. Y. Kim «Intelligent forecasting for financial time series subject to structural changes», Yonsei University, Keimyung University, 2009. В этой статье описывается двухэтапный подход к предсказанию финансовых рядов. Так как финансовые ряды время от времени подвергаются различным внешним шокам, классические методы прогноза часто оказываются неточными. Авторы полагают, что процедура разделение ряда на секции, а затем прогноз с учетом его текущего состояния сработает лучше.

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

Рассмотрим некоторый временной ряд . Этот ряд имеет критическую точку в момент времени , если и описываются одинаковыми законами распределения с разными параметрами. Если ряд имеет R критических точек, то , что означает разделение последовательности на R + 1 групп. Пусть - функция, определяющая группу, к которой принадлежит наблюдение

.

Теперь, пусть - вектор входных значений, а - результат для каждого . Тогда - тренировочная выборка для межгруппового классификатора . Затем этот классификатор применяется обратно к , чтобы обновить группы и получить тренировочную выборку для второго этапа: . Наконец, итоговый предиктор определяется как

, где

- функция соответствия между и , при условии

, а - стандартная ошибка. Если t - настоящий момент времени, то предсказание для t + 1 будет выглядеть как .

Основная проблема описанной модели - необходим очень хороший классификатор, так как ошибившись с определением группы для данного наблюдения, можно получить очень неточный результат прогноза. Поэтому авторы используют ансамбли различных эффективных классификаторов для максимизации точности.

Такой двухэтапный подход тестировался авторами на двух видах данных - ряде с одной критической точкой и с несколькими, а результаты сравнивались с результатами прогноза «обычной» нейросети. Как и ожидалось, для случая одного change point`а серьезных отличий нет, а вот для случая нескольких разница очень ощутима - в пользу двухэтапного метода.

В одной из частей своего исследования я также использую алгоритм прогноза, учитывающий наличие критических точек, однако меня интересует не столько точность предсказанного значения, сколько правильно предсказанный тренд, поскольку моя цель в этом случае - предсказать критические точки с помощью такого подхода.

На этом мы закончим обзор литературы и перейдем к описанию методов, используемых в исследовании.

Глава 2. Методы, используемые в исследовании

2.1 Оффлайн CPD

Начнем с предпосылок оффлайн CPD-моделей. Введем следующие обозначения: для наблюдаемого сигнала , подсигнал длины обозначим , а полный сигнал - . Представим многомерный нестационарный случайный процесс , принимающий значения в и имеющий T наблюдений. Процесс y является кусочно стационарным, что означает, что некоторые свойства этого процесса неожиданно меняются в моменты времени

. Как уже говорилось в разделе 1.1, задача обнаружения критических точек состоит в оценивании этих моментов времени . Мы также отмечали, что, по сути, оффлайн CPD заключается в выборе лучшей сегментации исходного процесса y, основываясь на определенном количественном критерии. Обозначим этот критерий или просто , так как он всегда рассматривается применительно к наблюдаемому сигналу у. Выбор лучшей модели (сегментации) основывается на минимизации функции V, которая может быть определена по-разному в зависимости от рассматриваемой ситуации. Оффлайн CPD-алгоритмы, использованные в этом исследовании, представляют функцию V как сумму издержек всех сегментов, определенных моделью: , где - функция издержек, определяющая «уровень принадлежности» того или иного наблюдения выделенному для него сегменту.

В зависимости от того, известно ли заранее количество критических точек , оффлайн CPD-задачи подразделяются на две категории:

Если количество change point`ов известно, оптимизационная задача выглядит как: .

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

При этом оффлайн методы определения критических точек состоят из следующих трех элементов:

Рис. 3. Три элемента оффлайн CPD-алгоритмов.

Источник: C. Truong, L. Oudre, N. Vayatis «Selective review of offline change point detection methods», 2019

Функция издержек (Cost function) - это мера однородности наблюдений в каждом сегменте. Если мала, то подсигнал считается однородным или гомогенным, что означает, что он не содержит в себе критических точек. Если же соответствующее значение велико, то сигнал гетерогенный и содержит в себе одну или несколько критических точек. Также в функции издержек заложен тип ожидаемых изменений (например, изменение в среднем значении).

Метод поиска (Search method) - это процедура, решающая одну из ранее описанных оптимизационных задач. Существует множество таких процедур, каждая из которых выдает точное или приближенное решение, таким образом различаясь в точности и вычислительной затратности.

Ограничение (Constraint) - параметр, добавляемый в случае неизвестного количества критических точек. При слишком малых значениях этого параметра определяется множество критических точек, в том числе и те, что обосновываются шумом. При слишком больших определяются только глобальные change point`ы либо не определяется ни одного.

Теперь перейдем к описанию и принципу работы конкретных функций издержек и методов поиска, использованных в данном исследовании.

Функции издержек делятся на два типа: параметрические и непараметрические, которые, в свою очередь, подразделяются еще на несколько. Более наглядно это можно увидеть на рисунке 4:

Рис. 4. Разновидности функций издержек оффлайн CPD-алгоритмов.

Источник: C. Truong, L. Oudre, N. Vayatis «Selective review of offline change point detection methods», 2019

В данном исследовании применялись функции издержек каждого из представленных на рисунке типов, кроме непараметрического оценивания максимального правдоподобия и ранговых функций. Начнем их описание по порядку.

Итак, параметрические функции издержек работают с вектором параметров конечной размерности. Наиболее часто встречаемый тип таких процедур - это процедуры, основанные на оценке максимального правдоподобия. В общем для CPD-задач виде их логика следующая: наблюдаемый сигнал состоит из независимых случайных величин, таких что , где - критические точки, - функции плотности с вектором параметров , - значения параметров. Другими словами, сигнал y моделируется независимыми одинаково распределенными величинами с кусочно постоянным распределением. Параметр обозначает интересующие нас количественные свойства этих распределений, изменение которых ожидается в момент времени , который и необходимо оценить. При таких предпосылках определение критических точек эквивалентно оценке максимального правдоподобия, если сумма издержек равна негативному логарифму правдоподобия.

Если же еще добавить предпосылку о том, что наблюдения распределены нормально с кусочно постоянным среднем и фиксированной дисперсией - получим так называемую -функцию издержек:

,

где - эмпирическое среднее подсигнала . Такая функция издержек также называется функцией квадратических потерь. Она определяет изменения в среднем и часто применяется к исследованиям ДНК и геологических сигналов.

Естественным дополнением к рассмотренной выше cost-функции было бы допущение о том, что дисперсия также может неожиданно меняться. Такая функция называется и определяется как

,

где и - эмпирическое среднее и эмпирическая ковариационная матрица подсигнала соответственно. Стоит заметить, что эта функция может определять изменения в первых двух моментах не только Гауссовского распределения и применяется к анализу финансовых рядов, биомедицинским данным и данным о потреблении электричества.

Следующий тип применяемых в данной работе cost-функций называется «кусочные линейные модели» (Piecewise или Multiple linear models). Не будем рассматривать общий вид таких функций, так как он сильно отличается от единственной применяемой здесь их разновидности - кусочной авторегрессии. Итак, для сигнала y и порядка , функция издержек

,

где - вектор лагированных наблюдений, - неизвестный параметр авторегрессии. Такая функция определяет изменения в коэффициенте авторегрессии нестационарного процесса и применяется на данных ЭЭГ/ЭКГ и для задач распознавания речи.

Еще один тип функций издержек получается, если расширить уже рассмотренную функцию с помощью псевдо-нормы Махаланобиса. Формально, для каждой симметричной положительной полуопределенной матрицы соответствующая псевдо-норма определяется как для любого наблюдения . Тогда интересующая нас cost-функция определяется как

,

где - эмпирическое среднее подсигнала . В базовом варианте матрица метрики M принимается равной обратной матрице ковариаций и получается метрика Махаланобиса, то есть , где - эмпирическая матрица ковариаций процесса y. Такая функция издержек, как и её «родитель», определяет изменения в среднем, однако, хорошо подобранная нелинейная трансформация данных увеличивает точность алгоритма.

Заключительная cost-функция, используемая в данном исследовании, относится к категории непараметрических. Такие функции очень полезны в ситуациях, когда предпосылки для параметрических моделей неизвестны. Одним из типов этих функций являются так называемые «функции ядра» (kernel-based functions). Их суть состоит в отображении наблюдаемого сигнала y в Гильбертово пространство https://ru.wikipedia.org/wiki/Гильбертово_пространство , соответствующее заранее выбранной функции ядра . Функция отображения определяется как , в результате производя следующие «внутренний продукт» и норму: и для любых наблюдений . Тогда общий вид «ядерных» функций издержек определяется следующим образом: для заданной функции ядра получаем cost-функцию , где - эмпирическое среднее «встроенного» сигнала , а определена выше. Для количественных данных одним из наиболее часто используемых ядер является Гауссовское ядро, и функция издержек в этом случае принимает вид: , где - так называемый «параметр пропускной способности» (bandwidth). Такая функция определяет изменения в среднем значении и используется в задачах видео-сегментации, распознавания эмоций и других.

Теперь перейдем к описанию используемых методов поиска. Как и cost-функции, методы поиска делятся на две общие категории - оптимальные решения и приближенные решения. Классификацию применяемых в данной работе search-методов можно увидеть на рисунке 5:

Рис. 5. Классификация применяемых в исследовании методов поиска.

Источник: C. Truong, L. Oudre, N. Vayatis «Selective review of offline change point detection methods», 2019

Итак, оптимальные методы находят точные решения задач поиска известного или неизвестного числа критических точек. Наивный подход состоит в переборе всех возможных сегментаций исходного сигнала и выборе той, что минимизирует целевую функцию, однако, как уже говорилось в разделе 1.1, такой подход крайне непрактичен и даже невозможен для длинных последовательностей. В данной работе рассматривается два алгоритма поиска оптимального решения, один для случая известного количества change point`ов, другой - для неизвестного.

Первый алгоритм называется «Opt» и предполагает фиксированное число критических точек. Решение основывается на принципе так называемого динамического программирования https://ru.wikipedia.org/wiki/Динамическое_программирование. Алгоритм основывается на аддитивной природе целевой функции и рекурсивно решает подзадачи. Формальное его представление выглядит так:

критическая точка фондовый рынок

Это уравнение означает, что первая критическая точка оптимальной сегментации может быть найдена, если известно оптимальное разбиение с

K - 1 элементами для всех подсигналов . Тогда итоговая сегментация определяется путем рекурсивного применения данного уравнения. Такой алгоритм имеет сложность . Примечательно, что изначально он был разработан для не связанных с CPD-областью целей, однако позже стал применяться к задачам анализа показателей ЭЭГ, исследованиям ДНК, финансовым рядам и другим CPD-задачам.

Второй алгоритм называется «Pelt» (Pruned Exact Linear Time) и решает задачу нахождения заранее неизвестного количества критических точек. Как уже упоминалось в начале этого раздела, целевая функция для такого случая представляет собой пенальтизированную (ограниченную) сумму издержек. Наивный подход состоит в применении алгоритма Opt для при достаточно большом и последующем выборе той сегментации, которая минимизирует целевую функцию. Однако, из-за квадратичной сложности метода Opt, такой подход вышел бы слишком вычислительно дорогим. Алгоритм Pelt представляет более быстрый подход для линейного класса ограничительных функций, которые и используются в данном исследовании. Формально, линейные функции ограничения -- это просто линейные функции от количества change point`ов: , где

является параметром сглаживания. Такой подход последовательно обходит каждое наблюдение и с помощью определенного правила может исключить либо оставить его в множестве потенциальных критических точек. Для двух индексов это правило выглядит следующим образом: выполняется, то t не может быть последней критической точкой до момента времени T. Добавление такого правила дает ощутимую прибавку в скорости: в предположении, что длины сегментов берутся случайно из равномерного распределения, сложность алгоритма равна . Такой подход используется в исследованиях ДНК, физиологических сигналах и данных океанографии.

Следующие три рассматриваемых алгоритма являются представителями приближенных методов. Такие методы применяются в случае, если оптимальные методы оказываются слишком вычислительно дорогими. Алгоритмы из этой категории определяют критические точки последовательно, что означает, что они возвращают единственный change point для k-ой итерации. Если количество критических точек известно, итераций последовательного алгоритма достаточно, чтобы получить разбиение с заданным числом change point`ов. Если же неизвестно, алгоритм работает до тех пор, пока не будет выполнен определенный критерий остановки.

Первый из таких алгоритмов называется Win (Window-sliding). Суть метода в подсчете меры расхождения между двумя соседними «окнами», которые перемещаются вдоль всего исходного сигнала y. Для заданной функции издержек мера расхождения выглядит следующим образом:

. Если два окна содержат сильно различающиеся сегменты, мера d достигает больших значений, что в графическом представлении выглядит как вершина. Как только кривая расхождения построена для всей последовательности, запускается процедура поиска вершин и определяются индексы критических точек. Основные преимущества такого подхода в его простоте и вычислительной экономичности - алгоритм имеет линейную сложность по количеству наблюдений. Он применяется для биологических сигналов, интернет данных, распознавания речи и финансовых рядов.

Следующим приближенным методом является BinSeg (Binary Segmentation). Это «жадный» последовательный алгоритм, логика которого в следующем: первая критическая точка оценивается как

.

Эта операция считается «жадной», так как она ищет change point, который сильнее всего снижает сумму издержек. После определения точки , исходная последовательность разделяется на две части относительно неё, и то же самое повторяется для двух получившихся подпоследовательностей. Так продолжается до тех пор, пока не выполняется критерий остановки. Вычислительная сложность такой процедуры . Минус алгоритма в том, что каждая последующая оцененная критическая точка зависит от предыдущей. Несмотря на это, такой подход находит широкое применение в различных областях от финансовых рядов до контекстного распознавания в мобильных устройствах.

Заключительный алгоритм, рассматриваемый здесь, называется BotUp

(Bottom-up Segmentation). Этот метод работает по принципу, противоположному процедуре BinSeg: сначала исходный сигнал делится на множество подсигналов, которые потом последовательно соединяются до тех пор, пока не останется ровно K критических точек. На каждом шаге все потенциальные change point`ы (индексы, разделяющие соседние подсигналы) ранжируются согласно мере расхождения, такой же, что для метода Win. Критические точки с наименьшими мерами расхождения перестают рассматриваться, а сегменты, которые они разделяют, соединяются. Такой подход называют «щедрым», в противоположность методу BinSeg, который «жадный». BotUp имеет линейную сложность и прост в понимании, однако есть и ряд минусов: если истинная критическая точка не принадлежит изначальному множеству кандидатов, алгоритм никогда её не определит, а процедура соединения сегментов на первых шагах может быть нестабильной, так как рассматриваются маленькие сегменты, для которых статистическая значимость ниже. Но несмотря на это, в литературе E. Keogh, S. Chu, D. Hart, M. Pazzani «An online algorithm for segmenting time series», 2001 упоминаются случаи, когда данный алгоритм показывал лучшие результаты, чем BinSeg, на данных ЭКГ и финансовых рядах.

На этом обзор использованных в исследовании оффлайн CPD-методов завершается. Все описанные в данном разделе подходы используются для определения критических точек на первом этапе двухшаговой процедуры предсказания временных рядов с помощью алгоритма Facebook Prophet, о котором и пойдет речь далее.

2.2 Facebook Prophet

Данная модель была представлена работниками компании Facebook Бенджамином Летамом и Сином Тейлором и подробно описана в их работе «Forecasting at Scale» S.J. Taylor, B. Letham «Forecasting at Scale», 2017. В основе лежит модель, предложенная Харви и Питерсом в 1990 году (Harvey & Peters 1990), которая раскладывается на три основных компонента: тренд, сезонность, выходные и праздники (holidays). Формально она представляется следующим уравнением:

,

где - функция тренда, моделирующая непериодические изменения, отвечает за периодические или сезонные изменения, представляет эффект праздников и выходных, из-за которых происходит изменение привычного расписания, - стандартная ошибка.

Алгоритм включает два типа функций тренда, так называемую модель насыщенного роста и кусочную линейную модель. Модель насыщенного роста в базовом варианте представляется логистической функцией роста

,

где C - пропускная способность, k - темп роста, m - параметр смещения. Однако, такая функция не учитывает два важных аспекта: пропускная способность не обязательно постоянна, также, как и темп роста. Авторы Prophet учитывают эти аспекты, меняя константную пропускную способность на зависящую от времени и добавляя в функцию тренда критические точки, которые влияют на темп роста. Таким образом, если на последовательности наблюдается S change point`ов в моменты времени , то им соответствует вектор корректировок , где - изменение темпа в момент времени . Тогда в любой момент времени t темп роста равен базовому темпу k плюс все корректировки до этого момента: . Более четко это можно представить, если ввести вектор такой, что . Тогда темп роста в момент времени t определяется как . После корректировки темпа роста параметр смещения m также должен быть скорректирован, чтобы соединить граничные точки сегментов. В момент критической точки j такая корректировка будет иметь вид

.

С учетом всего вышесказанного кусочная логистическая функция роста принимает вид

.

В случае, если функцией тренда выбирается кусочная линейная модель, то с учетом поправок на критические точки она выглядит следующим образом:

,

где, как и раньше, k - темп роста, - его корректировка, m - параметр смещения, а для непрерывности функции.

Также данная модель учитывает так называемую неуверенность в будущем тренде при прогнозе. Предполагается, что изменения в темпе роста , где параметр отвечает за гибкость этих изменений (при вместо кусочной функции тренда используется стандартная). Prophet может оценить будущие значения этого параметра либо с помощью Байесовского подхода, путем получения апостериорного распределения из иерархического априорного, либо с помощью оценки максимального правдоподобия параметра скалирования темпа роста . Будущие критические точки выбираются случайно при предположении, что их частота и величина изменений будет совпадать с исторической:

.

Как только получена из данных, модель симулирует возможные будущие тренды и строит для них интервалы неопределенности. Стоит заметить, что выдвинутые предположения относительно будущих значений довольно сильные, поэтому не стоит ожидать идеальной точности интервалов, однако они все равно являются полезной мерой неопределенности и, что более важно, мерой переобучения, так как при высоких модель будет более гибкой в подгонке исторических данных. Также напомню, что для данного исследования точность прогнозных значений не так важна, как правильно предсказанный тренд, так что описанные выше предпосылки в данном случае не делают модель неподходящей.

Сезонность в рассматриваемой модели описывается с помощью ряда Фурье https://ru.wikipedia.org/wiki/Ряд_Фурье . Пусть P - ожидаемый сезонный период (например, для годичной сезонности P = 365.25, а для недельной P = 7 в случае дневного шкалирования данных). Тогда сезонные эффекты аппроксимируются функцией

-

 стандартным рядом Фурье с опущенной константой, так как тренд моделируется отдельно. Для определения этой функции необходимо определить 2N параметров

...