Filtre à particule - Particle filter

Les filtres à particules ou méthodes de Monte Carlo séquentiel sont un ensemble d' algorithmes de Monte Carlo utilisés pour résoudre les problèmes de filtrage survenant dans le traitement du signal et l'inférence statistique bayésienne . Le problème de filtrage consiste à estimer les états internes dans les systèmes dynamiques lorsque des observations partielles sont faites, et des perturbations aléatoires sont présentes dans les capteurs ainsi que dans le système dynamique. L'objectif est de calculer les distributions a posteriori des états de certains processus de Markov , compte tenu de quelques observations bruitées et partielles. Le terme "filtres à particules" a été inventé pour la première fois en 1996 par Del Moral en référence aux méthodes de particules interagissant en champ moyen utilisées en mécanique des fluides depuis le début des années 1960. Le terme « Monte Carlo séquentiel » a été inventé par Liu et Chen en 1998.

Le filtrage particulaire utilise un ensemble de particules (également appelées échantillons) pour représenter la distribution a posteriori d'un processus stochastique compte tenu d'observations bruitées et/ou partielles. Le modèle d'espace d'état peut être non linéaire et les distributions initiales d'état et de bruit peuvent prendre n'importe quelle forme requise. Les techniques de filtrage de particules fournissent une méthodologie bien établie pour générer des échantillons à partir de la distribution requise sans nécessiter d'hypothèses sur le modèle d'espace d'état ou les distributions d'état. Cependant, ces méthodes ne fonctionnent pas bien lorsqu'elles sont appliquées à des systèmes de très grande dimension.

Les filtres à particules mettent à jour leur prédiction de manière approximative (statistique). Les échantillons de la distribution sont représentés par un ensemble de particules ; chaque particule se voit attribuer un poids de probabilité qui représente la probabilité que cette particule soit échantillonnée à partir de la fonction de densité de probabilité. La disparité de poids conduisant à l'effondrement du poids est un problème courant rencontré dans ces algorithmes de filtrage ; cependant, il peut être atténué en incluant une étape de rééchantillonnage avant que les poids ne deviennent trop inégaux. Plusieurs critères de rééchantillonnage adaptatif peuvent être utilisés, dont la variance des poids et l'entropie relative par rapport à la distribution uniforme. Dans l'étape de rééchantillonnage, les particules de poids négligeables sont remplacées par de nouvelles particules à proximité des particules de poids plus élevé.

Du point de vue statistique et probabiliste, filtres à particules peuvent être interprétées comme des particules de champ moyen interprétations de Feynman-Kac mesures de probabilité. Ces techniques d'intégration de particules ont été développées en chimie moléculaire et en physique informatique par Theodore E. Harris et Herman Kahn en 1951, Marshall N. Rosenbluth et Arianna W. Rosenbluth en 1955 et plus récemment par Jack H. Hetherington en 1984. En physique informatique, ces Les méthodes d'intégration de particules de chemin de type Feynman-Kac sont également utilisées en Monte Carlo quantique , et plus particulièrement les méthodes de Monte Carlo en diffusion . Les méthodes de particules en interaction Feynman-Kac sont également fortement liées aux algorithmes génétiques de sélection de mutations actuellement utilisés en informatique évolutive pour résoudre des problèmes d'optimisation complexes.

La méthodologie du filtre à particules est utilisée pour résoudre les problèmes de modèle de Markov caché (HMM) et de filtrage non linéaire . A l'exception notable des modèles linéaires-gaussiens d'observation du signal ( filtre de Kalman ) ou de classes de modèles plus larges (filtre de Benes) Mireille Chaleyat-Maurel et Dominique Michel ont prouvé en 1984 que la séquence des distributions postérieures des états aléatoires du signal étant donné la les observations (alias filtre optimal) n'ont pas de récursivité récursive finie. Diverses autres méthodes numériques basées sur des approximations de grille fixe, les techniques de Markov Chain Monte Carlo , la linéarisation conventionnelle, les filtres de Kalman étendus ou la détermination du meilleur système linéaire (au sens coût-erreur attendu) sont incapables de faire face aux systèmes à grande échelle, aux processus instables, ou lorsque les non-linéarités ne sont pas suffisamment lisses.

Les filtres à particules et les méthodologies de particules Feynman-Kac trouvent une application dans le traitement du signal et des images , l'inférence bayésienne , l'apprentissage automatique , l'analyse des risques et l'échantillonnage d'événements rares , l' ingénierie et la robotique , l' intelligence artificielle , la bioinformatique , la phylogénétique , la science informatique , l' économie et la finance mathématique , la chimie moléculaire , physique computationnelle , pharmacocinétique et autres domaines.

Histoire

Heuristique comme des algorithmes

Du point de vue statistique et probabiliste, les filtres particulaires appartiennent à la classe des algorithmes de type branchage / génétique , et des méthodologies particulaires en interaction de type champ moyen. L'interprétation de ces méthodes particulaires dépend de la discipline scientifique. En informatique évolutive , les méthodologies de particules de type génétique à champ moyen sont souvent utilisées comme algorithmes de recherche heuristique et naturelle (alias Metaheuristic ). En physique numérique et en chimie moléculaire, ils sont utilisés pour résoudre des problèmes d'intégration de chemin de Feynman-Kac, ou ils calculent des mesures de Boltzmann-Gibbs, des valeurs propres supérieures et des états fondamentaux des opérateurs de Schrödinger . En biologie et en génétique, ils représentent également l'évolution d'une population d'individus ou de gènes dans un environnement.

Les origines des techniques de calcul évolutives de type champ moyen remontent à 1950 et 1954 avec les travaux fondateurs d' Alan Turing sur les machines d'apprentissage par sélection de mutations de type génétique et les articles de Nils Aall Barricelli à l' Institute for Advanced Study de Princeton, New Jersey. . La première trace de filtres à particules en méthodologie statistique remonte au milieu des années 50 ; le « Monte Carlo du pauvre », qui a été proposé par Hammersley et al., en 1954, contenait des indices sur les méthodes de filtrage des particules de type génétique utilisées aujourd'hui. En 1963, Nils Aall Barricelli a simulé un algorithme de type génétique pour imiter la capacité des individus à jouer à un jeu simple. Dans la littérature informatique évolutionniste , les algorithmes de sélection de mutation de type génétique sont devenus populaires grâce aux travaux fondateurs de John Holland au début des années 1970, et en particulier à son livre publié en 1975.

Dans Biology and Genetics , le généticien australien Alex Fraser a également publié en 1957 une série d'articles sur la simulation de type génétique de la sélection artificielle d'organismes. La simulation informatique de l'évolution par les biologistes est devenue plus courante au début des années 1960, et les méthodes ont été décrites dans les livres de Fraser et Burnell (1970) et Crosby (1973). Les simulations de Fraser comprenaient tous les éléments essentiels des algorithmes modernes de particules génétiques de sélection de mutation.

Du point de vue mathématique, la distribution conditionnelle des états aléatoires d'un signal compte tenu de quelques observations partielles et bruitées est décrite par une probabilité de Feynman-Kac sur les trajectoires aléatoires du signal pondérée par une séquence de fonctions potentielles de vraisemblance. Les méthodes de Monte Carlo quantique , et plus spécifiquement de Monte Carlo de diffusion, peuvent également être interprétées comme une approximation particulaire de type génétique à champ moyen des intégrales de chemin de Feynman-Kac. Les origines des méthodes Quantum Monte Carlo sont souvent attribuées à Enrico Fermi et Robert Richtmyer qui ont développé en 1948 une interprétation particulaire en champ moyen des réactions en chaîne de neutrons, mais le premier algorithme de particules de type heuristique et de type génétique (alias Resampled ou Reconfiguration Monte Carlo méthodes) pour estimer les énergies de l'état fondamental des systèmes quantiques (dans les modèles matriciels réduits) est due à Jack H. Hetherington en 1984. On peut également citer les premiers travaux fondateurs de Theodore E. Harris et Herman Kahn en physique des particules, publiés en 1951, en utilisant des méthodes génétiques à champ moyen mais de type heuristique pour estimer les énergies de transmission des particules. En chimie moléculaire, l'utilisation de méthodologies de particules de type heuristique génétique (alias stratégies d'élagage et d'enrichissement) remonte à 1955 avec les travaux fondateurs de Marshall. N. Rosenbluth et Arianna. W. Rosenbluth.

L'utilisation d' algorithmes de particules génétiques dans le traitement avancé du signal et l'inférence bayésienne est plus récente. En janvier 1993, Genshiro Kitagawa développa un "filtre Monte Carlo", une version légèrement modifiée de cet article paru en 1996. En avril 1993, Gordon et al., publièrent dans leur ouvrage fondateur une application de l'algorithme de type génétique à l'inférence statistique bayésienne. Les auteurs ont nommé leur algorithme « le filtre d'amorçage » et ont démontré que, comparé à d'autres méthodes de filtrage, leur algorithme d'amorçage ne nécessite aucune hypothèse sur cet espace d'état ou le bruit du système. Indépendamment, ceux de Pierre Del Moral et Himilcon Carvalho, Pierre Del Moral, André Monin et Gérard Salut sur les filtres à particules publiés au milieu des années 1990. Les filtres à particules ont également été développés en traitement du signal au début de 1989-1992 par P. Del Moral, JC Noyer, G. Rigal et G. Salut au LAAS-CNRS dans une série de rapports de recherche restreints et classifiés avec le STCAN (Service Technique des Constructions et Armes Navales), la société informatique DIGILOG et le LAAS-CNRS (Laboratoire d'Analyse et d'Architecture des Systèmes) sur les problèmes de traitement du signal RADAR/SONAR et GPS.

Fondements mathématiques

De 1950 à 1996, toutes les publications sur les filtres à particules, les algorithmes génétiques, y compris les méthodes d'élagage et de rééchantillonnage de Monte Carlo introduites en physique numérique et en chimie moléculaire, présentent des algorithmes naturels et de type heuristique appliqués à différentes situations sans une seule preuve de leur cohérence, ni une discussion sur le biais des estimations et sur les algorithmes généalogiques et ancestraux basés sur les arbres.

Les fondements mathématiques et la première analyse rigoureuse de ces algorithmes particulaires sont dus à Pierre Del Moral en 1996. L'article contient également une preuve des propriétés non biaisées d'une particule d'approximations de fonctions de vraisemblance et de mesures de probabilité conditionnelles non normalisées . L'estimateur de particules sans biais des fonctions de vraisemblance présenté dans cet article est utilisé aujourd'hui dans l'inférence statistique bayésienne.

Des méthodologies de particules de type ramifié avec différentes tailles de population ont également été développées vers la fin des années 1990 par Dan Crisan, Jessica Gaines et Terry Lyons, et par Dan Crisan, Pierre Del Moral et Terry Lyons. D'autres développements dans ce domaine ont été développés en 2000 par P. Del Moral, A. Guionnet et L. Miclo. Les premiers théorèmes centraux limites sont dus à Pierre Del Moral et Alice Guionnet en 1999 et à Pierre Del Moral et Laurent Miclo en 2000. Les premiers résultats de convergence uniforme par rapport au paramètre temporel des filtres à particules ont été développés à la fin des années 1990 par Pierre Del Moral et Alice Guionnet. La première analyse rigoureuse des lisseurs de filtres à particules à base d'arbres généalogiques est due à P. Del Moral et L. Miclo en 2001

La théorie sur les méthodologies de particules Feynman-Kac et les algorithmes de filtres à particules associés a été développée en 2000 et 2004 dans les livres. Ces modèles probabilistes abstraits encapsulent des algorithmes de type génétique, des filtres de particules et d'amorçage, des filtres de Kalman en interaction (alias filtre de particules Rao-Blackwellized), des techniques de filtrage de particules de style d'échantillonnage et de rééchantillonnage, y compris des méthodologies basées sur l'arbre généalogique et les particules en arrière pour résoudre les problèmes de filtrage et de lissage. D'autres classes de méthodologies de filtrage de particules comprennent des modèles basés sur des arbres généalogiques, des modèles de particules de Markov en arrière, des modèles de particules de champ moyen adaptatifs, des modèles de particules de type îlot et des méthodologies de Monte Carlo à chaîne de Markov de particules.

Le problème du filtrage

Objectif

L'objectif d'un filtre particulaire est d'estimer la densité a posteriori des variables d'état compte tenu des variables d'observation. Le filtre à particules est conçu pour un modèle de Markov caché , où le système se compose à la fois de variables cachées et observables. Les variables observables (processus d'observation) sont liées aux variables cachées (processus d'état) par une forme fonctionnelle connue. De même le système dynamique décrivant l'évolution des variables d'état est également connu de manière probabiliste.

Un filtre à particules générique estime la distribution postérieure des états cachés en utilisant le processus de mesure d'observation. Considérons un espace d'état montré dans le diagramme ci-dessous.

${\displaystyle {\begin{array}{cccccccccc}X_{0}&\à &X_{1}&\à &X_{2}&\à &X_{3}&\à &\cdots &{\text{signal} }\\\flèche vers le bas &&\flèche vers le bas &&\flèche vers le bas &&\flèche vers le bas &&\cdots &\\Y_{0}&&Y_{1}&&Y_{2}&&Y_{3}&&\cdots &{\text{observation}}\end{ déployer}}}$

Le problème du filtrage est d'estimer séquentiellement les valeurs des états cachés , étant donné les valeurs du processus d'observation à tout pas de temps k . ${\displaystyle X_{k}}$${\displaystyle Y_{0},\cdots ,Y_{k},}$

Toutes les estimations bayésiennes de découlent de la densité postérieure . La méthodologie du filtre particulaire fournit une approximation de ces probabilités conditionnelles en utilisant la mesure empirique associée à un algorithme particulaire de type génétique. En revanche, la chaîne de Markov Monte Carlo ou l' approche d' échantillonnage par importance modéliseraient le postérieur complet . ${\displaystyle X_{k}}$ ${\style d'affichage p(x_{k}|y_{0},y_{1},...,y_{k})}$${\style d'affichage p(x_{0},x_{1},...,x_{k}|y_{0},y_{1},...,y_{k})}$

Le modèle Signal-Observation

Les méthodes particulaires supposent souvent et les observations peuvent être modélisées sous cette forme : ${\displaystyle X_{k}}$${\displaystyle Y_{k}}$

• ${\displaystyle X_{0},X_{1},\cdots }$est un processus de Markov sur (pour certains ) qui évolue en fonction de la densité de probabilité de transition . Ce modèle est aussi souvent écrit de manière synthétique comme ${\displaystyle \mathbb {R} ^{d_{x}}}$${\displaystyle d_{x}\geqslant 1}$${\style d'affichage p(x_{k}|x_{k-1})}$

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

avec une densité de probabilité initiale .${\style d'affichage p(x_{0})}$

• Les observations prennent des valeurs dans un espace d'état sur (pour certains ) et sont conditionnellement indépendantes à condition qu'elles soient connues. En d'autres termes, chacun ne dépend que de . De plus, nous supposons que les distributions conditionnelles pour donné sont absolument continues, et de manière synthétique nous avons ${\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}}$${\style d'affichage X_{k}=x_{k}}$

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

Un exemple de système avec ces propriétés est :

${\style d'affichage X_{k}=g(X_{k-1})+W_{k-1}}$

${\style d'affichage Y_{k}=h(X_{k})+V_{k}}$

où les deux et sont des séquences mutuellement indépendantes avec des fonctions de densité de probabilité connues et g et h sont des fonctions connues. Ces deux équations peuvent être considérées comme des équations d' espace d'état et ressemblent aux équations d'espace d'état pour le filtre de Kalman. Si les fonctions g et h dans l'exemple ci-dessus sont linéaires, et si les deux et sont gaussiennes , le filtre de Kalman trouve la distribution de filtrage bayésienne exacte. Sinon, les méthodes basées sur le filtre de Kalman sont une approximation du premier ordre ( EKF ) ou une approximation du deuxième ordre ( UKF en général, mais si la distribution de probabilité est gaussienne, une approximation du troisième ordre est possible). ${\displaystyle W_{k}}$${\displaystyle V_{k}}$${\displaystyle W_{k}}$${\displaystyle V_{k}}$

L'hypothèse selon laquelle la distribution initiale et les transitions de la chaîne de Markov sont absolument continues par rapport à la mesure de Lebesgue peut être relâchée. Pour concevoir un filtre à particules, nous devons simplement supposer que nous pouvons échantillonner les transitions de la chaîne de Markov et calculer la fonction de vraisemblance (voir par exemple la description de la mutation de sélection génétique du filtre à particules donnée ci-dessous). Les hypothèses absolument continues sur les transitions de Markov ne sont utilisées que pour dériver de manière informelle (et plutôt abusive) différentes formules entre distributions postérieures en utilisant la règle de Bayes pour les densités conditionnelles. ${\displaystyle X_{k-1}\to X_{k}}$${\style d'affichage X_{k},}$${\displaystyle x_{k}\mapsto p(y_{k}|x_{k})}$${\displaystyle X_{k}}$

Modèles de calcul bayésiens approximatifs

Dans certains problèmes, la distribution conditionnelle des observations compte tenu des états aléatoires du signal peut ne pas avoir de densité ou peut être impossible ou trop complexe à calculer. Dans cette situation, nous devons recourir à un niveau d'approximation supplémentaire. Une stratégie consiste à remplacer le signal par la chaîne de Markov et à introduire une observation virtuelle de la forme ${\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{pour certains paramètres}}\quad \epsilon \in [0,1]}$

pour une séquence de séquences indépendantes avec des fonctions de densité de probabilité connues . L'idée centrale est d'observer 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}\correct)}$

Le filtre particulaire associé au processus de Markov étant donné les observations partielles est défini en termes de particules évoluant en avec une fonction de vraisemblance donnée avec une notation manifestement abusive par . Ces techniques probabilistes sont étroitement liées au calcul bayésien approximatif (ABC). Dans le cadre des filtres particulaires, ces techniques de filtrage particulaire ABC ont été introduites en 1998 par P. Del Moral, J. Jacod et P. Protter. Ils ont été développés par P. Del Moral, A. Doucet et A. Jasra. ${\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})}$

L'équation de filtrage non linéaire

La règle de Bayes pour la probabilité conditionnelle donne :

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

où

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

Les filtres à particules sont également une approximation, mais avec suffisamment de particules, ils peuvent être beaucoup plus précis. L'équation de filtrage non linéaire est donnée par la récursivité

${\displaystyle {\begin{aligned}p(x_{k}|y_{0},\cdots ,y_{k-1})&{\stackrel {\text{updating}}{\longrightarrow }}p(x_ {k}|y_{0},\cdots ,y_{k})={\frac {p(y_{k}|x_{k})p(x_{k}|y_{0},\cdots ,y_ {k-1})}{\int p(y_{k}|x'_{k})p(x'_{k}|y_{0},\cdots ,y_{k-1})dx' _{k}}}\\&{\stackrel {\text{prediction}}{\longrightarrow }}p(x_{k+1}|y_{0},\cdots ,y_{k})=\int p (x_{k+1}|x_{k})p(x_{k}|y_{0},\cdots ,y_{k})dx_{k}\end{aligned}}}$

(Équation 1)

avec la convention pour k = 0. Le problème du filtrage non linéaire consiste à calculer séquentiellement ces distributions conditionnelles. ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{k-1})=p(x_{0})}$

Formulation Feynman-Kac

On fixe un horizon temporel n et une séquence d'observations , et pour chaque k = 0, ..., n on pose : ${\displaystyle Y_{0}=y_{0},\cdots ,Y_{n}=y_{n}}$

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

Dans cette notation, pour toute fonction bornée F sur l'ensemble des trajectoires de depuis l'origine k = 0 jusqu'au temps k = n , on a la formule 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{aligné}}}$

Ces modèles d'intégration de chemin Feynman-Kac surviennent dans une variété de disciplines scientifiques, notamment en physique numérique, en biologie, en théorie de l'information et en informatique. Leurs interprétations dépendent du domaine d'application. Par exemple, si nous choisissons la fonction indicatrice d'un sous-ensemble de l'espace d'état, elles représentent la distribution conditionnelle d'une chaîne de Markov étant donné qu'elle reste dans un tube donné ; c'est-à-dire que nous avons : ${\style d'affichage 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)}}}$

et

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

dès que la constante de normalisation est strictement positive.

Filtres à particules

Un algorithme de particules de type génétique

Initialement, nous commençons avec N variables aléatoires indépendantes avec une densité de probabilité commune . Les transitions sélection-mutation des algorithmes génétiques ${\displaystyle \left(\xi _{0}^{i}\right)_{1\leqslant i\leqslant N}}$${\style d'affichage 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 }}$

imiter/approximer les transitions de mise à jour-prédiction de l'évolution optimale du filtre ( Eq. 1 ) :

• Au cours de la transition de mise à jour de la sélection, nous échantillonnons N variables aléatoires indépendantes (conditionnellement) avec une distribution (conditionnelle) commune${\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})}$

où représente la mesure de Dirac à un état donné a. ${\displaystyle \delta _{a}}$

• Au cours de la transition mutation-prédiction, à partir de chaque particule sélectionnée, nous échantillonnons indépendamment une transition${\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.}$

Dans les formules affichées ci-dessus représente la fonction de vraisemblance évaluée à , et représente la densité conditionnelle évaluée à . ${\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})}$${\style d'affichage p(x_{k+1}|x_{k})}$${\displaystyle x_{k}={\widehat {\xi }}_{k}^{i}}$

A chaque instant k , on a les approximations particulaires

${\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}^{ je}}(dx_{k})}$

et

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

Dans la communauté des algorithmes génétiques et de l' informatique évolutive , la chaîne de Markov de sélection de mutation décrite ci-dessus est souvent appelée algorithme génétique avec sélection proportionnelle. Plusieurs variantes de branchement, y compris avec des tailles de population aléatoires ont également été proposées dans les articles.

Principes de Monte-Carlo

Les méthodes de particules, comme toutes les approches basées sur l'échantillonnage (par exemple, la chaîne de Markov Monte Carlo), génèrent un ensemble d'échantillons qui se rapprochent de la densité de filtrage

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

Par exemple, nous pouvons avoir N échantillons de la distribution postérieure approximative de , où les échantillons sont étiquetés avec des exposants comme ${\displaystyle X_{k}}$

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

Ensuite, les attentes par rapport à la distribution de filtrage sont approximées par

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

(Équation 2)

avec

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

où représente la mesure de Dirac à un état donné a. La fonction f , de la manière habituelle pour Monte Carlo, peut donner tous les moments etc. de la distribution jusqu'à une certaine erreur d'approximation. Lorsque l'équation d'approximation ( Eq. 2 ) est satisfaite pour toute fonction bornée f, nous écrivons ${\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})}$

Les filtres à particules peuvent être interprétés comme un algorithme de particules de type génétique évoluant avec des transitions de mutation et de sélection. Nous pouvons garder une trace des lignées 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)}$

des particules . Les états aléatoires , avec les indices inférieurs l=0,...,k, représentent l'ancêtre de l'individu au niveau l=0,...,k. Dans cette situation, on a la formule d'approximation ${\displaystyle i=1,\cdots ,N}$${\displaystyle {\widehat {\xi }}_{l,k}^{i}}$${\displaystyle {\widehat {\xi }}_{k,k}^{i}={\widehat {\xi }}_{k}^{i}}$

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

(Équation 3)

avec la mesure empirique

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

Ici, F représente toute fonction fondée sur l'espace de chemin du signal. Sous une forme plus synthétique ( Eq. 3 ) équivaut à

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

Les filtres à particules peuvent être interprétés de différentes manières. Du point de vue probabiliste, elles coïncident avec une interprétation particulaire à champ moyen de l'équation de filtrage non linéaire. Les transitions de mise à jour-prédiction de l'évolution optimale du filtre peuvent également être interprétées comme les transitions de sélection-mutation de type génétique classiques des individus. La technique de rééchantillonnage d'importance séquentielle fournit une autre interprétation des transitions de filtrage couplant l'échantillonnage d'importance avec l'étape de rééchantillonnage bootstrap. Enfin et surtout, les filtres à particules peuvent être considérés comme une méthodologie d'acceptation-rejet dotée d'un mécanisme de recyclage.

Simulation de particules de champ moyen

Le principe général des probabilités

L'évolution du filtrage non linéaire peut être interprétée comme un système dynamique dans l'ensemble de mesures de probabilité de la forme suivante où représente un mappage de l'ensemble de distribution de probabilité vers lui-même. Par exemple, l'évolution du prédicteur optimal en une étape${\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}}$

satisfait une évolution non linéaire à partir de la distribution de probabilité . L'un des moyens les plus simples d'approximer ces mesures de probabilité est de commencer avec N variables aléatoires indépendantes avec une distribution de probabilité commune . Supposons que nous ayons défini une séquence de N variables aléatoires telle 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})}$

À l'étape suivante, nous échantillonnons N variables aléatoires (conditionnellement) indépendantes de common law . ${\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}}$

Une interprétation particulaire de l'équation de filtrage

Nous illustrons ce principe de particules de champ moyen dans le contexte de l'évolution des prédicteurs optimaux à une étape

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

(Équation 4)

Pour k = 0 nous utilisons la convention . ${\displaystyle p(x_{0}|y_{0},\cdots ,y_{-1}):=p(x_{0})}$

Par la loi des grands nombres, on a

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

dans le sens où

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

pour toute fonction bornée . Nous supposons en outre que nous avons construit une séquence de particules à un certain rang k tel que ${\style d'affichage 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 ce sens que pour toute fonction bornée on a ${\style d'affichage 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}}$

Dans cette situation, en remplaçant par la mesure empirique dans l'équation d'évolution du filtre optimal à une étape indiqué dans ( Eq. 4 ), nous trouvons 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}) }}}$

Notez que le côté droit de la formule ci-dessus est un mélange de probabilités pondérées

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

où représente la densité évaluée à , et représente la densité évaluée à pour${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\style d'affichage p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\style d'affichage p(x_{k+1}|\xi _{k}^{i})}$${\style d'affichage p(x_{k+1}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$${\displaystyle i=1,\cdots ,N.}$

Ensuite, nous échantillonnons N variables aléatoires indépendantes avec une densité de probabilité commune de sorte 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}}$

En itérant cette procédure, nous concevons une chaîne de Markov telle 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}}$

Notez que le filtre optimal est approximé à chaque pas de temps k en utilisant les formules 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 terminologie "approximation de champ moyen" vient du fait que l'on remplace à chaque pas de temps la mesure de probabilité par l'approximation empirique . L'approximation particulaire en champ moyen du problème de filtrage est loin d'être unique. Plusieurs stratégies sont développées dans les livres. ${\displaystyle p(dx_{k}|y_{0},\cdots ,y_{k-1})}$${\displaystyle {\widehat {p}}(dx_{k}|y_{0},\cdots ,y_{k-1})}$

Quelques résultats de convergence

L'analyse de la convergence des filtres à particules a débuté en 1996 et en 2000 dans le livre et la série d'articles. Des développements plus récents peuvent être trouvés dans les livres, Lorsque l'équation de filtrage est stable (au sens où elle corrige toute condition initiale erronée), le biais et la variance des estimations de particule particule

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

sont contrôlés par les estimations uniformes non asymptotiques

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

pour toute fonction f bornée par 1, et pour certaines constantes finies De plus, pour toute : ${\style d'affichage c_{1},c_{2}.}$${\style d'affichage 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} }$

pour certaines constantes finies liées au biais asymptotique et à la variance de l'estimation des particules, et pour une constante finie c . Les mêmes résultats sont satisfaits si nous remplaçons le prédicteur optimal à une étape par l'approximation optimale du filtre. ${\style d'affichage c_{1},c_{2}}$

Arbres généalogiques et propriétés d'impartialité

Lissage des particules basé sur l'arbre généalogique

Remonter dans le temps les lignes 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}\right) }$

des individus et à chaque pas de temps k , on a aussi les approximations particulaires ${\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}}}$

Ces approximations empiriques sont équivalentes aux approximations intégrales de particules

${\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\gauche(\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\gauche(\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{aligné}}}$

pour toute fonction bornée F sur les trajectoires aléatoires du signal. Comme le montre l'évolution de l'arbre généalogique coïncide avec une interprétation particulaire à champ moyen des équations d'évolution associées aux densités postérieures des trajectoires des signaux. Pour plus de détails sur ces modèles d'espace de chemin, nous nous référons aux livres.

Estimations de particules non biaisées des fonctions de vraisemblance

Nous utilisons la formule du produit

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

avec

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

et les conventions et pour k = 0. Remplacement par l' approximation empirique${\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})}$

dans la formule affichée ci-dessus, nous concevons l'approximation de particules impartiale suivante de la fonction de vraisemblance

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

avec

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

où représente la densité évaluée à . La conception de cette estimation de particules et la propriété d'impartialité ont été prouvées en 1996 dans l'article. Des estimations de variance affinées peuvent être trouvées dans et. ${\displaystyle p(y_{k}|\xi _{k}^{i})}$${\style d'affichage p(y_{k}|x_{k})}$${\displaystyle x_{k}=\xi _{k}^{i}}$

Lisseurs de particules en arrière

En utilisant la règle de Bayes, on a la formule

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

Remarquerez 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{aligné}}}$

Cela implique 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}}}}$

Remplacement des prédicteurs optimaux en une étape par les mesures empiriques des particules${\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)}$

on trouve 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})}{\somme _{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}}}$

Nous concluons que

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

avec l'approximation particulaire en arrière

${\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 mesure de probabilité

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

est la probabilité que les chemins aléatoires d'une chaîne de Markov remontant dans le temps du temps k=n au temps k=0, et évoluant à chaque pas de temps k dans l'espace d'état associé à la population de particules${\displaystyle \left(\mathbb {X} _{k,n}^{\flat }\right)_{0\leqslant k\leqslant n}}$${\displaystyle \xi _{k}^{i},i=1,\cdots ,N.}$

• Initialement (au temps k=n) la chaîne choisit aléatoirement un état avec la distribution${\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})}$

• Du temps k au temps (k-1), la chaîne commençant à un certain état pour un certain temps au temps k se déplace au temps (k-1) vers un état aléatoire choisi avec la probabilité pondérée discrète${\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} )}$

Dans la formule affichée ci-dessus, représente la distribution conditionnelle évaluée à . Dans la même veine, et représentent les densités conditionnelles et évaluées à et Ces modèles permettent de réduire l'intégration par rapport aux densités en termes d'opérations matricielles par rapport aux transitions de Markov de la chaîne décrite ci-dessus. Par exemple, pour toute fonction, nous avons les estimations de particules ${\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})}$${\style d'affichage p(\xi _{k}^{i}|\xi _{k-1}^{j})}$${\style d'affichage p(y_{k-1}|x_{k-1})}$${\style d'affichage 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}}}$

où

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

Cela montre aussi que si

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

ensuite

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

Quelques résultats de convergence

On supposera que l'équation de filtrage est stable, au sens où elle corrige toute condition initiale erronée.

Dans cette situation, les approximations particulaires des fonctions de vraisemblance ne sont pas biaisées et la variance relative est contrôlée par

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

pour une constante finie c . De plus, pour tout : ${\style d'affichage 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}}$

pour certaines constantes finies liées au biais asymptotique et à la variance de l'estimation des particules, et pour une constante finie c . ${\style d'affichage c_{1},c_{2}}$

Le biais et la variance des estimations de particules particulaires basées sur les lignées ancestrales des arbres généalogiques

${\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}^{chemin }(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}}}$

sont contrôlés par les estimations uniformes non asymptotiques

${\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}^{chemin}(F)-I_{k}^{chemin}( F)\right]^{2}\right)\leqslant {\frac {c_{2}k}{N}},}$

pour toute fonction F bornée par 1, et pour certaines constantes finies De plus, pour toute : ${\style d'affichage c_{1},c_{2}.}$${\style d'affichage x\geqslant 0}$

${\displaystyle \mathbf {P} \left(\left|{\widehat {I}}_{k}^{chemin}(F)-I_{k}^{chemin}(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}^{chemin}(F)-I_{k}^{chemin}(F)\right|\leqslant c{\sqrt {\frac {xn\log(n)}{ N}}}\right)>1-e^{-x}}$

pour certaines constantes finies liées au biais asymptotique et à la variance de l'estimation des particules, et pour une constante finie c . Le même type d'estimations de biais et de variance est valable pour les lisseurs de particules en arrière. Pour les fonctionnelles additives de la forme ${\style d'affichage 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})}$

avec

${\displaystyle I_{n}^{chemin}({\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}))}$

avec des fonctions bornées par 1, on a ${\displaystyle f_{k}}$

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

et

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

pour certaines constantes finies Des estimations plus raffinées incluant une probabilité d'erreurs exponentiellement faible sont développées dans. ${\style d'affichage c_{1},c_{2},c_{3}.}$

Rééchantillonnage d'importance séquentielle (SIR)

Filtre Monte Carlo et filtre bootstrap

Le rééchantillonnage d' importance séquentielle (SIR) , le filtrage Monte Carlo (Kitagawa 1993) et l'algorithme de filtrage bootstrap (Gordon et al. 1993) sont également des algorithmes de filtrage couramment appliqués, qui approximent la densité de probabilité de filtrage par un ensemble pondéré de N échantillons. ${\displaystyle p(x_{k}|y_{0},\cdots ,y_{k})}$

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

Les poids d'importance sont des approximations des probabilités (ou densités) postérieures relatives des échantillons telles que ${\displaystyle w_{k}^{(i)}}$

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

L'échantillonnage d'importance séquentielle (SIS) est une version séquentielle (c'est-à-dire récursive) de l' échantillonnage d'importance . Comme dans l'échantillonnage d'importance, l'espérance d'une fonction f peut être approchée comme une moyenne pondérée

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

Pour un ensemble fini d'échantillons, la performance de l'algorithme dépend du choix de la distribution de la proposition

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

La distribution " optimale" de la proposition est donnée comme distribution cible

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

Ce choix particulier de proposition de transition a été proposé par P. Del Moral en 1996 et 1998. Lorsqu'il est difficile d'échantillonner des transitions selon la distribution, une stratégie naturelle consiste à utiliser l'approximation particulaire suivante ${\style d'affichage 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}))}{\somme _{j=1}^{N}p(y_{k}|X_{k}^{j}(x_{k-1}))}}}\delta _{X_{k}^{i}(x_{k-1})}(dx_{k})\end{aligned}}}$

avec l'approximation empirique

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

associé à N (ou à tout autre grand nombre d'échantillons) échantillons aléatoires indépendants avec la distribution conditionnelle de l'état aléatoire donnée . La cohérence du filtre à particules résultant de cette approximation et d'autres extensions sont développées dans. Dans l'affichage ci-dessus, la mesure de Dirac à un état donné 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}}$

Cependant, la distribution de probabilité a priori de transition est souvent utilisée comme fonction d'importance, car il est plus facile de dessiner des particules (ou des échantillons) et d'effectuer des calculs de poids d'importance ultérieurs :

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

Les filtres de rééchantillonnage d'importance séquentielle (SIR) avec une distribution de probabilité a priori de transition comme fonction d'importance sont communément appelés filtre d'amorçage et algorithme de condensation .

Le rééchantillonnage est utilisé pour éviter le problème de dégénérescence de l'algorithme, c'est-à-dire éviter la situation où tous les poids d'importance sauf un sont proches de zéro. Les performances de l'algorithme peuvent également être affectées par le bon choix de la méthode de rééchantillonnage. L' échantillonnage stratifié proposé par Kitagawa (1993) est optimal en termes de variance.

Une seule étape de rééchantillonnage d'importance séquentielle est la suivante :

1) Pour tirer des échantillons de la distribution de la proposition${\displaystyle i=1,\cdots ,N}$

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

2) Pour mettre à jour les poids d'importance jusqu'à une constante de normalisation : ${\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})}}.}$

Notez que lorsque nous utilisons la distribution de probabilité a priori de transition comme fonction d'importance,

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

cela se simplifie comme suit :

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

3) Pour calculer les poids d'importance normalisés : ${\displaystyle i=1,\cdots ,N}$

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

4) Calculer une estimation du nombre effectif de particules comme

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

Ce critère reflète la variance des poids, d'autres critères peuvent être trouvés dans l'article, notamment leur analyse rigoureuse et leurs théorèmes limites centraux.

5) Si le nombre effectif de particules est inférieur à un seuil donné , alors effectuer un rééchantillonnage : ${\displaystyle {\hat {N}}_{\mathit {eff}}<N_{thr}}$

a) Dessinez N particules de l'ensemble de particules actuel avec des probabilités proportionnelles à leurs poids. Remplacez le jeu de particules actuel par ce nouveau.

b) Pour l' ensemble${\displaystyle i=1,\cdots ,N}$${\displaystyle w_{k}^{(i)}=1/N.}$

Le terme "Sampling Importance Resampling" est également parfois utilisé pour désigner les filtres SIR, mais le terme Importance Resampling est plus précis car le mot "resampling" implique que l'échantillonnage initial a déjà été effectué.

Échantillonnage d'importance séquentielle (SIS)

• Identique au rééchantillonnage d'importance séquentielle, mais sans l'étape de rééchantillonnage.

Algorithme de "version directe"

L'algorithme de "version directe" est assez simple (comparé à d'autres algorithmes de filtrage de particules) et il utilise la composition et le rejet. Pour générer un seul échantillon x en k à partir de : ${\style d'affichage p_{x_{k}|y_{1:k}}(x|y_{1:k})}$

1) Définir n=0 (cela comptera le nombre de particules générées jusqu'à présent)

2) Choisir uniformément un indice i dans la gamme${\style d'affichage \{1,...,N\}}$

3) Générer un test à partir de la distribution avec${\displaystyle {\hat {x}}}$${\style d'affichage p(x_{k}|x_{k-1})}$${\displaystyle x_{k-1}=x_{k-1|k-1}^{(i)}}$

4) Générer la probabilité d' utiliser d' où est la valeur mesurée${\displaystyle {\hat {y}}}$${\displaystyle {\hat {x}}}$${\displaystyle p(y_{k}|x_{k}),~{\mbox{with}}~x_{k}={\hat {x}}}$${\displaystyle y_{k}}$

5) Générer un autre u uniforme d' où${\style d'affichage [0,m_{k}]}$${\displaystyle m_{k}=\sup _{x_{k}}p(y_{k}|x_{k})}$

6) Comparez-vous et ${\displaystyle p\left({\hat {y}}\right)}$

6a) Si u est plus grand, recommencez à partir de l'étape 2

6b) Si u est plus petit, enregistrez sous et incrémentez n${\displaystyle {\hat {x}}}$${\displaystyle x_{k|k}^{(i)}}$

7) Si n == N alors quittez

Le but est de générer P "particules" en k en utilisant uniquement les particules de . Cela nécessite qu'une équation de Markov puisse être écrite (et calculée) pour générer un basé uniquement sur . Cet algorithme utilise la composition des particules P à partir de pour générer une particule en k et se répète (étapes 2 à 6) jusqu'à ce que les particules P soient générées en k . ${\style d'affichage k-1}$${\style d'affichage x_{k}}$${\style d'affichage x_{k-1}}$${\style d'affichage k-1}$

Cela peut être plus facilement visualisé si x est considéré comme un tableau à deux dimensions. Une dimension est k et les autres dimensions sont le nombre de particules. Par exemple, serait la i ^ème particule à et peut également être écrite (comme fait ci-dessus dans l'algorithme). L'étape 3 génère un potentiel basé sur une particule choisie au hasard ( ) à un moment donné et le rejette ou l'accepte à l'étape 6. En d'autres termes, les valeurs sont générées à l'aide du . ${\style d'affichage x(k,i)}$${\style d'affichage k}$${\displaystyle x_{k}^{(i)}}$ ${\style d'affichage x_{k}}$${\displaystyle x_{k-1}^{(i)}}$${\style d'affichage k-1}$${\style d'affichage x_{k}}$${\style d'affichage x_{k-1}}$

Autres filtres à particules

• Filtre à particules naturel exponentiel
• Filtre à particules auxiliaire
• Filtre à particules auxiliaire régularisé
• Filtre à particules gaussien
• Filtre à particules non parfumé
• Filtre à particules Gauss-Hermite
• Filtre de particules de référence de coût
• Filtre à particules hiérarchique/évolutif
• Filtre à particules Rao-Blackwellized
• Filtre à particules optimal basé sur l' échantillonnage par rejet
• Filtre à particules poussé
• Méthodologies de Feynman-Kac et des particules à champ moyen
• Particule Markov-Chain Monte-Carlo, voir par exemple algorithme pseudo-marginal de Metropolis–Hastings .

Voir également

• Méthodes de particules de champ moyen
• Algorithme génétique
• Filtre de l'Ensemble Kalman
• Filtrage généralisé
• Estimation de l'horizon mobile
• Estimation bayésienne récursive
• Localisation Monte-Carlo

Les références

Bibliographie

• Del Moral, Pierre (1996). "Filtrage non linéaire : solution de particules en interaction" (PDF) . Processus de Markov et champs associés . 2 (4) : 555-580.
• Del Moral, Pierre (2004). Formules de Feynman-Kac. Approximations de particules généalogiques et en interaction . Springer. p. 575. "Série : probabilités et applications"
• Del Moral, Pierre (2013). Simulation de champ moyen pour l'intégration Monte Carlo . Chapman & Hall/CRC Press. p. 626. "Monographies sur les statistiques et les probabilités appliquées"
• Cappe, O.; Moulines, E. ; Ryden, T. (2005). Inférence dans les modèles de Markov cachés . Springer.
• Liu, JS ; Chen, R. (1998). « Méthodes de Monte Carlo séquentielles pour les systèmes dynamiques » (PDF) . Journal de l'Association statistique américaine . 93 (443) : 1032-1044. doi : 10.1080/01621459.1998.10473765 .
• Liu, JS (2001). Stratégies de Monte Carlo en calcul scientifique . Springer.
• Kong, A.; Liu, JS ; Wong, WH (1994). « Les imputations séquentielles et les problèmes de données manquantes bayésiennes » (PDF) . Journal de l'Association statistique américaine . 89 (425) : 278-288. doi : 10.1080/01621459.1994.10476469 .
• Liu, JS ; Chen, R. (1995). « Déconvolution aveugle via des imputations séquentielles » (PDF) . Journal de l'Association statistique américaine . 90 (430) : 567-576. doi : 10.2307/2291068 . JSTOR  2291068 .
• Ristic, B.; Arulampalam, S.; Gordon, N. (2004). Au-delà du filtre de Kalman : filtres à particules pour les applications de suivi . Maison Artech.
• Doucet, A.; Johansen, AM (décembre 2008). "Un tutoriel sur le filtrage et le lissage des particules : quinze ans après" (PDF) . Rapport technique .
• Doucet, A.; Godsill, S.; Andrieu, C. (2000). « Sur les méthodes d'échantillonnage séquentiel Monte Carlo pour le filtrage bayésien ». Statistiques et informatique . 10 (3) : 197-208. doi : 10.1023/A:108935410038 . S2CID  16288401 .
• Arulampalam, MS; Maskell, S.; Gordon, N.; Clapp, T. (2002). « Un tutoriel sur les filtres à particules pour le suivi bayésien non linéaire/non gaussien en ligne ». Transactions IEEE sur le traitement du signal . 50 (2) : 174-188. Bibcode : 2002ITSP ... 50..174A . CiteSeerX  10.1.1.471.8617 . doi : 10.1109/78.978374 .
• Cappe, O.; Godsill, S.; Moulines, E. (2007). « Un aperçu des méthodes existantes et des avancées récentes dans le Monte Carlo séquentiel ». Actes de l'IEEE . 95 (5) : 899–924. doi : 10.1109/JPROC.2007.893250 . S2CID  3081664 .
• Kitagawa, G. (1996). « Filtre et lissage de Monte Carlo pour les modèles d'espace d'état non-linéaires non gaussiens ». Journal des statistiques informatiques et graphiques . 5 (1) : 1–25. doi : 10.2307/1390750 . JSTOR  1390750 .
• Kotecha, JH; Djuric, P. (2003). "Filtrage de particules gaussien". Transactions IEEE sur le traitement du signal . 51 (10).
• Haug, AJ (2005). "Un didacticiel sur l'estimation bayésienne et les techniques de suivi applicables aux processus non linéaires et non gaussiens" (PDF) . La MITRE Corporation, États-Unis, Tech. Rép., fév . Récupéré le 06-05-2008 .
• Pitt, MK ; Shephard, N. (1999). « Filtrage par simulation : filtres à particules auxiliaires » . Journal de l'Association statistique américaine . 94 (446) : 590-591. doi : 10.2307/2670179 . JSTOR  2670179 . Récupéré le 06-05-2008 .
• Gordon, New Jersey; Salmond, DJ ; Smith, AFM (1993). « Nouvelle approche de l'estimation de l'état bayésien non linéaire/non gaussien ». IEE Proceedings F - Radar et traitement du signal . 140 (2) : 107-113. doi : 10.1049/ip-f-2.1993.0015 .
• Chen, Z. (2003). « Filtrage bayésien : des filtres de Kalman aux filtres à particules, et au-delà ». CiteSeerX  10.1.1.107.7415 . Citer le journal nécessite |journal=( aide )
• Vaswani, N. ; Rathi, Y.; Yezzi, A.; Tannenbaum, A. (2007). "Suivi des objets déformants à l'aide du filtrage particulaire pour les contours géométriques actifs" . Transactions IEEE sur l'analyse des modèles et l'intelligence machine . 29 (8) : 1470-1475. doi : 10.1109/tpami.2007.1081 . PMC  3663080 . PMID  17568149 .

Liens externes