Многочастичный фильтр

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

Истоки подобных вычислительных техник относятся к работам Алана Тьюринга (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 и др.), позволяют аппроксимировать функционалы искомых апостериорных распределений по конечной выборке частиц с весами.

Методы среднего поля заменяют меры вероятностей на их эмпирические аналоги, полученные по частиным образцам (частицам).

Доказано, что при стабильности уравнения фильтрации и достаточно большом числе частиц математическое ожидание и дисперсия аппроксимации оцениваются как величины порядка ${\displaystyle 1/N}$, где N — число частиц.

Отслеживание линий предков частиц (генеалогические деревья) позволяет строить так называемый сглаживатель траекторий. Предложены вычисления несмещённых аппроксимаций функции правдоподобия и других вероятностных характеристик через такие траекторные схемы.

Один из самых известных вариантов реализации — алгоритмы последовательного важностного ресемплирования ([SIR], bootstrap-фильтр): ансамбль N частиц с весами обновляется по определённым правилам, периодически проводится пересемплирование для предотвращения коллапса весов.

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

Включает генерацию новой частицы через композицию и отказ (по аналогии с rejection sampling), что обеспечивает дополнительную гибкость, но требует больших вычислительных затрат.

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

• байесовский вывод, машинное обучение, анализ рисков и отбор редких событий;
• биоинформатика^[10];
• вычислительная наука;
• экономика, финансовая математика и математические финансы (симуляция в сложных моделях, ценообразование опционов и др.)^[20];
• инженерия;
• эпидемиология инфекционных болезней (например, прогнозирование сезонных вспышек гриппа)^[21];
• выявление и изоляция неисправностей;
• молекулярная химия и вычислительная физика;
• фармакокинетика;
• филогенетика;
• робототехника, искусственный интеллект (локализация и ориентация, слежение и др.)^[22][23][24];
• обработка сигналов и изображений, визуальное слежение, распознавание признаков^[25].