Filtre particulaire (statistique)

Un article de Wikipédia, l'encyclopédie libre.

Cet article est en cours de traduction depuis « Particle filter » .

^{→ Pour plus d'informations ou participer, vous pouvez consulter la page de discussion.}

Étape 4/5 : En cours de Relecture.
^{• Si vous voyez des erreurs de traduction, vous pouvez modifier l'article ou les rapporter sur la page de discussion.}

Avertissement : le bandeau unique {{Projet:Traduction/Filtre particulaire (statistique)}} remplace désormais avantageusement tous ceux que vous utilisez actuellement. Veuillez consultez la page Projet:Traduction

Pour les articles homonymes, voir Particule.

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 (SMC), sont des techniques sophistiquées d'estimation de modèles basées sur la simulation.

Les filtres particulaires sont généralement utilisés pour estimer des modèles Bayésiens et constituent les méthodes 'en-ligne' analogues aux Méthodes de Monte-Carlo par Chaînes de Markov (MCMC) qui elles sont des méthodes 'hors-ligne' (donc a posteriori) et souvent similaires aux méthodes d'échantillonnage d'importance.

S'ils sont conçus correctement, les filtres particulaires peuvent être plus rapides que les MCMC. Ils constituent souvent une alternative aux filtres de Kalman étendus (EKF) avec l'avantage qu'avec suffisamment d'échantillons, ils approchent l'estimé Bayésien optimal. Ils peuvent donc être rendus plus précis que les EKF. Les approches peuvent aussi être combinées en utilisant un filtre de Kalman comme une proposition de distribution pour le filtre particulaire.

Sommaire

1 Objectif
2 Modélisation
3 Approximation de Monte-Carlo
4 Echantillonnage avec rééchantillonnage par importance (SIR)
5 Echantillonnage séquentiel par importance (SIS)
6 Version directe de l'algorithme
7 Voir aussi
8 References
9 Liens externes

[modifier] Objectif

Un filtre particulaire a pour but d'estimer la séquence de paramètres cachés, $x k$ pour $k = 0, 1, 2, 3, \cdots$ , en se basant seulement sur les données observées $y k$ pour $k = 0, 1, 2, 3, \cdots$ . Tous les paramètres estimés bayésiens de $x k$ viennent de la distribution a posteriori, mais plutôt que d'utiliser les probabilité 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)$ .

[modifier] Modélisation

Les filtres particulaires font l'hypothèse que les paramètres $x k$ et les observations $y k$ peuvent être modélisées sous la forme suivante :

La suite des paramètres $x_0, x_1, \cdots$ forment une chaîne de Markov de premier ordre, telle que $x_k | x_{k-1} \sim p_{x_k | x_{k-1}}(x | x_{k-1})$ et avec une distribution initiale $p (x 0)$ .
Les observations $y_0, y_1, \cdots$ sont indépendantes conditionnellement sous réserve que les $x_0, x_1, \cdots$ soient connus. En d'autres termes, chaque observation $y k$ ne dépend que du paramètre $x k$

y k | x k ˜ p y | x (y | x k)

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 $v k$ et $w k$ sont des séquences mutuellement indépendantes et distribuées à l'identique 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 $v k$ et $w k$ étaient des gaussiennes, alors le filtre de Kalman trouve la distribution de filtrage bayésien exacte. Dans le cas contraire, les méthodes à base de filtre de Kalman donnent une estimation de premier ordre. Les filtres particulaires donnent également des approximations, mais avec suffisamment de particules, les résultats peuvent être encore plus précis.

[modifier] Approximation de Monte-Carlo

Les méthodes à particules, comme toutes les 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)})$ et $f(\cdot)$ , de la façon habituelle des méthodes Monte-Carlo, peut donner tous les 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 $x k = 0 | k = 0$ pour toutes les particules fournit une position de départ pour générer $x 1$ , qui peut être utilisé pour générer $x 2$ , qui peut être utilisé pour générer $x 3$ , et ainsi de suite jusqu'à $k = N$ .

Une fois ceci effectué, la moyenne des $x k$ sur toutes les particules (ou $\frac{1}{P}\sum_{L=1}^P x_k^{(L)}$ ) est approximativement la véritable valeur de $x k$ .

[modifier] 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é très couramment. 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 : $π(x k | x 0: k - 1, y 0: k)$ .

La distribution d'importance optimale est donnée comme : $π(x k | x 0: k - 1, y 0: k) = p (x k | x k - 1, y k).$

Cependant, la probabilité de transition est souvent utilisée comme fonction d'importance, comme elle est plus aisée de calculer, et cela simplifie également les calculs des poids d'importance subséquents : $π(x k | x 0: k - 1, y 0: k) = p (x k | x k - 1).$

Les filtres à rééchantillonnage par importance (SIR) avec des probabilités de transitions comme fonction d'importance sont connues communément 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ù tous les 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 :

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})$
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})}.$
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}$
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}$
Si le nombre effectif de particules est plus petit qu'un seuil donné , alors on effectue le rééchantillonnage:
1. Tirer $P$ particules de l'ensemble de particules courant avec les probabilités proportionnelles à leur poids puis remplacer l'ensemble des particules courantes avec ce nouvel ensemble.
2. Pour $L=1, \ldots, P$ l'ensemble $w^{(L)}_k = 1/P$ .

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

[modifier] Echantillonnage séquentiel par importance (SIS)

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

[modifier] Version directe de l'algorithme

La version directe de l'algorithme est relativement 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émént 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})$ où

y k

est la valeur mesurée

(5) Générer une autre uniformémént u depuis

[0, m k]

(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

x k | k (p)

et incrémenter p

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

Cela peut être plus facilement visualisé si $x$ est vu comme un tableau à deux dimensions. Une dimension est $k$ et l'autre dimension correspond au nombre de particules. Par exemple, $x (k, L)$ serait la L^ème particule à l'étape $k$ et peut être donc écrite $x_k^{(L)}$ (comme effectué plus haut dans l'algorithme).

L'étape (3) génère un potentiel $x k$ 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 $x k$ valeurs sont générées en utilisant les $x k - 1$ générées précédemment.

[modifier] Voir aussi

filtre de Kalman, un estimateur analytique pour les distributions Gaussiennes
estimation récursive bayésienne

[modifier] References

Sequential Monte Carlo Methods in Practice, par A Doucet, N de Freitas et N Gordon. Publié par Springer.
On Sequential Monte Carlo Sampling Methods for Bayesian Filtering, par A Doucet, C Andrieu et S. Godsill, Statistics and Computing, vol. 10, no. 3, pp. 197-208, 2000 CiteSeer link
Tutorial on Particle Filters for On-line Nonlinear/Non-Gaussian Bayesian Tracking (2001); S. Arulampalam, S. Maskell, N. Gordon et T. Clapp; CiteSeer link
F. Dellaert, D. Fox, W. Burgard, et S. Thrun, "Monte Carlo Localization for Mobile Robots," IEEE International Conference on Robotics and Automation (ICRA99), Mai, 1999.