Главная
Новости
Строительство
Ремонт
Дизайн и интерьер

















Яндекс.Метрика

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

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

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

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

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

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

МЧФ предназначен для оценки последовательности скрытых переменных x n {displaystyle x_{n}} для n = 1 , 2 , … {displaystyle n=1,2,dots } на основании наблюдений y n {displaystyle y_{n}} при n = 1 , 2 , … {displaystyle n=1,2,dots } . Для простоты изложения будем считать, что рассматривается динамическая система, и x n {displaystyle x_{n}} и y n {displaystyle y_{n}} — действительные вектора состояния и измерений соответственно.

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

x k = f k ( x k − 1 , v k ) {displaystyle x_{k}=f_{k}(x_{k-1},v_{k})} ,

где f k {displaystyle f_{k}} функция изменения состояния системы, v k {displaystyle v_{k}} — случайная величина, возмущающее воздействие.

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

y k = h k ( x k , w k ) {displaystyle y_{k}=h_{k}(x_{k},w_{k})} ,

где h k {displaystyle h_{k}} функция измерения, w k {displaystyle w_{k}} — случайная величина, шум измерений.

Функции f k {displaystyle f_{k}} и h k {displaystyle h_{k}} в общем случае нелинейные, а статистические характеристики шума системы ( v k {displaystyle v_{k}} ) и измерений ( w k {displaystyle w_{k}} ) предполагаются известными.

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

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

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


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

Здесь нотация X ∣ Y ∼ f ( … ) {displaystyle Xmid Ysim f(dots )} означает, что X {displaystyle X} при условии Y {displaystyle Y} распределено как f ( … ) {displaystyle f(dots )} .

Реализации процесса { X n } {displaystyle {X_{n}}} (скрытые переменные x n {displaystyle x_{n}} ) наблюдаются посредством другого случайного процесса { Y n } n ⩾ 1 {displaystyle {Y_{n}}_{ngeqslant 1}} — процесса измерений — с маргинальными плотностями:


где h ( y n ∣ x n ) {displaystyle h(y_{n}mid x_{n})} — условная плотность вероятности (плотность измерений), измерения считаются статистически независимыми.

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

X 1 → X 2 → X 3 → X 4 → … ↓ ↓ ↓ ↓ … Y 1 Y 2 Y 3 Y 4 … {displaystyle {egin{array}{cccccccccc}X_{1}& ightarrow &X_{2}& ightarrow &X_{3}& ightarrow &X_{4}& ightarrow &ldots &downarrow &&downarrow &&downarrow &&downarrow &&ldots &Y_{1}&&Y_{2}&&Y_{3}&&Y_{4}&&ldots &end{array}}}

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

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

Уравнение (1) определяет априорное распределение для процесса { X n } {displaystyle {X_{n}}} :

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

Здесь и далее нотация x k : l {displaystyle x_{k:l}} для k ⩽ l {displaystyle kleqslant l} обозначает ( x k , … , x l ) {displaystyle (x_{k},dots ,x_{l})} .

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

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

p ( y 1 : n ) = ∫ p ( x 1 : n ) p ( y 1 : n ∣ x 1 : n ) d x 1 : n {displaystyle p(y_{1:n})=int p(x_{1:n})p(y_{1:n}mid x_{1:n}),dx_{1:n}} .

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

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

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

θ ¯ = ∫ θ ( x ) p ( x ) d x {displaystyle {ar { heta }}=int heta (x)p(x),dx} ,

где θ ( x ) {displaystyle heta (x)} — функция для оценивания. Например, для среднего можно положить: θ ( x ) = x {displaystyle heta (x)=x} .

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

θ ¯ ≈ 1 N ∑ i = 1 N θ ( x ( i ) ) {displaystyle {ar { heta }}approx {frac {1}{N}}sum _{i=1}^{N} heta (x^{(i)})}

В более общем случае, когда выборка из p {displaystyle p} затруднена, применяется другое распределение q {displaystyle q} (так называемое англ. instrumental or importance distribution), а для сохранения несмещённости оценки вводятся весовые коэффициенты w i {displaystyle w_{i}} на основе отношения r ( x ( i ) ) = p ( x ( i ) ) / q ( x ( i ) ) {displaystyle r(x^{(i)})=p(x^{(i)})/q(x^{(i)})} :

w i = r ( x ( i ) ) ∑ j = 1 N r ( x ( j ) ) {displaystyle w_{i}={frac {r(x^{(i)})}{sum _{j=1}^{N}r(x^{(j)})}}}

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

θ ¯ = ∫ θ ( x ) r ( x ) q ( x ) d x ≈ ∑ i = 1 N w i θ ( x ( i ) ) {displaystyle {ar { heta }}=int heta (x)r(x)q(x),dxapprox sum _{i=1}^{N}w_{i} heta (x^{(i)})} ,

Перевыборка

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

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

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

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

Последовательного методы Монте-Карло являются классом методов Монте-Карло, которые производят последовательную выборку из последовательности целевых плотностей вероятностей { f n ( x 1 : n ) } {displaystyle {f_{n}(x_{1:n})}} увеличивающейся размерности, где каждое f n ( x 1 : n ) {displaystyle f_{n}(x_{1:n})} определено на декартовой степени X n {displaystyle {mathcal {X}}^{n}} .

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

f n ( x 1 : n ) = ϕ n ( x 1 : n ) Z n {displaystyle f_{n}(x_{1:n})={frac {phi _{n}(x_{1:n})}{Z_{n}}}} , где ϕ n : X n → R + {displaystyle phi _{n}colon {mathcal {X}}^{n} o mathbb {R} ^{+}} известна поточечно, а Z n = ∫ ϕ n ( x 1 : n ) d x 1 : n {displaystyle Z_{n}=int phi _{n}(x_{1:n}),dx_{1:n}} — нормализующая, возможно неизвестная, постоянная, то

SMC-алгоритм будет находить приближения f k ( x 1 : k ) {displaystyle f_{k}(x_{1:k})} и оценки Z k {displaystyle Z_{k}} для k = 1 , 2 , … {displaystyle k=1,2,dots } .

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

ϕ n ( x 1 : n ) = p ( x 1 : n ) p ( y 1 : n ∣ x 1 : n ) {displaystyle phi _{n}(x_{1:n})=p(x_{1:n})p(y_{1:n}mid x_{1:n})} и Z n = p ( y 1 : n ) {displaystyle Z_{n}=p(y_{1:n})} ,

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

f n ( x 1 : n ) = p ( x 1 : n ) p ( y 1 : n ∣ x 1 : n ) p ( y 1 : n ) = p ( x 1 : n | y 1 : n ) {displaystyle 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})} .


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

p ( x 1 : n ∣ y 1 : n − 1 ) = p ( x 1 : n − 1 ∣ y 1 : n − 1 ) f ( x n ∣ x n − 1 ) {displaystyle 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 ∣ y 1 : n ) = h ( y n ∣ x n ) p ( x 1 : n ∣ y 1 : n − 1 ) p ( y n ∣ y 1 : n − 1 ) {displaystyle 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 ∣ y 1 : n − 1 ) ) − 1 {displaystyle (p(y_{n}mid y_{1:n-1}))^{-1}} — нормализующая постоянная, которая не требуется для обычного SMC-алгоритма.

Алгоритм

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

Алгоритм МЧФ -- инициализация для i = 1...N: выборка ξ 0 ( i ) {displaystyle xi _{0}^{(i)}} из q 0 ( x 0 ∣ y 0 ) {displaystyle q_{0}(x_{0}mid y_{0})} -- начальные веса ω 0 ( i ) := h ( y 0 ∣ ξ 0 ( i ) ) μ ( ξ 0 ( i ) )   /   q 0 ( ξ 0 ( i ) ∣ y 0 ) {displaystyle 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 ∈ { 1 , … , N } {displaystyle j_{i}in {1,dots ,N}} N частиц в соответствии с весами j 1 : N {displaystyle j_{1:N}} = SelectByWeight( { w n − 1 ( j ) } {displaystyle {w_{n-1}^{(j)}}} ) для i = 1...N: x n − 1 ( i ) := ξ n − 1 ( j i ) {displaystyle x_{n-1}^{(i)}:=xi _{n-1}^{(j_{i})}} w n − 1 ( i ) := 1 / N {displaystyle w_{n-1}^{(i)}:=1/N} иначе для i = 1...N: x n − 1 ( i ) := ξ n − 1 ( i ) {displaystyle x_{n-1}^{(i)}:=xi _{n-1}^{(i)}} для i = 1...N: -- шаг распространения частицы ξ n ( i ) ∼ q n ( ξ n ( i ) ∣ ξ n − 1 ( i ) , y n ) {displaystyle xi _{n}^{(i)}sim q_{n}(xi _{n}^{(i)}mid xi _{n-1}^{(i)},y_{n})} -- обновление весов ω n ( i ) := w n − 1 ( i ) h ( y n ∣ ξ n ( i ) ) f ( ξ n ( i ) ∣ x n − 1 ( i ) )   /   q n ( ξ n ( i ) ∣ x n − 1 ( i ) , y n ) {displaystyle 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 := ∑ j = 1 N ω n ( j ) {displaystyle s:=sum _{j=1}^{N}omega _{n}^{(j)}} для i = 1...N: w n ( i ) := ω n ( i ) / s {displaystyle w_{n}^{(i)}:=omega _{n}^{(i)}/s} кц