Filtro multipartículas

Filtro de partículas múltiples [1] ( MPF , filtro de partículas en inglés - "filtro de partículas", "filtro de partículas", "filtro corpuscular") - un método secuencial de Monte Carlo - un algoritmo recursivo para resolver numéricamente problemas de estimación ( filtrado , suavizado ), especialmente para casos no lineales y no gaussianos . Desde la descripción en 1993 [2] por N. Gordon, D. Salmond y A. Smith, se ha utilizado en varios campos: navegación, robótica , visión artificial .

En comparación con los métodos comúnmente utilizados para tales problemas, los filtros de Kalman extendidos (EKF), los filtros de partículas múltiples no dependen de métodos de linealización o aproximación . El EKF convencional no se adapta bien a los modelos esencialmente no lineales, así como en el caso del ruido del sistema y las mediciones que son muy diferentes de las gaussianas, por lo que se han desarrollado varias modificaciones, como UKF ( inglés unscented KF ), QKF ( Cuadratura inglesa KF ), etc. ][3 Cabe señalar que, a su vez, los filtros multipartículas son más exigentes en recursos informáticos.

El término "filtro de partículas" fue acuñado por Del Moral en 1996 [4] y "secuencial Monte Carlo" por Liu y Chen en 1998.

Muchos filtros multipartículas que se utilizan en la práctica se obtienen aplicando un método Monte Carlo secuencial a una secuencia de distribuciones objetivo [5] .

Planteamiento del problema

El FFM está diseñado para estimar la secuencia de variables latentes en función de las observaciones en . Para simplificar la presentación, supondremos que estamos considerando un sistema dinámico , y y son vectores de estado real y de medida, respectivamente [1] . $x_{n}$ ${\ estilo de visualización n = 1,2, \ puntos}$ $y_{n}$ ${\ estilo de visualización n = 1,2, \ puntos}$ $x_{n}$ $y_{n}$

La ecuación estocástica del estado del sistema tiene la forma:

x_{k}=f_{k}(x_{k-1},v_{k})

donde la función de cambiar el estado del sistema, es una variable aleatoria , el efecto perturbador. $f_{k}$ $v_{k}$

Ecuación de medida:

y_{k}=h_{k}(x_{k},w_{k})

donde es la función de medida, es una variable aleatoria, ruido de medida. ${\ Displaystyle h_ {k}}$ ${\ Displaystyle w_ {k}}$

Las funciones y son generalmente no lineales y se supone que se conocen las características estadísticas del ruido del sistema ( ) y las mediciones ( ). $f_{k}$ ${\ Displaystyle h_ {k}}$ $v_{k}$ ${\ Displaystyle w_ {k}}$

La tarea de filtrado es obtener una estimación basada en los resultados de medición conocidos en ese momento . ${\sombrero {x}}_{k}$ $k$ ${\ Displaystyle y_ {1: k}}$

Modelo oculto de Markov e inferencia bayesiana

Considere un proceso de Markov discreto con las siguientes distribuciones de probabilidad: $\{X_{n}\}_{n\geqslant 1}$

X_{1}\sim \mu (x_{1})\cuadrángulo

y ,

X_{n}\mid (X_{n-1}=x_{n-1})\sim f(x_{n}\mid x_{n-1})

(una)

donde es la densidad de probabilidad , es la densidad de probabilidad condicional ( densidad de probabilidad de transición ) en la transición de a . $\ mu (x)$ $f(x_{n}\mid x_{n-1})$ ${\ Displaystyle x_ {n-1}}$ $x_{n}$

Aquí la notación significa que la condición se distribuye como . $X\mid Y\sim f(\dots)$ $X$ $Y$ ${\ estilo de visualización f (\ puntos)}$

Las realizaciones del proceso (variables ocultas ) se observan a través de otro proceso aleatorio , el proceso de medición, con densidades marginales : $\{X_{n}\}$ $x_{n}$ ${\displaystyle \{Y_{n}\}_{n\geqslant 1))$

Y_{n}\mid (X_{n}=x_{n})\sim h(y_{n}\mid x_{n})

(2)

donde es la densidad de probabilidad condicional ( densidad de medidas ), las medidas se consideran estadísticamente independientes . $h(y_{n}\mid x_{n})$

El modelo se puede ilustrar mediante el siguiente diagrama de transición:

{\begin{matriz}{cccccccccc}X_{1}&\rightarrow &X_{2}&\rightarrow &X_{3}&\rightarrow &X_{4}&\rightarrow &\ldots &\\\downarrow &&\ flecha abajo &&\flecha abajo &&\flecha abajo &&\ldots &\\Y_{1}&&Y_{2}&&Y_{3}&&Y_{4}&&\ldots &\end{matriz}}

Para simplificar, asumimos que la densidad de transición y la densidad de medición no dependen de . Se supone que se dan los parámetros del modelo. $norte$

El sistema y modelo de medida así definido se conoce como Modelo Oculto de Markov [6] .

La ecuación (1) define la distribución previa para el proceso : $\{X_{n}\}$

p(x_{1:n})=\mu (x_{1})\prod _{k=2}^{n}f(x_{k}\mid x_{k-1})

(3)

De manera similar (2) define la función de verosimilitud :

p(y_{1:n}\mid x_{1:n})=\prod _{k=1}^{n}h(y_{k}\mid x_{k})

(cuatro)

Aquí y debajo, la notación para denota . ${\ Displaystyle x_ {k: l}}$ $k\leqslant l$ $(x_{k},\puntos,x_{l})$

Por lo tanto, la inferencia bayesiana para implementaciones conocidas de medidas , indicadas respectivamente por y , se basará en la distribución posterior ${\ estilo de visualización \ {X_ {1: n}} \}}$ ${\ estilo de visualización \ {Y_ {1: n}} \}}$ ${\ estilo de visualización \ {x_ {1: n}} \}}$ ${\ estilo de visualización \ {y_ {1: n}} \}}$

p(x_{1:n}\mid y_{1:n})={\frac {p(x_{1:n})p(y_{1:n}\mid x_{1:n})}{ p(y_{1:n})}}

(5)

donde (aquí está la medida dominante): $dx_{1:n}$

p(y_{1:n})=\int p(x_{1:n})p(y_{1:n}\mid x_{1:n})\,dx_{1:n}

Muestreo de importancia

Véase también Muestreo de importancia .

El método de Monte Carlo le permite evaluar las propiedades de distribuciones de probabilidad bastante complejas, por ejemplo, calculando las medias y la varianza en forma de integral [3] :

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

donde es la función de estimación. Por ejemplo, para el promedio, puedes poner: . $\el impuesto)$ ${\ estilo de visualización \ theta (x) = x}$

Si una solución analítica es imposible, el problema se puede resolver numéricamente generando muestras aleatorias con una densidad , denótelas como y obteniendo la media aritmética sobre los puntos de muestra [3] : $p(x)$ ${x^{(i)}}_{1\leqslant i\leqslant N}$

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

En un caso más general, cuando el muestreo de es difícil, se aplica otra distribución (la llamada distribución inglesa instrumental o de importancia ), y para mantener la estimación insesgada, se introducen coeficientes de ponderación basados en la relación [3] : $pags$ $q$ $Wisconsin}$ $r(x^{(i)})=p(x^{(i)})/q(x^{(i)})$

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

y luego calcula el promedio ponderado:

{\bar {\theta }}=\int \theta (x)r(x)q(x)\,dx\approx \sum_{i=1}^{N}w_{i}\theta (x^{(i)})

Remuestreo

Aunque la distribución auxiliar se utiliza principalmente para simplificar el muestreo a partir de la distribución principal , a menudo se utiliza el procedimiento de “muestreo y remuestreo por significancia” (en inglés , samplingimportance resampling, SIR ). Este procedimiento consta de dos etapas: muestreo real por significación con cálculo de pesos , y muestreo adicional de puntos que toman en cuenta estos pesos [3] . $pags$ $Wisconsin}$

El remuestreo es especialmente necesario para los filtros en serie [3] .

Método secuencial de Monte Carlo

Los métodos de filtrado y suavizado de partículas múltiples son los ejemplos más conocidos de algoritmos secuenciales de Monte Carlo ( SMC ) . Hasta el punto de que la literatura muchas veces no distingue entre ellos. Sin embargo, SMC incluye una clase más amplia de algoritmos aplicables para describir métodos de filtrado y suavizado aproximados más complejos [7] .

Los métodos secuenciales de Monte Carlo son una clase de métodos de Monte Carlo que muestrean secuencialmente a partir de una secuencia de densidades de probabilidad objetivo de dimensión creciente, donde cada una se define en una potencia cartesiana [5] . $\{f_{n}(x_{1:n})\}$ $f_{n}(x_{1:n})$ ${\mathcal {X}}^{n}$

Si escribimos la densidad como: [5]

f_{n}(x_{1:n})={\frac {\phi _{n}(x_{1:n})}{Z_{n))}

, dónde

\phi _{n}\colon {\mathcal {X}}^{n}\to \mathbb {R} ^{+}

se conoce puntualmente, y

Z_{n}=\int \phi_{n}(x_{1:n})\,dx_{1:n}

es una normalización, posiblemente desconocida, constante, entonces

El algoritmo SMC encontrará aproximaciones y estimaciones para . $f_{k}(x_{1:k})$ $Z_{k}$ $k=1,2,\puntos$

Por ejemplo, para el caso del filtrado, se puede poner (ver (5) ):

\phi _{n}(x_{1:n})=p(x_{1:n})p(y_{1:n}\mid x_{1:n})

Z_{n}=p(y_{1:n})

de la cual tendremos:

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})

Omitiendo la salida, el esquema predictor-corrector se puede representar de la siguiente manera [3] :

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})

— predictor,

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})}}

- corrector de pruebas.

El multiplicador es una constante de normalización que no se requiere para el algoritmo SMC normal. ${\displaystyle (p(y_{n}\mid y_{1:n-1}))^{-1))$

Algoritmo

Un algoritmo típico de filtro de partículas múltiples se puede representar de la siguiente manera [3] :

algoritmo MCF -- inicialización para i = 1...N: muestra de

{\ estilo de visualización \ xi _{0} ^ {(i)))

q_{0}(x_{0}\mid y_{0})

-- pesos iniciales

\omega _{0}^{(i)}:=h(y_{0}\mid \xi _{0}^{(i)})\mu (\xi _{0}^{( i)})\ /\ q_{0}(\xi _{0}^{(i)}\mid y_{0})

nudos para n = 1...T: si VOLVER A SELECCIONAR entonces -- seleccionar índices de N partículas según pesos = SelectByWeight( )

j_{i}\en \{1,\puntos,N\}

{\ estilo de visualización j_ {1: N}}

{\ estilo de visualización \ {w_ {n-1} ^ {(j)} \}}

para i = 1...N:

{\displaystyle x_{n-1}^{(i)}:=\xi _{n-1}^{(j_{i)))))

w_{n-1}^{(i)}:=1/N

de lo contrario para i = 1...N:

{\displaystyle x_{n-1}^{(i)}:=\xi _{n-1}^{(i)))

para i = 1...N: -- paso de propagación de partículas

\xi _{n}^{(i)}\sim q_{n}(\xi _{n}^{(i)}\mid \xi _{n-1}^{(i)} ,y_{n})

-- actualización de escala

\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)}\ medio x_{n-1}^{(i)},y_{n})

nudos -- normalización de pesos

{\displaystyle s:=\sum _{j=1}^{N}\omega _{n}^{(j)))

para i = 1...N:

w_{n}^{(i)}:=\omega _{n}^{(i)}/s

nudos

Véase también

Filtro de Kalman#UKF

Notas

↑ 1 2 Mikaelyan, 2011 .
↑ Gordon, Salmond, Smith, 1993 .
↑ 1 2 3 4 5 6 7 8 Cappé, Godsill, Moulines, 2007 .
↑ Del Moral, Pierre. Filtrado no lineal: solución de partículas que interactúan. (Inglés) // Procesos de Markov y Campos Relacionados. - 1996. - vol. 2 , núm. 4 . - Pág. 555-580 .
↑ 1 2 3 Doucet, Johansen, 2011 .
↑ Doucet, Johansen, 2011 , 2.1 Modelos ocultos de Markov y objetivos de inferencia.
↑ Doucet, Johansen, 2011 , 3 métodos secuenciales de Monte Carlo.

Literatura

Doucet Arnaud, Johansen Adam M. Un tutorial sobre filtrado y suavizado de partículas: quince años después // El manual de Oxford de filtrado no lineal / D. Crisan, B. Rozovsky. - Oxford: Oxford University Press, 2011. - P. 656-704. — ISBN 978-0-19-953290-2 .
Cappe, Olivier and Godsill, Simon J. y Moulines, Eric. Una descripción general de los métodos existentes y los avances recientes en Monte Carlo secuencial // Actas del IEEE. - IEEE, 2007. - T. 95 , No. 5 . - Pág. 899-924. — ISSN 0018-9219 . Archivado desde el original el 10 de marzo de 2016.

Doucet, Arnaud y de Freitas, Nando y Gordon, Neil. Introducción a los métodos secuenciales de Monte Carlo // Métodos secuenciales de Monte Carlo en la práctica / Doucet, Arnaud and de Freitas, Nando and Gordon, Neil. — Springer Nueva York. - 3-14 págs. — ISBN 978-1-4419-2887-0 .
Arulampalam, MS y Maskell, S. y Gordon, N. y Clapp, T. Un tutorial sobre filtros de partículas para el seguimiento bayesiano no lineal/no gaussiano en línea // Trans . Sig. Proc.. - IEEE Press, 2002. - vol. 50 , núm. 2 . - Pág. 174-188. — ISSN 1053-587X . Véase también la versión anterior
Gordon, Nueva Jersey; Salmón, DJ; Smith, AFM Enfoque novedoso para la estimación del estado bayesiano no lineal/no gaussiano // IEEE Proceedings F, Radar and Signal Processing. - IET, 1993. - Vol. 140 , núm. 2 . - pág. 107-113 . -doi : 10.1049 / ip-f-2.1993.0015 .
Mikaelyan S. V. Métodos de filtración basados en la aproximación multipunto de la densidad de probabilidad de estimación en el problema de determinar los parámetros del movimiento del objetivo utilizando un medidor con una característica no lineal . Nauka i obrazovanie: edición electrónica. - MSTU im. N.E. Bauman, 2011. - ISSN 1994-0408 . Archivado desde el original el 4 de marzo de 2016.
Ristic, B., Arulampalam, S., Gordon, N. Más allá del filtro de Kalman: filtros de partículas para aplicaciones de seguimiento. - Casa Artech, 2004. - 299 p. — ISBN 9781580536318 .

Simón, Dan. 15 El filtro de partículas // Estimación del estado óptimo: Kalman, H ∞ y enfoques no lineales . - Wiley-Interscience, 2006. - Pág. 461-480 . — ISBN 0471708585 .

Enlaces

Filtro de partículas , libro de cocina SciPy