Filtro de partículas

Desde un punto de vista estadístico y probabilístico, los filtros de partículas pertenecen a la clase de algoritmos de ramificación / genéticos y metodologías de partículas interactuantes de 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 genéticas de campo medio se utilizan a menudo como algoritmos heurísticos y de búsqueda natural (también conocidos como metaheurísticas ). 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, autovalores máximos 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 un entorno determinado.

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 de mutación-selección de tipo genético ^{[ 22 ]} y los artículos de Nils Aall Barricelli en el Instituto de Estudios Avanzados en Princeton, Nueva Jersey . ^{[ 23 ] [ 24 ]} El primer rastro de filtros de partículas en metodología estadística data de mediados de la década de 1950; el 'Monte Carlo del pobre', ^{[ 25 ]} que fue propuesto por John Hammersley et al., en 1954, contenía indicios de los métodos de filtrado de partículas de tipo genético que se utilizan 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 popularizaron gracias al trabajo fundamental 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 genética de la selección artificial de organismos. ^{[ 28 ]} La simulación por computadora de la evolución por parte de los biólogos se hizo 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 algoritmos modernos 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 sobre las trayectorias aleatorias de la señal ponderada por una secuencia de funciones de potencial de verosimilitud. ^{[ 7 ] [ 8 ]} Los métodos de Monte Carlo cuántico , y más específicamente los de Monte Carlo de difusión, también pueden interpretarse 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 a menudo se atribuyen 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 fundamental 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, Neil J. Gordon et al. publicaron en su trabajo seminal ^{[ 37 ]} una aplicación de algoritmos de tipo genético en la inferencia estadística bayesiana. Los autores llamaron a su algoritmo "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 (Laboratorio de Análisis y Arquitectura de Sistemas) sobre problemas de procesamiento de señales de RADAR/SONAR y GPS. ^{[ 39 ] [ 40 ] [ 41 ] [ 42 ] [ 43 ] [ 44 ]}

Desde 1950 hasta 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 heurísticos aplicados a diferentes situaciones sin una sola prueba de su consistencia, ni una discusión sobre el sesgo de las estimaciones y los algoritmos genealógicos y ancestrales basados ​​en árboles.

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 incluye una demostración de las propiedades insesgadas de una aproximación de partículas de las funciones de verosimilitud y de las medidas de probabilidad condicional no normalizadas . El estimador de partículas insesgado de las funciones de verosimilitud presentado en este artículo se utiliza actualmente 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 hacia finales 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 del límite central en 1999, y Pierre Del Moral y Laurent Miclo ^{[ 8 ]} los demostraron en 2000. Los primeros resultados de convergencia uniforme con respecto al 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 basados ​​en árboles genealógicos se debe a P. Del Moral y L. Miclo en 2001 ^{[ 52 ]}

La teoría sobre las metodologías de partículas de 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 de Kalman interactivos (también conocido como filtro de partículas Rao-Blackwell ^{[ 53 ]} ), técnicas de filtro de partículas de muestreo de importancia y de remuestreo, 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 secuenciales ^{[ 63 ]} y Bootstrap bayesiano basado en ABC de Monte Carlo secuencial. ^{[ 64 ]}

El objetivo de un filtro de partículas es estimar la densidad posterior de las variables de estado dadas las variables de observación. Este filtro está diseñado para usarse con un modelo oculto de Markov , en el que el sistema incluye variables tanto ocultas como observables. Las variables observables (proceso de observación) están vinculadas a las variables ocultas (proceso de estado) mediante una función conocida. De igual manera, 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 utilizando 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{señal}}\\\downarrow &&\downarrow &&\downarrow &&\downarrow &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{observación}}\end{array}}}$

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

Todas las estimaciones bayesianas de${\displaystyle X_{k}}$se deduce de la densidad posterior${\displaystyle p(x_{k}|y_{0},y_{1},...,y_{k})}$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. En contraste, el método de Monte Carlo de cadena de Markov o el enfoque de muestreo de importancia modelarían la distribución posterior completa.${\displaystyle p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})}$.

Los métodos de partículas a menudo asumen${\displaystyle X_{k}}$y las observaciones${\displaystyle Y_{k}}$puede modelarse de esta forma:

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

  ${\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${\displaystyle Y_{0},Y_{1},\cdots }$ tomar valores en algún espacio de estado en${\displaystyle \mathbb {R} ^{d_{y}}}$(para algunos${\displaystyle d_{y}\geqslant 1}$) y son condicionalmente independientes siempre que${\displaystyle X_{0},X_{1},\cdots }$son conocidos. En otras palabras, cada${\displaystyle Y_{k}}$solo depende de${\displaystyle X_{k}}$Además, asumimos una distribución condicional para${\displaystyle Y_{k}}$dado${\displaystyle X_{k}=x_{k}}$son absolutamente continuos y de forma sintética tenemos

  ${\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 ambos${\displaystyle W_{k}}$y${\displaystyle V_{k}}$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 se parecen 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 ambas${\displaystyle W_{k}}$y${\displaystyle V_{k}}$Si la distribución de probabilidad es gaussiana , 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).

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

En ciertos problemas, la distribución condicional de las 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 requiere un nivel adicional de aproximación. Una estrategia es reemplazar la señal${\displaystyle X_{k}}$mediante la cadena de Markov${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$y para introducir una observación virtual de la forma

${\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${\displaystyle {\mathcal {V}}_{k}}$con funciones de densidad de probabilidad conocidas . La idea central es observar que

${\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 al proceso de Markov${\displaystyle {\mathcal {X}}_{k}=\left(X_{k},Y_{k}\right)}$dadas las observaciones parciales${\displaystyle {\mathcal {Y}}_{0}=y_{0},\cdots ,{\mathcal {Y}}_{k}=y_{k},}$se define en términos de partículas que evolucionan en${\displaystyle \mathbb {R} ^{d_{x}+d_{y}}}$con una función de probabilidad dada con alguna notación obviamente abusiva por${\displaystyle p({\mathcal {Y}}_{k}|{\mathcal {X}}_{k})}$Estas técnicas probabilísticas están estrechamente relacionadas con la Computación Bayesiana Aproximada (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 ]} Posteriormente fueron desarrolladas por P. Del Moral, A. Doucet y A. Jasra. ^{[ 66 ] [ 67 ]}

La regla de Bayes para la probabilidad condicional establece:

${\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 viene dada por la recursión

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

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

${\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 de${\displaystyle X_{k}}$Desde el origen k = 0 hasta el tiempo k = n , tenemos la fórmula de Feynman-Kac.

${\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 diversas disciplinas científicas, incluyendo 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${\displaystyle G_{n}(x_{n})=1_{A}(x_{n})}$de algún subconjunto del espacio de estados, representan la distribución condicional de una cadena de Markov dado que permanece en un tubo dado; es decir, tenemos:

${\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 de normalización sea estrictamente positiva.

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

${\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 del filtro óptimo ( Ec. 1 ):

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

${\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})}$

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

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

${\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 anteriormente ${\displaystyle p(y_{k}|\xi _{k}^{i})}$representa la función de verosimilitud${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$evaluado en${\displaystyle x_{k}=\xi _{k}^{i}}$, y${\displaystyle p(x_{k+1}|{\widehat {\xi }}_{k}^{i})}$representa la densidad condicional${\displaystyle p(x_{k+1}|x_{k})}$evaluado en${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$.

En cada instante 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 conoce comúnmente como algoritmo genético con selección proporcional. En los artículos también se han propuesto varias variantes de ramificación, incluyendo aquellas con tamaños de población aleatorios. ^{[ 5 ] [ 45 ] [ 48 ]}

Los métodos de partículas, al igual que todos los enfoques basados ​​en muestreo (por ejemplo, el método de Monte Carlo de cadenas de Markov ), generan un conjunto de muestras que aproximan 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${\displaystyle X_{k}}$donde las muestras están etiquetadas con superíndices como:

${\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})}$

dónde${\displaystyle \delta _{a}}$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 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 realizar 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${\displaystyle i=1,\cdots ,N}$Los estados aleatorios${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$, con los índices inferiores l=0,...,k, representa al antepasado del individuo.${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$en el nivel l=0,...,k. En esta situación, tenemos la fórmula de aproximación

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 pueden interpretarse de diversas maneras. 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 del filtro óptimo también pueden interpretarse como las transiciones clásicas de selección-mutación de tipo genético de los individuos. La técnica de remuestreo de importancia secuencial proporciona otra interpretación de las transiciones de filtrado, acoplando el muestreo de importancia con el paso de remuestreo bootstrap. Por último, pero no menos importante, los filtros de partículas pueden considerarse una metodología de aceptación-rechazo equipada con un mecanismo de reciclaje. ^{[ 10 ] [ 5 ]}

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 ]} Desarrollos más recientes se pueden encontrar 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${\displaystyle c_{1},c_{2}.}$ Además, para cualquier${\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${\displaystyle c_{1},c_{2}}$relacionado con el sesgo asintótico y la varianza de la estimación de partículas, y alguna constante finita c . Se obtienen los mismos resultados si reemplazamos el predictor óptimo de un paso por la aproximación del filtro óptimo.

Rastreando los linajes ancestrales a lo largo del tiempo

${\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${\displaystyle {\widehat {\xi }}_{k}^{i}\left(={\widehat {\xi }}_{k,k}^{i}\right)}$y${\displaystyle \xi _{k}^{i}\left(={\xi }_{k,k}^{i}\right)}$En cada paso de tiempo k , también tenemos las aproximaciones de partículas.

${\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 de la integral 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 en 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, remitimos a los libros. ^{[ 10 ] [ 5 ]}

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${\displaystyle p(y_{0}|y_{0},\cdots ,y_{-1})=p(y_{0})}$y${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1})=p(x_{0}),}$para k = 0. Reemplazando${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k-1})dx_{k}}$mediante la aproximación empírica

${\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 anteriormente, diseñamos la siguiente aproximación de partículas insesgada de la función de verosimilitud.

${\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})}$