Filtrage bayésien et approximation particulaire

ENSTA, cycle ingénieur 3ème année, cours SOD333 : ce cours fait partie du parcours SOD, Sciences de l'Optimisation et des Données

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

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 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
    Systèmes non linéaires à bruits non gaussiens : exemples en localisation, navigation et poursuite
  2. Dérivation du filtre (et du lisseur) bayésien optimal : représentation probabiliste vs. équation récurrente Distribution de Feynman-Kac : représentation probabiliste vs. équation récurrente
  3. Méthodes de Monte Carlo : simulation selon une distribution de Gibbs-Boltzmann Méthodes de Monte Carlo : simulation selon un mélange fini 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 :
  5. Méthodes de Monte Carlo séquentielles : échantillonnage selon une distribution de Gibbs-Boltzmann 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) Exemples en évaluation de risque
Supports de cours et TP : Sujet d'examen :

Références bibliographiques :

ouvrages de référence

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

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


Archives (sujets d'examen) :