Interested Article - Многочастичный фильтр
![](/images/006/787/6787280/1.jpg?rand=388398)
![](https://cdn.wafarin.com/avatars/df3f0853efdcdde7b751885486a58efd.gif)
- 2021-12-25
- 1
Многочасти́чный фильтр ( МЧФ , англ. particle filter — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания ( фильтрации , сглаживания ), особенно для нелинейных и не- гауссовских случаев. Со времени описания в 1993 году Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике , компьютерном зрении .
В сравнении с обычно применяемыми для подобных задач методами — расширенными фильтрами Кальмана (EKF) — многочастичные фильтры не зависят от методов линеаризации или апроксимации . Обычный EKF плохо справляется с существенно нелинейными моделями, а также в случае шумов системы и измерений, сильно отличающихся от гауссовых, поэтому были разработаны различные модификации, такие как UKF ( англ. unscented KF ), QKF ( англ. Quadrature KF ) и т. п. . Следует отметить, что в свою очередь многочастичные фильтры более требовательны к вычислительным ресурсам.
Термин «particle filter» был дан Дел Моралом в 1996 году , а «sequential Monte Carlo» — Лю (Liu) и Ченом (Chen) в 1998.
Многие используемые на практике многочастичные фильтры выводятся применением последовательного метода Монте-Карло к последовательности целевых распределений .
Постановка задачи
МЧФ предназначен для оценки последовательности скрытых переменных для на основании наблюдений при . Для простоты изложения будем считать, что рассматривается динамическая система , и и — действительные вектора состояния и измерений соответственно .
Стохастическое уравнение состояния системы имеет вид:
- ,
где функция изменения состояния системы, — случайная величина , возмущающее воздействие.
Уравнение измерений:
- ,
где функция измерения, — случайная величина, шум измерений.
Функции и в общем случае нелинейные , а статистические характеристики шума системы ( ) и измерений ( ) предполагаются известными.
Задачей фильтрации является получение оценки на основе известных к моменту результатов измерений .
Скрытая марковская модель и байесовский вывод
Рассмотрим дискретный марковский процесс со следующими распределениями вероятностей:
и
, |
(1) |
где — плотность вероятности , — условная плотность вероятности ( переходная плотность вероятности) при переходе от к .
Здесь нотация означает, что при условии распределено как .
Реализации процесса (скрытые переменные ) наблюдаются посредством другого случайного процесса — процесса измерений — с маргинальными плотностями :
, | (2) |
где — условная плотность вероятности ( плотность измерений ), измерения считаются статистически независимыми .
Модель может проиллюстрирована следующей диаграммой переходов:
Для простоты считаем, что переходная плотность и плотность измерений не зависят от . Параметры модели считаются заданными.
Определённая таким образом модель системы и измерений известна как скрытая марковская модель .
Уравнение определяет априорное распределение для процесса :
(3) |
Аналогично задаёт функцию правдоподобия :
, | (4) |
Здесь и далее нотация для обозначает .
Таким образом, байесовский вывод для при известных реализациях измерений , обозначенных соответственно как и , будет опираться на апостериорное распределение
, | (5) |
где (здесь — доминирующая мера):
- .
Выборка по значимости
См. также Выборка по значимости .
Метод Монте-Карло позволяет оценивать свойства довольно сложных распределений вероятностей, например, путём вычисления средних и дисперсии в виде интеграла :
- ,
где — функция для оценивания. Например, для среднего можно положить: .
В случае невозможности аналитического решения, задача может быть решена численно генерированием случайных выборок с плотностью , обозначим их как , и получением среднего арифметического по точкам выборки :
В более общем случае, когда выборка из затруднена, применяется другое распределение (так называемое англ. instrumental or importance distribution ), а для сохранения несмещённости оценки вводятся весовые коэффициенты на основе отношения :
после чего вычисляет взвешенное среднее:
- ,
Перевыборка
Хотя вспомогательное распределение используется в основном для упрощения выборки из основного распределения , часто применяется процедура «выборки и перевыборки по значимости» ( англ. sampling importance resampling, SIR ). Эта процедура состоит из двух этапов: собственно выборки по значимости с вычислением весов , и дополнительной выборки точек, учитывающих эти веса .
Перевыборка особенно необходима для последовательных фильтров .
Последовательный метод Монте-Карло
Методы многочастичной фильтрации и сглаживания являются наиболее известными примерами алгоритмов последовательного метода Монте-Карло ( англ. sequential Monte Carlo, SMC ). До такой степени, что в литературе часто не делают между ними различия. Тем не менее, SMC включает в себя более широкий класс алгоритмов, применимых для описания более сложных приблизительных методов фильтрации и сглаживания .
Последовательные методы Монте-Карло являются классом методов Монте-Карло, которые производят последовательную выборку из последовательности целевых плотностей вероятностей увеличивающейся размерности, где каждое определено на декартовой степени .
Если записать плотность как:
- , где
-
- известна поточечно, а
-
- — нормализующая, возможно неизвестная, постоянная, то
SMC-алгоритм будет находить приближения и оценки для .
Например, для случая фильтрации можно положить (см. ):
- и
- ,
из чего будем иметь:
- .
Опуская вывод,
схему предиктор-корректор
можно представить в следующем виде
:
- — предиктор,
- — корректор.
Множитель — нормализующая постоянная, которая не требуется для обычного SMC-алгоритма.
Алгоритм
Типичный алгоритм многочастичного фильтра можно представить в следующем виде :
Алгоритм МЧФ -- инициализация для i = 1...N: выборка из -- начальные веса кц для n = 1...T: если ПЕРЕВЫБОРКА то -- выбор индексов N частиц в соответствии с весами = SelectByWeight() для i = 1...N: иначе для i = 1...N: для i = 1...N: -- шаг распространения частицы -- обновление весов кц -- нормализация весов для i = 1...N: кц
См. также
Примечания
- ↑ .
- .
- ↑ .
- Del Moral, Pierre. (англ.) // Markov Processes and Related Fields. — 1996. — Vol. 2 , no. 4 . — P. 555–580 . 4 марта 2016 года.
- ↑ .
- , 2.1 Hidden Markov Models and Inference Aims.
- , 3 Sequential Monte Carlo Methods.
Литература
- Doucet Arnaud, Johansen Adam M. // The Oxford Handbook of Nonlinear Filtering / D. Crisan, B. Rozovsky. — Oxford : Oxford University Press, 2011. — P. 656—704. — ISBN 978-0-19-953290-2 .
- Cappé, Olivier and Godsill, Simon J. and Moulines, Eric. // Proceedings of the IEEE. — IEEE, 2007. — Т. 95 , № 5 . — P. 899—924. — ISSN . 10 марта 2016 года.
- Doucet, Arnaud and de Freitas, Nando and Gordon, Neil. An Introduction to Sequential Monte Carlo Methods // Sequential Monte Carlo Methods in Practice / Doucet, Arnaud and de Freitas, Nando and Gordon, Neil. — Springer New York. — 3-14 p. — ISBN 978-1-4419-2887-0 .
- Arulampalam, M.S. and Maskell, S. and Gordon, N. and Clapp, T. (англ.) // Trans. Sig. Proc.. — IEEE Press, 2002. — Vol. 50 , no. 2 . — P. 174—188. — ISSN . См. также (англ.)
- Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. Novel approach to nonlinear/non-Gaussian Bayesian state estimation (англ.) // IEEE Proceedings F, Radar and Signal Processing. — IET, 1993. — Vol. 140 , no. 2 . — P. 107—113 . — doi : .
- Микаэльян С. В. // Наука и образование : электронное издание. — МГТУ им. Н. Э. Баумана, 2011. — ISSN . 4 марта 2016 года.
- Ristic, B., Arulampalam, S., Gordon, N. Beyond the Kalman Filter — Particle Filters for Tracking Applications. — Artech House, 2004. — 299 p. — ISBN 9781580536318 .
- Simon, Dan. 15 The particle filter // . — Wiley-Interscience, 2006. — P. —480. — ISBN 0471708585 .
Ссылки
- , SciPy Cookbook
![](https://cdn.wafarin.com/avatars/df3f0853efdcdde7b751885486a58efd.gif)
- 2021-12-25
- 1