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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску

Многочасти́чный фильтр[1] (МЧФ, англ. particle filter — «фильтр частиц», «частичный фильтр», «корпускулярный фильтр») — последовательный метод Монте-Карло — рекурсивный алгоритм для численного решения проблем оценивания (фильтрации, сглаживания), особенно для нелинейных и не-гауссовских случаев. Со времени описания в 1993 году[2] Н. Гордоном, Д. Салмондом и А. Смитом используется в различных областях — навигации, робототехнике, компьютерном зрении.

В сравнении с обычно применяемыми для подобных задач методами — расширенными фильтрами Калмана (EKF) — многочастичные фильтры не зависят от методов линеаризации или апроксимации. Обычный EKF плохо справляется с существенно нелинейными моделями, а также в случае шумов системы и измерений, сильно отличающихся от гауссовых, поэтому были разработаны различные модификации, такие как UKF (англ. unscented KF), QKF (англ. Quadrature KF) и т. п.[3]. Следует отметить, что в свою очередь многочастичные фильтры более требовательны к вычислительным ресурсам.

Термин «particle filter» был дан Дел Моралом в 1996 году[4], а «sequential Monte Carlo» — Лю (Liu) и Ченом (Chen) в 1998.

Многие используемые на практике многочастичные фильтры выводятся применением последовательного метода Монте-Карло к последовательности целевых распределений[5].

Постановка задачи[править | править код]

МЧФ предназначен для оценки последовательности скрытых переменных для на основании наблюдений при . Для простоты изложения будем считать, что рассматривается динамическая система, и и  — действительные вектора состояния и измерений соответственно[1].

Стохастическое уравнение состояния системы имеет вид:

,

где функция изменения состояния системы,  — случайная величина, возмущающее воздействие.

Уравнение измерений:

,

где функция измерения,  — случайная величина, шум измерений.

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

Задачей фильтрации является получение оценки на основе известных к моменту результатов измерений .

Скрытая марковская модель и байесовский вывод[править | править код]

Рассмотрим дискретный марковский процесс со следующими распределениями вероятностей:


и
,
(1)

где  — плотность вероятности,  — условная плотность вероятности (переходная плотность вероятности) при переходе от к .

Здесь нотация означает, что при условии распределено как .

Реализации процесса (скрытые переменные ) наблюдаются посредством другого случайного процесса  — процесса измерений — с маргинальными плотностями:


, (2)

где  — условная плотность вероятности (плотность измерений), измерения считаются статистически независимыми.

Модель может проиллюстрирована следующей диаграммой переходов:

Для простоты считаем, что переходная плотность и плотность измерений не зависят от . Параметры модели считаются заданными.

Определённая таким образом модель системы и измерений известна как скрытая марковская модель[6].

Уравнение (1) определяет априорное распределение для процесса :

(3)

Аналогично (2) задаёт функцию правдоподобия:

, (4)

Здесь и далее нотация для обозначает .

Таким образом, байесовский вывод для при известных реализациях измерений , обозначенных соответственно как и , будет опираться на апостериорное распределение

, (5)

где (здесь  — доминирующая мера):

.

Выборка по значимости[править | править код]

См. также Выборка по значимости.

Метод Монте-Карло позволяет оценивать свойства довольно сложных распределений вероятностей, например, путём вычисления средних и дисперсии в виде интеграла[3]:

,

где  — функция для оценивания. Например, для среднего можно положить: .

В случае невозможности аналитического решения, задача может быть решена численно генерированием случайных выборок с плотностью , обозначим их как , и получением среднего арифметического по точкам выборки[3]:

В более общем случае, когда выборка из затруднена, применяется другое распределение (так называемое англ. instrumental or importance distribution), а для сохранения несмещённости оценки вводятся весовые коэффициенты на основе отношения [3]:

после чего вычисляет взвешенное среднее:

,

Перевыборка[править | править код]

Хотя вспомогательное распределение используется в основном для упрощения выборки из основного распределения , часто применяется процедура «выборки и перевыборки по значимости» (англ. sampling importance resampling, SIR). Эта процедура состоит из двух этапов: собственно выборки по значимости с вычислением весов , и дополнительной выборки точек, учитывающих эти веса[3].

Перевыборка особенно необходима для последовательных фильтров[3].

Последовательный метод Монте-Карло[править | править код]

Методы многочастичной фильтрации и сглаживания являются наиболее известными примерами алгоритмов последовательного метода Монте-Карло (англ. sequential Monte Carlo, SMC). До такой степени, что в литературе часто не делают между ними различия. Тем не менее, SMC включает в себя более широкий класс алгоритмов, применимых для описания более сложных приблизительных методов фильтрации и сглаживания[7].

Последовательного методы Монте-Карло являются классом методов Монте-Карло, которые производят последовательную выборку из последовательности целевых плотностей вероятностей увеличивающейся размерности, где каждое определено на декартовой степени [5].

Если записать плотность как:[5]

, где
известна поточечно, а
 — нормализующая, возможно неизвестная, постоянная, то

SMC-алгоритм будет находить приближения и оценки для .

Например, для случая фильтрации можно положить (см. (5)):

и
,

из чего будем иметь:

.


Опуская вывод, схему предиктор-корректор можно представить в следующем виде[3]:

 — предиктор,
 — корректор.

Множитель  — нормализующая постоянная, которая не требуется для обычного SMC-алгоритма.

Алгоритм[править | править код]

Типичный алгоритм многочастичного фильтра можно представить в следующем виде[3]:

   Алгоритм МЧФ
   -- инициализация
   для i = 1...N:
     выборка  из 
     -- начальные веса
      
   кц
   для n = 1...T:
     если ПЕРЕВЫБОРКА то
       -- выбор индексов  N частиц в соответствии с весами
        = SelectByWeight()
       для i = 1...N:
         
         
     иначе
       для i = 1...N:
         
     для i = 1...N:
       -- шаг распространения частицы
       
       -- обновление весов
        
     кц
     -- нормализация весов
     
     для i = 1...N:
       
   кц

См. также[править | править код]

Примечания[править | править код]

  1. 1 2 Микаэльян, 2011.
  2. Gordon, Salmond, Smith, 1993.
  3. 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007.
  4. Del Moral, Pierre. Non Linear Filtering: Interacting Particle Solution. (англ.) // Markov Processes and Related Fields. — 1996. — Vol. 2, no. 4. — P. 555–580.
  5. 1 2 3 Doucet, Johansen, 2011.
  6. Doucet, Johansen, 2011, 2.1 Hidden Markov Models and Inference Aims.
  7. Doucet, Johansen, 2011, 3 Sequential Monte Carlo Methods.

Литература[править | править код]

  • Simon, Dan. 15 The particle filter // Optimal State Estimation: Kalman, H, and Nonlinear Approaches. — Wiley-Interscience, 2006. — P. 461—480. — ISBN 0471708585.

Ссылки[править | править код]