Многочасти́чный фильтр (МЧФ, — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания (фильтрации, сглаживания), особенно для нелинейных и не-гауссовских случаев. Со времени описания в 1993 году Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике, компьютерном зрении.
В сравнении с обычно применяемыми для подобных задач методами — расширенными фильтрами Кальмана (EKF) — многочастичные фильтры не зависят от методов линеаризации или апроксимации. Обычный EKF плохо справляется с существенно нелинейными моделями, а также в случае шумов системы и измерений, сильно отличающихся от гауссовых, поэтому были разработаны различные модификации, такие как UKF (), QKF () и т. п.. Следует отметить, что в свою очередь многочастичные фильтры более требовательны к вычислительным ресурсам.
Термин «particle filter» был дан Дел Моралом в 1996 году, а «sequential Monte Carlo» — Лю (Liu) и Ченом (Chen) в 1998.
Многие используемые на практике многочастичные фильтры выводятся применением последовательного метода Монте-Карло к последовательности целевых распределений.
Постановка задачи МЧФ предназначен для оценки последовательности скрытых переменных для на основании наблюдений при . Для простоты изложения будем считать, что рассматривается динамическая система, и и — действительные вектора состояния и измерений соответственно.
Стохастическое уравнение состояния системы имеет вид:
,
где функция изменения состояния системы, — случайная величина, возмущающее воздействие.
Уравнение измерений:
,
где функция измерения, — случайная величина, шум измерений.
Функции и в общем случае нелинейные, а статистические характеристики шума системы () и измерений () предполагаются известными.
Задачей фильтрации является получение оценки на основе известных к моменту результатов измерений .
Скрытая марковская модель и байесовский вывод
Рассмотрим дискретный марковский процесс со следующими распределениями вероятностей:
где — плотность вероятности, — условная плотность вероятности (переходная плотность вероятности) при переходе от к .
Здесь нотация означает, что при условии распределено как .
Реализации процесса (скрытые переменные ) наблюдаются посредством другого случайного процесса — процесса измерений — с маргинальными плотностями:
где — условная плотность вероятности (плотность измерений), измерения считаются статистически независимыми.
Модель может проиллюстрирована следующей диаграммой переходов:
Для простоты считаем, что переходная плотность и плотность измерений не зависят от . Параметры модели считаются заданными.
Определённая таким образом модель системы и измерений известна как скрытая марковская модель.
Уравнение определяет априорное распределение для процесса :
Аналогично задаёт функцию правдоподобия:
Здесь и далее нотация для обозначает .
Таким образом, байесовский вывод для при известных реализациях измерений , обозначенных соответственно как и , будет опираться на апостериорное распределение
где (здесь — доминирующая мера):
.
Выборка по значимости См. также Выборка по значимости.
Метод Монте-Карло позволяет оценивать свойства довольно сложных распределений вероятностей, например, путём вычисления средних и дисперсии в виде интеграла:
,
где — функция для оценивания. Например, для среднего можно положить: .
В случае невозможности аналитического решения, задача может быть решена численно генерированием случайных выборок с плотностью , обозначим их как , и получением среднего арифметического по точкам выборки:
В более общем случае, когда выборка из затруднена, применяется другое распределение (так называемое ), а для сохранения несмещённости оценки вводятся весовые коэффициенты на основе отношения :
после чего вычисляет взвешенное среднее:
,
Перевыборка Хотя вспомогательное распределение используется в основном для упрощения выборки из основного распределения , часто применяется процедура «выборки и перевыборки по значимости» (). Эта процедура состоит из двух этапов: собственно выборки по значимости с вычислением весов , и дополнительной выборки точек, учитывающих эти веса.
Перевыборка особенно необходима для последовательных фильтров.
Последовательный метод Монте-Карло Методы многочастичной фильтрации и сглаживания являются наиболее известными примерами алгоритмов последовательного метода Монте-Карло (). До такой степени, что в литературе часто не делают между ними различия. Тем не менее, SMC включает в себя более широкий класс алгоритмов, применимых для описания более сложных приблизительных методов фильтрации и сглаживания.
Последовательные методы Монте-Карло являются классом методов Монте-Карло, которые производят последовательную выборку из последовательности целевых плотностей вероятностей увеличивающейся размерности, где каждое определено на декартовой степени .
Если записать плотность как:
, где
известна поточечно, а
— нормализующая, возможно неизвестная, постоянная, то
SMC-алгоритм будет находить приближения и оценки для .
Например, для случая фильтрации можно положить (см. ):
и
,
из чего будем иметь:
.
Опуская вывод, схему предиктор-корректор можно представить в следующем виде:
— предиктор,
— корректор.
Множитель — нормализующая постоянная, которая не требуется для обычного SMC-алгоритма.
Алгоритм Типичный алгоритм многочастичного фильтра можно представить в следующем виде: Алгоритм МЧФ -- инициализация для i = 1...N: выборка из -- начальные веса
кц для n = 1...T: если ПЕРЕВЫБОРКА то -- выбор индексов N частиц в соответствии с весами = SelectByWeight() для i = 1...N:
иначе для i = 1...N:
для i = 1...N: -- шаг распространения частицы
-- обновление весов
кц -- нормализация весов
для i = 1...N:
кц
См. также Фильтр Кальмана#UKF
Примечания
Литература
См. также более раннюю версию
Ссылки Particle Filter, SciPy Cookbook
Категория:Цифровая обработка сигналов Категория:Фильтрация Категория:Теория управления