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

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

В сравнении с обычно применяемыми для подобных задач методами — расширенными фильтрами Кальмана (EKF) — многочастичные фильтры не зависят от методов линеаризации или апроксимации. Обычный EKF плохо справляется с существенно нелинейными моделями, а также в случае шумов системы и измерений, сильно отличающихся от гауссовых, поэтому были разработаны различные модификации, такие как UKF (Шаблон:Lang-en), QKF (Шаблон:Lang-en) и т. п.Шаблон:Sfn. Следует отметить, что в свою очередь многочастичные фильтры более требовательны к вычислительным ресурсам.

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

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

Постановка задачи

МЧФ предназначен для оценки последовательности скрытых переменных $x_n$ для $n=1,2,\dots$ на основании наблюдений $y_n$ при $n=1,2,\dots$. Для простоты изложения будем считать, что рассматривается динамическая система, и $x_n$ и $y_n$ — действительные вектора состояния и измерений соответственноШаблон:Sfn.

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

$x_k=f_k(x_{k-1},v_k)$,

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

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

$y_k=h_k(x_k,w_k)$,

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

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

Задачей фильтрации является получение оценки ${\hat{x}}_k$ на основе известных к моменту $k$ результатов измерений $y_{1:k}$.

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

Рассмотрим дискретный марковский процесс $\{X_n{\}}_{n⩾1}$ со следующими распределениями вероятностей:

где $\mu (x)$ — плотность вероятности, $f(x_n\mid x_{n-1})$ — условная плотность вероятности (переходная плотность вероятности) при переходе от $x_{n-1}$ к $x_n$.

Здесь нотация $X\mid Y\sim f(\dots )$ означает, что $X$ при условии $Y$ распределено как $f(\dots )$.

Реализации процесса $\{X_n\}$ (скрытые переменные $x_n$) наблюдаются посредством другого случайного процесса $\{Y_n{\}}_{n⩾1}$ — процесса измерений — с маргинальными плотностями:

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

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

$\begin{array}{cccccccccc}{X}_1& \to & X_2& \to & X_3& \to & X_4& \to & \dots & \\ \downarrow & & \downarrow & & \downarrow & & \downarrow & & \dots & \\ Y_1& & Y_2& & Y_3& & Y_4& & \dots & \end{array}$

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

Определённая таким образом модель системы и измерений известна как скрытая марковская модельШаблон:Sfn.

Уравнение Шаблон:Eqref определяет априорное распределение для процесса $\{X_n\}$:

Шаблон:EF

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

Шаблон:EF

Здесь и далее нотация $x_{k:l}$ для $k⩽l$ обозначает $(x_k,\dots ,x_l)$.

Таким образом, байесовский вывод для $\{X_{1:n}\}$ при известных реализациях измерений $\{Y_{1:n}\}$, обозначенных соответственно как $\{x_{1:n}\}$ и $\{y_{1:n}\}$, будет опираться на апостериорное распределение

Шаблон:EF

где (здесь $d{x}_{1:n}$ — доминирующая мера):

$p(y_{1:n})=\int p(x_{1:n})p(y_{1:n}\mid x_{1:n})d{x}_{1:n}$.

Выборка по значимости

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

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

$\overline{\theta }=\int \theta (x)p(x)dx$,

где $\theta (x)$ — функция для оценивания. Например, для среднего можно положить: $\theta (x)=x$.

В случае невозможности аналитического решения, задача может быть решена численно генерированием случайных выборок с плотностью $p(x)$, обозначим их как ${x^{(i)}}_{1⩽i⩽N}$, и получением среднего арифметического по точкам выборкиШаблон:Sfn:

$\overline{\theta }\approx \frac{1}{N}\sum _{i=1}^N\theta (x^{(i)})$

В более общем случае, когда выборка из $p$ затруднена, применяется другое распределение $q$ (так называемое Шаблон:Lang-en), а для сохранения несмещённости оценки вводятся весовые коэффициенты $w_i$ на основе отношения $r(x^{(i)})=p(x^{(i)})/q(x^{(i)})$Шаблон:Sfn:

$w_i=\frac{r(x^{(i)})}{\sum _{j=1}^{N}r(x^{(j)})}$

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

$\overline{\theta }=\int \theta (x)r(x)q(x)dx\approx \sum _{i=1}^N{w}_i\theta (x^{(i)})$,

Перевыборка

Хотя вспомогательное распределение используется в основном для упрощения выборки из основного распределения $p$, часто применяется процедура «выборки и перевыборки по значимости» (Шаблон:Lang-en). Эта процедура состоит из двух этапов: собственно выборки по значимости с вычислением весов $w_i$, и дополнительной выборки точек, учитывающих эти весаШаблон:Sfn.

Перевыборка особенно необходима для последовательных фильтровШаблон:Sfn.

Последовательный метод Монте-Карло

Методы многочастичной фильтрации и сглаживания являются наиболее известными примерами алгоритмов последовательного метода Монте-Карло (Шаблон:Lang-en). До такой степени, что в литературе часто не делают между ними различия. Тем не менее, SMC включает в себя более широкий класс алгоритмов, применимых для описания более сложных приблизительных методов фильтрации и сглаживанияШаблон:Sfn.

Последовательные методы Монте-Карло являются классом методов Монте-Карло, которые производят последовательную выборку из последовательности целевых плотностей вероятностей $\{f_n(x_{1:n})\}$ увеличивающейся размерности, где каждое $f_n(x_{1:n})$ определено на декартовой степени ${𝒳}^n$Шаблон:Sfn.

Если записать плотность как:Шаблон:Sfn

$f_n(x_{1:n})=\frac{{\varphi }_n(x_{1:n})}{Z_n}$, где

${\varphi }_n:{𝒳}^n\to {ℝ}^{+}$ известна поточечно, а

$Z_n=\int {\varphi }_n(x_{1:n})d{x}_{1:n}$ — нормализующая, возможно неизвестная, постоянная, то

SMC-алгоритм будет находить приближения $f_k(x_{1:k})$ и оценки $Z_k$ для $k=1,2,\dots$.

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

${\varphi }_n(x_{1:n})=p(x_{1:n})p(y_{1:n}\mid x_{1:n})$ и

$Z_n=p(y_{1:n})$,

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

$f_n(x_{1:n})=\frac{p(x_{1:n})p(y_{1:n}\mid x_{1:n})}{p(y_{1:n})}=p(x_{1:n}|y_{1:n})$.

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

$p(x_{1:n}\mid y_{1:n-1})=p(x_{1:n-1}\mid y_{1:n-1})f(x_n\mid x_{n-1})$ — предиктор,

$p(x_{1:n}\mid y_{1:n})=\frac{h(y_n\mid x_n)p(x_{1:n}\mid y_{1:n-1})}{p(y_n\mid y_{1:n-1})}$ — корректор.

Множитель $(p(y_n\mid y_{1:n-1}){)}^{-1}$ — нормализующая постоянная, которая не требуется для обычного SMC-алгоритма.

Алгоритм

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

   Алгоритм МЧФ
   -- инициализация
   для i = 1...N:
     выборка ${\xi }_0^{(i)}$ из $q_0(x_0\mid y_0)$
     -- начальные веса
     ${\omega }_0^{(i)}:=h(y_0\mid {\xi }_0^{(i)})\mu ({\xi }_0^{(i)})/q_0({\xi }_0^{(i)}\mid y_0)$ 
   кц
   для n = 1...T:
     если ПЕРЕВЫБОРКА то
       -- выбор индексов $j_i\in \{1,\dots ,N\}$ N частиц в соответствии с весами
       $j_{1:N}$ = SelectByWeight($\{w_{n-1}^{(j)}\}$)
       для i = 1...N:
         $x_{n-1}^{(i)}:={\xi }_{n-1}^{(j_i)}$
         $w_{n-1}^{(i)}:=1/N$
     иначе
       для i = 1...N:
         $x_{n-1}^{(i)}:={\xi }_{n-1}^{(i)}$
     для i = 1...N:
       -- шаг распространения частицы
       ${\xi }_n^{(i)}\sim q_n({\xi }_n^{(i)}\mid {\xi }_{n-1}^{(i)},y_n)$
       -- обновление весов
       ${\omega }_n^{(i)}:=w_{n-1}^{(i)}h(y_n\mid {\xi }_n^{(i)})f({\xi }_n^{(i)}\mid x_{n-1}^{(i)})/q_n({\xi }_n^{(i)}\mid x_{n-1}^{(i)},y_n)$ 
     кц
     -- нормализация весов
     $s:=\sum _{j=1}^N{\omega }_n^{(j)}$
     для i = 1...N:
       $w_n^{(i)}:={\omega }_n^{(i)}/s$
   кц

См. также

• Фильтр Кальмана#UKF

Литература

• Шаблон:Публикация
• Шаблон:Статья

• Шаблон:Публикация
• Шаблон:Статья См. также более раннюю версиюШаблон:Ref-en
• Шаблон:Статья
• Шаблон:Статья
• Шаблон:Книга

• Шаблон:Книга

Ссылки

• Particle Filter, SciPy Cookbook