Многочастичный фильтр
Многочастичный фильтр (англ. particle filter), также известный как последовательные методы Монте‑Карло (англ. Sequential Monte Carlo), — это класс алгоритмов Монте‑Карло, предназначенных для поиска приближённых решений задач фильтрации в нелинейных системах с состояниями, например, в обработке сигналов и байесовском статистическом выводе[1]. Задача фильтрации состоит в оценивании внутренних состояний динамической системы при наличии лишь частичных наблюдений, а также случайных помех в сенсорах и самой системе. Основная цель — вычислить апостериорные распределения состояний марковского процесса по шумным и неполным наблюдениям. Термин «многочастичный фильтр» был впервые предложен Пьером Дель Моралем (Pierre Del Moral) в 1996 году применительно к методам взаимодействующих частиц среднего поля, используемым в гидродинамике с начала 1960-х[2]. Термин «последовательные методы Монте‑Карло» (Sequential Monte Carlo) был введён в 1998 году Цзюнь С. Лю (Jun S. Liu) и Жун Ченом (Rong Chen)[3].
Многочастичный фильтр использует набор частиц (или образцов) для представления апостериорного распределения состояния случайного процесса по шумным и/или частичным наблюдениям. Модель пространства состояний может быть нелинейной, а законы распределения начального состояния и помех — произвольной формы. Многочастичные фильтры не требуют строгих предположений о виде моделей или распределений состояний, однако их эффективность падает при работе с высокоразмерными системами[2][4][5].
Методы многочастичных фильтров реализуют аппроксимацию апостериорного распределения на основе набора частиц с соответствующими весами вероятности. Важной проблемой при этом является «деградация весов», когда только немногие частицы оказываются с ненулевыми весами (коллапс весов); данное явление смягчается применением шага ресемплирования[6]. С математической точки зрения эти методы интерпретируются как частично-детерминированные приближения мер Фейнмана — Каца с использованием многочастичных систем[7][8]. Аналогичные методы применялись с 1950-х годов в молекулярной химии, вычислительной физике, а в современности — в алгоритмах Монте‑Карло для квантовой механики и вычислительного моделирования.
Многочастичные фильтры применяются для нерекурсивных задач фильтрации в случае нелинейных и негауссовских моделей (за исключением линейных или гауссовских, где применим фильтр Калмана)[9]. Они не чувствительны к размерности пространства, гибко настраиваются и применяются к широкому классу систем.
Многочастичные фильтры широко используются в обработке сигналов и изображений, байесовском выводе, машинном обучении, анализе рисков и редких событий, робототехнике, искусственном интеллекте, биоинформатике[10], филогенетике, вычислительной науке, экономике и финансовой математике, молекулярной химии, фармакокинетике, страховании и других областях.
История
Эвристические алгоритмы
С точки зрения статистики и вероятности, многочастичные фильтры относятся к классу ветвящихся и генетических алгоритмов и взаимодействующих частиц среднего поля. Их интерпретация варьируется по научным дисциплинам: в эволюционном моделировании это поисковые алгоритмы, в физике и химии — методы интегрирования путей Фейнмана — Каца, в биологии и генетике — моделирование эволюции популяций или генов.
Истоки подобных вычислительных техник относятся к работам Алана Тьюринга (Alan Turing) о обучающих машинах с мутациями и отбором[11] и публикациям Нильса Олла Баррикелли (Nils Aall Barricelli) в 1950-х годах[12][13], а также к работам Дж. Хаммерсли (J. Hammersley) середины 1950-х, где были заложены идеи многочастичных фильтров[14]. Моделирование эволюции органищмов с помощью численных методов развитием пользовалось и в биологии (Алекс Фрейзер, Jack L. Crosby и др.)[15][16].
С математической точки зрения, условные распределения случайных состояний рассматриваются как меры Фейнмана — Каца на путях сигнала с весами вероятности[7][8].
Методы многочастичного фильтра получили развитие в 1990-х годах (P. Del Moral[2], G. Kitagawa, N. Gordon и др.)[17][18].
Математические основы
До середины 1990-х публикации по многочастичным фильтрам были преимущественно эвристическими, без строгих доказательств их сходимости или оценки смещения и разброса. Математическая основа и первое строгое исследование этих алгоритмов были проведены Пьером Дель Моралем[2][4]. Были доказаны несмещённость оценки правдоподобия, центральные предельные теоремы, а также результаты о равномерной сходимости[19]. Впоследствии методы были развиты для различных вариантов фильтров — с деревьями предков, обратным отслеживанием, адаптивными моделями и др[5].
Задача фильтрации
Цели
Основная цель — по наблюдаемым переменным (наблюдениям) оценить апостериорную плотность скрытых переменных состояния. Предполагается модель скрытого марковского процесса, где наблюдаемые переменные связаны с невидимыми через известную функцию.
Модель сигнал-наблюдение
Обычно предполагается, что скрытые состояния формуируют марковский процесс, а наблюдения — условно независимы при известных состояниях. Если динамика и наблюдения линейны с гауссовским шумом, результат даёт точное байесовское распределение Калман‑фильтра; при нелинейных функциях применяются приближённые фильтры (например, расширенный или неусечённый фильтр Калмана), однако более общей аппроксимацией служит многочастичный фильтр.
Приближённые байесовские вычисления
Если условные распределения наблюдений не имеют плотности или слишком сложны, могут использоваться приближённые методы на основе введения виртуальных наблюдений и приближённых процедур Монте‑Карло (ABC, approximate Bayesian computation)[10].
Нелинейное уравнение фильтрации
Последовательное обновление апостериорных распределений строится с применением формулы Байеса; в общем случае вычисление происходит по рекуррентной схеме — шага обновления и прогноза.
Формулировка Фейнмана — Каца
Теория многочастичных фильтров тесно связана с интегральными функциями Фейнмана — Каца для случайных траекторий. Данная связь используется для описания перехода от теории вероятностей к вычислительным аппроксимациям частицами.
Многочастичные фильтры
Генетический тип алгоритма
В основе лежит имитация мутации и отбора: на каждом шаге создаётся выборка из N независимых частиц с весами, соответствующими вероятности наблюдений при данных состояниях, после чего выполняется мутационный переход по динамике состояния.
Принципы Монте‑Карло
Многочастичные фильтры, как и другие выборочные методы Монте-Карло (Markov Chain Monte Carlo и др.), позволяют аппроксимировать функционалы искомых апостериорных распределений по конечной выборке частиц с весами.
Симуляция частиц среднего поля
Методы среднего поля заменяют меры вероятностей на их эмпирические аналоги, полученные по частиным образцам (частицам).
Результаты сходимости
Доказано, что при стабильности уравнения фильтрации и достаточно большом числе частиц математическое ожидание и дисперсия аппроксимации оцениваются как величины порядка , где N — число частиц.
Генеалогические деревья и свойства несмещённости
Отслеживание линий предков частиц (генеалогические деревья) позволяет строить так называемый сглаживатель траекторий. Предложены вычисления несмещённых аппроксимаций функции правдоподобия и других вероятностных характеристик через такие траекторные схемы.
Последовательное важностное ресемплирование (SIR)
Фильтр Монте‑Карло и бутстреп-фильтр
Один из самых известных вариантов реализации — алгоритмы последовательного важностного ресемплирования ([SIR], bootstrap-фильтр): ансамбль N частиц с весами обновляется по определённым правилам, периодически проводится пересемплирование для предотвращения коллапса весов.
Sequential importance sampling (SIS)
Вариант без процедуры пересемплирования. Часто возникает проблема, что большинство весов стремятся к нулю, и только немногие частицы «выживают».
«Прямой» алгоритм
Включает генерацию новой частицы через композицию и отказ (по аналогии с rejection sampling), что обеспечивает дополнительную гибкость, но требует больших вычислительных затрат.
Применения
Многочастичные фильтры (и связанные методы Фейнмана — Каца) применяются во множестве задач, связанных с шумными наблюдениями и выраженной нелинейностью, включая:
- байесовский вывод, машинное обучение, анализ рисков и отбор редких событий;
- биоинформатика[10];
- вычислительная наука;
- экономика, финансовая математика и математические финансы (симуляция в сложных моделях, ценообразование опционов и др.)[20];
- инженерия;
- эпидемиология инфекционных болезней (например, прогнозирование сезонных вспышек гриппа)[21];
- выявление и изоляция неисправностей;
- молекулярная химия и вычислительная физика;
- фармакокинетика;
- филогенетика;
- робототехника, искусственный интеллект (локализация и ориентация, слежение и др.)[22][23][24];
- обработка сигналов и изображений, визуальное слежение, распознавание признаков[25].