Détails du cours OROC-SC-FP

Optimal Bayesian filtering and particle approximation

Cette page est essentiellement destinée aux enseignants et regroupe toutes les informations nécessaires à la gestion d'un cours ENSTA.

Identité du cours

Sigle : OROC-SC-FP
Titre français : Filtrage bayésien optimal et approximation particulaire
Titre anglais : Optimal Bayesian filtering and particle approximation
Méta infos : modifiée le : 15/06/2016   par : zidani   Nb de visiteurs : 667   annee : 3A      periode : 1      Rattachement/module : B      ECTS : 1.5      type : unknown     
ouvert : Oui     modif. autorisée : Oui     email auto. au responsable : Oui     à évaluer : Oui     en ligne : Non    
domaine ParisTech : 1    

Equipe pédagogique

Responsable (login) :
Professeur principal :
Professeurs participants : François LE GLAND,   
Maitres de conférences :

Contenu

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. 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 éventuellemnent 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.
Mots clés : filtrage, système non linéaire à bruits non gaussiens, modèle de Markov
caché, estimation bayésienne, méthode de Monte Carlo, système de particules
en interaction, localisation, navigation, poursuite, simulation d'évènements
rares
Objectives : The general goal of filtering is to estimate recursively a hidden state (eg, position and attitude of a mobile) given noisy observations. The main field of application is the positioning, navigation and tracking of moving in the military or civilian field, mobile robotics, computer vision, in wireless communications (GSM outdoor, indoor WiFi), where it is to combine: an a priori model of the mobile displacement measurements from sensors and measurements. In the special case of Gaussian linear systems, the filtering problem has an explicit solution, called Kalman filter. In the case of nonlinear systems with (not necessarily) Gaussian noise, or in the more general case of hidden Markov models, highly efficient Monte Carlo simulation methods have emerged recently, as the particulate filters. Intuitively, each particle represents a possible hidden state here, explores the state space by following the a priori model of movement, and is replicated or otherwise eliminated to the next generation in view of its consistency with the current observation , quantified by the likelihood function. This mutation process/selection has the effect of automatically focusing the particles (ie the available computing power) in regions of interest of the state space. More generally, the particle algorithms allow to approach Feynman-Kac distribution (or distributions Boltzmann-Gibbs pathwise) by means of the weighted empirical probability distribution associated with a system of interacting particles, with applications that go far Step outside the filtering: simulation of rare events, global optimization, molecular simulation, etc.
The objective of this course is:
  • presenting different particle algorithms,
  • implement such algorithms in the context of Hands-on sessions (MATLAB),
  • analysis of some convergence results using the general framework of particle approximation of Feynman-Kac distributions
Keywords : filtering, nonlinear system with non Gaussian noises, hidden Markov model (HMM),
Bayesian estimation, Monte Carlo method, interacting particle system,
localization, navigation, tracking, rare events simulation
Supports :
Lien : http://www.irisa.fr/aspi/legland/ensta/,
Biblio :
Contrôle : Examen final + TP MATLAB

Besoins particuliers et remarques éventuelles

Moyens :
Commentaires :

Séances

ven. 16 sept. 2016   - 13:30 à 17:15 : Bloc de Module (1/2 journée) (MOD)
programme : 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 de Kalman
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 couleurs
  • poursuite d'une cible furtive (track-before-detect)
  • navigation en environnement intérieur

besoin :
Intervenants : François LE GLAND,
ven. 23 sept. 2016   - 13:30 à 15:00 : Cours Magistral (CM)
programme : 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
besoin :
Intervenants : François LE GLAND,
ven. 23 sept. 2016   - 15:15 à 17:15 : TD en salle info (TD)
programme : Recalage altimétrique de navigation inertielle
besoin :
Intervenants : François LE GLAND,
ven. 30 sept. 2016   - 13:30 à 15:00 : Cours Magistral (CM)
programme : 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)

besoin :
Intervenants : François LE GLAND,
ven. 30 sept. 2016   - 15:15 à 17:45 : TD en salle info (TD)
programme : Suivi visuel par histogramme de couleur
besoin :
Intervenants : François LE GLAND,
ven. 07 oct. 2016   - 13:30 à 15:00 : Cours Magistral (CM)
programme : 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

besoin :
Intervenants : François LE GLAND,
ven. 07 oct. 2016   - 15:15 à 17:15 : TD en salle info (TD)
programme : Navigation en environnement intérieur
besoin :
Intervenants : François LE GLAND,
ven. 14 oct. 2016   - 13:30 à 15:00 : Cours Magistral (CM)
programme : Rappels : inégalité de Marcinkiewicz-Zygmund, théorème central limite «conditionnel»
Théorèmes limites pour les approximations particulaires : convergence dans Lp, théorème central limite
besoin :
Intervenants : François LE GLAND,
ven. 14 oct. 2016   - 15:15 à 17:15 : TD en salle info (TD)
programme : Navigation en environnement intérieur (suite)
besoin :
Intervenants : François LE GLAND,
ven. 21 oct. 2016   - 13:30 à 15:00 : Contrôle (CC)
programme : Contrôle
besoin :
Intervenants : François LE GLAND,
ven. 21 oct. 2016   - 15:15 à 17:15 : TD en salle info (TD)
programme : Evaluation du risque de collision
besoin :
Intervenants : François LE GLAND,