Filtro de partículas

Type of Monte Carlo algorithms for signal processing and statistical inference

Los filtros de partículas, o métodos secuenciales de Monte Carlo , son un conjunto de algoritmos de Monte Carlo utilizados para encontrar soluciones aproximadas a problemas de filtrado para sistemas no lineales de espacio de estados, como el procesamiento de señales y la inferencia estadística bayesiana . ^[1] El problema de filtrado consiste en estimar los estados internos en sistemas dinámicos cuando se realizan observaciones parciales y hay perturbaciones aleatorias presentes en los sensores así como en el sistema dinámico. El objetivo es calcular las distribuciones posteriores de los estados de un proceso de Markov , dadas las observaciones ruidosas y parciales. El término "filtros de partículas" fue acuñado por primera vez en 1996 por Pierre Del Moral sobre los métodos de partículas interactuantes de campo medio utilizados en mecánica de fluidos desde principios de la década de 1960. ^[2] El término "Monte Carlo secuencial" fue acuñado por Jun S. Liu y Rong Chen en 1998. ^[3]

El filtrado de partículas utiliza un conjunto de partículas (también llamadas muestras) para representar la distribución posterior de un proceso estocástico dadas las observaciones ruidosas y/o parciales. El modelo de espacio de estados puede ser no lineal y las distribuciones iniciales de estado y ruido pueden adoptar cualquier forma requerida. Las técnicas de filtrado de partículas proporcionan una metodología bien establecida ^{[2] [4] [5]} para generar muestras a partir de la distribución requerida sin requerir suposiciones sobre el modelo de espacio de estados o las distribuciones de estados. Sin embargo, estos métodos no funcionan bien cuando se aplican a sistemas de dimensiones muy altas.

Los filtros de partículas actualizan su predicción de manera aproximada (estadística). Las muestras de la distribución están representadas por un conjunto de partículas; cada partícula tiene un peso de probabilidad asignado que representa la probabilidad de que esa partícula sea muestreada a partir de la función de densidad de probabilidad . La disparidad de peso que conduce al colapso de peso es un problema común encontrado en estos algoritmos de filtrado. Sin embargo, se puede mitigar incluyendo un paso de remuestreo antes de que los pesos se vuelvan desiguales. Se pueden utilizar varios criterios de remuestreo adaptativo, incluida la varianza de los pesos y la entropía relativa con respecto a la distribución uniforme. ^[6] En el paso de remuestreo, las partículas con pesos insignificantes se reemplazan por nuevas partículas en la proximidad de las partículas con pesos más altos.

Desde el punto de vista estadístico y probabilístico, los filtros de partículas pueden interpretarse como interpretaciones de partículas de campo medio de las medidas de probabilidad de Feynman-Kac . ^{[7] [8] [9] [10] [11]} Estas técnicas de integración de partículas fueron desarrolladas en química molecular y física computacional por Theodore E. Harris y Herman Kahn en 1951, Marshall N. Rosenbluth y Arianna W. Rosenbluth en 1955, ^[12] y más recientemente por Jack H. Hetherington en 1984. ^[13] En física computacional, estos métodos de integración de partículas de trayectoria de tipo Feynman-Kac también se utilizan en Monte Carlo cuántico y, más específicamente, en los métodos de Monte Carlo de difusión . ^{[14] [15] [16]} Los métodos de partículas interactuantes de Feynman-Kac también están fuertemente relacionados con los algoritmos genéticos de mutación-selección que se utilizan actualmente en la computación evolutiva para resolver problemas complejos de optimización.

La metodología del filtro de partículas se utiliza para resolver problemas de filtrado no lineal y del modelo oculto de Markov (HMM). Con la notable excepción de los modelos de observación de señales lineales-gaussianos ( filtro de Kalman ) o clases más amplias de modelos (filtro de Benes ^[17] ), Mireille Chaleyat-Maurel y Dominique Michel demostraron en 1984 que la secuencia de distribuciones posteriores de los estados aleatorios de una señal, dadas las observaciones (también conocido como filtro óptimo), no tiene recursión finita. ^[18] Varios otros métodos numéricos basados ​​en aproximaciones de cuadrícula fija, técnicas de Monte Carlo de cadena de Markov , linealización convencional, filtros de Kalman extendidos o determinación del mejor sistema lineal (en el sentido de error-costo esperado) no pueden hacer frente a sistemas de gran escala, procesos inestables o no linealidades insuficientemente suaves.

Los filtros de partículas y las metodologías de partículas de Feynman-Kac encuentran aplicación en el procesamiento de señales e imágenes , inferencia bayesiana , aprendizaje automático , análisis de riesgos y muestreo de eventos raros , ingeniería y robótica , inteligencia artificial , bioinformática , ^[19] filogenética , ciencia computacional , economía y finanzas matemáticas , química molecular , física computacional , farmacocinética , riesgo cuantitativo y seguros ^{[20] [21]} y otros campos.

Historia

Algoritmos de tipo heurístico

Desde un punto de vista estadístico y probabilístico, los filtros de partículas pertenecen a la clase de algoritmos de tipo genético / ramificación y metodologías de partículas interactuantes de tipo campo medio. La interpretación de estos métodos de partículas depende de la disciplina científica. En Computación Evolutiva , las metodologías de partículas de tipo genético de campo medio se utilizan a menudo como algoritmos heurísticos y de búsqueda natural (también conocidos como Metaheurísticos ). En física computacional y química molecular , se utilizan para resolver problemas de integración de trayectorias de Feynman-Kac o para calcular medidas de Boltzmann-Gibbs, valores propios superiores y estados fundamentales de operadores de Schrödinger . En Biología y Genética , representan la evolución de una población de individuos o genes en algún entorno.

Los orígenes de las técnicas computacionales evolutivas de tipo campo medio se remontan a 1950 y 1954 con el trabajo de Alan Turing sobre máquinas de aprendizaje por selección por mutación de tipo genético ^[22] y los artículos de Nils Aall Barricelli en el Instituto de Estudios Avanzados de Princeton, Nueva Jersey . ^{[23] [24]} El primer rastro de filtros de partículas en la metodología estadística se remonta a mediados de la década de 1950; el "Monte Carlo del pobre", ^[25] que fue propuesto por Hammersley et al., en 1954, contenía indicios de los métodos de filtrado de partículas de tipo genético utilizados hoy en día. En 1963, Nils Aall Barricelli simuló un algoritmo de tipo genético para imitar la capacidad de los individuos para jugar un juego simple. ^[26] En la literatura sobre computación evolutiva , los algoritmos de selección de mutaciones de tipo genético se hicieron populares gracias al trabajo seminal de John Holland a principios de la década de 1970, en particular su libro ^[27] publicado en 1975.

En Biología y genética , el genetista australiano Alex Fraser también publicó en 1957 una serie de artículos sobre la simulación de tipos genéticos de la selección artificial de organismos. ^[28] La simulación por computadora de la evolución por parte de biólogos se volvió más común a principios de la década de 1960, y los métodos fueron descritos en libros de Fraser y Burnell (1970) ^[29] y Crosby (1973). ^[30] Las simulaciones de Fraser incluían todos los elementos esenciales de los modernos algoritmos de partículas genéticas de mutación-selección.

Desde el punto de vista matemático, la distribución condicional de los estados aleatorios de una señal dadas algunas observaciones parciales y ruidosas se describe mediante una probabilidad de Feynman-Kac en las trayectorias aleatorias de la señal ponderada por una secuencia de funciones potenciales de verosimilitud. ^{[7] [8] Los métodos} de Monte Carlo cuántico , y más específicamente los métodos de Monte Carlo de difusión, también se pueden interpretar como una aproximación de partículas de tipo genético de campo medio de las integrales de trayectoria de Feynman-Kac. ^{[7] [8] [9] [13] [14] [31] [32]} Los orígenes de los métodos de Monte Carlo cuántico se atribuyen a menudo a Enrico Fermi y Robert Richtmyer, quienes desarrollaron en 1948 una interpretación de partículas de campo medio de las reacciones en cadena de neutrones, ^[33] pero el primer algoritmo de partículas de tipo heurístico y genético (también conocido como métodos de Monte Carlo remuestreados o de reconfiguración) para estimar las energías del estado fundamental de los sistemas cuánticos (en modelos de matriz reducida) se debe a Jack H. Hetherington en 1984. ^[13] También se pueden citar los trabajos seminales anteriores de Theodore E. Harris y Herman Kahn en física de partículas, publicados en 1951, que utilizan métodos genéticos de campo medio pero de tipo heurístico para estimar las energías de transmisión de partículas. ^[34] En química molecular, el uso de metodologías de partículas similares a la heurística genética (también conocidas como estrategias de poda y enriquecimiento) se remonta a 1955 con el trabajo seminal de Marshall N. Rosenbluth y Arianna W. Rosenbluth. ^[12]

El uso de algoritmos de partículas genéticas en el procesamiento avanzado de señales y la inferencia bayesiana es más reciente. En enero de 1993, Genshiro Kitagawa desarrolló un "filtro de Monte Carlo", ^[35] una versión ligeramente modificada de este artículo apareció en 1996. ^[36] En abril de 1993, Gordon et al., publicaron en su trabajo seminal ^[37] una aplicación del algoritmo de tipo genético en la inferencia estadística bayesiana. Los autores llamaron a su algoritmo "el filtro bootstrap" y demostraron que, en comparación con otros métodos de filtrado, su algoritmo bootstrap no requiere ninguna suposición sobre ese espacio de estados o el ruido del sistema. Independientemente, los de Pierre Del Moral ^[2] y Himilcon Carvalho, Pierre Del Moral, André Monin y Gérard Salut ^[38] sobre filtros de partículas publicados a mediados de la década de 1990. Los filtros de partículas también fueron desarrollados en el procesamiento de señales a principios de 1989-1992 por P. Del Moral, JC Noyer, G. Rigal y G. Salut en el LAAS-CNRS en una serie de informes de investigación restringidos y clasificados con STCAN (Service Technique des Constructions et Armes Navales), la empresa de TI DIGILOG y el LAAS-CNRS (el Laboratorio de Análisis y Arquitectura de Sistemas) sobre problemas de procesamiento de señales RADAR/SONAR y GPS. ^{[39] [40] [41] [42] [43] [44]}

Fundamentos matemáticos

Desde 1950 a 1996, todas las publicaciones sobre filtros de partículas y algoritmos genéticos, incluidos los métodos de poda y remuestreo de Monte Carlo introducidos en la física computacional y la química molecular, presentan algoritmos naturales y de tipo heurístico aplicados a diferentes situaciones sin una sola prueba de su consistencia, ni una discusión sobre el sesgo de las estimaciones y algoritmos basados ​​en árboles genealógicos y ancestrales.

Los fundamentos matemáticos y el primer análisis riguroso de estos algoritmos de partículas se deben a Pierre Del Moral ^{[2] [4]} en 1996. El artículo ^{[2] también contiene pruebas de las propiedades imparciales de una aproximación de partículas de funciones de verosimilitud y medidas de} probabilidad condicional no normalizadas . El estimador de partículas imparcial de las funciones de verosimilitud presentado en este artículo se utiliza hoy en día en la inferencia estadística bayesiana.

Dan Crisan, Jessica Gaines y Terry Lyons, ^{[45] [46] [47]} así como Pierre Del Moral y Terry Lyons, ^[48] crearon técnicas de partículas de tipo ramificado con varios tamaños de población alrededor del final de la década de 1990. P. Del Moral, A. Guionnet y L. Miclo ^{[8] [49] [50]} hicieron más avances en este tema en 2000. Pierre Del Moral y Alice Guionnet ^[51] demostraron los primeros teoremas de límite central en 1999, y Pierre Del Moral y Laurent Miclo ^[8] los demostraron en 2000. Los primeros resultados de convergencia uniforme relacionados con el parámetro de tiempo para filtros de partículas fueron desarrollados a finales de la década de 1990 por Pierre Del Moral y Alice Guionnet. ^{[49] [50]} El primer análisis riguroso de suavizadores de filtros de partículas con forma de árbol genealógico se debe a P. Del Moral y L. Miclo en 2001 ^[52].

La teoría sobre las metodologías de partículas Feynman-Kac y los algoritmos de filtro de partículas relacionados se desarrolló en 2000 y 2004 en los libros. ^{[8] [5]} Estos modelos probabilísticos abstractos encapsulan algoritmos de tipo genético, filtros de partículas y bootstrap, filtros Kalman interactivos (también conocidos como filtros de partículas Rao-Blackwellizados ^[53] ), técnicas de filtro de partículas de estilo de remuestreo y muestreo de importancia, incluidas metodologías basadas en árboles genealógicos y de partículas hacia atrás para resolver problemas de filtrado y suavizado. Otras clases de metodologías de filtrado de partículas incluyen modelos basados ​​en árboles genealógicos, ^{[10] [5] [54]} modelos de partículas de Markov hacia atrás, ^{[10] [55]} modelos de partículas de campo medio adaptativos, ^[6] modelos de partículas de tipo isla, ^{[56] [57]} metodologías de Monte Carlo de cadena de Markov de partículas, ^{[58] [59]} muestreadores de Monte Carlo secuenciales ^{[60] [61] [62]} y métodos de Computación Bayesiana Aproximada de Monte Carlo secuencial ^[63] y Bootstrap Bayesiano basado en ABC de Monte Carlo secuencial. ^[64]

El problema del filtrado

Objetivo

El objetivo de un filtro de partículas es estimar la densidad posterior de las variables de estado dadas las variables de observación. El filtro de partículas está pensado para usarse con un modelo oculto de Markov , en el que el sistema incluye tanto variables ocultas como observables. Las variables observables (proceso de observación) están vinculadas a las variables ocultas (proceso de estado) a través de una forma funcional conocida. De manera similar, se conoce la descripción probabilística del sistema dinámico que define la evolución de las variables de estado.

Un filtro de partículas genérico estima la distribución posterior de los estados ocultos mediante el proceso de medición de la observación. Con respecto a un espacio de estados como el que se muestra a continuación:

${\displaystyle {\begin{array}{cccccccccc}X_{0}&\to &X_{1}&\to &X_{2}&\to &X_{3}&\to &\cdots &{\text{signal}}\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{observation}}\end{array}}}$

El problema del filtrado es estimar secuencialmente los valores de los estados ocultos , dados los valores del proceso de observación en cualquier paso de tiempo k . ${\displaystyle X_{k}}$ ${\displaystyle Y_{0},\cdots ,Y_{k},}$

Todas las estimaciones bayesianas de se derivan de la densidad posterior . La metodología del filtro de partículas proporciona una aproximación de estas probabilidades condicionales utilizando la medida empírica asociada con un algoritmo de partículas de tipo genético. Por el contrario, el método de muestreo de importancia o Monte Carlo de cadena de Markov modelaría la densidad posterior completa . ${\displaystyle X_{k}}$ ${\displaystyle p(x_{k}|y_{0},y_{1},...,y_{k})}$ ${\displaystyle p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})}$

El modelo de observación de señales

Los métodos de partículas a menudo asumen que las observaciones se pueden modelar de esta forma: ${\displaystyle X_{k}}$ ${\displaystyle Y_{k}}$

• ${\displaystyle X_{0},X_{1},\cdots }$es un proceso de Markov en (para algunos ) que evoluciona de acuerdo con la densidad de probabilidad de transición . Este modelo también se escribe a menudo de forma sintética como ${\displaystyle \mathbb {R} ^{d_{x}}}$ ${\displaystyle d_{x}\geqslant 1}$ ${\displaystyle p(x_{k}|x_{k-1})}$

  ${\displaystyle X_{k}|X_{k-1}=x_{k}\sim p(x_{k}|x_{k-1})}$

con una densidad de probabilidad inicial . ${\displaystyle p(x_{0})}$

• Las observaciones toman valores en algún espacio de estados en (para algún ) y son condicionalmente independientes siempre que se conozcan. En otras palabras, cada una depende únicamente de . Además, suponemos que la distribución condicional para dados es absolutamente continua y, de manera sintética, tenemos ${\displaystyle Y_{0},Y_{1},\cdots }$ ${\displaystyle \mathbb {R} ^{d_{y}}}$ ${\displaystyle d_{y}\geqslant 1}$ ${\displaystyle X_{0},X_{1},\cdots }$ ${\displaystyle Y_{k}}$ ${\displaystyle X_{k}}$ ${\displaystyle Y_{k}}$ ${\displaystyle X_{k}=x_{k}}$

  ${\displaystyle Y_{k}|X_{k}=y_{k}\sim p(y_{k}|x_{k})}$

Un ejemplo de sistema con estas propiedades es:

${\displaystyle X_{k}=g(X_{k-1})+W_{k-1}}$

${\displaystyle Y_{k}=h(X_{k})+V_{k}}$

donde tanto y son secuencias mutuamente independientes con funciones de densidad de probabilidad conocidas y g y h son funciones conocidas. Estas dos ecuaciones pueden verse como ecuaciones de espacio de estados y parecen similares a las ecuaciones de espacio de estados para el filtro de Kalman. Si las funciones g y h en el ejemplo anterior son lineales, y si tanto y son gaussianas , el filtro de Kalman encuentra la distribución de filtrado bayesiano exacta. Si no, los métodos basados ​​en el filtro de Kalman son una aproximación de primer orden ( EKF ) o una aproximación de segundo orden ( UKF en general, pero si la distribución de probabilidad es gaussiana, es posible una aproximación de tercer orden). ${\displaystyle W_{k}}$ ${\displaystyle V_{k}}$ ${\displaystyle W_{k}}$ ${\displaystyle V_{k}}$

La suposición de que la distribución inicial y las transiciones de la cadena de Markov son continuas para la medida de Lebesgue se puede relajar. Para diseñar un filtro de partículas, simplemente debemos suponer que podemos muestrear las transiciones de la cadena de Markov y calcular la función de verosimilitud (véase, por ejemplo, la descripción de la mutación por selección genética del filtro de partículas que se proporciona a continuación). La suposición continua sobre las transiciones de Markov de se utiliza únicamente para derivar de manera informal (y bastante abusiva) fórmulas diferentes entre distribuciones posteriores utilizando la regla de Bayes para densidades condicionales. ${\displaystyle X_{k-1}\to X_{k}}$ ${\displaystyle X_{k},}$ ${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$ ${\displaystyle X_{k}}$

Modelos de cálculo bayesianos aproximados

En ciertos problemas, la distribución condicional de observaciones, dados los estados aleatorios de la señal, puede no tener una densidad; esta última puede ser imposible o demasiado compleja de calcular. ^[19] En esta situación, se necesita un nivel adicional de aproximación. Una estrategia es reemplazar la señal por la cadena de Markov e introducir una observación virtual de la forma ${\displaystyle X_{k}}$ ${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$

${\displaystyle {\mathcal {Y}}_{k}=Y_{k}+\epsilon {\mathcal {V}}_{k}\quad {\mbox{for some parameter}}\quad \epsilon \in [0,1]}$

para alguna secuencia de variables aleatorias independientes con funciones de densidad de probabilidad conocidas . La idea central es observar que ${\displaystyle {\mathcal {V}}_{k}}$

${\displaystyle {\text{Law}}\left(X_{k}|{\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k}\right)\approx _{\epsilon \downarrow 0}{\text{Law}}\left(X_{k}|Y_{0}=y_{0},\cdots ,Y_{k}=y_{k}\right)}$

El filtro de partículas asociado con el proceso de Markov dadas las observaciones parciales se define en términos de partículas que evolucionan en con una función de probabilidad dada con una notación abusiva obvia por . Estas técnicas probabilísticas están estrechamente relacionadas con el Cálculo Bayesiano Aproximado (ABC). En el contexto de los filtros de partículas, estas técnicas de filtrado de partículas ABC fueron introducidas en 1998 por P. Del Moral, J. Jacod y P. Protter. ^[65] Fueron desarrolladas posteriormente por P. Del Moral, A. Doucet y A. Jasra. ^{[66] [67]} ${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$ ${\displaystyle {\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},}$ ${\displaystyle \mathbb {R} ^{d_{x}+d_{y}}}$ ${\displaystyle p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})}$

La ecuación de filtrado no lineal

La regla de Bayes para la probabilidad condicional da:

${\displaystyle p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})={\frac {p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})}{p(y_{0},\cdots ,y_{k})}}}$

dónde

${\displaystyle {\begin{aligned}p(y_{0},\cdots ,y_{k})&=\int p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})p(x_{0},\cdots ,x_{k})dx_{0}\cdots dx_{k}\\p(y_{0},\cdots ,y_{k}|x_{0},\cdots ,x_{k})&=\prod _{l=0}^{k}p(y_{l}|x_{l})\\p(x_{0},\cdots ,x_{k})&=p_{0}(x_{0})\prod _{l=1}^{k}p(x_{l}|x_{l-1})\end{aligned}}}$

Los filtros de partículas también son una aproximación, pero con suficientes partículas pueden ser mucho más precisos. ^{[2] [4] [5] [49] [50]} La ecuación de filtrado no lineal está dada por la recursión.

con la convención de k = 0. El problema de filtrado no lineal consiste en calcular estas distribuciones condicionales secuencialmente. ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})}$

Formulación de Feynman-Kac

Fijamos un horizonte temporal n y una secuencia de observaciones , y para cada k = 0, ..., n fijamos: ${\displaystyle Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}}$

${\displaystyle G_{k}(x_{k})=p(y_{k}|x_{k}).}$

En esta notación, para cualquier función acotada F en el conjunto de trayectorias desde el origen k = 0 hasta el tiempo k = n , tenemos la fórmula de Feynman-Kac ${\displaystyle X_{k}}$

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n})p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n})dx_{0}\cdots dx_{n}&={\frac {\int F(x_{0},\cdots ,x_{n})\left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}{\int \left\{\prod \limits _{k=0}^{n}p(y_{k}|x_{k})\right\}p(x_{0},\cdots ,x_{n})dx_{0}\cdots dx_{n}}}\\&={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}\end{aligned}}}$

Los modelos de integración de trayectorias de Feynman-Kac surgen en una variedad de disciplinas científicas, incluidas la física computacional, la biología, la teoría de la información y las ciencias de la computación. ^{[8] [10] [5]} Sus interpretaciones dependen del dominio de aplicación. Por ejemplo, si elegimos la función indicadora de algún subconjunto del espacio de estados, representan la distribución condicional de una cadena de Markov dado que permanece en un tubo determinado; es decir, tenemos: ${\displaystyle G_{n}(x_{n})=1_{A}(x_{n})}$

${\displaystyle E\left(F(X_{0},\cdots ,X_{n})|X_{0}\in A,\cdots ,X_{n}\in A\right)={\frac {E\left(F(X_{0},\cdots ,X_{n})\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}{E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}}}$

y

${\displaystyle P\left(X_{0}\in A,\cdots ,X_{n}\in A\right)=E\left(\prod \limits _{k=0}^{n}G_{k}(X_{k})\right)}$

tan pronto como la constante normalizadora sea estrictamente positiva.

Filtros de partículas

Un algoritmo de partículas de tipo genético

Inicialmente, un algoritmo de este tipo comienza con N variables aleatorias independientes con una densidad de probabilidad común . Las transiciones de selección-mutación del algoritmo genético ^{[2] [4]} ${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$ ${\displaystyle p(x_{0})}$

${\displaystyle \xi _{k}:=\left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{selection}}{\longrightarrow }}{\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}{\stackrel {\text{mutation}}{\longrightarrow }}\xi _{k+1}:=\left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$

imitar/aproximar las transiciones de actualización-predicción de la evolución óptima del filtro ( Ec. 1 ):

• Durante la transición de selección-actualización, muestreamos N variables aleatorias (condicionalmente) independientes con distribución común (condicional) ${\displaystyle {\widehat {\xi }}_{k}:=\left({\widehat {\xi }}_{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

donde representa la medida de Dirac en un estado dado a. ${\displaystyle \delta _{a}}$

• Durante la transición de mutación-predicción, de cada partícula seleccionada muestreamos de forma independiente una transición ${\displaystyle {\widehat {\xi }}_{k}^{i}}$

${\displaystyle {\widehat {\xi }}_{k}^{i}\longrightarrow \xi _{k+1}^{i}\sim p(x_{k+1}|{\widehat {\xi }}_{k}^{i}),\qquad i=1,\cdots ,N.}$

En las fórmulas mostradas arriba, representa la función de verosimilitud evaluada en , y representa la densidad condicional evaluada en . ${\displaystyle p(y_{k}|\xi _{k}^{i})}$ ${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$ ${\displaystyle p(x_{k+1}|{\widehat {\xi }}_{k}^{i})}$ ${\displaystyle p(x_{k+1}|x_{k})}$ ${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$

En cada tiempo k , tenemos las aproximaciones de partículas

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}\delta _{\xi _{k}^{i}}(dx_{k})}$

y

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

En la comunidad de algoritmos genéticos y computación evolutiva , la cadena de Markov de mutación-selección descrita anteriormente se suele denominar algoritmo genético con selección proporcional. En los artículos también se han propuesto varias variantes de ramificación, incluidas aquellas con tamaños de población aleatorios. ^{[5] [45] [48]}

Principios de Montecarlo

Los métodos de partículas, como todos los enfoques basados ​​en muestreo (por ejemplo, Markov Chain Monte Carlo ), generan un conjunto de muestras que se aproximan a la densidad de filtrado.

${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k}).}$

Por ejemplo, podemos tener N muestras de la distribución posterior aproximada de , donde las muestras están etiquetadas con superíndices como: ${\displaystyle X_{k}}$

${\displaystyle {\widehat {\xi }}_{k}^{1},\cdots ,{\widehat {\xi }}_{k}^{N}.}$

Luego, las expectativas con respecto a la distribución de filtrado se aproximan mediante

con

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

donde representa la medida de Dirac en un estado dado a. La función f , de la forma habitual para Monte Carlo, puede dar todos los momentos, etc. de la distribución hasta cierto error de aproximación. Cuando la ecuación de aproximación ( Ec. 2 ) se satisface para cualquier función acotada f, escribimos ${\displaystyle \delta _{a}}$

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k}):=p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{{\widehat {\xi }}_{k}^{i}}(dx_{k})}$

Los filtros de partículas pueden interpretarse como un algoritmo de partículas de tipo genético que evoluciona con transiciones de mutación y selección. Podemos hacer un seguimiento de las líneas ancestrales

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right)}$

de las partículas . Los estados aleatorios , con los índices inferiores l=0,...,k, representan el ancestro del individuo en el nivel l=0,...,k. En esta situación, tenemos la fórmula de aproximación ${\displaystyle i=1,\cdots ,N}$ ${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$ ${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$

con la medida empírica

${\displaystyle {\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))}$

Aquí F representa cualquier función fundada en el espacio de trayectorias de la señal. En una forma más sintética ( Ec. 3 ) es equivalente a

${\displaystyle {\begin{aligned}p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k})\,dx_{0}\cdots dx_{k}\\&\approx _{N\uparrow \infty }{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\end{aligned}}}$

Los filtros de partículas se pueden interpretar de muchas maneras diferentes. Desde el punto de vista probabilístico, coinciden con una interpretación de partículas de campo medio de la ecuación de filtrado no lineal. Las transiciones de actualización-predicción de la evolución óptima del filtro también se pueden interpretar como las transiciones clásicas de selección de tipo genético-mutación de individuos. La técnica de remuestreo de importancia secuencial proporciona otra interpretación de las transiciones de filtrado que acopla el muestreo de importancia con el paso de remuestreo bootstrap. Por último, pero no menos importante, los filtros de partículas se pueden ver como una metodología de aceptación-rechazo equipada con un mecanismo de reciclaje. ^{[10] [5]}

Simulación de partículas de campo medio

El principio probabilístico general

La evolución del filtrado no lineal se puede interpretar como un sistema dinámico en el conjunto de medidas de probabilidad de la forma donde representa una cierta correspondencia del conjunto de distribuciones de probabilidad con el conjunto mismo. Por ejemplo, la evolución del predictor óptimo de un paso ${\displaystyle \eta _{n+1}=\Phi _{n+1}\left(\eta _{n}\right)}$ ${\displaystyle \Phi _{n+1}}$ ${\displaystyle \eta _{n}(dx_{n})=p(x_{n}|y_{0},\cdots ,y_{n-1})dx_{n}}$

satisface una evolución no lineal que comienza con la distribución de probabilidad . Una de las formas más simples de aproximar estas medidas de probabilidad es comenzar con N variables aleatorias independientes con una distribución de probabilidad común . Supongamos que hemos definido una secuencia de N variables aleatorias tales que ${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$ ${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$ ${\displaystyle \eta _{0}(dx_{0})=p(x_{0})dx_{0}}$ ${\displaystyle \left(\xi _{n}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}(dx_{n})\approx _{N\uparrow \infty }\eta _{n}(dx_{n})}$

En el siguiente paso, muestreamos N variables aleatorias (condicionalmente) independientes con ley común. ${\displaystyle \xi _{n+1}:=\left(\xi _{n+1}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle \Phi _{n+1}\left({\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}\right)\approx _{N\uparrow \infty }\Phi _{n+1}\left(\eta _{n}\right)=\eta _{n+1}}$

Una interpretación de partículas de la ecuación de filtrado

Ilustramos este principio de partícula de campo medio en el contexto de la evolución de los predictores óptimos de un paso.

Para k = 0 utilizamos la convención . ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})}$

Por la ley de los grandes números, tenemos

${\displaystyle {\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{0}^{i}}(dx_{0})\approx _{N\uparrow \infty }p(x_{0})dx_{0}}$

en el sentido de que

${\displaystyle \int f(x_{0}){\widehat {p}}(dx_{0})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{0}^{i})\approx _{N\uparrow \infty }\int f(x_{0})p(dx_{0})dx_{0}}$

para cualquier función acotada . Suponemos además que hemos construido una secuencia de partículas en algún rango k tal que ${\displaystyle f}$ ${\displaystyle \left(\xi _{k}^{i}\right)_{1\leqslant i\leqslant N}}$

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }~p(x_{k}~|~y_{0},\cdots ,y_{k-1})dx_{k}}$

en el sentido de que para cualquier función acotada tenemos ${\displaystyle f}$

${\displaystyle \int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}f(\xi _{k}^{i})\approx _{N\uparrow \infty }\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

En esta situación, reemplazando por la medida empírica en la ecuación de evolución del filtro óptimo de un paso enunciada en ( Ec. 4 ) encontramos que ${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$ ${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

${\displaystyle p(x_{k+1}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }\int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}}$

Tenga en cuenta que el lado derecho de la fórmula anterior es una mezcla de probabilidad ponderada.

${\displaystyle \int p(x_{k+1}|x'_{k}){\frac {p(y_{k}|x_{k}'){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x''_{k}){\widehat {p}}(dx''_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{j})}}p(x_{k+1}|\xi _{k}^{i})=:{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

donde representa la densidad evaluada en , y representa la densidad evaluada en para ${\displaystyle p(y_{k}|\xi _{k}^{i})}$ ${\displaystyle p(y_{k}|x_{k})}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$ ${\displaystyle p(x_{k+1}|\xi _{k}^{i})}$ ${\displaystyle p(x_{k+1}|x_{k})}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$ ${\displaystyle i=1,\cdots ,N.}$

Luego, tomamos una muestra de N variables aleatorias independientes con densidad de probabilidad común de modo que ${\displaystyle \left(\xi _{k+1}^{i}\right)_{1\leqslant i\leqslant N}}$ ${\displaystyle {\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})}$

${\displaystyle {\widehat {p}}(dx_{k+1}|y_{0},\cdots ,y_{k}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k+1}^{i}}(dx_{k+1})\approx _{N\uparrow \infty }{\widehat {q}}(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}\approx _{N\uparrow \infty }p(x_{k+1}|y_{0},\cdots ,y_{k})dx_{k+1}}$

Iterando este procedimiento, diseñamos una cadena de Markov tal que

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1}):=p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

Nótese que el filtro óptimo se aproxima en cada paso de tiempo k utilizando las fórmulas de Bayes.

${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k})\approx _{N\uparrow \infty }{\frac {p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}{\int p(y_{k}|x'_{k}){\widehat {p}}(dx'_{k}|y_{0},\cdots ,y_{k-1})}}=\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k}^{j})}}~\delta _{\xi _{k}^{i}}(dx_{k})}$

La terminología "aproximación de campo medio" proviene del hecho de que reemplazamos en cada paso de tiempo la medida de probabilidad por la aproximación empírica . La aproximación de partículas de campo medio del problema de filtrado está lejos de ser única. Se desarrollan varias estrategias en los libros. ^{[10] [5]} ${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k-1})}$ ${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

Algunos resultados de convergencia

El análisis de la convergencia de los filtros de partículas se inició en 1996 ^{[2] [4]} y en 2000 en el libro ^[8] y la serie de artículos. ^{[48] [49] [50] [51] [52] [68] [69]} Se pueden encontrar desarrollos más recientes en los libros, ^{[10] [5]} Cuando la ecuación de filtrado es estable (en el sentido de que corrige cualquier condición inicial errónea), el sesgo y la varianza de las estimaciones de partículas

${\displaystyle I_{k}(f):=\int f(x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})\approx _{N\uparrow \infty }{\widehat {I}}_{k}(f):=\int f(x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

están controlados por las estimaciones uniformes no asintóticas

${\displaystyle \sup _{k\geqslant 0}\left\vert E\left({\widehat {I}}_{k}(f)\right)-I_{k}(f)\right\vert \leqslant {\frac {c_{1}}{N}}}$

${\displaystyle \sup _{k\geqslant 0}E\left(\left[{\widehat {I}}_{k}(f)-I_{k}(f)\right]^{2}\right)\leqslant {\frac {c_{2}}{N}}}$

para cualquier función f acotada por 1, y para algunas constantes finitas Además, para cualquier : ${\displaystyle c_{1},c_{2}.}$ ${\displaystyle x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}(f)-I_{k}(f)\right|\leqslant c{\sqrt {\frac {x\log(n)}{N}}}\right)>1-e^{-x}}$

para algunas constantes finitas relacionadas con el sesgo asintótico y la varianza de la estimación de la partícula, y alguna constante finita c . Se satisfacen los mismos resultados si reemplazamos el predictor óptimo de un paso por la aproximación de filtro óptima. ${\displaystyle c_{1},c_{2}}$

Árboles genealógicos y propiedades de imparcialidad

Suavizado de partículas basado en árboles genealógicos

Rastreando en el tiempo las líneas ancestrales

${\displaystyle \left({\widehat {\xi }}_{0,k}^{i},{\widehat {\xi }}_{1,k}^{i},\cdots ,{\widehat {\xi }}_{k-1,k}^{i},{\widehat {\xi }}_{k,k}^{i}\right),\quad \left(\xi _{0,k}^{i},\xi _{1,k}^{i},\cdots ,\xi _{k-1,k}^{i},\xi _{k,k}^{i}\right)}$

de los individuos y en cada paso de tiempo k , también tenemos las aproximaciones de partículas ${\displaystyle {\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)}$ ${\displaystyle \xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)}$

${\displaystyle {\begin{aligned}{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{0,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\ \\{\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)}(d(x_{0},\cdots ,x_{k}))\\&\approx _{N\uparrow \infty }p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&:=p(x_{0},\cdots ,x_{k}|y_{0},\cdots ,y_{k-1})dx_{0},\cdots ,dx_{k}\end{aligned}}}$

Estas aproximaciones empíricas son equivalentes a las aproximaciones integrales de partículas.

${\displaystyle {\begin{aligned}\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left({\widehat {\xi }}_{0,k}^{i},\cdots ,{\widehat {\xi }}_{0,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k})\\&\approx _{N\uparrow \infty }\sum _{i=1}^{N}{\frac {p(y_{k}|\xi _{k,k}^{i})}{\sum _{j=1}^{N}p(y_{k}|\xi _{k,k}^{j})}}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\ \\\int F(x_{0},\cdots ,x_{n}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})&:={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\\&\approx _{N\uparrow \infty }\int F(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\end{aligned}}}$

para cualquier función acotada F sobre las trayectorias aleatorias de la señal. Como se muestra en ^[54] la evolución del árbol genealógico coincide con una interpretación de partículas de campo medio de las ecuaciones de evolución asociadas con las densidades posteriores de las trayectorias de la señal. Para más detalles sobre estos modelos de espacio de trayectorias, nos remitimos a los libros. ^{[10] [5]}

Estimaciones imparciales de funciones de probabilidad a partir de partículas

Utilizamos la fórmula del producto.

${\displaystyle p(y_{0},\cdots ,y_{n})=\prod _{k=0}^{n}p(y_{k}|y_{0},\cdots ,y_{k-1})}$

con

${\displaystyle p(y_{k}|y_{0},\cdots ,y_{k-1})=\int p(y_{k}|x_{k})p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

y las convenciones y para k = 0. Reemplazando por la aproximación empírica ${\displaystyle p(y_{0}|y_{0},\cdots ,y_{-1})=p(y_{0})}$ ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1})=p(x_{0}),}$ ${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$

${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1}):={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k}^{i}}(dx_{k})\approx _{N\uparrow \infty }p(dx_{k}|y_{0},\cdots ,y_{k-1})}$

En la fórmula mostrada arriba, diseñamos la siguiente aproximación de partículas imparcial de la función de probabilidad.

${\displaystyle p(y_{0},\cdots ,y_{n})\approx _{N\uparrow \infty }{\widehat {p}}(y_{0},\cdots ,y_{n})=\prod _{k=0}^{n}{\widehat {p}}(y_{k}|y_{0},\cdots ,y_{k-1})}$

con

${\displaystyle {\widehat {p}}(y_{k}|y_{0},\cdots ,y_{k-1})=\int p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}p(y_{k}|\xi _{k}^{i})}$

donde representa la densidad evaluada en . El diseño de esta estimación de partículas y la propiedad de imparcialidad se han demostrado en 1996 en el artículo. ^[2] Se pueden encontrar estimaciones de varianza refinadas en ^[5] y. ^[10] ${\displaystyle p(y_{k}|\xi _{k}^{i})}$ ${\displaystyle p(y_{k}|x_{k})}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$

Suavizadores de partículas hacia atrás

Usando la regla de Bayes, tenemos la fórmula

${\displaystyle p(x_{0},\cdots ,x_{n}|y_{0},\cdots ,y_{n-1})=p(x_{n}|y_{0},\cdots ,y_{n-1})p(x_{n-1}|x_{n},y_{0},\cdots ,y_{n-1})\cdots p(x_{1}|x_{2},y_{0},y_{1})p(x_{0}|x_{1},y_{0})}$

Tenga en cuenta que

${\displaystyle {\begin{aligned}p(x_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))&\propto p(x_{k}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-1}))\\p(x_{k-1}|(y_{0},\cdots ,y_{k-1})&\propto p(y_{k-1}|x_{k-1})p(x_{k-1}|(y_{0},\cdots ,y_{k-2})\end{aligned}}}$

Esto implica que

${\displaystyle p(x_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))={\frac {p(y_{k-1}|x_{k-1})p(x_{k}|x_{k-1})p(x_{k-1}|y_{0},\cdots ,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})p(x_{k}|x'_{k-1})p(x'_{k-1}|y_{0},\cdots ,y_{k-2})dx'_{k-1}}}}$

Reemplazar los predictores óptimos de un paso por las medidas empíricas de partículas ${\displaystyle p(x_{k-1}|(y_{0},\cdots ,y_{k-2}))dx_{k-1}}$

${\displaystyle {\widehat {p}}(dx_{k-1}|(y_{0},\cdots ,y_{k-2}))={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{k-1}^{i}}(dx_{k-1})\left(\approx _{N\uparrow \infty }p(dx_{k-1}|(y_{0},\cdots ,y_{k-2})):={p}(x_{k-1}|(y_{0},\cdots ,y_{k-2}))dx_{k-1}\right)}$

Encontramos que

${\displaystyle {\begin{aligned}p(dx_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))&\approx _{N\uparrow \infty }{\widehat {p}}(dx_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))\\&:={\frac {p(y_{k-1}|x_{k-1})p(x_{k}|x_{k-1}){\widehat {p}}(dx_{k-1}|y_{0},\cdots ,y_{k-2})}{\int p(y_{k-1}|x'_{k-1})~p(x_{k}|x'_{k-1}){\widehat {p}}(dx'_{k-1}|y_{0},\cdots ,y_{k-2})}}\\&=\sum _{i=1}^{N}{\frac {p(y_{k-1}|\xi _{k-1}^{i})p(x_{k}|\xi _{k-1}^{i})}{\sum _{j=1}^{N}p(y_{k-1}|\xi _{k-1}^{j})p(x_{k}|\xi _{k-1}^{j})}}\delta _{\xi _{k-1}^{i}}(dx_{k-1})\end{aligned}}}$

Concluimos que

${\displaystyle p(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))\approx _{N\uparrow \infty }{\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))}$

con la aproximación de partículas hacia atrás

${\displaystyle {\begin{aligned}{\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))={\widehat {p}}(dx_{n}|(y_{0},\cdots ,y_{n-1})){\widehat {p}}(dx_{n-1}|x_{n},(y_{0},\cdots ,y_{n-1}))\cdots {\widehat {p}}(dx_{1}|x_{2},(y_{0},y_{1})){\widehat {p}}(dx_{0}|x_{1},y_{0})\end{aligned}}}$

La medida de probabilidad

${\displaystyle {\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))}$

es la probabilidad de las trayectorias aleatorias de una cadena de Markov que se ejecutan hacia atrás en el tiempo desde el tiempo k = n hasta el tiempo k = 0, y evolucionan en cada paso de tiempo k en el espacio de estados asociado con la población de partículas ${\displaystyle \left(\mathbb {X} _{k,n}^{\flat }\right)_{0\leqslant k\leqslant n}}$ ${\displaystyle \xi _{k}^{i},i=1,\cdots ,N.}$

• Inicialmente (en el momento k=n) la cadena elige aleatoriamente un estado con la distribución ${\displaystyle \mathbb {X} _{n,n}^{\flat }}$

${\displaystyle {\widehat {p}}(dx_{n}|(y_{0},\cdots ,y_{n-1}))={\frac {1}{N}}\sum _{i=1}^{N}\delta _{\xi _{n}^{i}}(dx_{n})}$

• Desde el tiempo k hasta el tiempo (k-1), la cadena que comienza en algún estado durante algún tiempo k se mueve en el tiempo (k-1) a un estado aleatorio elegido con la probabilidad ponderada discreta ${\displaystyle \mathbb {X} _{k,n}^{\flat }=\xi _{k}^{i}}$ ${\displaystyle i=1,\cdots ,N}$ ${\displaystyle \mathbb {X} _{k-1,n}^{\flat }}$

${\displaystyle {\widehat {p}}(dx_{k-1}|\xi _{k}^{i},(y_{0},\cdots ,y_{k-1}))=\sum _{j=1}^{N}{\frac {p(y_{k-1}|\xi _{k-1}^{j})p(\xi _{k}^{i}|\xi _{k-1}^{j})}{\sum _{l=1}^{N}p(y_{k-1}|\xi _{k-1}^{l})p(\xi _{k}^{i}|\xi _{k-1}^{l})}}~\delta _{\xi _{k-1}^{j}}(dx_{k-1})}$

En la fórmula mostrada arriba, representa la distribución condicional evaluada en . En la misma línea, y representan las densidades condicionales y evaluadas en y Estos modelos permiten reducir la integración con respecto a las densidades en términos de operaciones matriciales con respecto a las transiciones de Markov de la cadena descrita arriba. ^[55] Por ejemplo, para cualquier función tenemos las estimaciones de partículas ${\displaystyle {\widehat {p}}(dx_{k-1}|\xi _{k}^{i},(y_{0},\cdots ,y_{k-1}))}$ ${\displaystyle {\widehat {p}}(dx_{k-1}|x_{k},(y_{0},\cdots ,y_{k-1}))}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$ ${\displaystyle p(y_{k-1}|\xi _{k-1}^{j})}$ ${\displaystyle p(\xi _{k}^{i}|\xi _{k-1}^{j})}$ ${\displaystyle p(y_{k-1}|x_{k-1})}$ ${\displaystyle p(x_{k}|x_{k-1})}$ ${\displaystyle x_{k}=\xi _{k}^{i}}$ ${\displaystyle x_{k-1}=\xi _{k-1}^{j}.}$ ${\displaystyle p((x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))}$ ${\displaystyle f_{k}}$

${\displaystyle {\begin{aligned}\int p(d(x_{0},\cdots ,x_{n})&|(y_{0},\cdots ,y_{n-1}))f_{k}(x_{k})\\&\approx _{N\uparrow \infty }\int {\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))f_{k}(x_{k})\\&=\int {\widehat {p}}(dx_{n}|(y_{0},\cdots ,y_{n-1})){\widehat {p}}(dx_{n-1}|x_{n},(y_{0},\cdots ,y_{n-1}))\cdots {\widehat {p}}(dx_{k}|x_{k+1},(y_{0},\cdots ,y_{k}))f_{k}(x_{k})\\&=\underbrace {\left[{\tfrac {1}{N}},\cdots ,{\tfrac {1}{N}}\right]} _{N{\text{ times}}}\mathbb {M} _{n-1}\cdots \mathbb {M} _{k}{\begin{bmatrix}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k}(\xi _{k}^{N})\end{bmatrix}}\end{aligned}}}$

dónde

${\displaystyle \mathbb {M} _{k}=(\mathbb {M} _{k}(i,j))_{1\leqslant i,j\leqslant N}:\qquad \mathbb {M} _{k}(i,j)={\frac {p(\xi _{k}^{i}|\xi _{k-1}^{j})~p(y_{k-1}|\xi _{k-1}^{j})}{\sum \limits _{l=1}^{N}p(\xi _{k}^{i}|\xi _{k-1}^{l})p(y_{k-1}|\xi _{k-1}^{l})}}}$

Esto también demuestra que si

${\displaystyle {\overline {F}}(x_{0},\cdots ,x_{n}):={\frac {1}{n+1}}\sum _{k=0}^{n}f_{k}(x_{k})}$

entonces

${\displaystyle {\begin{aligned}\int {\overline {F}}(x_{0},\cdots ,x_{n})p(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))&\approx _{N\uparrow \infty }\int {\overline {F}}(x_{0},\cdots ,x_{n}){\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))\\&={\frac {1}{n+1}}\sum _{k=0}^{n}\underbrace {\left[{\tfrac {1}{N}},\cdots ,{\tfrac {1}{N}}\right]} _{N{\text{ times}}}\mathbb {M} _{n-1}\mathbb {M} _{n-2}\cdots \mathbb {M} _{k}{\begin{bmatrix}f_{k}(\xi _{k}^{1})\\\vdots \\f_{k}(\xi _{k}^{N})\end{bmatrix}}\end{aligned}}}$

Algunos resultados de convergencia

Supondremos que la ecuación de filtrado es estable, en el sentido de que corrige cualquier condición inicial errónea.

En esta situación, las aproximaciones de partículas de las funciones de probabilidad son imparciales y la varianza relativa está controlada por

${\displaystyle E\left({\widehat {p}}(y_{0},\cdots ,y_{n})\right)=p(y_{0},\cdots ,y_{n}),\qquad E\left(\left[{\frac {{\widehat {p}}(y_{0},\cdots ,y_{n})}{p(y_{0},\cdots ,y_{n})}}-1\right]^{2}\right)\leqslant {\frac {cn}{N}},}$

Para una constante finita c . Además, para cualquier : ${\displaystyle x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left\vert {\frac {1}{n}}\log {{\widehat {p}}(y_{0},\cdots ,y_{n})}-{\frac {1}{n}}\log {p(y_{0},\cdots ,y_{n})}\right\vert \leqslant c_{1}{\frac {x}{N}}+c_{2}{\sqrt {\frac {x}{N}}}\right)>1-e^{-x}}$

para algunas constantes finitas relacionadas con el sesgo asintótico y la varianza de la estimación de la partícula, y para alguna constante finita c . ${\displaystyle c_{1},c_{2}}$

El sesgo y la varianza de las estimaciones de partículas basadas en las líneas ancestrales de los árboles genealógicos

${\displaystyle {\begin{aligned}I_{k}^{path}(F)&:=\int F(x_{0},\cdots ,x_{k})p(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&\approx _{N\uparrow \infty }{\widehat {I}}_{k}^{path}(F)\\&:=\int F(x_{0},\cdots ,x_{k}){\widehat {p}}(d(x_{0},\cdots ,x_{k})|y_{0},\cdots ,y_{k-1})\\&={\frac {1}{N}}\sum _{i=1}^{N}F\left(\xi _{0,k}^{i},\cdots ,\xi _{k,k}^{i}\right)\end{aligned}}}$

están controlados por las estimaciones uniformes no asintóticas

${\displaystyle \left|E\left({\widehat {I}}_{k}^{path}(F)\right)-I_{k}^{path}(F)\right|\leqslant {\frac {c_{1}k}{N}},\qquad E\left(\left[{\widehat {I}}_{k}^{path}(F)-I_{k}^{path}(F)\right]^{2}\right)\leqslant {\frac {c_{2}k}{N}},}$

para cualquier función F acotada por 1, y para algunas constantes finitas Además, para cualquier : ${\displaystyle c_{1},c_{2}.}$ ${\displaystyle x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}^{path}(F)-I_{k}^{path}(F)\right|\leqslant c_{1}{\frac {kx}{N}}+c_{2}{\sqrt {\frac {kx}{N}}}\land \sup _{0\leqslant k\leqslant n}\left|{\widehat {I}}_{k}^{path}(F)-I_{k}^{path}(F)\right|\leqslant c{\sqrt {\frac {xn\log(n)}{N}}}\right)>1-e^{-x}}$

para algunas constantes finitas relacionadas con el sesgo asintótico y la varianza de la estimación de la partícula, y para alguna constante finita c . El mismo tipo de estimaciones de sesgo y varianza se cumplen para los suavizadores de partículas hacia atrás. Para funcionales aditivos de la forma ${\displaystyle c_{1},c_{2}}$

${\displaystyle {\overline {F}}(x_{0},\cdots ,x_{n}):={\frac {1}{n+1}}\sum _{0\leqslant k\leqslant n}f_{k}(x_{k})}$

con

${\displaystyle I_{n}^{path}({\overline {F}})\approx _{N\uparrow \infty }I_{n}^{\flat ,path}({\overline {F}}):=\int {\overline {F}}(x_{0},\cdots ,x_{n}){\widehat {p}}_{backward}(d(x_{0},\cdots ,x_{n})|(y_{0},\cdots ,y_{n-1}))}$

con funciones acotadas por 1, tenemos ${\displaystyle f_{k}}$

${\displaystyle \sup _{n\geqslant 0}{\left\vert E\left({\widehat {I}}_{n}^{\flat ,path}({\overline {F}})\right)-I_{n}^{path}({\overline {F}})\right\vert }\leqslant {\frac {c_{1}}{N}}}$

y

${\displaystyle E\left(\left[{\widehat {I}}_{n}^{\flat ,path}(F)-I_{n}^{path}(F)\right]^{2}\right)\leqslant {\frac {c_{2}}{nN}}+{\frac {c_{3}}{N^{2}}}}$

Para algunas constantes finitas, se desarrollan estimaciones más refinadas que incluyen una probabilidad de error exponencialmente pequeña en ^{[10] .} ${\displaystyle c_{1},c_{2},c_{3}.}$

Remuestreo de importancia secuencial (SIR)

Filtro de Monte Carlo y filtro bootstrap

El remuestreo de importancia secuencial (SIR) , el filtrado de Monte Carlo (Kitagawa 1993 ^[35] ), el algoritmo de filtrado bootstrap (Gordon et al. 1993 ^[37] ) y el remuestreo de distribución única (Bejuri WMYB et al. 2017 ^[70] ), también son algoritmos de filtrado comúnmente aplicados, que aproximan la densidad de probabilidad de filtrado mediante un conjunto ponderado de N muestras. ${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k})}$

${\displaystyle \left\{\left(w_{k}^{(i)},x_{k}^{(i)}\right)\ :\ i\in \{1,\cdots ,N\}\right\}.}$

Los pesos de importancia son aproximaciones a las probabilidades posteriores relativas (o densidades) de las muestras tales que ${\displaystyle w_{k}^{(i)}}$

${\displaystyle \sum _{i=1}^{N}w_{k}^{(i)}=1.}$

El muestreo de importancia secuencial (SIS) es una versión secuencial (es decir, recursiva) del muestreo de importancia . Al igual que en el muestreo de importancia, la expectativa de una función f se puede aproximar como un promedio ponderado

${\displaystyle \int f(x_{k})p(x_{k}|y_{0},\dots ,y_{k})dx_{k}\approx \sum _{i=1}^{N}w_{k}^{(i)}f(x_{k}^{(i)}).}$

Para un conjunto finito de muestras, el rendimiento del algoritmo depende de la elección de la distribución propuesta.

${\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})\,}$.

La distribución propuesta "óptima" se da como la distribución objetivo .

${\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1},y_{k})={\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k})p(x_{k}|x_{k-1})dx_{k}}}~p(x_{k}|x_{k-1}).}$

Esta elección particular de propuesta de transición fue propuesta por P. Del Moral en 1996 y 1998. ^[4] Cuando es difícil muestrear transiciones según la distribución, una estrategia natural es utilizar la siguiente aproximación de partículas ${\displaystyle p(x_{k}|x_{k-1},y_{k})}$

${\displaystyle {\begin{aligned}{\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k})p(x_{k}|x_{k-1})dx_{k}}}p(x_{k}|x_{k-1})dx_{k}&\simeq _{N\uparrow \infty }{\frac {p(y_{k}|x_{k})}{\int p(y_{k}|x_{k}){\widehat {p}}(dx_{k}|x_{k-1})}}{\widehat {p}}(dx_{k}|x_{k-1})\\&=\sum _{i=1}^{N}{\frac {p(y_{k}|X_{k}^{i}(x_{k-1}))}{\sum _{j=1}^{N}p(y_{k}|X_{k}^{j}(x_{k-1}))}}\delta _{X_{k}^{i}(x_{k-1})}(dx_{k})\end{aligned}}}$

con la aproximación empírica

${\displaystyle {\widehat {p}}(dx_{k}|x_{k-1})={\frac {1}{N}}\sum _{i=1}^{N}\delta _{X_{k}^{i}(x_{k-1})}(dx_{k})~\simeq _{N\uparrow \infty }p(x_{k}|x_{k-1})dx_{k}}$

asociado con N (o cualquier otro gran número de muestras) muestras aleatorias independientes con la distribución condicional del estado aleatorio dado . La consistencia del filtro de partículas resultante de esta aproximación y otras extensiones se desarrollan en. ^[4] En la pantalla anterior se representa la medida de Dirac en un estado dado a. ${\displaystyle X_{k}^{i}(x_{k-1}),i=1,\cdots ,N}$ ${\displaystyle X_{k}}$ ${\displaystyle X_{k-1}=x_{k-1}}$ ${\displaystyle \delta _{a}}$

Sin embargo, la distribución de probabilidad previa de transición se utiliza a menudo como función de importancia, ya que es más fácil extraer partículas (o muestras) y realizar cálculos de peso de importancia posteriores:

${\displaystyle \pi (x_{k}|x_{0:k-1},y_{0:k})=p(x_{k}|x_{k-1}).}$

Los filtros de remuestreo de importancia secuencial (SIR) con distribución de probabilidad previa de transición como función de importancia se conocen comúnmente como filtro bootstrap y algoritmo de condensación .

El remuestreo se utiliza para evitar el problema de la degeneración del algoritmo, es decir, evitar la situación en la que todos los pesos de importancia, excepto uno, estén cerca de cero. El rendimiento del algoritmo también puede verse afectado por la elección adecuada del método de remuestreo. El muestreo estratificado propuesto por Kitagawa (1993 ^[35] ) es óptimo en términos de varianza.

Un solo paso de remuestreo de importancia secuencial es el siguiente:

1) Para extraer muestras de la distribución propuesta ${\displaystyle i=1,\cdots ,N}$

${\displaystyle x_{k}^{(i)}\sim \pi (x_{k}|x_{0:k-1}^{(i)},y_{0:k})}$

2) Para actualizar los pesos de importancia hasta una constante normalizadora: ${\displaystyle i=1,\cdots ,N}$

${\displaystyle {\hat {w}}_{k}^{(i)}=w_{k-1}^{(i)}{\frac {p(y_{k}|x_{k}^{(i)})p(x_{k}^{(i)}|x_{k-1}^{(i)})}{\pi (x_{k}^{(i)}|x_{0:k-1}^{(i)},y_{0:k})}}.}$

Tenga en cuenta que cuando utilizamos la distribución de probabilidad previa de transición como función de importancia,

${\displaystyle \pi (x_{k}^{(i)}|x_{0:k-1}^{(i)},y_{0:k})=p(x_{k}^{(i)}|x_{k-1}^{(i)}),}$

Esto se simplifica a lo siguiente:

${\displaystyle {\hat {w}}_{k}^{(i)}=w_{k-1}^{(i)}p(y_{k}|x_{k}^{(i)}),}$

3) Para calcular los pesos de importancia normalizados: ${\displaystyle i=1,\cdots ,N}$

${\displaystyle w_{k}^{(i)}={\frac {{\hat {w}}_{k}^{(i)}}{\sum _{j=1}^{N}{\hat {w}}_{k}^{(j)}}}}$

4) Calcule una estimación del número efectivo de partículas como

${\displaystyle {\hat {N}}_{\mathit {eff}}={\frac {1}{\sum _{i=1}^{N}\left(w_{k}^{(i)}\right)^{2}}}}$

^{Este criterio refleja la varianza de los pesos. En el artículo [6]} se pueden encontrar otros criterios, incluido su análisis riguroso y los teoremas del límite central.

5) Si el número efectivo de partículas es menor que un umbral determinado , entonces realice un nuevo muestreo: ${\displaystyle {\hat {N}}_{\mathit {eff}}<N_{thr}}$

a) Extraiga N partículas del conjunto de partículas actual con probabilidades proporcionales a sus pesos. Reemplace el conjunto de partículas actual por este nuevo.

b) Para el conjunto ${\displaystyle i=1,\cdots ,N}$ ${\displaystyle w_{k}^{(i)}=1/N.}$

El término "Remuestreo de Importancia de Muestreo" también se utiliza a veces cuando se hace referencia a los filtros SIR, pero el término Remuestreo de Importancia es más preciso porque la palabra "remuestreo" implica que el muestreo inicial ya se ha realizado. ^[71]

Muestreo de importancia secuencial (SIS)

• Es lo mismo que el remuestreo de importancia secuencial, pero sin la etapa de remuestreo.

Algoritmo de "versión directa"

El algoritmo de "versión directa" ^{[ cita requerida ]} es bastante simple (en comparación con otros algoritmos de filtrado de partículas) y utiliza composición y rechazo. Para generar una sola muestra x en k a partir de : ${\displaystyle p_{x_{k}|y_{1:k}}(x|y_{1:k})}$

1) Establezca n = 0 (esto contará la cantidad de partículas generadas hasta el momento)

2) Elija uniformemente un índice i del rango ${\displaystyle \{1,...,N\}}$

3) Generar una prueba a partir de la distribución con ${\displaystyle {\hat {x}}}$ ${\displaystyle p(x_{k}|x_{k-1})}$ ${\displaystyle x_{k-1}=x_{k-1|k-1}^{(i)}}$

4) Generar la probabilidad de utilizar de donde es el valor medido ${\displaystyle {\hat {y}}}$ ${\displaystyle {\hat {x}}}$ ${\displaystyle p(y_{k}|x_{k}),~{\mbox{with}}~x_{k}={\hat {x}}}$ ${\displaystyle y_{k}}$

5) Generar otra u uniforme desde donde ${\displaystyle [0,m_{k}]}$ ${\displaystyle m_{k}=\sup _{x_{k}}p(y_{k}|x_{k})}$

6) Compara u y ${\displaystyle p\left({\hat {y}}\right)}$

6a) Si u es mayor entonces repita desde el paso 2

6b) Si u es menor entonces guárdelo como e incremente n ${\displaystyle {\hat {x}}}$ ${\displaystyle x_{k|k}^{(i)}}$

7) Si n == N entonces salga

El objetivo es generar P "partículas" en k utilizando únicamente las partículas de . Esto requiere que se pueda escribir (y calcular) una ecuación de Markov para generar una basada únicamente en . Este algoritmo utiliza la composición de las P partículas de para generar una partícula en k y repite (pasos 2 a 6) hasta que se generen P partículas en k . ${\displaystyle k-1}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k-1}}$ ${\displaystyle k-1}$

Esto se puede visualizar más fácilmente si x se ve como una matriz bidimensional. Una dimensión es k y la otra dimensión es el número de partículas. Por ejemplo, sería la i- ^ésima partícula en y también se puede escribir (como se hizo anteriormente en el algoritmo). El paso 3 genera un potencial basado en una partícula elegida aleatoriamente ( ) en el momento y lo rechaza o lo acepta en el paso 6. En otras palabras, los valores se generan utilizando el . ${\displaystyle x(k,i)}$ ${\displaystyle k}$ ${\displaystyle x_{k}^{(i)}}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k-1}^{(i)}}$ ${\displaystyle k-1}$ ${\displaystyle x_{k}}$ ${\displaystyle x_{k-1}}$

Aplicaciones

Los filtros de partículas y las metodologías de partículas Feynman-Kac encuentran aplicación en varios contextos, como un medio eficaz para abordar observaciones ruidosas o fuertes no linealidades, tales como:

• Inferencia bayesiana , aprendizaje automático , análisis de riesgos y muestreo de eventos raros
• Bioinformática ^[19]
• Ciencia computacional
• Economía , matemáticas financieras y finanzas matemáticas : los filtros de partículas pueden realizar simulaciones necesarias para calcular integrales de alta dimensión y/o complejas relacionadas con problemas como los modelos de equilibrio general estocástico dinámico en macroeconomía y fijación de precios de opciones ^[72]
• Ingeniería
• Epidemiología de enfermedades infecciosas , donde se han aplicado a una serie de problemas de pronóstico de epidemias, por ejemplo, la predicción de epidemias de gripe estacional ^[73]
• Detección y aislamiento de fallas : en esquemas basados ​​en observadores, un filtro de partículas puede pronosticar la salida esperada de los sensores, lo que permite el aislamiento de fallas ^{[74] [75] [76]}
• Química molecular y física computacional
• Farmacocinética ^[77]
• Filogenética
• Robótica , inteligencia artificial : la localización de Monte Carlo es un estándar de facto en la localización de robots móviles ^{[78] [79] [80]}
• Procesamiento de señales e imágenes : localización visual, seguimiento, reconocimiento de características ^[81]

Otros filtros de partículas

• Filtro auxiliar de partículas ^[82]
• Cost Reference particle filter
• Exponential Natural Particle Filter^[83]
• Feynman-Kac and mean-field particle methodologies^[2][10][5]
• Gaussian particle filter
• Gauss–Hermite particle filter
• Hierarchical/Scalable particle filter^[84]
• Nudged particle filter^[85]
• Particle Markov-Chain Monte-Carlo, see e.g. pseudo-marginal Metropolis–Hastings algorithm.
• Rao–Blackwellized particle filter^[53]
• Regularized auxiliary particle filter^[86]
• Rejection-sampling based optimal particle filter^[87][88]
• Unscented particle filter

See also

• Ensemble Kalman filter
• Generalized filtering
• Genetic algorithm
• Mean-field particle methods
• Monte Carlo localization
• Moving horizon estimation
• Recursive Bayesian estimation

References

1. Wills, Adrian G.; Schön, Thomas B. (3 May 2023). "Sequential Monte Carlo: A Unified Review". Annual Review of Control, Robotics, and Autonomous Systems. 6 (1): 159–182. doi:10.1146/annurev-control-042920-015119. ISSN 2573-5144. S2CID 255638127.
2. Del Moral, Pierre (1996). "Non Linear Filtering: Interacting Particle Solution" (PDF). Markov Processes and Related Fields. 2 (4): 555–580.
3. Liu, Jun S.; Chen, Rong (1998-09-01). "Sequential Monte Carlo Methods for Dynamic Systems". Journal of the American Statistical Association. 93 (443): 1032–1044. doi:10.1080/01621459.1998.10473765. ISSN 0162-1459.
4. Del Moral, Pierre (1998). "Measure Valued Processes and Interacting Particle Systems. Application to Non Linear Filtering Problems". Annals of Applied Probability. 8 (2) (Publications du Laboratoire de Statistique et Probabilités, 96-15 (1996) ed.): 438–495. doi:10.1214/aoap/1028903535.
5. Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. Series: Probability and Applications. p. 556. ISBN 978-0-387-20268-6.
6. Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2012). "On Adaptive Resampling Procedures for Sequential Monte Carlo Methods" (PDF). Bernoulli. 18 (1): 252–278. doi:10.3150/10-bej335. S2CID 4506682.
7. Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Probability and its Applications. Springer. p. 575. ISBN 9780387202686. Series: Probability and Applications
8. Del Moral, Pierre; Miclo, Laurent (2000). "Branching and Interacting Particle Systems Approximations of Feynman-Kac Formulae with Applications to Non-Linear Filtering". In Jacques Azéma; Michel Ledoux; Michel Émery; Marc Yor (eds.). Séminaire de Probabilités XXXIV (PDF). Lecture Notes in Mathematics. Vol. 1729. pp. 1–145. doi:10.1007/bfb0103798. ISBN 978-3-540-67314-9.
9. Del Moral, Pierre; Miclo, Laurent (2000). "A Moran particle system approximation of Feynman-Kac formulae". Stochastic Processes and Their Applications. 86 (2): 193–216. doi:10.1016/S0304-4149(99)00094-0. S2CID 122757112.
10. Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. p. 626. Monographs on Statistics & Applied Probability
11. Moral, Piere Del; Doucet, Arnaud (2014). "Particle methods: An introduction with applications". ESAIM: Proc. 44: 1–46. doi:10.1051/proc/201444001.
12. Rosenbluth, Marshall, N.; Rosenbluth, Arianna, W. (1955). "Monte-Carlo calculations of the average extension of macromolecular chains". J. Chem. Phys. 23 (2): 356–359. Bibcode:1955JChPh..23..356R. doi:10.1063/1.1741967. S2CID 89611599.{{cite journal}}: CS1 maint: multiple names: authors list (link)
13. Hetherington, Jack, H. (1984). "Observations on the statistical iteration of matrices". Phys. Rev. A. 30 (2713): 2713–2719. Bibcode:1984PhRvA..30.2713H. doi:10.1103/PhysRevA.30.2713.{{cite journal}}: CS1 maint: multiple names: authors list (link)
14. Del Moral, Pierre (2003). "Particle approximations of Lyapunov exponents connected to Schrödinger operators and Feynman-Kac semigroups". ESAIM Probability & Statistics. 7: 171–208. doi:10.1051/ps:2003001.
15. Assaraf, Roland; Caffarel, Michel; Khelif, Anatole (2000). "Diffusion Monte Carlo Methods with a fixed number of walkers" (PDF). Phys. Rev. E. 61 (4): 4566–4575. Bibcode:2000PhRvE..61.4566A. doi:10.1103/physreve.61.4566. PMID 11088257. Archived from the original (PDF) on 2014-11-07.
16. Caffarel, Michel; Ceperley, David; Kalos, Malvin (1993). "Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms". Phys. Rev. Lett. 71 (13): 2159. Bibcode:1993PhRvL..71.2159C. doi:10.1103/physrevlett.71.2159. PMID 10054598.
17. Ocone, D. L. (January 1, 1999). "Asymptotic stability of beneš filters". Stochastic Analysis and Applications. 17 (6): 1053–1074. doi:10.1080/07362999908809648. ISSN 0736-2994.
18. Maurel, Mireille Chaleyat; Michel, Dominique (January 1, 1984). "Des resultats de non existence de filtre de dimension finie". Stochastics. 13 (1–2): 83–102. doi:10.1080/17442508408833312. ISSN 0090-9491.
19. Hajiramezanali, Ehsan; Imani, Mahdi; Braga-Neto, Ulisses; Qian, Xiaoning; Dougherty, Edward R. (2019). "Scalable optimal Bayesian classification of single-cell trajectories under regulatory model uncertainty". BMC Genomics. 20 (Suppl 6): 435. arXiv:1902.03188. Bibcode:2019arXiv190203188H. doi:10.1186/s12864-019-5720-3. PMC 6561847. PMID 31189480.
20. Cruz, Marcelo G.; Peters, Gareth W.; Shevchenko, Pavel V. (2015-02-27). Fundamental Aspects of Operational Risk and Insurance Analytics: A Handbook of Operational Risk (1 ed.). Wiley. doi:10.1002/9781118573013. ISBN 978-1-118-11839-9.
21. Peters, Gareth W.; Shevchenko, Pavel V. (2015-02-20). Advances in Heavy Tailed Risk Modeling: A Handbook of Operational Risk (1 ed.). Wiley. doi:10.1002/9781118909560. ISBN 978-1-118-90953-9.
22. Turing, Alan M. (October 1950). "Computing machinery and intelligence". Mind. LIX (238): 433–460. doi:10.1093/mind/LIX.236.433.
23. Barricelli, Nils Aall (1954). "Esempi numerici di processi di evoluzione". Methodos: 45–68.
24. Barricelli, Nils Aall (1957). "Symbiogenetic evolution processes realized by artificial methods". Methodos: 143–182.
25. Hammersley, J. M.; Morton, K. W. (1954). "Poor Man's Monte Carlo". Journal of the Royal Statistical Society. Series B (Methodological). 16 (1): 23–38. doi:10.1111/j.2517-6161.1954.tb00145.x. JSTOR 2984008.
26. Barricelli, Nils Aall (1963). "Numerical testing of evolution theories. Part II. Preliminary tests of performance, symbiogenesis and terrestrial life". Acta Biotheoretica. 16 (3–4): 99–126. doi:10.1007/BF01556602. S2CID 86717105.
27. "Adaptation in Natural and Artificial Systems | The MIT Press". mitpress.mit.edu. Retrieved 2015-06-06.
28. Fraser, Alex (1957). "Simulation of genetic systems by automatic digital computers. I. Introduction". Aust. J. Biol. Sci. 10 (4): 484–491. doi:10.1071/BI9570484.
29. Fraser, Alex; Burnell, Donald (1970). Computer Models in Genetics. New York: McGraw-Hill. ISBN 978-0-07-021904-5.
30. Crosby, Jack L. (1973). Computer Simulation in Genetics. London: John Wiley & Sons. ISBN 978-0-471-18880-3.
31. Assaraf, Roland; Caffarel, Michel; Khelif, Anatole (2000). "Diffusion Monte Carlo Methods with a fixed number of walkers" (PDF). Phys. Rev. E. 61 (4): 4566–4575. Bibcode:2000PhRvE..61.4566A. doi:10.1103/physreve.61.4566. PMID 11088257. Archived from the original (PDF) on 2014-11-07.
32. Caffarel, Michel; Ceperley, David; Kalos, Malvin (1993). "Comment on Feynman-Kac Path-Integral Calculation of the Ground-State Energies of Atoms". Phys. Rev. Lett. 71 (13): 2159. Bibcode:1993PhRvL..71.2159C. doi:10.1103/physrevlett.71.2159. PMID 10054598.
33. Fermi, Enrique; Richtmyer, Robert, D. (1948). "Note on census-taking in Monte Carlo calculations" (PDF). LAM. 805 (A). Declassified report Los Alamos Archive{{cite journal}}: CS1 maint: multiple names: authors list (link)
34. Herman, Kahn; Harris, Theodore, E. (1951). "Estimation of particle transmission by random sampling" (PDF). Natl. Bur. Stand. Appl. Math. Ser. 12: 27–30.{{cite journal}}: CS1 maint: multiple names: authors list (link)
35. Kitagawa, G. (January 1993). "A Monte Carlo Filtering and Smoothing Method for Non-Gaussian Nonlinear State Space Models" (PDF). Proceedings of the 2nd U.S.-Japan Joint Seminar on Statistical Time Series Analysis: 110–131.
36. Kitagawa, G. (1996). "Monte carlo filter and smoother for non-Gaussian nonlinear state space models". Journal of Computational and Graphical Statistics. 5 (1): 1–25. doi:10.2307/1390750. JSTOR 1390750.
37. Gordon, N.J.; Salmond, D.J.; Smith, A.F.M. (April 1993). "Novel approach to nonlinear/non-Gaussian Bayesian state estimation". IEE Proceedings F - Radar and Signal Processing. 140 (2): 107–113. doi:10.1049/ip-f-2.1993.0015. ISSN 0956-375X.
38. Carvalho, Himilcon; Del Moral, Pierre; Monin, André; Salut, Gérard (July 1997). "Optimal Non-linear Filtering in GPS/INS Integration" (PDF). IEEE Transactions on Aerospace and Electronic Systems. 33 (3): 835. Bibcode:1997ITAES..33..835C. doi:10.1109/7.599254. S2CID 27966240. Archived from the original (PDF) on 2022-11-10. Retrieved 2015-06-01.
39. P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : An unified framework for particle solutions
    LAAS-CNRS, Toulouse, Research Report no. 91137, DRET-DIGILOG- LAAS/CNRS contract, April (1991).
40. P. Del Moral, G. Rigal, and G. Salut. Nonlinear and non-Gaussian particle filters applied to inertial platform repositioning.
    LAAS-CNRS, Toulouse, Research Report no. 92207, STCAN/DIGILOG-LAAS/CNRS Convention STCAN no. A.91.77.013, (94p.) September (1991).
41. P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Experimental results.
    Convention DRET no. 89.34.553.00.470.75.01, Research report no.2 (54p.), January (1992).
42. P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation. Theoretical results
    Convention DRET no. 89.34.553.00.470.75.01, Research report no.3 (123p.), October (1992).
43. P. Del Moral, J.-Ch. Noyer, G. Rigal, and G. Salut. Particle filters in radar signal processing : detection, estimation and air targets recognition.
    LAAS-CNRS, Toulouse, Research report no. 92495, December (1992).
44. P. Del Moral, G. Rigal, and G. Salut. Estimation and nonlinear optimal control : Particle resolution in filtering and estimation.
    Studies on: Filtering, optimal control, and maximum likelihood estimation. Convention DRET no. 89.34.553.00.470.75.01. Research report no.4 (210p.), January (1993).
45. Crisan, Dan; Gaines, Jessica; Lyons, Terry (1998). "Convergence of a branching particle method to the solution of the Zakai". SIAM Journal on Applied Mathematics. 58 (5): 1568–1590. doi:10.1137/s0036139996307371. S2CID 39982562.
46. Crisan, Dan; Lyons, Terry (1997). "Nonlinear filtering and measure-valued processes". Probability Theory and Related Fields. 109 (2): 217–244. doi:10.1007/s004400050131. S2CID 119809371.
47. Crisan, Dan; Lyons, Terry (1999). "A particle approximation of the solution of the Kushner–Stratonovitch equation". Probability Theory and Related Fields. 115 (4): 549–578. doi:10.1007/s004400050249. S2CID 117725141.
48. Crisan, Dan; Del Moral, Pierre; Lyons, Terry (1999). "Discrete filtering using branching and interacting particle systems" (PDF). Markov Processes and Related Fields. 5 (3): 293–318.
49. Del Moral, Pierre; Guionnet, Alice (1999). "On the stability of Measure Valued Processes with Applications to filtering". C. R. Acad. Sci. Paris. 39 (1): 429–434.
50. Del Moral, Pierre; Guionnet, Alice (2001). "On the stability of interacting processes with applications to filtering and genetic algorithms". Annales de l'Institut Henri Poincaré. 37 (2): 155–194. Bibcode:2001AIHPB..37..155D. doi:10.1016/s0246-0203(00)01064-5. Archived from the original on 2014-11-07.
51. Del Moral, P.; Guionnet, A. (1999). "Central limit theorem for nonlinear filtering and interacting particle systems". The Annals of Applied Probability. 9 (2): 275–297. doi:10.1214/aoap/1029962742. ISSN 1050-5164.
52. Del Moral, Pierre; Miclo, Laurent (2001). "Genealogies and Increasing Propagation of Chaos For Feynman-Kac and Genetic Models". The Annals of Applied Probability. 11 (4): 1166–1198. doi:10.1214/aoap/1015345399. ISSN 1050-5164.
53. Doucet, A.; De Freitas, N.; Murphy, K.; Russell, S. (2000). Rao–Blackwellised particle filtering for dynamic Bayesian networks. Proceedings of the Sixteenth conference on Uncertainty in artificial intelligence. pp. 176–183. CiteSeerX 10.1.1.137.5199.
54. Del Moral, Pierre; Miclo, Laurent (2001). "Genealogies and Increasing Propagations of Chaos for Feynman-Kac and Genetic Models". Annals of Applied Probability. 11 (4): 1166–1198.
55. Del Moral, Pierre; Doucet, Arnaud; Singh, Sumeetpal, S. (2010). "A Backward Particle Interpretation of Feynman-Kac Formulae" (PDF). M2AN. 44 (5): 947–976. doi:10.1051/m2an/2010048. S2CID 14758161.{{cite journal}}: CS1 maint: multiple names: authors list (link)
56. Vergé, Christelle; Dubarry, Cyrille; Del Moral, Pierre; Moulines, Eric (2013). "On parallel implementation of Sequential Monte Carlo methods: the island particle model". Statistics and Computing. 25 (2): 243–260. arXiv:1306.3911. Bibcode:2013arXiv1306.3911V. doi:10.1007/s11222-013-9429-x. S2CID 39379264.
57. Chopin, Nicolas; Jacob, Pierre, E.; Papaspiliopoulos, Omiros (2011). "SMC^2: an efficient algorithm for sequential analysis of state-space models". arXiv:1101.1528v3 [stat.CO].{{cite arXiv}}: CS1 maint: multiple names: authors list (link)
58. Andrieu, Christophe; Doucet, Arnaud; Holenstein, Roman (2010). "Particle Markov chain Monte Carlo methods". Journal of the Royal Statistical Society, Series B. 72 (3): 269–342. doi:10.1111/j.1467-9868.2009.00736.x.
59. Del Moral, Pierre; Patras, Frédéric; Kohn, Robert (2014). "On Feynman-Kac and particle Markov chain Monte Carlo models". arXiv:1404.5733 [math.PR].
60. Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2006). "Sequential Monte Carlo Samplers". Journal of the Royal Statistical Society. Series B (Statistical Methodology). 68 (3): 411–436. arXiv:cond-mat/0212648. doi:10.1111/j.1467-9868.2006.00553.x. ISSN 1369-7412. JSTOR 3879283.
61. Peters, Gareth (2005). "Topics in Sequential Monte Carlo Samplers". SSRN Electronic Journal. doi:10.2139/ssrn.3785582. ISSN 1556-5068.
62. Del Moral, Pierre; Doucet, Arnaud; Peters, Gareth (2004). "Sequential Monte Carlo Samplers CUED Technical Report". SSRN Electronic Journal. doi:10.2139/ssrn.3841065. ISSN 1556-5068.
63. Sisson, S. A.; Fan, Y.; Beaumont, M. A., eds. (2019). Handbook of approximate Bayesian computation. Boca Raton: CRC Press, Taylor and Francis Group. ISBN 978-1-315-11719-5.
64. Peters, Gareth W.; Wüthrich, Mario V.; Shevchenko, Pavel V. (2010-08-01). "Chain ladder method: Bayesian bootstrap versus classical bootstrap". Insurance: Mathematics and Economics. 47 (1): 36–51. arXiv:1004.2548. doi:10.1016/j.insmatheco.2010.03.007. ISSN 0167-6687.
65. Del Moral, Pierre; Jacod, Jean; Protter, Philip (2001-07-01). "The Monte-Carlo method for filtering with discrete-time observations". Probability Theory and Related Fields. 120 (3): 346–368. doi:10.1007/PL00008786. hdl:1813/9179. ISSN 0178-8051. S2CID 116274.
66. Del Moral, Pierre; Doucet, Arnaud; Jasra, Ajay (2011). "An adaptive sequential Monte Carlo method for approximate Bayesian computation". Statistics and Computing. 22 (5): 1009–1020. CiteSeerX 10.1.1.218.9800. doi:10.1007/s11222-011-9271-y. ISSN 0960-3174. S2CID 4514922.
67. Martin, James S.; Jasra, Ajay; Singh, Sumeetpal S.; Whiteley, Nick; Del Moral, Pierre; McCoy, Emma (May 4, 2014). "Approximate Bayesian Computation for Smoothing". Stochastic Analysis and Applications. 32 (3): 397–420. arXiv:1206.5208. doi:10.1080/07362994.2013.879262. ISSN 0736-2994. S2CID 17117364.
68. Del Moral, Pierre; Rio, Emmanuel (2011). "Concentration inequalities for mean field particle models". The Annals of Applied Probability. 21 (3): 1017–1052. arXiv:1211.1837. doi:10.1214/10-AAP716. ISSN 1050-5164. S2CID 17693884.
69. Del Moral, Pierre; Hu, Peng; Wu, Liming (2012). On the Concentration Properties of Interacting Particle Processes. Hanover, MA, USA: Now Publishers Inc. ISBN 978-1601985125.
70. Bejuri, Wan Mohd Yaakob Wan; Mohamad, Mohd Murtadha; Raja Mohd Radzi, Raja Zahilah; Salleh, Mazleena; Yusof, Ahmad Fadhil (2017-10-18). "Adaptive memory-based single distribution resampling for particle filter". Journal of Big Data. 4 (1): 33. doi:10.1186/s40537-017-0094-3. ISSN 2196-1115. S2CID 256407088.
71. Gelman, Andrew; Carlin, John B.; Stern, Hal S.; Dunson, David B.; Vehtari, Aki; Rubin, Donald B. (2013). Bayesian Data Analysis, Third Edition. Chapman and Hall/CRC. ISBN 978-1-4398-4095-5.
72. Creal, Drew (2012). "A Survey of Sequential Monte Carlo Methods for Economics and Finance". Econometric Reviews. 31 (2): 245–296. doi:10.1080/07474938.2011.607333. hdl:1871/15287. S2CID 2730761.
73. Moss, Robert; Zarebski, Alexander; Dawson, Peter; McCaw, James M. (2016). "Forecasting influenza outbreak dynamics in Melbourne from Internet search query surveillance data". Influenza and Other Respiratory Viruses. 10 (4): 314–323. doi:10.1111/irv.12376. PMC 4910172. PMID 26859411.
74. Shen, Yin; Xiangping, Zhu (2015). "Intelligent Particle Filter and Its Application to Fault Detection of Nonlinear System". IEEE Transactions on Industrial Electronics. 62 (6): 1. doi:10.1109/TIE.2015.2399396. S2CID 23951880.
75. D'Amato, Edigio; Notaro, Immacolata; Nardi, Vito Antonio; Scordamaglia, Valerio (2021). "A Particle Filtering Approach for Fault Detection and Isolation of UAV IMU Sensors: Design, Implementation and Sensitivity Analysis". Sensors. 21 (9): 3066. Bibcode:2021Senso..21.3066D. doi:10.3390/s21093066. PMC 8124649. PMID 33924891.
76. Kadirkamanathan, V.; Li, P.; Jaward, M. H.; Fabri, S. G. (2002). "Particle filtering-based fault detection in non-linear stochastic systems". International Journal of Systems Science. 33 (4): 259–265. doi:10.1080/00207720110102566. S2CID 28634585.
77. Bonate P: Pharmacokinetic-Pharmacodynamic Modeling and Simulation. Berlin: Springer; 2011.
78. Dieter Fox, Wolfram Burgard, Frank Dellaert, and Sebastian Thrun, "Monte Carlo Localization: Efficient Position Estimation for Mobile Robots." Proc. of the Sixteenth National Conference on Artificial Intelligence John Wiley & Sons Ltd, 1999.
79. Sebastian Thrun, Wolfram Burgard, Dieter Fox. Probabilistic Robotics MIT Press, 2005. Ch. 8.3 ISBN 9780262201629.
80. Sebastian Thrun, Dieter Fox, Wolfram Burgard, Frank Dellaert. "Robust monte carlo localization for mobile robots." Artificial Intelligence 128.1 (2001): 99–141.
81. Abbasi, Mahdi; Khosravi, Mohammad R. (2020). "A Robust and Accurate Particle Filter-Based Pupil Detection Method for Big Datasets of Eye Video". Journal of Grid Computing. 18 (2): 305–325. doi:10.1007/s10723-019-09502-1. S2CID 209481431.
82. Pitt, M.K.; Shephard, N. (1999). "Filtering Via Simulation: Auxiliary Particle Filters". Journal of the American Statistical Association. 94 (446): 590–591. doi:10.2307/2670179. JSTOR 2670179. Archived from the original on 2007-10-16. Retrieved 2008-05-06.
83. Zand, G.; Taherkhani, M.; Safabakhsh, R. (2015). "Exponential Natural Particle Filter". arXiv:1511.06603 [cs.LG].
84. Canton-Ferrer, C.; Casas, J.R.; Pardàs, M. (2011). "Human Motion Capture Using Scalable Body Models". Computer Vision and Image Understanding. 115 (10): 1363–1374. doi:10.1016/j.cviu.2011.06.001. hdl:2117/13393.
85. Akyildiz, Ömer Deniz; Míguez, Joaquín (2020-03-01). "Nudging the particle filter". Statistics and Computing. 30 (2): 305–330. doi:10.1007/s11222-019-09884-y. hdl:10044/1/100011. ISSN 1573-1375. S2CID 88515918.
86. Liu, J.; Wang, W.; Ma, F. (2011). "A Regularized Auxiliary Particle Filtering Approach for System State Estimation and Battery Life Prediction". Smart Materials and Structures. 20 (7): 1–9. Bibcode:2011SMaS...20g5021L. doi:10.1088/0964-1726/20/7/075021. S2CID 110670991.
87. Blanco, J.L.; Gonzalez, J.; Fernandez-Madrigal, J.A. (2008). An Optimal Filtering Algorithm for Non-Parametric Observation Models in Robot Localization. IEEE International Conference on Robotics and Automation (ICRA'08). pp. 461–466. CiteSeerX 10.1.1.190.7092.
88. Blanco, J.L.; Gonzalez, J.; Fernandez-Madrigal, J.A. (2010). "Optimal Filtering for Non-Parametric Observation Models: Applications to Localization and SLAM". The International Journal of Robotics Research. 29 (14): 1726–1742. CiteSeerX 10.1.1.1031.4931. doi:10.1177/0278364910364165. S2CID 453697.

Bibliography

• Del Moral, Pierre (1996). "Non Linear Filtering: Interacting Particle Solution" (PDF). Markov Processes and Related Fields. 2 (4): 555–580. Archived from the original (PDF) on 2016-03-04. Retrieved 2015-05-31.
• Del Moral, Pierre (2004). Feynman-Kac formulae. Genealogical and interacting particle approximations. Springer. p. 575. "Series: Probability and Applications"
• Del Moral, Pierre (2013). Mean field simulation for Monte Carlo integration. Chapman & Hall/CRC Press. p. 626. "Monographs on Statistics & Applied Probability"
• Cappe, O.; Moulines, E.; Ryden, T. (2005). Inference in Hidden Markov Models. Springer.
• Liu, J.S.; Chen, R. (1998). "Sequential Monte Carlo methods for dynamic systems" (PDF). Journal of the American Statistical Association. 93 (443): 1032–1044. doi:10.1080/01621459.1998.10473765.
• Liu, J.S. (2001). Monte Carlo strategies in Scientific Computing. Springer.
• Kong, A.; Liu, J.S.; Wong, W.H. (1994). "Sequential imputations and Bayesian missing data problems" (PDF). Journal of the American Statistical Association. 89 (425): 278–288. doi:10.1080/01621459.1994.10476469.
• Liu, J.S.; Chen, R. (1995). "Blind deconvolution via sequential imputations" (PDF). Journal of the American Statistical Association. 90 (430): 567–576. doi:10.2307/2291068. JSTOR 2291068.
• Ristic, B.; Arulampalam, S.; Gordon, N. (2004). Beyond the Kalman Filter: Particle Filters for Tracking Applications. Artech House.
• Doucet, A.; Johansen, A.M. (December 2008). "A tutorial on particle filtering and smoothing: fifteen years later" (PDF). Technical Report.
• Doucet, A.; Godsill, S.; Andrieu, C. (2000). "On sequential Monte Carlo sampling methods for Bayesian filtering". Statistics and Computing. 10 (3): 197–208. doi:10.1023/A:1008935410038. S2CID 16288401.
• Arulampalam, M.S.; Maskell, S.; Gordon, N.; Clapp, T. (2002). "A tutorial on particle filters for online nonlinear/non-Gaussian Bayesian tracking". IEEE Transactions on Signal Processing. 50 (2): 174–188. Bibcode:2002ITSP...50..174A. CiteSeerX 10.1.1.471.8617. doi:10.1109/78.978374. S2CID 55577025.
• Cappe, O.; Godsill, S.; Moulines, E. (2007). "An overview of existing methods and recent advances in sequential Monte Carlo". Proceedings of the IEEE. 95 (5): 899–924. doi:10.1109/JPROC.2007.893250. S2CID 3081664.
• Kitagawa, G. (1996). "Monte carlo filter and smoother for non-Gaussian nonlinear state space models". Journal of Computational and Graphical Statistics. 5 (1): 1–25. doi:10.2307/1390750. JSTOR 1390750.
• Kotecha, J.H.; Djuric, P. (2003). "Gaussian Particle filtering". IEEE Transactions on Signal Processing. 51 (10).
• Haug, A.J. (2005). "A Tutorial on Bayesian Estimation and Tracking Techniques Applicable to Nonlinear and Non-Gaussian Processes" (PDF). The MITRE Corporation, USA, Tech. Rep., Feb. Archived (PDF) from the original on December 22, 2021. Retrieved 2021-12-22.
• Pitt, M.K.; Shephard, N. (1999). "Filtering Via Simulation: Auxiliary Particle Filters". Journal of the American Statistical Association. 94 (446): 590–591. doi:10.2307/2670179. JSTOR 2670179. Archived from the original on 2007-10-16. Retrieved 2008-05-06.
• Gordon, N. J.; Salmond, D. J.; Smith, A. F. M. (1993). "Novel approach to nonlinear/non-Gaussian Bayesian state estimation". IEE Proceedings F - Radar and Signal Processing. 140 (2): 107–113. doi:10.1049/ip-f-2.1993.0015.
• Chen, Z. (2003). "Bayesian Filtering: From Kalman Filters to Particle Filters, and Beyond". CiteSeerX 10.1.1.107.7415. {{cite journal}}: Cite journal requires |journal= (help)
• Vaswani, N.; Rathi, Y.; Yezzi, A.; Tannenbaum, A. (2007). "Tracking deforming objects using particle filtering for geometric active contours". IEEE Transactions on Pattern Analysis and Machine Intelligence. 29 (8): 1470–1475. doi:10.1109/tpami.2007.1081. PMC 3663080. PMID 17568149.

External links

• Feynman–Kac models and interacting particle algorithms (a.k.a. Particle Filtering) Theoretical aspects and a list of application domains of particle filters
• Sequential Monte Carlo Methods (Particle Filtering) homepage on University of Cambridge
• Dieter Fox's MCL Animations
• Rob Hess' free software
• SMCTC: A Template Class for Implementing SMC algorithms in C++
• Java applet on particle filtering
• vSMC : Vectorized Sequential Monte Carlo
• Particle filter explained in the context of self driving car