Filrtage
bayésien en grande dimension par Méthodes de Monte Carlo |
Les méthodes de simulation de
type Monte Carlo sont des outils numériques pour la résolution de
problèmes inverses. Ces méthodes sont par exemple utilisées pour
l'exploration de lois de probabilités dans une approche bayésienne
des problèmes inverses, ou pour la restauration de données
manquantes dans l'analyse de modèles partiellement observés. Comme
l'atteste la littérature scientifique, ces approches ont été app
liquées avec succès à de très nombreuses applications (navigation et
localisation, classification en imagerie, traitement du signal
audio, communications numériques, etc.).
Cependant, le défi majeur pour les prochaines années
est lié à l'analyse de données de très grandes dimensions et de
données massives. Dans ce contexte, il est nécessaire de faire
évoluer ces méthodes afin de les rendre robustes à la grande
dimension des supports à explorer et aussi de les rendre robustes
à la multimodalité des lois tout en intégrant les aspects
séquentiels du traitement de l'Information soit du fait du
phénomène d'acquisition des données soit du fait du caractère
massif des données.
Le but de cette journée est de faire le point sur les
travaux récents en méthodes de Monte Carlo séquentielles pour les
problèmes d’inférence en grande dimension. Cette journée est
organisée autour d’un tutoriel d’une heure par Arnaud Doucet
(Oxford University), de 4 exposés invités de 30 min (Etienne Mémin
– INRIA/IRISA Rennes, Pierre Minvielle - CEA, Christophe
Baehr – Météo-France/CNRS Toulouse et Randal Douc – Télécom SudParis
), ainsi que de quelques contributions
spontanées.
10h - 11h |
Arnaud
DOUCET |
Efficient implementation of the Particle Marginal Metropolis-Hastings Algorithm | |
11h - 11h30 |
Christophe BAEHR |
Filtrage non-linéaire et approximations particulaires pour les fluides géophysiques. Entre grandes dimensions et modèles imparfaits, quelques questions posées et solutions proposées |
|
11h30 -12h |
Etienne
MEMIN |
|
|
13h30 - 14h |
Pierre
MINVIELLE |
Particle MCMC for Bayesian microwave control |
|
14h - 14h30 |
Randal DOUC |
Uniform ergodicity of the Particle Gibbs sampler |
|
14h30 - 15h |
Jean-François
GIOVANNELLI |
Echantillonnage efficace de Champs Gaussiens en grande dimension
|
|
15h15 -15h45 |
Yosra MARNISSI |
Schéma d'échantillonnage Métropolis-Hastings adapté par Majoration- Minimisation |
|
15h45 -16h15 |
Marcelo
PEREYRA |
Proximal Markov chain Monte Carlo: convex optimisation meets stochastic sampling |
|
16h15 - 16h45 |
Pierre
GRANGEAT |
Traitement de l’information en mode comptage appliqué aux détecteurs spectrométriques |
10h-11h : Arnaud DOUCET (Dpt of Statistics, Oxford University, UK)
Titre : Efficient
implementation of the Particle Marginal Metropolis-Hastings Algorithm
Résumé : When an
unbiased estimator of the likelihood is used within an
Metropolis-Hastings scheme, it is necessary to tradeoff the number of
samples used to evaluate the likelihood against the computing time.
Many samples will result in a scheme which has similar properties to
the case where the likelihood is exactly known but will be expensive.
Few samples will result in faster estimation but at the expense of
slower mixing of the Markov chain. We explore the relationship between
the number of samples and the efficiency of the resulting
Metropolis-Hastings estimates. Under the assumption that the
distribution of the additive noise introduced by the log-likelihood
estimator is independent of the point at which this log-likelihood is
evaluated and other relatively mild assumptions, we provide guidelines
on the number of samples to select for a general Metropolis-Hastings
proposal. We illustrate on a complex stochastic volatility model that
these assumptions are approximately satisfied experimentally and that
the theoretical insights with regards to inefficiency and
computational time hold true.
(Papier disponible a http://arxiv.org/abs/1210.1871)
11h-11h30 : Christophe BAEHR (Meteo France - CNRS)
Titre: Filtrage non-linéaire et approximations particulaires pour les fluides géophysiques. Entre grandes dimensions et modèles imparfaits, quelques questions posées et solutions proposées
Résumé : Dans cette courte présentation, nous allons aborder plusieurs thèmes relatifs aux filtres particulaires pour les fluides géophysiques. Effectivement, le fait de traiter des fluides réels représentés numériquement par des systèmes de grandes dimensions contient plusieurs difficultés.
Après un rappel sur le filtrage non-linéaire décrit par des flots de Feynman-Kac résolus par particules, nous présenterons des résultats numériques sur le nombre de particules critiques pour qu'un filtre utilisant une sélection génétique ne dégénère pas. Nous nous poserons alors la question de l'adaptation des noyaux de sélection aux cas de grandes dimensions. Des exemples de filtres adaptés seront montrés.
La seconde partie de l'exposé portera sur l'utilisation de modèles imparfaits dans le filtrage non-linéaire. Cette situation est constamment présente lorsqu'on a à traiter des fluides réels. Soit le modèle numérique de la dynamique a subi des approximations, soit la numérisation des EdPs sur une grille induit des erreurs de représentation du fluide. Nous montrerons comment s'articule l'estimation des distributions de Feynman-Kac dans le cas particulier des modèles imparfaits. Nous présenterons alors un exemple de résolution pour des erreurs déterministes multidimensionnelles.
Pour conclure sur l'utilisation des techniques de Monte-Carlo en assimilation de données pour les fluides géophysiques, nous montrerons les résultats de reconstitutions locales de milieu aléatoire dans le cas d'atmosphères turbulentes.
11h30-12h
:
Etienne MEMIN (Inria, centre Inria Rennes, Equipe Fluminance)
Titre : Filtrage particulaire pour l'analyse d'écoulements à partir de séquence d’images
Résumé : Dans cet exposé nous présenterons deux instances différentes de filtres particulaires pour la reconstruction de champs de vitesses d'un écoulement fluide et le suivi de courbes libres. De façon à contrer les problèmes que rencontrent les filtres particulaires dans le cas d'un espace d'état de grande dimension le premier filtre est bâti à partir d'une fonction de proposition définie au moyen d'un mécanisme calqué sur la technique des filtres de Kalman d'ensemble. Ce filtre permet donc de faire un pont entre les techniques ensemblistes et les filtres à particules. Le filtre résultant a l'avantage d'assouplir l'hypothèse gaussienne forte du filtre de Kalman d'ensemble. Nous montrerons divers résultats de ce filtre pour la reconstruction de cartes de vorticité d'un écoulement que ce soit à partir d'une équation de mesure linéaire ou non linéaire. Nous présenterons également un filtre particulaire pour le suivi d'interfaces. Ce filtre particulaire s'appuie lui sur un modèle dynamique guidé par les mesures image et associé à un bruit de très faible dimension. Nous montrons que ce choix conduit à une technique de suivi efficace sur des exemples d'images satellites diverses. Ces deux exemples mettrons en exergues quelques stratégies complémentaires pour face à un problème de filtrage dans des espaces d’état de très grande dimension.
13h30-14h : Pierre MINVIELLE (CEA - DAM)
Titre : Particle MCMC for Bayesian microwave control
Résumé : In this talk, we consider the estimation of local radioelectric material properties from global electromagnetic scattering measurements. This inverse scattering problem requires going upstream a parallelized harmonic Maxwell solver, which provides the numerical solution to Maxwell's equations in free space. In a statistical viewpoint, it can be expressed as a general Hidden
Markov Model, involving a dynamic state and a fixed hyper-parameter, related to a multiple components (Debye relaxation/Lorenzian resonant) material model. The sequential Bayesian analysis is performed by "particle Markov Chain Monte Carlo", an emerging important class of techniques in signal processing and Bayesian statistics that combines MCMC and SMC (filtering). More precisely, a "particle Marginal Metropolis-Hastings" algorithm is designed, including Rao-Blackwellised Sequential Monte Carlo. And yet, it is a computationally intensive technique. Moreover, computation time increases with both state/observation dimensions. How to deal with high dimension? The issue is just partly solved by the Rao-Blackwellisation strategy as well as likelihood metamodeling (resulting from intensive training on a petaflopic supercomputer). To go further, there are two main ways: high performance computing adaptations or/and high dimension oriented approximations.
Joint work with A. Todeschini, F. Caron and P. Del Moral.
14h-14h30 : Randal DOUC (Telecom SudParis - Institut Mines-Telecom)
Titre : Uniform ergodicity of the Particle Gibbs sampler
Résumé : The particle Gibbs (PG) sampler is a systematic way of using a particle filter within Markov chain Monte Carlo (MCMC). This results in an off-the-shelf Markov kernel on the space of state trajectories, which can be used to simulate from the full joint smoothing distribution for a state space model in an MCMC scheme. We show that the PG Markov kernel is uniformly ergodic under rather general assumptions, that we will carefully review and discuss. In particular, we provide an explicit rate of convergence which reveals that: (I) for fixed number of data points, the convergence rate can be made arbitrarily good by increasing the number of particles, and (ii) under general mixing assumptions, the convergence rate can be kept constant by increasing the number of particles superlinearly with the number of observations. We illustrate the applicability of our result by studying in detail two common state space models with non-compact state spaces.
Joint work with F. Lindsten and E. Moulines.
14h30
-15h : Jean-François GIOVANNELLI (IMS, Univ. Bordeaux)
Titre : Echantillonnage de Champs Gaussiens en grande dimension
Résumé :
Nous nous intéressons à la question de l'échantillonnage de vecteurs
gaussiens en grande dimension. Les approches classiques reposent sur
la manipulation de la matrice de covariance ou de la matrice de
précision (factorisation de Cholesky, en racine carré,
diagonalisation, ...) En (très) grande dimension, ces approches ne
sont utilisables que dans des situations particulières (matrices
creuses ou circulantes). La controbution repose sur une approche dite
par Perturbation-Optimisation : on génère des perturbations adéquates
d'un critère quadratique puis on l'optimise pour obtenir un
échantillon de la distribution ciblée. L'approche est valide en
particulier pour les structures spécifiques de la matrice de précision
qui apparaissent en inversion. L'algorithme proposé trouve une
application directe en inversion myope et/ou non supervisée, fondée
sur des modèles hiérarchiques, des approches bayésiennes et des
algorithmes d'échantilonnage stochastique de type MCMC. L'efficacité
de l'approche est illustrée sur plusieurs exemples : inversion non
supervisée en super-résolution, en imagerie astrophysique, en imagerie
par illumination structurée ...
Travail en
collaboration avec F. Orieux et O. Féron
15h15-15h45 : Yosra MARNISSI (LIGM, Univ. Paris-Est)
Titre : Schéma d'échantillonnage Métropolis-Hastings adapté par Majoration- Minimisation
Résumé : Dans le but d'échantillonner suivant une certaine densité de probabilité, l'idée sous-jacente aux méthodes MCMC est de produire, à partir d'une loi de transition donnée, une chaîne de Markov qui converge vers la loi cible. Une classe importante de méthodes MCMC est inspirée de la discrétisation de l'équation différentielle stochastique de Langevin en y intégrant un schéma de correction de type Metropolis-Hastings (MH). Ces méthodes introduisent alors un biais dans la loi de proposition de MH en fonction de l'information contenue dans le gradient, ayant pour effet de pousser la chaîne vers les zones les plus probables afin d'accélérer la convergence. Notons que ces méthodes dépendent de deux paramètres dans leur implémentation : le pas de discrétisation et la matrice d'échelle contrôlant la direction, dont le choix influe fortement sur l'efficacité de l'échantillonnage. En particulier, il a été montré qu'un choix astucieux d'une matrice d'échelle adaptative (matrice Hessienne ou matrice de Fisher) peut accélérer la convergence des algorithmes.
Toutefois, cela nécessite souvent l'inversion, à chaque itération, d'une matrice de grande taille, ce qui peut entraîner un coût de calcul prohibitif dans des problèmes de grande dimension. Dans ce travail, on se propose d'utiliser une matrice d'échelle définie positive élaborée à partir d'une approche de majoration-minimisation (MM). Ce choix permet non seulement d'accélérer l'algorithme, mais aussi d'éviter les problèmes d'inversion matricielle en offrant un coût de calcul minimal. Les résultats expérimentaux pour la restauration des données 1D et 2D confirment la rapidité de cette nouvelle approche par rapport à l'échantillonneur usuel de Langevin.
Travail en collaboration avec A. Benazza-Benyahia, E. Chouzenoux et J.-C. Pesquet.
15h45-16h15 : Marcelo PEREYRA ( School of Mathematics, Univ. Bristol -UK)
Titre : Proximal Markov chain Monte Carlo: convex optimisation meets stochastic sampling
Résumé : Convex optimisation and stochastic sampling are two powerful methodologies for performing statistical inference in inverse problems related to signal and image processing. It is widely acknowledged that these methodologies can complement each other very well; yet they are generally studied and used separately. This talk presents two new Langevin Markov chain Monte Carlo methods that use elements of convex analysis and proximal optimisation to simulate efficiently from high-dimensional densities that are log-concave. The methods are based on a new first-order approximation for Langevin diffusions that uses Moreau-Yoshida approximations and proximity mappings to capture the log-concavity of the target density and construct Markov chains with favourable convergence properties. The methods are shown to be geometrically ergodic in many cases where the conventional Langevin MCMC algorithms are transient or explosive and do not converge geometrically. The proposed methodology is demonstrated on a series of illustrative examples and on two challenging high-dimensional applications related to audio compressive sensing and image resolution enhancement.
16h15-16h45 : Pierre GRANGEAT (CEA – LETI)
Titre : Traitement de l’information en mode comptage appliqué aux détecteurs spectrométriques
Résumé : La miniaturisation des composants électroniques conduit aujourd’hui au développement de capteurs ultra-sensibles. En particulier, les capteurs NEMS (systèmes électromécaniques nanométriques) ont maintenant une sensibilité suffisante pour détecter des molécules uniques. Ceci permet d’intégrer ces capteurs dans des dispositifs de spectrométrie de masse dont la particularité sera d’opérer en mode comptage de molécules uniques. Notre travail consiste à reconstruire le spectre de masse de la solution analysée à partir des signaux fréquentiels délivrés par les NEMS.
Nous nous plaçons dans le cadre des approches problèmes inverses et des méthodes d’inférence bayésienne. Nous modélisons le système de mesure qui lie les inconnues aux signaux observés par un modèle graphique hiérarchique et nous introduisons un modèle de signal de type processus ponctuel marqué. Nous le comparons par rapport à un modèle de type processus à temps discret.
Nous mettons en place un algorithme de déconvolution impulsionnelle intégrant une exploration de modèles qui réalise la détection des molécules analysées, l’estimation de leur masse et le comptage, afin de reconstruire le spectre de masse de la solution analysée.
Nous présentons des résultats sur données simulées et sur des données expérimentales acquises au CEA/INAC sur des agrégats de Tantale en utilisant des capteurs NEMS développés au CEA-Leti/DCOS. Relativement aux méthodes de l’état de l’art, la méthode que nous proposons améliore le taux de comptage tout en gardant un taux de fausses détections suffisamment bas. Notre méthode délivre également les incertitudes sur les paramètres reconstruits. Enfin, nous développons le cas particulier de la reconstruction de spectres de masse discrets.
Travail en collaboration avec R. Perenon et A. Mohammad Djafari.