Введение 5
Глава 1. Основные результаты 6
1.1. Теоретические результаты 6
1.1.1. Модель с гауссовским шумом 6
1.1.2. Пуассоновский случайный процесс 7
1.2. Результаты моделирования 9
1.3. Гауссовский шум 10
1.3.1. Обнаружение и оценка моментов разладки 10
1.4. Пуассоновский процесс 21
1.4.1. Обнаружение и оценка моментов разладки 21
1.5. Анализ времени работы алгоритмов 28
Глава 2. Методы обнаружения разладки 29
2.1. Исчерпывающий поиск (exhaustive search) 29
2.2. Пошаговый отбор (stepwise selection) 30
2.3. Алгоритм отсеивания и ранжирования (SaRa) 30
2.4. Алгоритм одновременного многомасштабного оценивания скачков (SMUCE) 31
2.5. Обнаружение скачков с помощью диадических интервалов 34
2.5.1. Метрическое пространство интервалов 34
2.5.2. Одномерный случай 35
2.6. Проверка гипотез: false discovery 38
Глава 3. Обнаружение и оценивание скачков для различного шума . . 40
3.1. Гауссовский шум 40
3.1.1. Одномерный случай 40
3.1.2. Двумерный случай 45
3.2. Пуассоновский случайный процесс 48
3.2.1. Одномерный случай 48
3.2.2. Двумерный случай 54
Заключение
Список литературы 61
Приложение А. Анализ алгоритмов для одномерного случая 63
А.1. Реализация алгоритмов 63
А.1.1. Реализация алгоритма Мунка 63
А.1.2. Реализация SaRa 66
А.1.3. Реализация алгоритма В. Г. Спокойного 70
Целью данной выпускной работы является изучение вопроса обнаружения скачков и оценивания скачкообразных функций, когда имеется много моментов разладки.
Такие задачи встречаются во многих сферах деятельности, в том числе экономике, медицине и естественных науках, мобильной связи, обработке изображений и т.д. Этот вопрос изучался в большом числе работ. Например, обнаружение вариаций числа копий генов в ДНК (CNV - Copy Number Variations) сводится к задаче нахождения моментов разладки в исходных данных. В статье [1] был рассмотрен метод для решения такой задачи. Вопрос обнаружения моментов разладки в зашумленных данных был также изучен в работах [2], [3]. При этом одним из ключевых вопросов являлась минимальная ширина скачка, которую можно обнаружить. Этот вопрос был досконально изучен для одномерной регрессии.
Нами изучается данный вопрос для скачков в пуассоновских процессах. Мы находим точную (с точности до константы) асимптотическую ширину скачка (разрыва) для пуассоновских процессов, которую можно обнаружить в контексте одного из первых алгоритмов обнаружения моментов раздалки, представленных в работе [5]. Существует много методов оценивания регрессионной модели со скачками, но наиболее распространенными являются работы [4] и [1], однако результаты этих работ не сравнивались ранее. Таким образом, основной задачей было сравнить работу алгоритмов в работах [4] и [1], а также рассмотреть один из первых алгоритмов [5], реализовать его и сравнить с методами [4] и [1].
В главе (2) приведен подробный обзор существующих методов решений такого типа задачи.
Основные результаты, полученные в ходе исследованияя представлены в главе (1), а именно:
• Теоретические оценки для исходного и модифицированного алгоритмов;
• Практические результаты и сравнительный анализ алгоритмов.
Подробный анализ и доказательства приведены в главе (3).
В данной выпускной работе была изучена проблема оценивания разреженных функций и также был подробно изучен вопрос обнаружения скачков в зашумленных данных.
В ходе работы было выполнено следующее:
• Найдена нижняя и верхняя границы ширины скачка для обнаружения его в пуассоновских процессах. Кроме того, было показано, что эти границы достигаются
(см. раздел 3.2). Также нами был рассмотрен двумерный вариант скачка для исходной постановки задачи (регрессионной модели с гауссовским шумом) и для
пуассоновских случайных процессов (см. разделы 3.1.2 и 3.2.2).
• Дан обзор методов, оценивающих модель регрессии, которая имеет скачкообразный характер.
• Осуществлено сравнение 3–х алгоритмов (Алгоритм Мунка [4], Спокойного [5] и
SaRa [1]), которые ранее не сравнивались между собой (см. раздел 1.2). Реализация алгоритмов выполнена в среде программирования R А.
Сравнив все три алгоритма ( [4], [1], [5]), можно сделать такие выводы:
• Для модели регрессии с гауссовским шумом точнее всего оценивает моменты разладки, ширину и высоту скачка алгоритм Мунка [4]. Оценки SaRa [1] прближаются
к истинному значению, но гораздо хуже оценок алгоритма Мунка. Алгоритм Спокойного [5] в текущей реализации оценивает моменты разладки, высоту и ширину
скачка хуже остальных алгоритмов.
• Для пуассоновских процессов самым точным также оказался алгоритм Мунка [4].
Оценки алгоритмов SaRa [1] и Спокойного [5] также приближаются к истинным
значениям, однако хуже, чем алгоритм Мунка.
Полученные в данной выпускной работе результаты могут послужить основой для
продолжения исследования по задаче “размазанной” разреженности. Дальнейшими перспективами являются изучение задачи асимптотического обнаружения скачка, когда
его размер зависит от мощности скачка, а также изучение сложной геометрии многомерных разрывов
