В результате работы по гранту были построены и обоснованы новые алгоритмы, связанные с методом анализа сингулярного спектра (SSA): (1) позволяющие более точно выделять компоненты временного ряда, такие как сигнал (поиск оптимальных весов в методе Кэдзоу, модифицированный метод Гаусса-Ньютона, метод смешанных попеременных проекций), тренд и периодичности (обоснование метода EOSSA), (2) устойчивые к выбросам и работающие в условиях нестационарного шума (итеративный метод с динамическим определением порогового значения) для вещественного и комплексного случаев, (3) позволяющие работать с сигналами сложной структуры (прогноз по динамически строящейся прогнозирующей формуле на основе локальных структур, выделенных SSA). Кроме этого, были получены теоретические результаты по асимптотической разделимости линейного тренда и синусоиды базовым методом SSA, теоретической точности прогноза, построены и обоснованы алгоритмы взвешенной модификации Multiple Monte Carlo SSA для ограничения групповой ошибки при проверке гипотезы об отсутствии сигнала в шуме для уменьшения ложных срабатываний теста, а также предложены алгоритмы по определению того, является ли второй ряд поддерживающим при прогнозе SSA-методами.
Временные ряды, т.е. последовательность измерений во времени, например, изменение температуры воздуха по дням, объемы продаж по месяцам, число заболеваний и многое-многое другое, возникают практически во всех областях жизни, так как все процессы протекают во времени. Соответственно, возникает задача их анализа для последующего принятия решений, например, для прогноза или понимания причин их временного поведения. Среди множества методов анализа и прогноза временных рядов отдельное место занимает метод анализа сингулярного спектра (АСС или англоязычная аббревиатура SSA).
Часто временной ряд состоит из сигнала, неслучайной части, и шума, случайной компоненты, нерегулярно колеблющейся вокруг нуля, а сигнал состоит из суммы тренда и периодической компоненты, например, сезонной. Модель для сигнала, хорошо подходящего для метода SSA – это ряд, управляемый линейной рекуррентной формулой, или, что эквивалентно, временной ряд, члены которого являются суммой произведений полиномов, экспонент и косинусов. Такие ряды еще называют рядами конечного ранга. Представляют интерес такие задачи как, например, оценка сигнала, выделение тренда и периодичностей, прогноз.
Метод SSA сочетает в себе возможность анализа данных без задания модели временного ряда, возможность построить эту модель и затем оценить ее параметры. Он строится путем преобразования временного ряда в матрицу, сингулярного разложения этой матрицы, группировки компонент разложения в матричной форме и потом получения разложения в векторной форме. Аппроксимация сигнала рядом конечного ранга позволяет построить его прогноз. Чем точнее выделен сигнал, тем точнее можно построить прогноз.
В рамках работы по гранту были получены результаты относительно порядка асимптотической точности выделения линейного тренда при наличии периодической компоненты, что важно, так как тренд часто предполагается линейным, и результаты относительно техники оценки ошибок SSA-прогноза компоненты сигнала. Результаты были получены без предположения, что помеха (амплитуда в случае периодической добавки) является малой.
Другой блок результатов относится к построению алгоритмов выделения сигналов из зашумленного ряда, которые одновременно устойчивые и быстрые. Один из результатов существенно улучшает устойчивость выделения полиномиального тренда. Другой результат состоит из трех частей. Для решения задачи в матричной форме с оптимальными весами сначала доказано, что для случая авторегрессионного шума таких весов не существует. Потом построен способ нахождения приближенно оптимальных весов, а затем с использованием этих субоптимальных весов построен новый эффектиынй алгоритм смешанных переменных проекций.
Кроме оценки сигнала и его прогноза нужна еще уверенность в том, что этот сигнал есть во временном ряде. Поэтому важным вопросом является проверка гипотезы о том, что наблюдаемый временной ряд состоит только из шума. Если гипотеза отвергается, то можно говорить о наличии сигнала. В рамках метода SSA и случая шума в виде процесса авторегрессии первого порядка с положительным коэффициентов, называемого «красным шумом», существует метод с именем Monte Carlo SSA. При его использовании есть проблема отсутствия контроля групповой ошибки, который важен, чтобы не было ложного обнаружения сигнала. В рамках работы по гранту были построены асимптотически точные алгоритмы проверки гипотезы с контролем групповой ошибки. При этом предполагаемую область частот сигнала можно задавать с помощью введения в критерий весов, что повышает мощность критерия против альтернативной гипотезы о наличии сигнала в соответствующем диапазоне частот.
В рамках гранта были получены предварительные результаты по прогнозу временных рядов, локально управляемых линейными рекуррентными формулами, предложен алгоритм, определяющий, является ли второй ряд поддерживающим, т.е. улучшает ли его использование точность прогноза первого ряда, предложены алгоритмы устойчивых модификаций метода SSA по отношению к выбросам в значениях временного ряда, которые работают в условиях нестационарного шума, рассмотрены условия разделимости компонент сигнала для комплекснозначных сигналов.
Было также рассмотрено применение SSA в качестве предобработки при использовании методов машинного обучения, в том числе, искусственных нейронных сетей. При этом была выработана методика сравнения методов, в рамках которой было, в частности, опровергнуто утверждение из статьи Du K., Zhao Y., Lei J. The wrong usage of singular spectral analysis and discrete wavelet trans-form in hybrid models to predict hydrological time series // Journal of Hydrology, 2017. Vol. 552, p. 44-51 об отсутствии улучшения точности при предобработке методом SSA. Для получения данного результата, а также для использования SSA при анализе данных для получения биологических результатов относительно экспрессии генов использовалась теория метод SSA, что и позволило получить хорошие результаты на практике.
1.Большой блок результатов посвящен построению и обоснованию алгоритмов построения аппроксимаций сигнала небольшого ранга по наблюдаемому зашумленному сигналу, все они опубликованы. Задача оценки сигнала малого ранга для временных рядов может быть поставлена в двух формах, в форме взвешенной аппроксимации временного ряда и в форме взвешенной аппроксимации ганкелевой матрицы, построенной по временному ряду, которая в терминах метода SSA называется траекторной матрицей. Аппроксимация в матричной форме принадлежит классу методов попеременных проекций и достаточно просто реализуется. С другой стороны, для более точного решения, веса в матричной аппроксимации должны строиться определенным образом. Получены следующие результаты (1) построены и обоснованы эффективные алгоритмы для решения задачи аппроксимации временного ряда (статьи Zvonarev&Golyandina (2022,2023)), (2) доказано, что не существует весов для задачи в матричной форме, эквивалентных оптимальным весам в задаче в форме временных рядов, если временной ряд является суммой сигнала и авторегрессионного процесса; соответственно, можно только найти приближенно оптимальные веса численными методами (статья Golyandina&Zhigljavsky (2020)), (3) построен алгоритм для нахождения приближенно оптимальных весов для задачи в матричной форме (статья Zvonarev (2021)), (4) построен алгоритм и доказана его эффективность для решения задачи в матричной форме, в котором смешаны попеременные проекции по двум разным нормам (статья Zvonarev&Golyandina (2022)).
2.Для задачи проверки гипотезы о наличии сигнала в зашумленном ряде построены и обоснованы статистические критерии, основанные на методе анализа сингулярного спектра (SSA). Критерии отличаются от существующих тем, что они контролируют групповую ошибку, причем делают это с большей мощностью, чем критерии с поправкой Бонферрони. Также в критериях есть возможность задания весов для частот, в которых наиболее возможен синусоидальный сигнал. Показано, что стандартно применяемая модификация критерия является радикальной, т.е. в ней ошибка первого рода не контролируется (статья Golyandina (2023)). К той же задаче применяется подход через ROC-кривые, который позволяет построить точный критерий на основе неточного и сравнивать такие подправленные критерии. Было проведено численное сравнение критериев через ROC-кривые. В том числе, подход был расширен на применение к системам рядов на основе многомерного SSA. (статья Ларин (2022)).
3.Следующее направление – исследование разделимости компонент сигнала во временном ряде с помощью метода SSA. Получены теоретические условия отделимости линейного тренда от синусоидального ряда, а именно, показано, что максимальная ошибка при выделении линейного тренда имеет порядок 1/N, где N – длина ряда, т.е. стремится к нулю при N, стремящемся к бесконечности. При этом синусоидальный ряд рассматривается как помеха, но не требуется, чтобы его амплитуда стремилась к нулю (статья Nekrutkin (2022)). В качестве продолжения данного результата показано, как от ошибки разделения компонент можно переходить к оцениванию ошибки рекуррентного SSA прогноза. В частности, предлагаемая техника позволяет получить порядок ошибки прогноза линейного тренда на один шаг при синусоидальной помехе, который оказывается равным 1/N1/2 (статья Зенкова&Некруткин (2023)).
Результаты выше касаются вещественных временных рядов. Также были рассмотрены вопросы точности выделения сигнала для комплексных временных рядов. Были получены результаты о соотношении точности применения Complex SSA к комплексному синусоидальному сигналу и точности применения SSA к вещественной и мнимой части по-отдельности. В отличие от результатов по точности выделения тренда, удалось получить формулы только для первого порядка оценки по величине помехи. Соотношение ошибки первого порядка и полной ошибки были изучены только численно. Был получен интересный результат относительно соотношения ошибки при применении CSSA и суммы ошибок двух применений SSA к вещественной и мнимой частям.
4.Рассмотрены вопросы применимости метода SSA в качестве метода предобработки для последующего прогноза ряда методами машинного обучения. Разработана методика устойчивого сравнения методов по точности. Показано, что при грамотном использовании SSA предобработка может значительно улучшить точность прогноза. Однако, это происходит не всегда, поэтому остается открытым вопрос, когда предобработка методом SSA улучшает точность, а когда нет (статья Ежов (2022)).
5.Умение метода SSA очищать данные от шума и оценивать параметры модели позволило применить его для анализа биологических данных, результат опубликован. К реальным данным по экспрессии генов были применены методы SSA и 2D-SSA с выбором параметров, основанном на теоретических результатах, а также была применена методика проверки результатов выделения шума (статья Alexandrov et al (2021)).
6.Были построены алгоритмы для анализа вещественных и комплексных рядов с выбросами. Для вещественного случая была предложена модификация уже разработанного ранее алгоритма для случая выбросов в нестационарных временных рядах. Алгоритмы для вещественных временных рядов были перенесены на комплексный случай.
7.Для улучшения разделимости компонент временного ряда известно несколько методов, связанных с косоугольным SSA, который не обладает аппроксимирующими свойствами. Одним из таких методов является EOSSA, ESPRIT-мотивированный метод косоугольного SSA. Было получено обоснование метода, а также того, почему он разделяет компоненты сигнала, соответствующие корням характеристического полинома кратности 1. Был предложен метод для разделения компонент с произвольной кратностью соответствующих корней. Данные результаты обосновывают один из методов улучшения разделимости, который в дальнейшем может помочь методам идентификации компонент разложения в методе SSA.
8.Для временных рядов, структура которых может меняться во времени, были предложены методы для прогноза в случае, если структура меняется медленно, и алгоритм обнаружения разладки, если структура меняется одномоментно, т.е., происходит разладка (последнее рассмотрено для зашумленного синусоидального сигнала). В первом случае был построен алгоритм прогнозирования на основе следующего нового подхода: если структура ряда меняется медленно, то коэффициенты прогнозирующей линейной рекуррентной формулы также меняются медленно; поэтому можно прогнозировать эти коэффициенты и строить прогноз по формуле со спрогнозированными коэффициентами. В случае разладки был предложен алгоритм для обнаружении разладки в частоте синусоидального сигнала за ограниченное время запаздывания обнаружения.
9.Для многомерных временных рядов было введено понятие поддерживающего временного ряда в рамках метода SSA, т.е. ряда, который уменьшает ошибку прогноза основного ряда путем одновременного анализа рядов многомерным обобщением MSSA. Показано, что оно основано на согласованности сигналов в этих рядах и величине шума в поддерживающем ряде. Для константного сигнала удалось получить формулы для ошибок выделения сигнала для метода MSSA, которые потенциально могут помочь аналитически вывести, является ли ряд поддерживающим. Кроме этого, построен алгоритм для определения, является ли ряд поддерживающим, который основан на сравнении ошибок прогноза на исторической части ряда. Чтобы понять границы применения метода MSSA, проведено численное исследование чувствительности свойства поддерживаемости к небольшим отклонениям от согласованности структур сигналов.
10.Для большинства разработанных методов были написаны скрипты на R:
https://github.com/neg99/MGN - R-пакет, в котором реализованы методы для построения низко-ранговой аппроксимации разными способами. Используется в статьях Zvonarev N., Golyandina N. (2022) Fast and stable modification of the Gauss–Newton method for low‐rank signal estimation и Zvonarev N., Golyandina N. (2023) Low-rank signal subspace: parameterization, projection and signal estimation
https://zenodo.org/record/5544575 - R-скрипты (DOI: 10.5281/zenodo.4568495), с помощью которых выполняется множественный вариант метода Monte Carlo SSA и оцениваются ошибки первого и второго рода. DOI: 10.5281/zenodo.4568495. Используются в статье Golyandina Nina (2023) Detection of signals by Monte Carlo singular spectrum analysis: Multiple testing.
https://zenodo.org/record/5155679 -- R-скрипты (DOI: 10.5281/zenodo.5155678), с помощью которых проведен анализ данных (данные содержатся там же) для статьи A. Shlemov, Th. Alexandrov, N. Golyandina, D. Holloway, St. Baumgartner, A. Spirov (2021) "Quantification reveals early dynamics in Drosophila maternal gradients"
https://zenodo.org/record/4841415 - R-скрипты (DOI: 10.5281/zenodo.4817635) для прогноза временных рядов, локально управляемых линейными рекуррентными формулами. Выполняют прогноз с использованием прогноза коэффициентов линейных рекуррентных формул.
1.Большой блок результатов посвящен построению и обоснованию алгоритмов построения аппроксимаций сигнала небольшого ранга по наблюдаемому зашумленному сигналу, все они опубликованы. Задача оценки сигнала малого ранга для временных рядов может быть поставлена в двух формах, в форме взвешенной аппроксимации временного ряда и в форме взвешенной аппроксимации ганкелевой матрицы, построенной по временному ряду, которая в терминах метода SSA называется траекторной матрицей. Аппроксимация в матричной форме принадлежит классу методов попеременных проекций и достаточно просто реализуется. С другой стороны, для более точного решения, веса в матричной аппроксимации должны строиться определенным образом. Получены следующие результаты: построены и обоснованы эффективные алгоритмы для решения задачи аппроксимации временного ряда (статьи Zvonarev&Golyandina (2022,2023)), построен алгоритм и доказана его эффективность для решения задачи в матричной форме, в котором смешаны попеременные проекции по двум разным нормам (статья Zvonarev&Golyandina (2022)).
2.Для задачи проверки гипотезы о наличии сигнала в зашумленном ряде построены и обоснованы статистические критерии, основанные на методе анализа сингулярного спектра (SSA). Критерии отличаются от существующих тем, что они контролируют групповую ошибку, причем делают это с большей мощностью, чем критерии с поправкой Бонферрони. Также в критериях есть возможность задания весов для частот, в которых наиболее возможен синусоидальный сигнал. Показано, что стандартно применяемая модификация критерия является радикальной, т.е. в ней ошибка первого рода не контролируется (статья Golyandina (2023)). К той же задаче применяется подход через ROC-кривые, который позволяет построить точный критерий на основе неточного и сравнивать такие подправленные критерии. Было проведено численное сравнение критериев через ROC-кривые. В том числе, подход был расширен на применение к системам рядов на основе многомерного SSA. (статья Ларин (2022)).
3.Следующее направление – исследование разделимости компонент сигнала во временном ряде с помощью метода SSA. Получены теоретические условия отделимости линейного тренда от синусоидального ряда, а именно, показано, что максимальная ошибка при выделении линейного тренда имеет порядок 1/N, где N – длина ряда, т.е. стремится к нулю при N, стремящемся к бесконечности. При этом синусоидальный ряд рассматривается как помеха, но не требуется, чтобы его амплитуда стремилась к нулю (статья Nekrutkin (2022)). В качестве продолжения данного результата показано, как от ошибки разделения компонент можно переходить к оцениванию ошибки рекуррентного SSA прогноза. В частности, предлагаемая техника позволяет получить порядок ошибки прогноза линейного тренда на один шаг при синусоидальной помехе, который оказывается равным 1/N1/2 (статья Зенкова&Некруткин (2023)).
4.Рассмотрены вопросы применимости метода SSA в качестве метода предобработки для последующего прогноза ряда методами машинного обучения. Разработана методика устойчивого сравнения методов по точности. Показано, что при грамотном использовании SSA предобработка может значительно улучшить точность прогноза. Однако, это происходит не всегда, поэтому остается открытым вопрос, когда предобработка методом SSA улучшает точность, а когда нет (статья Ежов (2022)).
На третьем этапе проекта были расширены и доведены до публикации результаты по точности выделения и прогноза сигнала при неслучайной помехе, проверке гипотезы о существовании сигнала, построению эффективных алгоритмов выделения сигнала малого ранга. Также были доложены на конференции и опубликованы результаты о возможности использования метода анализа сингулярного спектра в качестве предобработки временных рядом при применении методов машинного обучения.
Голяндина Н.Э. - общее руководство по всем темам, исследования, получение результатов, публикации.
Дудник П.Д. - исследования
Сенов М.А. - исследования, подготовка публикации
Ларин Е.С. - исследования, публикация
Некруткин В.В. - получение результатов, публикация
Звонарев Н.К. - получение результатов, публикации
Шаповал Е.А. - исследования
Ежов Ф.В. - исследования, публикация
Ткаченко Е.А. - исследования
Коробейников А.И. - программная поддержка реализаций предлагаемых методов.
| Acronym | RFBR_a_2020 - 3 |
|---|
| Status | Finished |
|---|
| Effective start/end date | 24/03/22 → 28/12/22 |
|---|
