Filtre particulaire

Les filtres particulaires, aussi connus comme Méthodes de Monte-Carlo séquentielles, sont des techniques particulièrement élaborées d'estimation de modèles basées sur la simulation.



Catégories :

Algorithme numérique - Filtre - Statistiques

Page(s) en rapport avec ce sujet :

  • Les filtres bayésiens permettent de faire du suivi d'hypothèses multiples, ... un ensemble de particules. Le problème est par conséquent de générer un... On introduit pour cela une fonction d'importance π (x) telle que :... Un des avantages du filtre particulaire est qu'il se prête bien à la fusion de données pro-... (source : ensta)
  • le calcul de celle-ci par la mise en œuvre d'un filtre particulaire est présenté. Ce filtre approxime la densité d'importance... is used to approximate the optimal importance density.... au moyen de filtres particulaires qui permettent d'appro-... 1, consistent `a simuler Ns nouvelles particules `a partir... (source : documents.irevues.inist)
  • ... Idée - Le filtre particulaire est une approximation de Monte Carlo du filtre bayésien... Filtre particulaire avec loi d'importance optimale et redistribution (n=10)... En pratique, nécessite un assez grand nombre de particules..... contrairement aux filtres introduits auparavant.... (source : www-labsticc.univ-ubs)
Résultat d'un filtrage particulaire (courbe rouge) basé sur les données observées générées depuis la courbe bleue.

Les filtres particulaires, aussi connus comme Méthodes de Monte-Carlo séquentielles, sont des techniques particulièrement élaborées d'estimation de modèles basées sur la simulation.

Les filtres particulaires sont le plus souvent utilisés pour estimer des modèles Bayésiens et forment les méthodes'en-ligne'analogues aux Méthodes de Monte-Carlo par Chaînes de Markov qui elles sont des méthodes'hors-ligne' (donc a posteriori) et fréquemment identiques aux méthodes d'échantillonnage d'importance.

S'ils sont conçus correctement, les filtres particulaires peuvent être plus rapides que les Méthodes de Monte-Carlo par Chaînes de Markov. Ils forment fréquemment une alternative aux filtres de Kalman étendus avec l'avantage qu'avec suffisamment d'échantillons, ils approchent l'estimé Bayésien optimal. Ils peuvent par conséquent être rendus plus précis que les filtres de Kalman. Les approches peuvent aussi être combinées en utilisant un filtre de Kalman comme une proposition de distribution pour le filtre particulaire.

Objectif

Un filtre particulaire a pour but d'estimer la séquence de paramètres cachés, xk pour k = 0, 1, 2, 3, \dots en se basant uniquement sur les données observées yk pour k = 0, 1, 2, 3, \dots. L'ensemble des paramètres estimés bayésiens de xk viennent de la distribution a posteriori, mais plutôt que d'utiliser les probabilités jointes a posteriori  p(x_0, x_1, \dots, x_k  | y_0, y_1, \dots, y_k), qui résulteraient d'une MCMC usuelle ou d'un échantillonnage d'importance, les méthodes particulaires estiment la distribution de filtrage p(x_k|y_0,y_1,\dots,y_k).

Modélisation

Les filtres particulaires font l'hypothèse que les états xk et les observations yk peuvent être modélisées sous la forme suivante :

Un exemple de ce scénario est \{\begin{matrix} x_k=f(x_{k-1}) + v_k \\ y_k = h(x_k) + w_k\end{matrix}

où à la fois vk et wk sont des séquences mutuellement indépendantes et distribuées comme une copie conforme avec des fonctions de densité de probabilité connues et où f () et h () sont des fonctions connues. Ces deux équations peuvent être vues comme des équations de l'espace d'état et ressemblent à celles du filtre de Kalman.

Si les fonctions f(\cdot) et h(\cdot) étaient linéaires, et si à la fois vk et wk étaient des gaussiennes, alors le filtre de Kalman trouve la distribution de filtrage bayésien exacte. Dans le cas opposé, les méthodes à base de filtre de Kalman donnent une estimation de premier ordre. Les filtres particulaires donnent aussi des approximations, mais avec suffisamment de particules, les résultats peuvent être toujours plus précis.

Approximation de Monte-Carlo

Les méthodes à particules, comme l'ensemble des méthodes à base d'échantillonnages (telles que les MCMC), génèrent un ensemble d'échantillons qui approximent la distribution de filtrage p(x_k|y_0,\dots,y_k). Ainsi, avec P échantillons, les valeurs espérées vis-à-vis de la distribution de filtrage sont approximées par : \int f(x_k)p(x_k|y_0,\dots,y_k)dx_k\approx\frac1P\sum_{L=1}ˆPf(x_kˆ{(L)})x_kˆ{(L)} est la (L) -ième particule à l'instant k; et f(\cdot), de la façon habituelle des méthodes Monte-Carlo, peut donner l'ensemble des données de la distribution (moments, etc. ) jusqu'à un certain degré d'approximation.

En général, l'algorithme est répété itérativement pour un nombre donné de valeurs k (que nous noterons N).

Initialiser xk = 0 | k = 0 pour l'ensemble des particules apporte une position de départ pour générer x1, qui est parfois utilisé pour générer x2, qui est parfois utilisé pour générer x3, et ainsi de suite jusqu'à k = N.

Une fois ceci effectué, la moyenne des xk sur l'ensemble des particules (ou \frac{1}{P}\sum_{L=1}ˆP x_kˆ{(L)}) est approximativement la véritable valeur de xk.

Echantillonnage avec rééchantillonnage par importance (SIR)

L'échantillonnage avec rééchantillonnage par importance (Sampling Importance Resampling ou SIR) est un algorithme de filtrage utilisé particulièrement fréquemment. Il approxime la distribution de filtrage p(x_k|y_0,\ldots,y_k) par un ensemble de particules pondérées : \{(wˆ{(L)}_k,xˆ{(L)}_k)∼:∼L=1,\ldots,P\}.

Les poids d'importance wˆ{(L)}_k sont des approximations des probabilités (ou des densités) a posteriori relatives des particules telles que \sum_{L=1}ˆP wˆ{(L)}_k = 1.

L'algorithme SIR est une version récursive de l'échantillonnage par importance. Comme en échantillonnage par importance, l'espérée de la fonction f(\cdot) peut être approximé comme une moyenne pondérée : 
\int f(x_k) p(x_k|y_0,\dots,y_k) dx_k \approx
\sum_{L=1}ˆP wˆ{(L)} f(x_kˆ{(L)}).

La performance de l'algorithme est dépendante du choix des distributions d'importances : π (xk | x0 :k − 1, y0 :k) .

La distribution d'importance optimale est donnée comme : π (xk | x0 :k − 1, y0 :k) = p (xk | xk − 1, yk).

Cependant, la probabilité de transition est fréquemment utilisée comme fonction d'importance, comme elle est plus aisée de calculer, et cela simplifie aussi les calculs des poids d'importance subséquents : π (xk | x0 :k − 1, y0 :k) = p (xk | xk − 1).

Les filtres à rééchantillonnage par importance (SIR) avec des probabilités de transitions comme fonction d'importance sont connues couramment comme filtres à amorçage (bootstrap filters) ou algorithme de condensation.

Le rééchantillonnage permet d'éviter le problème de la dégénérescence de l'algorithme. On évite ainsi les situations où l'ensemble des poids d'importance sauf un sont proches de zéro. La performance de l'algorithme peut aussi être affectée par le choix de la méthode de rééchantillonnage appropriée. Le rééchantillonnage stratifié proposé par Kitagawa (1996) est optimal en termes de variance.

Un seul pas de rééchantillonnage d'importance séquentiel se déroule de la façon suivante :

  1. Pour L=1, \ldots, P, on tire les échantillons des distributions d'importances : xˆ{(L)}_k \sim \pi(x_k|xˆ{(L)}_{0:k-1},y_{0:k})
  2. Pour L=1, \ldots, P, on évalue les poids d'importance avec une constante de normalisation : 
\hat{w}ˆ{(L)}_k = wˆ{(L)}_{k-1}
\frac{p(y_k|xˆ{(L)}_k) p(xˆ{(L)}_k|xˆ{(L)}_{k-1})}
{\pi(x_kˆ{(L)}|xˆ{(L)}_{0:k-1},y_{0:k})}.
  3. Pour L=1, \ldots, P on calcule les poids d'importance normalisés : 
wˆ{(L)}_k = \frac{\hat{w}ˆ{(L)}_k}{\sum_{J=1}ˆP \hat{w}ˆ{(J)}_k}
  4. On calcule une estimation du nombre effectif de particules comme 
\hat{N}_\mathit{eff} = \frac{1}{\sum_{L=1}ˆP\left(wˆ{(L)}_k\right)ˆ2}
  5. Si le nombre effectif de particules est plus petit qu'un seuil donné \hat{N}_\mathit{eff} < N_{thr}, alors on effectue le rééchantillonnage :
    1. Tirer P particules de la totalité de particules courant avec les probabilités proportionnelles à leur poids puis remplacer la totalité des particules courantes avec ce nouvel ensemble.
    2. Pour L=1, \ldots, P la totalité wˆ{(L)}_k = 1/P.

Le terme Rééchantillonnage d'importance séquentiel (Sequential Importance Resampling) est aussi utilisé quelquefois pour se référer aux filtres SIR.

Echantillonnage séquentiel par importance (SIS)

L'Echantillonnage séquentiel par importance (ou SIS pour Sequential Importance Sampling) est comparable à l'Echantillonnage avec rééchantillonage par importance (SIR) mais sans l'étape de rééchantillonnage.

Version directe de l'algorithme

La version directe de l'algorithme est assez simple en comparaison des autres algorithmes de filtrage particulaire et utilise la composition et le rejet. Pour générer un simple échantillon x à k de p_{x_k|y_{1:k}}(x|y_{1:k}) :

(1) Fixer p=1
(2) Générer uniformément L depuis {1, ..., P}
(3) Générer un test \hat{x} depuis sa distribution p_{x_k|x_{k-1}}(x|x_{k-1|k-1}ˆ{(L)})
(4) Générer les probabilités de \hat{y} en utilisant \hat{x} depuis p_{y|x}(y_k|\hat{x})yk est la valeur mesurée
(5) Générer une autre uniformément u depuis [0, mk]
(6) Comparer u et \hat{y}
(a) Si u est plus grand alors répéter depuis l'étape (2)
(b) Si u est plus petite alors sauver \hat{x} comme xk | k (p) et incrémenter p
(c) Si p > P alors arrêter

L'objectif est de générer P particules au pas k en n'utilisant uniquement que les particules du pas k − 1. Cela requiert qu'une équation markovienne puisse être écrite (et calculée) pour générer un xk en se basant uniquement sur xk − 1. Cet algorithme utilise la composition de P particules depuis k − 1 pour générer à k.

Cela peut être plus aisément visualisé si x est vu comme un tableau à deux dimensions. Une dimension est k et l'autre dimension correspond au nombre de particules. A titre d'exemple, x (k, L) serait la Lème particule à l'étape k et peut être par conséquent écrite x_kˆ{(L)} (comme effectué plus haut dans l'algorithme).

L'étape (3) génère un potentiel xk basé sur une particule choisie aléatoirement (x_{k-1}ˆ{(L)}) a temps k − 1 et rejette ou accepte cette particule à l'étape (6). En d'autres termes, les xk valeurs sont générées en utilisant les xk − 1 générées auparavant.

Voir aussi

Références

Liens externes

Recherche sur Amazon (livres) :



Ce texte est issu de l'encyclopédie Wikipedia. Vous pouvez consulter sa version originale dans cette encyclopédie à l'adresse http://fr.wikipedia.org/wiki/Filtre_particulaire.
Voir la liste des contributeurs.
La version présentée ici à été extraite depuis cette source le 07/04/2010.
Ce texte est disponible sous les termes de la licence de documentation libre GNU (GFDL).
La liste des définitions proposées en tête de page est une sélection parmi les résultats obtenus à l'aide de la commande "define:" de Google.
Cette page fait partie du projet Wikibis.
Accueil Recherche Aller au contenuDébut page
ContactContact ImprimerImprimer liens d'évitement et raccourcis clavierAccessibilité
Aller au menu