---

Filtrage bayésien et approximation particulaire

---

Objectifs :

En toute généralité, le filtrage consiste à estimer de façon récursive un état caché (par exemple, la position et l'attitude d'un mobile) au vu d'observations bruitées. Compte tenu que l'état caché évolue en principe au cours du temps, il est nécessaire d'introduire un modèle a priori de déplacement du mobile, et de considérer le problème d'estimation dans un cadre bayésien. Le domaine d'application principal est la localisation, la navigation et la poursuite de mobiles, dans le domaine militaire ou civil, en robotique mobile, en vision par ordinateur, en communications sans-fil (GSM en extérieur, WiFi en indoor), où il s'agit de combiner : un modèle a priori de déplacement du mobile, des mesures issues de capteurs, et éventuellement une base de mesures de références, disponibles par exemples sous la forme d'une carte numérique (modèle numérique de terrain, carte de couverture, etc.).

Dans le cas particulier des systèmes linéaires gaussiens, le problème de filtrage possède une solution explicite, appelée filtre de Kalman. Dans le cas des systèmes non-linéaires avec des bruits non nécessairement gaussiens, ou dans le cas plus général des modèles de Markov cachés, des méthodes de simulation Monte Carlo très efficaces sont apparues récemment, sous le nom de filtres particulaires. De manière intuitive, chaque particule représente ici un état caché possible, explore l'espace d'état en suivant le modèle a priori de déplacement, et est répliquée ou au contraire éliminée à la génération suivante au vu de sa cohérence avec l'observation courante, quantifiée par la fonction de vraisemblance. Ce mécanisme de mutation / sélection a pour effet de concentrer automatiquement les particules (i.e. la puissance de calcul disponible) dans les régions d'intérêt de l'espace d'état.

Plus généralement, les algorithmes particulaires permettent d'approcher des distributions de Feynman-Kac (ou distributions de Boltzmann-Gibbs trajectorielles) au moyen de la distribution de probabilité empirique pondérée associée à un système de particules en interaction, avec des applications qui vont bien au-delà du filtrage : simulation d'évènements rares, optimisation globale, simulation moléculaire, etc.

L'objectif de ce cours est

• de présenter différents algorithmes particulaires,
• de les mettre en œuvre dans le cadre de travaux pratiques en MATLAB,
• et de démontrer quelques résultats de convergence en utilisant le cadre général de l'approximation particulaire des distributions de Feynman-Kac.

Programmation détaillée :

1. Introduction au filtrage : estimation récursive d'un état caché au vu d'observations, importance du modèle a priori, estimation bayésienne, borne de Cramér-Rao a posteriori
   Systèmes non linéaires à bruits non gaussiens : exemples en localisation, navigation et poursuite
   • recalage altimétrique de navigation inertielle
   • suivi visuel par histogramme de couleur
   • poursuite d'une cible furtive (track-before-detect)
   • navigation en environnement intérieur
   • prise en compte de contraintes et d'occultations
   Systèmes linéaires gaussiens et conditionnellement linéaires gaussiens : filtre et lisseur de Kalman, loi conditionnelle jointe comme loi jointe d'un système linéaire gaussien rétrograde
   
2. Méthodes de Monte Carlo : simulation selon une distribution de Gibbs-Boltzmann
   • acceptation / rejet
   • échantillonnage pondéré, changement de probabilité « optimal » (variance nulle)
   • simulation séquentielle (contrôle de la taille de l'échantillon)
   • réduction de variance par conditionnement (Rao-Blackwell)
   Méthodes de Monte Carlo : simulation selon un mélange fini
   • échantillonnage multinomial, algorithme de Malmquist
   • stratification et échantillonnage résiduel
   • stratification et randomisation
   • échantillonnage systématique
   • stratification et tirage uniforme sans remise (cas particulier des poids 0/1)
3. Dérivation du filtre bayésien optimal : représentation probabiliste vs. équation récurrente
   • systèmes non linéaires à bruits non gaussiens
   • modèles de Markov cachés
   • chaînes de Markov partiellement observées
   Distribution de Feynman-Kac : représentation probabiliste vs. équation récurrente
   Approximation particulaire : algorithme SIS, algorithme SIR, redistribution adaptative
4. Rappels : inégalité de Marcinkiewicz-Zygmund, théorème central limite « conditionnel »
   Théorèmes limites pour les approximations particulaires :
   • probabilité d'extinction
   • convergence dans L_p
   • théorème central limite
5. Méthodes de Monte Carlo séquentielles : échantillonnage selon une distribution de Gibbs-Boltzmann
   • v.a. conditionnées ou contraintes
   • pondération « progressive »
   • recuit
   Dynamique markovienne artificielle : algorithme de Metropolis-Hastings, échantillonneur de Gibbs
   Méthodes de branchement multi-niveaux : taux de branchement fixe vs. taille d'échantillon fixe, sélection des niveaux (fonction d'importance optimale, seuils)
   • évaluation d'une probabilité de dépassement de niveau (cas statique)
   • optimisation globale
   • simulation d'évènements rares (cas dynamique)
   Exemples en évaluation de risque
   • collision entre satellite et débris
   • conflit ou collision en trafic aérien

• Support de cours 18/19 : polycopié (version du 3 octobre 2018)
  • séances des 21 et 28 septembre
  • séance du 5 octobre
  • séance du 12 octobre (commencée le 5 octobre)
  • séance du 19 octobre
• Travaux pratiques 18/19 :
  1. Recalage altimétrique de navigation inertielle : énoncé
  2. Suivi visuel par histogramme de couleur (proposé par Élise Arnaud) : énoncé

• Examen 18/19 : énoncé, corrigé
  TCL pour l'approximation particulaire (avec redistribution multinomiale) du prédicteur.
  Simulation séquentielle et application à l'estimation d'une probabilité de dépassement.

Références bibliographiques :

ouvrages de référence

• Nathalie Bartoli et Pierre Del Moral, Simulation et Algorithmes Stochastiques, Cépaduès, Toulouse, 2001.
• Olivier Cappé, Éric Moulines and Tobias Ryden, Inference in Hidden Markov Models, Springer Series in Statistics, Springer, New York, 2005.
• Pierre Del Moral, Feynman-Kac Formulae. Genealogical and Interacting Particle Systems with Applications, Probability and its Applications, Springer, New York, 2004.
• Randal Douc, Éric Moulines, David Stoffer, Nonlinear Time Series: Theory, Methods and Applications with R Examples, Texts in Statistical Science, CRC Press, Boca Raton, 2014.
• Arnaud Doucet, Nando de Freitas and Neil Gordon, editors, Sequential Monte Carlo Methods in Practice, Statistics for Engineering and Information Science, Springer, New York, 2001.
• James Durbin and Siem Jan Koopman, Time Series Analysis by State Space Methods (2nd edition), Oxford University Press, Oxford, 2012.
• Branko Ristić, Sanjeev Arulampalam and Neil J. Gordon, Beyond the Kalman Filter: Particle Filters for Tracking Applications, Artech House, Boston, 2004.

articles téléchargeables (format PDF) : méthodologie

• Neil J. Gordon, David J. Salmond and Adrian F. M. Smith, Novel approach to nonlinear / non-Gaussian Bayesian state estimation, IEE Proceedings, Part F, Radar, Sonar and Navigation, 140, 2, 107-113, April 1993.
• Arnaud Doucet, Simon J. Godsill and Christophe Andrieu, On sequential Monte Carlo sampling methods for Bayesian filtering, Statistics and Computing, 10, 3, 197-208, July 2000.
• Sanjeev M. Arulampalam, Simon Maskell, Neil J. Gordon and Tim C. Clapp, A tutorial on particle filters for online nonlinear / non-Gaussian Bayesian tracking, IEEE Transactions on Signal Processing, SP-50, 2 (special issue on Monte Carlo Methods for Statistical Signal Processing), 174-188, February 2002.
• Olivier Cappé, Simon J. Godsill and Éric Moulines, An overview of existing methods and recent advances in sequential Monte Carlo, Proceedings of the IEEE, 95, 5, 899-924, May 2007.

articles téléchargeables (format PDF) : applications

• David J. Salmond and H. Birch, A particle filter for track-before-detect, American Control Conference (ACC'01), Arlington, June 2001, 3755-3760, IEEE-CSS, 2001.
• Patrick Pérez, Carine Hue, Jako Vermaak and Marc Gangnet, Color-based probabilistic tracking, European Conference on Computer Vision (ECCV'02), Copenhagen, June 2002, Lecture Notes in Computer Science 2350, 661-675, Springer, Berlin, 2002.
• Dieter Fox, Jeffery Hightower, Lin Liao, Dirk Schulz and Gaetano Borriello, Bayesian filtering for location estimation, IEEE Pervasive Computing, 2, 3, 24-33, July / September 2003.
• Fredrik Gustafsson, Fredrik Gunnarsson, Niclas Bergman, Urban Forssell, Jonas Jansson, Rickard Karlsson and Per-Johan Nordlund, Particle filters for positioning, navigation, and tracking, IEEE Transactions on Signal Processing, SP-50, 2 (special issue on Monte Carlo Methods for Statistical Signal Processing), 425-437, February 2002.
• René Carmona, Jean-Pierre Fouque and Douglas Vestal, Interacting particle systems for the computation of rare credit portfolio losses, Finance and Stochastics, 13, 4 (Special issue on Computational Methods in Finance (Part II)), 613-633, September 2009.

Archives (sujets d'examen) :

• Examen 17/18 : énoncé, corrigé
  Approximation d'une distribution de Gibbs-Boltzmann par échantillonnage pondéré séquentiel.
• Examen 16/17 : énoncé, corrigé
  Estimation de la probabilité d'extinction pour l'algorithme SIR avec des fonctions de sélection non strictement positives.
• Examen 15/16 : énoncé, corrigé
  Approximations particulaires pour le calcul de probabilités de dépassement de niveau.
• Examen 14/15 : énoncé, corrigé
  Algorithme APF (pour auxiliary particle filter).
• Examen 13/14 : énoncé, corrigé
  Estimation de l'erreur d'approximation particulaire pour des fonctions non-nécessairement bornées.
• Examen 12/13 : énoncé, corrigé
  Modèle de Markov non-linéaire pour l'étude de l'algorithme SIR avec redistribution adaptative.
• Examen 10/11 : énoncé, corrigé
  Filtre bayésien pour les systèmes non-linéaires non-gaussiens avec bruits non-nécessairement indépendants.
  Algorithme de rejet controlé.
• Examen 09/10 : énoncé, corrigé
  Filtre bayésien pour les chaînes de Markov cachées avec bruit d'observation représenté par un modèle ARMA.
  Lisseur bayésien pour les chaînes de Markov cachées.
• Examen 07/08 : énoncé, corrigé
  Filtre particulaire généralisé, ou ABC (pour approximate Bayesian computation).
  Approximation particulaire combinant deux types de poids, pour la redistribution ou simplement pour la pondération.
• Examen 06/07 : énoncé, corrigé partiel
  Distribution de Boltzmann-Gibbs : simulation d'un échantillon et calcul de la fonction de partition.
  Filtre bayésien pour une classe de systèmes conditionnellement linéaires gaussiens, flot paramétré, flot hybride et approximation particulaire.
• Examen 05/06 : énoncé, corrigé
  Simulation d'une chaîne de Markov conditionnée.
  Optimisation globale.

Retour à la page de François Le Gland