Русская Википедия:Многочастичный фильтр

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

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

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

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

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

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

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

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

<math>x_k = f_k(x_{k-1}, v_k)</math>,

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

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

<math>y_k = h_k(x_k, w_k)</math>,

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

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

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

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

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

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

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

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

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

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

<math>\begin{array}{cccccccccc}

X_1&\rightarrow&X_2&\rightarrow&X_3&\rightarrow&X_4&\rightarrow&\ldots&\\ \downarrow&&\downarrow&&\downarrow&&\downarrow&&\ldots&\\ Y_1&&Y_2&&Y_3&&Y_4&&\ldots& \end{array}</math>

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

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

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

Шаблон:EF

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

Шаблон:EF

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

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

Шаблон:EF

где (здесь <math>dx_{1:n}</math> — доминирующая мера):

<math>p(y_{1:n}) = \int p(x_{1:n}) p(y_{1:n}\mid x_{1:n})\,dx_{1:n}</math>.

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

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

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

<math>\bar{\theta} = \int \theta(x) p(x)\,dx</math>,

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

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

<math>\bar{\theta} \approx \frac{1}{N} \sum_{i=1}^N \theta(x^{(i)})</math>

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

<math>w_i = \frac{r(x^{(i)})} {\sum^{N}_{j=1} r(x^{(j)})}</math>

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

<math>\bar{\theta} = \int \theta(x) r(x) q(x)\,dx \approx \sum_{i=1}^N w_i \theta(x^{(i)})</math>,

Перевыборка

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

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

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

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

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

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

<math>f_n(x_{1:n}) = \frac{\phi_n(x_{1:n})}{Z_n}</math>, где

<math>\phi_n\colon \mathcal{X}^n \to \mathbb{R}^{+}</math> известна поточечно, а

<math>Z_n = \int \phi_n(x_{1:n})\,dx_{1:n}</math> — нормализующая, возможно неизвестная, постоянная, то

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

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

<math>\phi_n(x_{1:n}) = p(x_{1:n}) p(y_{1:n}\mid x_{1:n})</math> и

<math>Z_n = p(y_{1:n})</math>,

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

<math>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})</math>.

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

<math>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})</math> — предиктор,

<math>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})}</math> — корректор.

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

Алгоритм

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

   Алгоритм МЧФ
   -- инициализация
   для i = 1...N:
     выборка <math>\xi_0^{(i)}</math> из <math>q_0(x_0\mid y_0)</math>
     -- начальные веса
     <math>\omega_0^{(i)} := h(y_0\mid \xi_0^{(i)}) \mu(\xi_0^{(i)})\ /\ q_0(\xi_0^{(i)}\mid y_0)</math> 
   кц
   для n = 1...T:
     если ПЕРЕВЫБОРКА то
       -- выбор индексов <math>j_i \in \{1,\dots,N\}</math> N частиц в соответствии с весами
       <math>j_{1:N}</math> = SelectByWeight(<math>\{ w_{n-1}^{(j)}\}</math>)
       для i = 1...N:
         <math>x_{n-1}^{(i)} := \xi_{n-1}^{(j_i)}</math>
         <math>w_{n-1}^{(i)} := 1 / N</math>
     иначе
       для i = 1...N:
         <math>x_{n-1}^{(i)} := \xi_{n-1}^{(i)}</math>
     для i = 1...N:
       -- шаг распространения частицы
       <math>\xi_{n}^{(i)} \sim q_n(\xi_{n}^{(i)}\mid \xi_{n-1}^{(i)}, y_n)</math>
       -- обновление весов
       <math>\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)</math> 
     кц
     -- нормализация весов
     <math>s := \sum^{N}_{j=1} \omega_{n}^{(j)}</math>
     для i = 1...N:
       <math>w_{n}^{(i)} := \omega_{n}^{(i)} / s</math>
   кц

См. также

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

Литература

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

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

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

Ссылки

• Particle Filter, SciPy Cookbook