Archive
Séminaire BIG'MC
Méthodes de Monte Carlo en grande dimension
Archive 2009 - 2013
(suite du séminaire ADAP'MC: 2006 - 2008
Méthodes de Monte Carlo Adaptatives)
Institut Henri Poincaré
11, rue Pierre et Marie Curie
75 005 Paris
Le séminaire Big'MC a lieu une fois par mois. Il est ouvert à tous, étudiant comme enseignant-chercheur intéressé.
Pour tout renseignement, contacter l'un des organisateurs.
Programme du séminaire
Le séminaire a lieu à 15h, à l'IHP
2012 - 2013
Organisateurs : Nicolas CHOPIN et Gersende FORT
Jeudi 13 Juin [Ampĥi Perrin]
Jeudi 16 Mai [Amphi Hermite]
[15h] Pierre Del Moral (INRIA Bordeaux)
Titre : Particle approximation of multiple object nonlinear filtering problems
Résumé : We consider the problem of estimating a latent point process, given the realization of another point process on abstract measurable state spaces.
First, we establish an expression of the conditional distribution of a latent Poisson point process given the observation process when the transformation from the latent process to the observed process includes displacement, thinning and augmentation with extra points. We present an original analysis based on a self-contained random measure theoretic approach combined with reversed Markov kernel techniques. In the second part, we analyse the exponential stability properties of nonlinear multi-target filtering equations. We prove uniform convergence properties w.r.t. the time parameter of a rather general class of stochastic filtering algorithms, including sequential Monte Carlo type models and mean field particle interpretation models. We illustrate these results in the context of the Bernoulli and the Probability Hypothesis Density filter.
[16h15] François Septier (Telecom Lille 1)
Titre : Bayesian Filtering in High-Dimensional Spaces using Sequential MCMC
Résumé : Nonlinear non-Gaussian state-space models arise in numerous applications in control and signal processing. In this context, one of the most successful and popular approximation techniques is Sequential Monte Carlo (SMC) methods, also known as particle filters. Nevertheless, these methods tend to be inefficient when applied to high dimensional problems. In this talk, I will present an overview of Markov chain Monte Carlo (MCMC) methods for sequential simulation from posterior distributions, which represent efficient alternatives to SMC methods especially in high dimensional spaces. Then, I will describe ongoing work on Sequential Markov chain Monte Carlo (SMCMC) algorithms in which we incorporate a component of Approximate Bayesian Computation (ABC) in order to obtain a sequential estimation methodology for a class of non-linear, non-Gaussian state space models in which the observation process is intractable to express in closed form. Numerical simulations applied to multiple target tracking and sensor network will be presented.
Jeudi 18 Avril [Amphi Hermite] (séance annulée)
Jeudi 28 Mars [Salle 314]
[15h] Yves Atchadé (Univ. Michigan, USA)
Titre: Assessing Monte Carlo errors in MCMC and adaptive MCMC
Résumé: The talk will present some asymptotic results on quadratic forms of Markov chains and adaptive Markov chains. The results are used to derive Monte Carlo confidence intervals using the standard Gaussian distribution, and the so-called fixed-b asymptotic. We will also discuss some convergence rates of quadratic forms that give some insight on the rates of convergence of these confidence intervals.
[16h15] O. Papaspiliopoulos (UPF, Espagne)
Titre: Optimal filtering and the dual process
Résumé: In this talk I will present ongoing work on a class of partially observed Markov models for which the so-called filtering distributions belong in mixtures of known finite dimensional distributions, the parameters and weights of which can be computed sequentially. This class contains as special case the models for which the well-known Baum or Kalman filters can be used for the computation of the filtering distributions, and involves high and infinite-dimensional unobserved signals. The filters for this class are computable because the law of the unobserved signals in these models admits a representation in terms of an auxiliary discrete state-space, continuous-time Markov chain. This auxiliary process is directly related with the so-called dual process in population genetics, and as we show the processes in the class we identify are related to the so-called Fleming-Viot process.
Joint work with Matteo Ruggiero (University of Turin)
Jeudi 21 Février [Salle 314]
[15h] Benjamin Jourdain et Tony Lelièvre (ENPC)
Titre : Optimal scaling of the transient phase of Metropolis Hastings algorithms
Résumé : We consider the Random Walk Metropolis algorithm on R^n with Gaussian proposals, and when the target probability measure is the n-fold product of a one dimensional law. It is well-known that, in the limit n tends to infinity, starting at equilibrium and for an appropriate scaling of the variance and of the timescale as a function of the dimension n, a diffusive limit is obtained for each component of the Markov chain. We generalize this result when the initial distribution is not the target probability measure. The obtained diffusive limit is the solution to a stochastic differential equation nonlinear in the sense of McKean. We prove convergence to equilibrium for this equation. We discuss practical counterparts in order to optimize the variance of the proposal distribution to accelerate convergence to equilibrium. Our analysis confirms the interest of the constant acceptance rate strategy (with acceptance rate between 1/4 and 1/3).
[16h15] Adam M. Johansen (Univ. Warwick, UK)
Titre : Exact Approximation of Rao-Blackwellised Particle Filters
Résumé : Particle methods are a category of Monte Carlo algorithms that have become popular for performing inference in non-linear non-Gaussian state-space models. The class of “Rao- Blackwellised” particle filters exploits the analytic marginalisation that is possible for some state- space models to reduce the variance of the Monte Carlo estimates. Despite being applicable to only a restricted class of state-space models, such as conditionally linear Gaussian models, these algorithms have found numerous applications. In scenarios where no such analytical integration is possible, it has recently been proposed in Chen et al. [2011] to use “local” particle filters to carry out this integration numerically. We propose here an alternative approach also relying on “local” particle filters which is more broadly applicable and has attractive theoretical properties. Proof-of-concept simulation results are presented.
Joint work with Nick Whiteley and Arnaud Doucet
T. Chen, T. Schoen, H. Ohlsson, and L. Ljung. Decentralized particle filter with arbitrary state decomposition. IEEE Trans. Sig. Proc., 59(2):465–478, 2011
Jeudi 10 Janvier 2013 [Salle 314] (séance annulée)
Jeudi 15 Novembre [Salle 201]
[15 h] Jean-Michel Marin (Univ. Montpellier 2)
Titre : Consistency of Adaptive Multiple Importance Sampling
Résumé :Among Monte Carlo techniques, the importance sampling requires fine tuning of a proposal distribution, which is now fluently done with iterative schemes. The Adaptive Multiple Importance Sampling (AMIS) of Cornuet et al. (2012) provides a significant improvement in stability and Effective Sample Size due to the introduction of a recycling procedure. However, the consistency of the AMIS estimator remains largely open. In this work we provides proofs of the convergence of the AMIS, at a cost of a slightmodification in the learning process. First numerical experiments exhibit that this modification might even improve the original scheme.
Réf. Cornuet, J.-M., Marin, J.-M., Mira, A., and Robert, C. P. (2012). Adaptive Multiple Importance Sampling. Scandinavian Journal of Statistics.
[16h15] Benjamin Guedj (LSTA, UPMC & LTCI, Telecom ParisTech)
Titre : A Stochastic Search MCMC algorithm for sparse additive models.
Résumé : Penalty-based estimators such as the Lasso proved successful in addressing high-dimensional regression problems under a constraint of sparsity. However, their good theoretical properties only hold under stringent conditions on the design (mutual coherence, R.I.P.), which may appear too much of a burden when it comes to building prediction algorithms. In this work, an alternative PAC-Bayesian strategy in investigated, carrying no assumption on the design. We
will focus on the explicit implementation of our exponentially weighted estimator. Our procedure relies on a stochastic search throughout the models space, the key idea being to favor local moves of the Markov Chain. Numerical evidence of the relevance of our method will be provided on simulated data.
Réf. Joint work with Éric Moulines (LTCI, Telecom ParisTech), Gérard Biau (LSTA, UPMC & IUF), Pierre Alquier (School of Mathematical Sciences, University College of Dublin).http://arxiv.org/abs/1208.1211 http://www.cran.r-project.org/web/packages/pacbpred/index.html
Jeudi 18 Octobre [Amphi Hermite]
[15 h] Orateur : Olivier Ratmann (Univ. Duke, USA)
Titre : Feature-based inference of virus phylodynamics, with ABC calibrated for exact parameter inference
Résumé : The infectious disease dynamics of many viral pathogens like influenza, norovirus and coro- navirus are inextricably tied to their evolution. This interaction between evolutionary and ecological processes complicates our ability to understand the infectious disease behavior of rapidly evolving pathogens. Most statistical methods for the analysis of these “phylodynamics” require that the likelihood of the data can be explicitly calculated. Currently, this is not possible for many phylodynamic models, so that questions on the interactionbetween viral variants cannot be well-addressed within this framework. Simulation-based statistical methods circumvent likelihood calculations. I here illustrate the effectiveness of these methods to fit and assess complex phylodynamic models against both sequence and surveillance data, and also present a new, fairly broadly applicable, theoretical framework for standard ABC parameter inference that aims to improve on existing, rather heuristic algorithm formulations.
[16 h15] Orateur : Rémi Bardenet (LAL & LRI, Univ Orsay)
Titre : When cosmic particles switch labels: Adaptive Metropolis with online relabeling, motivated by the data analysis of the Pierre Auger experiment
Résumé : The Pierre Auger experiment is a giant cosmic ray observatory located in Argentina. Cosmic rays are charged particles that travel through the universe at very high energies. When one of these particles hits our atmosphere, it generates a cascade of particles that strike the surface of Earth on several square kilometers. Auger has a 3000 km2 wide array of 1600+ detectors gathering data from these cascades. The objective of the data analysis is to infer the parameters of the original incoming particles. In this talk, we first derive a model of part of the detection process, which involves elementary particles called muons. The resulting model is invariant to permutations of these muons, thus making MCMC inference prone to label-switching, similarly to what happens with MCMC in mixture models. In addition, our model is high dimensional and involves a lot of correlated variables, which motivates the use of adaptive MCMC, such as the adaptive Metropolis (AM) of Haario et al. (Bernoulli, 2001). However, running AM on our model requires to solve the label-switching online. Building on previous approaches, we present AMOR, a variant of AM that learns together an optimal proposal and an optimal relabeling of the marginal chains. We present applications and state convergence results for AMOR, including a law of large numbers, and demonstrate interesting links between relabeling and vector quantization.
Jeudi 20 Septembre [Amphi Darboux]
[15 h] Orateur : Kengo Kamatani (Graduate School of Engineering Science, Japan)
Titre : Local consistency of MCMC and its application to cumulative link model
Résumé : Cumulative link model is a general model for ordinal data which includes binary probit model as a special case. Bayesian inference for the model is usually performed by a simple data augmentation strategy, which is a kind of Markov chain Monte Carlo (MCMC). However, It is known to work poorly except some simple cases. Two MCMC strategies are described in this talk. One is a simple extension of marginal augmentation strategy and the other is a kind of multi-step MCMC. The efficiency is discussed in terms of local consistency,which is a large sample asymptotic property. We discuss some properties of local consistency and its other applications.
2011 - 2012
Organisateurs : Nicolas CHOPIN et Gersende FORT
Jeudi 14 Juin [Amphi Hermite]
[15h] Orateur : Cyrille Dubarry (Telecom SudParis)
Titre : On the convergence of Island particle models
Résumé : Numerical approximation of Feynman-Kac semigroups by systems of interacting particles is a very active research field. Such methods are increasingly used to sample complex high dimensional distributions and they found a wide range of applications in applied probability, among others filtering, smoothing for non linear state-space models, Bayesian inference of hierarchical models, branching processes in biology, absorption problems in physics.
The sequences of distributions involved are approximated sequentially using interacting particle systems. Such particle approximations are often referred to as sequential Monte-Carlo (SMC) methods. The asymptotic behavior of such particle approximation is now well understood.
Recently, the development of parallel computing methods lead to the study of parallel implementation of this particle approximation. In this paper we focus on the so-called island particle models, consisting in running N2 interacting particle systems each of size N1. This problem gives rise to several questions among which the optimization of the size of the islands N1 compared to the number of islands N2 for a given total computational cost and the opportunity of letting the islands interact.
When the N2 islands are run independently, the bias induced in each of them only depends on their population size N1; thus it can be interesting to introduce an interaction between the islands even though this interaction increases the final estimator variance through the sampling steps. We propose here to study the asymptotic bias and variance in each case so that when N1 and N2 are large and fixed, we can determine which choice is the best in terms of asymptotic mean squared error.
Keywords: Feynman-Kac model, Particle approximation, Island particle model, Asymptotic variance, Asymptotic bias
Joint work with : P. Del Moral (ALEA, INRIA Bordeaux), E. Moulines (LTCI, Telecom ParisTech).
[16 h] Orateur : Julien Cornebise (University College London)
Titre : MCMC Particulaire Adaptatif pour Modèles à Effets Mixtes Stochastiques
Résumé : MCMC Particulaires et MCMC Adaptatives sont une combinaison puissante pour des modèles à structure complexe; nous présentons ici notre expérience sur des modèles non-linéaires à effets-mixtes, basés sur des équations différentielles stochastiques, pour des études longitudinales sur population. Nous expliquons pourquoi la complexité de ces modèles pharmacocinétique/pharmacodynamique, tant au niveau stochastique, que temporel et hiérarchique en fait des terrains de jeux fabuleux pour la statistique computationnelle. L'application d'intérêt est un système de régulation glucose/insuline sur une cohorte de patients; par ailleurs, la même structure de dépendance se retrouve bien au-delà de la pharmacologie: agronomie, retraitement des eaux, sylviculture...
Nous montrons ensuite comment les méthodes de Monte-Carlo adaptatives peuvent fortement améliorer la mélangeance du MCMC Particulaire; en particulier nous exploitons certaines relations d'indépendance conditionnelle pour réduire considérablement le nombre de paramètres à adapter; nous montrons également que ceci permet dans de nombreux cas une proposition exacte des paramètres de population, alternant étapes de Particle Metropolis Hastings et d'échantillonneur de Gibbs. Enfin, nous esquissons des liens avec les extensions récentes de la communauté MCMC pour incorporer les aspects géométriques du modèle en étendant les approches Riemannian Manifold MALA aux chaînes de Markov cachées.
Travaux en cours avec Arnaud Doucet et Gareth W. Peters
Jeudi 10 Mai [Amphi Hermite] Attention, changement d'horaire (exceptionnellement)
[15h30] Orateur : Meili Baragatti (MISTEA, SupAgro)
Titre : Parallel Tempering with Equi-Energy Moves, and Likelihood Free Parallel tempering
Résumé : We will consider the common problem of generating samples from a target density $\pi$, in particular using Population-based Monte Carlo markov Chain approaches. In conventional MCMC methods (Metropolis-Hastings, Gibbs Sampler), a Markov process is built to sample the target probability distribution. But in practice this process can be easily trapped into a local mode from where it cannot escape in reasonable time. Many techniques have been proposed to address this waiting time problem, including among others Parallel Tempering (PT) (see Geyer [1991] or Geyer and Thompson [1995]), and the Equi-Energy Sampler (EES) (Kou et al. [2006]). The EES is based on a population of chains which are updated by local moves and global moves, also called Equi-Energy jumps. The state space is partitioned into energy rings, and the current state of a chain can jump to a past state of an adjacent chain that has an energy level close to its level. This algorithm has been developed to facilitate global moves between different chains, resulting in a good exploration of the state space by the target chain.This method seems to be more efficient than the classical PT algorithm. However the process obtained is non Markovian, it is difficult to use in combination with a Gibbs sampler and it necessitates increased storage. We will present an adaptation of this EES that combines PT with the principle of swapping between chains with same levels of energy. This adaptation, that we shall call Parallel Tempering with Equi-Energy Moves (PTEEM), keeps the original idea of the EES method while generating a Markovian process and requiring less storage. Performances of the PTEEM algorithm will be compared with those of the EES and of the standard PT algorithms in the context of mixture models, and in a problem of identification of transcription factor binding motifs.
In a second part of the presentation, we will present an other Population-based Monte Carlo markov Chain approach which can be use in an Approximate Bayesian Computational (ABC) framework (or likelihood-free framework). ABC methods have appeared in the past fifteen years as useful methods to perform Bayesian analysis when the likelihood is analytically or computationally intractable. Several approaches have been proposed: Monte Carlo Markov Chains (MCMC) methods have been developed by Marjoram et al. [2003] and by Bortot et l. [2007] for instance, and sequential methods have been proposed among others by Sisson et al. [2007], Beaumont et al. [2009] and Del Moral et al. [2012]. Until recently, while ABC-MCMC methods were the reference, sequential ABC methods have appeared to outperform them (see for example McKinley et al. [2009] or Sisson et al. [2007]). We will present a new algorithm combining population-based MCMC methods with ABC requirements, using an analogy with the Parallel Tempering algorithm.
Joint work with A. Grimaud, D. Pommeret.
Références :
Baragatti M, Grimaud A, Pommeret D. Likelihood-Free Parallel Tempering, Statistics and Computing, in press, 2012.
Baragatti M, Grimaud A, Pommeret D. Parallel tempering with Equi-Energy moves, Statistics and Computing, in press, 2012.
[16h40] Orateur : Kerrie Mengersen (Queensland Univ. of Technology , Australia)
Titre : Understanding images: from inferential aims to models to algorithms
Résumé : In the excitement of working with algorithms, it is sometimes salutory to remind ourselves of their purpose. In this presentation, we consider the analysis of image data and try to match inferential aims, models and computational methods. We describe and compare the approaches in the context of some real case studies in agriculture and environmentalmonitoring.
Jeudi 12 Avril [Amphi Darboux]
[15h] Orateur : Pierre Jacob (ENSAE) et Robin Ryder (CEREMADE)
Titre : Some aspects of the Wang-Landau algorithm.
Résumé : The Wang-Landau algorithm is an adaptive MCMC algorithm which generates a Markov chain designed to move efficiently in the state space, by constantly penalizing already-visited regions. It hence falls into the class of exploratory algorithms, especially when the chosen regions correspond to different levels of density values. We explore two novel aspects of the Wang-Landau algorithm. First, we show that the algorithm reaches the so-called Flat Histogram criterion in finite time, which ensures convergence properties. Second, we examine the effect of using multiple chains, interacting through a common component. That component essentially represents the history of already-visited regions, computed on all the chains. We show numerically the benefit of using parallel chains even if a single processing unit is available, in terms of stabilization of the schedule used in the adaptation process. If time permits, we shall present an ongoing attempt to study theoretically the effect of parallelization using Feynman-Kac semigroups.
Références http://arxiv.org/abs/1110.4025 et http://arxiv.org/abs/1109.3829
[16h] Orateur : Nick Whiteley ( Univ. Bristol, UK)
Titre : A particle method for approximating principal eigen-functions and related quantities
Résumé : Perron-Frobenius theory treats the existence of a positive eigen-vector associated with the principal eigen-value \lambda_{\star} of a non-negative matrix, say Q. A simple method for approximating this eigen-vector involves computing the iterate \lambda_{\star}^{-n}Q^{(n)}, for large n. In the more general case that Q is a non-negative integral kernel, an extended Perron-Frobenius theory applies, but it is typical that neither the principal eigen-function nor the iterate \lambda_{\star}^{-n}Q^{(n)} can be computed exactly. In this setting we introduce an interacting particle algorithm which yields a numerical approximation of the principal eigen-function and the associated twisted Markov kernel. Some of its theoretical properties will be discussed and applications will be outlined. In particular, the algorithm allows approximation of an optimal importance sampling method for Markov chain rare event estimation.
Joint work with Nikolas Kantas.
Référence : http://arxiv.org/abs/1202.6678
Jeudi 15 Mars [salle 314]
(séminaire annulé)
Jeudi 9 Février [Amphi Darboux]
[15h] Orateur : A. Kebaier (LAGA, Paris 13)
Titre : Central limit theorem for the multi-level algorithm
Résumé : This paper deals with the problem of the multi-level Monte Carlo method, introduced by Giles (Multilevel Monte Carlo path simulation Operations Research, 2008; 56:607-617) as an extended method of the statistical Romberg one of Kebaier (Romberg Extrapolation: A New Variance Reduction Method and Applications to Option Pricing. Ann. Appl. Probab. 15 (2005),no. 4, 2681-2705). When approximating the expected value of a function of a stochastic differential equation solution, these methods improve efficiently the computational complexity of standard Monte Carlo. In this work, we analyze the asymptotic error of this algorithm and establish a central limit theorem based on a new stable functional central limit theorem on the error in the Euler scheme for a given level. This allows us to obtain the optimal choice of the parameters method. Then, we investigate the application of this method to the pricing of Asianoptions. In this setting, the approximation relies on the discretization of the integral of the price process over a time interval. We also analyze the error process and prove a stable functional central limit theorem. Finally, We use our result in order to optimize the choice of the parameters, which are different from the ones in the Euler scheme. Numerical simulations were processed.
[16h15] Orateur : N. Chopin (CREST)
Titre : SMC2: A sequential Monte Carlo algorithm with particle Markov chain Monte Carlo updates
Résumé : We consider the generic problem of performing sequential Bayesian inference in a state-space model with observation process y, state process x and fixed parameter theta. An idealized approach would be to apply the iterated batch importance sampling (IBIS) algorithm of Chopin (2002). This is a sequential Monte Carlo algorithm in the theta-dimension, that samples values of theta, reweights iteratively these values using the likelihood increments p(y_t|y_1:t-1, theta), and rejuvenates the theta-particles through a resampling step and a MCMC update step. In state-space models these likelihood increments are intractable in most cases, but they may be unbiasedly estimated by a particle filter in the x-dimension, for any fixed theta. This motivates the SMC^2 algorithm proposed in this article: a sequential Monte Carlo algorithm, defined in the theta-dimension, which propagates and resamples many particle filters in the x-dimension. The filters in the x-dimension are an example of the random weight particle filter as in Fearnhead et al. (2010). On the other hand, the particle Markov chain Monte Carlo (PMCMC) framework developed in Andrieu et al. (2010) allows us to design appropriate MCMC rejuvenation steps. Thus, the theta-particles target the correct posterior distribution at each iteration t, despite the intractability of the likelihood increments. We explore the applicability of our algorithm in both sequential and non-sequential applications and consider various degrees of freedom, as for example increasing dynamically the number of x-particles. We contrast our approach to various competing methods, both conceptually and empirically through a detailed simulation study, included here and in a supplement, and based on particularly challenging examples.
Joint work with Pierre E. Jacob, and Omiros Papaspiliopoulos.
Référence : Paper available at: http://arxiv.org/abs/1101.1528
Jeudi 12 Janvier [Amphi Darboux]
[15h] Orateur : S. Allassonnière (CMAP, Ecole Polytechnique)
Titre : Anisotropic Metropolis Adjusted Langevin Algorithm: convergence and utility in Stochastic EM algorithm
Résumé : Sampling a random variable in a high dimensional framework becomes a crucial issue regarding the large range of applications which require such samples, such as image analysis. The Langevin simulation method is well adapted in this context. However, the use of an isotropic covariance matrix usually prevents from a numerical convergence which suffers from the low acceptation rate. In this work, we propose to adapt the Langevin simulation taking into account the anisotropy of the distribution to sample from. We prove that this new algorithm leads to a uniform ergodic Markov chain. Moreover, we apply this new Monte Carlo Markov Chain method into a stochastic Expectation-Maximization algorithm in order to estimate some model parameter by maximizing the likelihood. We prove that under mild conditions, the estimated parameters converge almost surely and are asymptotically Gaussian distributed. All this pipeline is numerically tested on handwritten digits and some medical images for the deformable template estimation.
[16h15] Orateur : A. Fulop (Essec)
Titre : Bayesian Learning of Impacts of Self-Exciting Jumps in Returns and Volatility
Résumé : The paper proposes a new class of continuous-time asset pricing models where negative jumps play a crucial role. Whenever there is a negative jump in asset returns, it is simultaneously passed on to diffusion variance and the jump intensity, generating self-exciting co-jumps of prices and volatility and jump clustering. To properly deal with parameter uncertainty and in-sample over-fitting, a Bayesian learning approach combined with an efficient particle filter is employed. It not only allows for comparison of both nested and non-nested models, but also generates all quantities necessary for sequential model analysis. Empirical investigation using S&P 500 index returns shows that volatility jumps at the same time as negative jumps in asset returns mainly through jumps in diffusion volatility. We find substantial evidence for jump clustering, in particular, after the recent financial crisis in 2008, even though parameters driving dynamics of the jump intensity remain difficult to identify.
Référence : http://www.andrasfulop.com/home/Self_Exciting_Dec14.pdf?attredirects=0
Jeudi 8 décembre [salle 314]
[15h] Orateur : S. Le Corff (LTCI)
Titre : Block online EM for hidden Markov models with application to parameter estimation in general state-spaces
Résumé : The EM algorithm has been successfully applied for ML inference in HMM. However, when processing large data sets or data streams, the EM algorithm might become computationally very intensive and different online variants have been recently proposed. Despite the encouraging first results, the convergence of these algorithms remain an open question in the common framework of general state-spaces. In this contribution, we propose a new online EM algorithm, the block online EM algorithm. In this block online EM algorithm, the M-step (and thus, the update of the parameter) occurs at some deterministic times known in advance.The k-th (block) E-step consists in the computation of a mean value of the sufficient statistics associated to the observations in the k-th block. This algorithm relies on the ability to compute this mean value sequentially, i.e. without storing all the observations. At the end of the block, the parameter is updated based on a weighted average of all the mean statistics (over the successive blocks). The convergence properties of this algorithm are addressed for HMM models for which expectations under the joint smoothing distribution can be computed explicitly (e.g. finite state space or linear Gaussian model) and for a stochastic variant based on Sequential Monte Carlo methods in the case of more general models. The behavior of the proposed algorithms is numerically evaluated for different models.
[16h15] Orateur : T. Lelièvre (CERMICS)
Titre : Generating efficiently metastable dynamics
Résumé : We will present two methods to sample metastable trajectories of solutions to some stochastic differential equations which are used in molecular dynamics. Naive approaches are typically inefficient since transitions between two given metastable states are very rare. The interest of such sampling techniques is to obtain typical transition paths between two metastable regions, to compute some reaction rates, to determine the transition states, etc.
The first method is an adaptation of the Adaptive Multilevel Splitting approach proposed by F. Cérou and A. Guyader in 2007. The idea is to select trajectories which go the most far in some given direction. We have recently used this technique on simple test cases, and most of the mathematical analysis remains to be done [1].
The second method (the parallel replica method) is an algorithm which has been proposed by A. Voter in 1997. It is in particular used in molecular dynamics simulations in material sciences. We have recently analyzed mathematically this algorithm [2]. The quasi stationary distribution plays a crucial role in the analysis.
[1] F. Cérou, A. Guyader, T. Lelièvre and D. Pommier, A multiple replica approach to simulate reactive trajectories, Journal of Chemical Physics, 134, 054108, (2011).
[2] C. Le Bris, T. Lelièvre, M. Luskin and D. Perez, A mathematical formalization of the parallel replica dynamics, http://hal.archives-ouvertes.fr/hal-00596161/fr/ .
Mardi 15 Novembre
Exceptionnellement, le séminaire est remplacé par une journée scientifique qui aura lieu à Telecom ParisTech. Voir site web
Jeudi 13 Octobre [Amphi Hermite]
[15h] Orateur : B. Miasojedow (LTCI, Paris)
Titre : Nonasymptotic bounds on the estimation error of MCMC algorithms
Résumé : MCMC methods are used not only to sample from posterior distributions but also to estimate expectations. We derive bounds on the mean square error of MCMC estimators. Our analysis is non-asymptotic. We first establish a general result valid for essentially all ergodic Markov chains encountered in Bayesian computation and a possibly unbounded target function f. Assuming minorization condition we cut the trajectory by regeneration technique into iid blocks. In further analysis we use tools of statistical sequential analysis and renewal theory, such as Wald's identities and Lorden's theorem. The bound is sharp in the sense that the leading term is equal to the well known aspymptotic results. Next, we proceed to specific assumptions (drift and minorization conditions) and give explicit computable bounds for geometrically and polynomially ergodic Markov chains. In both cases final results are in terms of computable quantities which appear in the drift and minorization conditions. The talk is based on a joint paper with K. Latuszynski and W. Niemiro.
[16h15] : Pas de séminaire / Réunion du projet BigMC
Jeudi 1er Septembre [salle 201]
Orateur : X-L. Meng (Univ. Harvard, USA)
Titre : Statistical Inception for the MCMC Dream: The kick is in the residual (augmentation)!
Résumé : The development of MCMC algorithms via data augmentation (DA) or equivalently auxiliary variables has some resemblance to the theme plot of the recent Hollywood hit Inception. We MCMC designers all share essentially the same ?3S? dream, that is, to create algorithms that are simple, stable, and speedy. Within that grand dream, however, we havecreated a rather complex web of tools, with some of them producing very similar algorithms but for unclear reasons, or others that were thought to be of different origins but actually are layered when viewed from a suitable distance. These include conditional augmentation, marginal augmentation, PX-DA, partially non-centering parameterization, sandwiched algorithms, interweaving strategies, ASIS, etc. It turns out that there is a simple statistical insight that can unify essentially all these methods conceptually, and it also provides practical guidelines for their DA constructions. It is the simple concept of regression residuals, which are constructed to be orthogonal to the regression functions. All these methods in one form or anothereffectively build a residual augmentation. Given a DA distribution f(T,A), where T is our targeted variable (i.e., f(T) is our targeted distribution) and A is the augmented variable, there are two broad classes of residuals depending on whether we regress T on A or A on T. In this talk we will demonstrate how methods like conditional augmentation and partially non-centering parameterization build their residual augmentations by regressing A on T, whereas methods such as marginal augmentation and ASIS effectively use residual augmentations from regressing T on A. For either class, the attempted orthogonality helps to reduce the dependence among MCMC draws, and when the orthogonality leads to true independence as occurring in some special cases, we reach the dream of producing i.i.d. draws. (The talk is based on an upcoming discussion article, especially its rejoinder, Yu and Meng (2011, JCGS) )
2010 - 2011
Organisateurs : Nicolas CHOPIN et Gersende FORT
Jeudi 9 Juin [Salle 314]
[15 h] Orateur :H. F. Lopes (Univ. of Chicago, US)
Titre : Parsimonious Bayesian Factor Analysis when the Number of Factors is Unknown
Résumé : We introduce a new and general set of identifiability conditions for factor models which handles the ordering problem associated with current common practice. In addition, the new class of parsimonious Bayesian factor analysis leads to a factor loading matrix representation which is an intuitive and easy to implement factor selection scheme. We argue that the structuring the factor loadings matrix is in concordance with recent trends in applied factor analysis. Our MCMC scheme for posterior inference makes several improvements over the existing alternatives while outlining various strategies for conditional posterior inference in a factor selection scenario. Four applications, two based on synthetic data and two based on well known real data, are introduced to illustrate the applicability and generality of the new class of parsimonious factor models, as well as to highlight features of the proposed sampling schemes. (Joint work with Sylvia Fruhwirth-Schnatter, Univ. of Linz - Austria).
[16h15] Orateur : A. Eberle (Univ. Bonn, Germany)
Titre : Mixing times of Metropolis-adjusted Langevin algorithms for log-concave probability measures in high dimensions
Résumé : The Metropolis-adjusted Langevin algorithm (MALA) is a Metropolis-Hastings algorithm for approximate sampling from continuous distributions. We derive upper bounds for the distance from equilibrium after a finite number of steps for MALA with semi-implicit Euler proposals applied to log-concave perturbations of Gaussian measures. For sufficiently ``regular´´ perturbations, the estimates are dimension-independent in a sense to be specified.
Jeudi 5 Mai [Salle 314]
[15 h] Orateur : M. Vihola (Univ. Jyvaslyla, Finlande)
Titre : Stability of adaptive random-walk Metropolis algorithms
Résumé : Most results on adaptive MCMC in the literature are based on assumptions that require the adaptation process to be `stable' (in a certain sense). Such stability can rarely be established, unless the process is modified by introducing specific stabilisation structures. This talk outlines recent stability and ergodicity results for adaptive MCMC algorithms without such stabilisation. The key idea behind the results is that the ergodic averages can converge even if the Markov kernels gradually `lose' their ergodic properties.
[16h15] Orateur: B. Bouzy (Univ. Descartes, Paris)
Titre : Monte-Carlo Tree Search for the game of Go
Résumé : This talk describes Monte-Carlo Tree Search (MCTS) the successful technique now used in many complex games such as the game of Go. In a first part, the talk reminds the results achieved by old go programs until 2003, i.e. medium on the human scale. This average result was firstly caused by the game tree size that forbids global tree search. Building an accurate evaluation functions for non terminal positions was the second difficulty. These difficulties lead to erratic behaviour of go programs until 2003. In a second part, the talk shows how the Monte-Carlo (MC) approach has simplified the computer go between 2003 and 2006. To evaluate a non terminal position, the MC method consists in launching random games starting from this position, and playing them out until terminal positions, easy to score, are reached. The MC evaluation of a position is the mean of the scores encountered. MC evaluations cost a lot of time, but they are robust, and their precision improves with the time available. In a third part, the talk shows the success of MCTS since 2006. MCTS cleverly integrates tree search and simulations. MCTS progressively builds a tree whose nodes contain statistics about simulations. While thinking time is available, MCTS repeatedly executes four stages: the selection stage (browsing the tree from the root to a leaf), the expansion stage (adding a new node), the simulation stage (performing the simulation until the end of the game et getting the outcome) and the update stage (updating node values). MCTS resulted in a big improvement of Go programs. On 9x9 boards the best playing programs reached human professional level. On 19x19 boards, the best playing programs reached human strong amator level. In a last part, the talk shows how MCTS can be refined. First, using domain-dependent knowledge is advised in the selection and simulation stages. Reinforcement learning or supervised learning can be used to automatically learn this knowledge. Second, the selection stage can be very efficient with the RAVE (Rapid Action Value Estimation) heuristic. Parallelization is a third mandatory tool to demonstrate the power of MCTS in go. Before conclusion, the talk shows the remaining obstacles and future works.
Jeudi 7 Avril [Salle 314]
[15 h] Orateur : O. Papaspiliopoulos (Univ. P. Fabra, Barcelone)
Titre : Bayesian inference of coefficients of diffusion processes using data augmentation
Résumé : We consider estimation of scalar functions which determine the dynamics of diffusion processes. It is known that nonparametric maximum likelihood is ill-posed in this context. We adopt a probabilistic approach to regularize the problem by the adoption of a prior distribution for the unknown functional. Our first result is that a Bayesian Gaussian conjugate analysis for the drift of one-dimensional non-linear diffusions is feasible given high-frequency data. This is achieved by expressing the log-likelihood as a quadratic function of the drift, with sufficient statistics given by the so-called local time process and the end points of the observed path. We show how to implement such analysis using flexible and amenable to efficient computations Gaussian Markov process priors. We provide a simple estimator of the local time and a finite element method for the numerical derivation of the posterior mean and precision, as well as the posterior simulation of the unknown functional. We embed this technology in partially observed situations and adopt a data augmentation approach whereby we iteratively generate missing data paths and draws from the (conditionally) Gaussian posterior distribution of the functional given complete data. Our methodology is applied to estimate the drift of models used in molecular dynamics and financial econometrics using high and low frequency, real and simulated, data. We discuss extensions to other partially observed schemes, connections to other types of non/semi-parametric inference, and to estimation of vector-valued functions.
Joint work with Pokern, Roberts and Stuart.
[16h15] Orateur : P. Bui Quang (ONERA Palaiseau)
Titre : High-dimensional importance sampling: An analysis via the Laplace method
Résumé : Several authors have underlined that importance sampling for Bayesian inference often behaves poorly when the dimension of the parameter of interest is large. We consider here the asymptotic variance of the importance weights to quantify the impact of dimensionality on the inference. To calculate this variance, we propose to use the Laplace method, which allows us to approximate accurately multidimensional integrals. When applied in a Bayesian framework, the approximation converges with respect to the data size. We use this method to calculate the asymptotic variance of the importance weights, and in particular to analyze its dependence on the dimension.
Travail en collaboration avec C. Musso (ONERA Palaiseau) et F. Le Gland (INRIA Rennes).
Jeudi 3 Mars [Salle 201]
[15 h] Orateur : O. Feron (EDF)
Titre : Echantillonnage de champs gaussiens de grande dimension : le cas non creux / non circulant
Résumé : Ces travaux ont été menés par François Orieux, Post-doc à l'institut Pasteur, Jean-François Giovannelli, professeur au laboratoire de l'intégration du matériau au système de l'université de Bordeaux, et moi-même. Dans un premier temps, nous proposons une nouvelle approche pour l'échantillonnage de champs gaussiens corrélés dans le cas où lesapproches classiques ne sont pas utilisables : lorsque la dimension du problème est très grande et lorsque la matrice inverse de covariance (ou matrice de précision) n'est pas creuse et n'est pas circulante. Cette approche est valide dans le cas où une structure particulière de la matrice de précision est disponible. Cette structure apparaît dans la résolution de problèmes inverses par des méthodes d'estimation bayésienne. L'algorithme proposé trouve une application directe pour les méthodes d'inversion myopes et/ou non supervisées, fondées sur des méthodes d'échantillonnage de type MCMC. L'efficacité de cette approche est illustrée sur l'inversion non supervisée d'un problème de super résolution d'images. Aujourd'hui, nous étudions des extensions à cet algorithme dans le but d'accélérer les algorithmes MCMC mis en oeuvre. Dans ce but, nous énoncerons les différentes pistes envisagées et les difficultésrencontrées pour assurer la convergence des algorithmes MCMC.
[16h15] Orateur : O. Cappé (LTCI)
Titre : L'algorithme EM en ligne et ses possibles extensions Monte Carlo
Résumé : Dans cet exposé, je décrirai le principe de l'algorithme EM en ligne (ou adaptatif) qui a pour but d'estimer les paramètres d'un modèle à données latentes (a priori à partir d'observations indépendantes) en incorporant les observations une à une. Je présenterai également une façon légèrement différente d'utiliser l'algorithme ayant pour but de déterminer l'estimateur du maximum de vraisemblance correspondant à un ensemble fixé d'observations (ce qui en fait un concurrent direct de l'algorithme EM classique). Après une discussion des propriétés de convergence de l'algorithme, je présenterai des travaux en cours sur des extensions de l'approche en particulier à des cas où l'étape E de l'algorithme EM en ligne nécessite l'utilisation de simulations Monte Carlo.
Réf. O. Cappé and E. Moulines. On-line Expectation-Maximization Algorithm for Latent Data Models. J. Royal Statist. Soc. B, 71(3):593-613, 2009.
Jeudi 3 Février [Salle 314]
[15h] Orateur : F. Perron (Univ. de Montréal, Canada)
Titre : Estimation de copules, une approche bayésienne
Résumé : La copule associée à un couple aléatoire continu (X,Y) est une mesure de dépendance qui est invariante pour les transformations monotones sur X et Y. Cette mesure a une forme particulière dans le cas des valeurs extrêmes qui fait intervenir la fonction de dépendance de Pickands ( fonction convex sur [0,1] avec conditions aux bornes ). On cherche à estimer la fonction de Pickands. Pour cela nous allons constuire des modèles bayésiens. Ces modèles seront motivés par une construction géométrique, un lien avec la mesure spectrale et une utilisation des polynômes. L`aspect computationnel va prendre une place très importante. Nous allons discuter du comment faire les calculs en faisant appel à des méthodes de simulation basées sur les chaînes de Markov. Finalement, on traitera le problème standard où les variables ne sont pas à valeurs extrêmes.
[16h15] GdT : J. Rousseau (Univ. Dauphine / CREST)
Référence : Y. Pokern, O. Papaspiliopoulos, G.O. Roberts ans A. Stuart. Nonparametric Bayesian drift estimation for one-dimensional diffusion processes, submitted to the Ann.Statist. Available in pdf
Jeudi 6 Janvier [Salle 314]
[15h] Orateur : J.L. Foulley (INRA)
Titre : Calcul de la vraisemblance marginale par la méthode des posteriors de puissance : rappels et applications
Résumé : Cet exposé se place dans le cadre des méthodes de calcul de la vraisemblance marginale après intégration des paramètres par rapport à leur densité a priori. Après un bref rappel des principales méthodes standard (Importance Sampling, Newton & Raftery, Gelfand & Dey, Chib, « Bridge sampling » notamment), l'exposé se focalisera sur la méthode des posteriors de puissance de température due à Friel & Pettitt (2008). Nous rappellerons les fondements théoriques de la méthode et discuterons de sa mise en Å“uvre calculatoire. Nous évoquerons ses liens avec l'approche du facteur de Bayes fractionnaire d'O Hagan et avec le critère DIC. Nous montrerons comment cette méthode peut être implantée sous Winbugs. Nous illustrerons le propos par deux exemples : l'un relatif à l'analyse de données longitudinales par des modèles mixtes, et l'autre, ayant trait à l'analyse de différenciation génétique de marqueurs moléculaires SNP par des modèles bayésiens hiérarchiques simples.
Référence : Friel N, Pettitt AN (2008) Marginal likelihood estimation via power posteriors, JRSS, B, 70, 589-607
[16h15] Orateur : G. Celeux (INRIA, Futur)
Titre : Méthodes d'estimation pour le modèle des blocs latents.
Résumé : Le modèle des blocs latents est un modèle de mélange proposé par Govaert et Nadif (2007) qui permet la classification conjointe des lignes et des colonnes d'un tableau de données. Après sa présentation, nous comparerons différentes méthodes d'estimation des paramètres de ce modèle pour lequel l'inférence pose des difficultés. Nous évoquerons une approximation variationnelle de l'algorithme EM (Govert et Nadif 2007), une version stochastique de EM de type EM à la Gibbs et une approche bayésienne proposée par Wyse et Friel (2010). Pour finir le problème du choix d'un nombre de blocs sera évoqué et ses particularités souligné.
Govaert and Nadif (2007) Block Clustering with Bernoulli miture models: Comparison of different approaches. Computational Statistics and Data Analysis 52, 3233-3245.
Wyse and Friel (2010) Block clustering with collapsed latent block model. In revision for Statistics and Computing
Jeudi 2 Décembre [Salle 314]
Séance annulée
Jeudi 18 Novembre
[15h] Orateur : D. Woodard (Cornell Univ., USA)
Titre : Convergence rate of Markov chain methods for genomic motif discovery
Résumé : We analyze the convergence rate of a popular Gibbs sampling method used for statistical discovery of gene regulatory binding motifs in DNA sequences. This sampler satisfies a very strong form of ergodicity (uniform ergodicity). However, we show that, due to multimodality of the posterior distribution, the rate of convergence often decreases exponentially in the length of the DNA sequence. Specifically, we show exponential or polynomial decay for several cases, which support the conjecture that the decay is exponential if and only if more than one true repeating pattern exists in the data. Since there are typically multiple, even numerous, such patterns in real data (the goal being to detect well-conserved and frequently-occurring patterns), we argue that the Gibbs sampler rate of convergence decays exponentially in practice.
This matches empirical results, which find such poor mixing of the motif-discovery Gibbs sampler that it is used only for discovering modes of the posterior distribution (candidate motifs). This is one of the first examples of a Markov chain method that provably fails to obtain samples from the posterior distribution of a statistical model within polynomial time.
[16h15] GdT : C. Schäfer (CREST, Paris)
Titre : Adaptive Monte Carlo on multivariate binary sampling spaces
Résumé : A Monte Carlo algorithm is said to be adaptive if it can adjust automatically its current proposal distribution using past simulations. The choice of the parametric family that defines the set of proposal distributions is critical for good performance. In this paper, we discuss such parametric families for adaptive sampling on multivariate binary spaces. A practical motivation for this problem is variable selection in a linear regression context. We want to sample from a Bayesian posterior distribution on the model space using Sequential Monte Carlo for sampling and the Cross-Entropy method for optimization. Raw versions of the algorithm are easily implemented using binary vectors with independent components. For high-dimensional variable selection problems, however, these straightforward proposals do not yield satisfactory results. The key to efficient adaptive algorithms are binary parametric families which take correlations into account, analogously to the multivariate normal distribution on continuous spaces.
Article : arXiv
Jeudi 7 Octobre [Salle 314]
[15h] Orateur : A. Samson (Paris V)
Titre : Estimation pour des modeles mixtes définis par équations différentielles stochastiques via l'algorithme SAEM et un filtre particulaire
Résumé : Les données longitudinales biologiques peuvent être analysées par des modèles mixtes définis par une équation différentielle stochastique (EDS). L'estimation par maximum de vraisemblance dans ces modeles est complexe, la vraisemblance n'étant pas explicite. L'algorithme SAEM (Delyon et al, 1999) a été proposé pour l'estimation des modeles mixtes mais n'est pas adapté au cas des modeles définis par EDS. Dans ce travail, nous proposons de coupler l'algorithme SAEM avec un algorithme PMCMC (Andrieu et al, 2010), ce qui permet de realiser de facon efficace l'etape E de l'algorithme EM. Nous montrons la convergence de notre algorithme vers le maximum de vraisemblance. Nous illustrons notre approche sur deux exemples, un processus d'Ornstein-Ulhenbeck et un modele à volatilité stochastique non homogène en temps très utilisé pour modéliser des courbes de croissance.
[16h15] Orateur : G. Fort (LTCI, CNRS)
Groupe de Travail : Approximation stochastique et Algorithmes MCMC adaptatifs
Résumé : Nous présenterons quelques résultats récents sur la convergence d'échantillonneurs MCMC adaptatifs lorsque le mécanisme d'adaptation se fait selon une dynamique d'approximation stochastique. Nous verrons que la convergence du processus d'adaptation n'est pas nécessairement requise, ni même sa stabilité. Nous illustrerons nos propos en considérant l'algorithme "adaptive Metropolis" proposé par Haario et al. (1999); et l'algorithme Equi-Energy proposé par Kou et al. (2006). Discussion à partir des résultats énoncés dans
M. Vihola (2010) On the Stability and Ergodicity of an Adaptive Scaling Metropolis Algorithm, Preprint [format pdf]
E. Saksman and M. Vihola (2010) On the Ergodicity of the Adaptive Metropolis Algorithm on Unbounded Domains , Ann.Appl. Probab. [format pdf]
G. Fort, E. Moulines et P. Priouret (2010) Convergence of adaptive MCMC algorithms: ergodicity and law of large numbers, Preprint [format pdf]
2009 - 2010
Organisateurs : Nicolas CHOPIN , Gersende FORT et Pierre VANDEKERKHOVE
Jeudi 10 Juin 2010 [Salle 201]
[15h] Orateur : Yves Atchadé (Univ. Michigan, USA)
Titre : Asymptotic variance estimation for Adaptive Markov Chain Monte Carlo.
Résumé : Broadly speaking, Adaptive Markov Chain Monte Carlo (MCMC) corresponds to MCMC algorithms where the transition kernel is allows to change with the iterations. Such an approach to Monte Carlo simulation is now better understood and conditions are known under which these algorithms are ergodic, satisfy a law of large numbers and a central limit theorem. We take the discussion one step further and consider the problem of estimating the asymptotic variance of adaptive MCMC estimates. We will see that the behavior of the asymptotic variance estimators is closely related to the asymptotic behavior of the adaptation parameter.
[16h15] (ANNULE) Orateur : David Dunson (Duke Univ., USA)
Titre : Sparse nonparametric Bayesian latent factor models for high-dimensional data
Résumé : In many application areas, massive dimensional predictors are routinely collected, with some of these predictors being moderately to highly correlated. Standard Bayes and frequentist methods tend to select one of a correlated group of predictors, and have trouble scaling to very high dimensions (10,000 or more predictors). Sparse latent factor regression models represent a promising approach for dealing with this problem, but current approaches rely on restrictive normality and linearity assumptions. For greater flexibility and to enable a greater degree of dimensionality reduction, we propose a sparse non-linear factor modeling framework. The proposed model relates the high-dimensional measured variables to a non-linear transformation of a low-dimensional vector of latent variables. A carefully structured Gaussian process prior is chosen for the unknown transformation function, with the prior being centered on a sparse linear factor model. The proposed structure allows for the inclusion of infinitely-many factors with the impact of these factors on the response decreasing in the factor index, so that an adaptive truncation can be chosen with all factors above a certain index discarded with negligible impact. Theoretical results are considered and efficient methods are developed for posterior computation via blocked Gibbs sampling combined with grid approximations. The methods are assessed in simulation studies, compared to competitors such as elastic net, and applied to gene expression data.
Joint work with Anirban Bhattacharya
Jeudi 27 Mai 2010 [Salle 201]
[15h] Orateur : Sylvain Rubenthaler (Univ. de Nice)
Titre : Développement dans la propagation du chaos pour les systèmes de Bird et Nanbbu.
Résumé : Les systèmes de Bird (et Nanbu) sont des systèmes de particules en interaction dont la mesure empririque approche la solution de l'équation de Bolzmann mollifiée. Je montrerai dans cet exposé comment l'étude fine de la propagation du chaos permet de récupérer un TCL pour ce type de système. L'exposé sera basé sur des raisonnements probabilistes élémentaires (dont un couplage facile).
[16h15] Orateur : Laure Amate (IMAG, Grenoble)
Titre : Application d'une variante de l'EM à l'apprentissage de modèles de courbes.
Résumé : Dans de nombreuses situations, nous voulons trouver des représentations pour les propriétés collectives d'un ensemble d'objets. Ici, les objets sont des contours (2D) extraits d'images et donc des courbes simples fermées et nous choisissons comme représentation les courbes splines pour leur compacité et leur flexibilité. Notre modèle est alors basé sur la définition d'une famille paramétrique de distributions sur l'espace des paramètres des splines. L'identification des paramètres du modèle repose sur l'utilisation d'un critère de maximum de vraisemblance et, comme il n'a pas de solution analytique, nous proposons une variante de l'algorithme Expectation-Maximization (EM) pour résoudre le problème d'estimation. Nous illustrons enfin cette approche sur des données simulées puis sur des données réelles.
Jeudi 15 Avril 2010 [Salle 201]
[15h] Orateur : Omiros Papaspiliopoulos (Univ. Pompeu Fabra, Barcelone)
Titre : Making black boxes out of black boxes - the Bernoulli Factory problem and its applications
Résumé : [Slides disponibles] Assume that a black box generating p-coins is available and 0< p< 1 is unknown. Is it possible to use these p-coins and generate a min(1,2p)-coin? Given a known function f, is it possible to obtain an f(p)-coin? The problem, in a simplified form, originates from John von Neumann and naturally arises in several problems in stochastic simulation, e.g exact simulation of diffusions. I will present a reverse time martingale approach that offers a constructive solution. This is joint work with Ioannis Kosmidis, Krzystof Latuzsynski, Gareth O. Roberts (Warwick), and corresponds to an article which is to appear in Random Structures and Algortithms (available from CRiSM preprint web page)
[16h15] Orateur : Pierre Jacob (ENSAE)
Groupe de Travail : Particle Markov Chain Monte Carlo
Résumé : Discussion du papier Particle Markov Chain Monte Carlo, de C. Andrieu, A. Doucet & R. Holenstein, disponible à l'adresse suivante:http://www.rss.org.uk/pdf/Andrieu_et_al._14.10.09.pdf L'article se situe dans le cadre des modèles à chaîne de Markov cachée. Dans ces modèles on s'intéresse typiquement à la distribution des états cachés sachant les observations, et à la distribution des paramètres sachant les observations (loi a posteriori dans une approche bayésienne). La méthode proposée permet de simuler un échantillon suivant la loi jointe des paramètres et des états cachés sachant les observations, ce qui correspond à la fois au filtrage et à l'estimation des paramètres; la nouveauté réside surtout dans l'estimation des paramètres et rend cet article particulièrement ambitieux. L'objectif de la séance est d'étudier en détail les différents algorithmes proposés par l'article ainsi que leurs propriétés de convergence, et de comparer la méthode aux différentes approches existantes (EKF, MCMC, filtres régularisés et autres).
Jeudi 25 Mars 2010 [Salle 314]
[15h] Orateur : Estelle Kuhn (INRA, Jouy-en-Josas)
Titre : Estimation par maximum de vraisemblance dans un modèle de fragilité via un algorithme EM stochastique
Résumé : Le modèle de Cox (1972) joue un rôle essentiel en analyse de survie. Une hypothèse classique sous-jacente est l'indépendance des données. Mais cette hypothèse n'est souvent pas vérifiée du fait de l'hétérogénéité intrinsèque à la population observée. Les modèles de fragilité, qui prennent en compte cette hétérogénéité en introduisant un effet aléatoire, ont été introduit par Vaupel et al. en 1979.
Pour estimer les paramètres dans les modèles de fragilité, on considère en général la vraisemblance observée et l'estimateur du maximum de vraisemblance associé. Mais il est souvent difficile voir impossible de le calculer directement. Pour résoudre ce problème, les variables aléatoires de fragilité étant non observées, on peut se placer dans le contexte plus général des modèles à variables latentes. Pour approcher l'estimateur du maximum de vraisemblance observée dans de tels modèles, on a généralement recours à l'algorithme Expectation Maximization (EM) proposé par Dempster et al. en 1977. Cependant, il n'est pas applicable dans beaucoup de cas pratiques. Plusieurs auteurs ont donc proposé des approximations de cet algorithme dans le but de pouvoir l'appliquer plus largement.
Nous proposons un algorithme convergent pour l'estimation par maximum de vraisemblance dans les modèles de fragilité. Nous considérons une approximation stochastique de l'algorithme EM couplé à une méthode de Monte Carlo par chaînes de Markov (SAEM-MCMC) proposé par Kuhn et Lavielle en 2004. La suite générée par cet algorithme converge presque sûrement vers un maximum local de la vraisemblance sous des hypothèses raisonnables. Cet algorithme reste rapide bien que faisant appel à la simulation du fait de l'imbrication astucieuse des deux méthodes SAEM et MCMC. Nous présentons des applications sur données simulées et réelles de cancer de la vessie.
Travail en collaboration avec Charles El-Nouty, Université Paris Nord, Unité de Recherche en Epidémiologie Nutritionnelle.
[16h15] Orateur : Gabriel Stoltz (CERMICS, ENPC)
Titre : Optimal tuning of the Hybrid Monte-Carlo Algorithm
Groupe de Travail : Je présenterai l'article "Optimal tuning of the Hybrid Monte-Carlo Algorithm" par Alexandros Beskos, Natesh S. Pillai, Gareth O. Roberts, Jesus M. Sanz-Serna, Andrew M. Stuart (http://arxiv.org/abs/1001.4460), avec deux objectifs :
1 - vous parler des méthodes de type HMC qui mélangent dynamique Hamiltonienne et méthodes de Monte-Carlo = il y a donc des probas, bien sûr, mais aussi des résultats mathématiques sur les systèmes symplectiques qui sont utilisés dans l'article en question
2 - présenter les idées de l'optimisation des paramètres en considérant une dynamique limite, à la Roberts/Rosenthal (cf. exposé de Randal Douc l'automne dernier)
Jeudi 18 Février 2010 [Salle 201]
[15h] Orateur : Raphaël Roux (CERMICS, ENPC)
Titre : Calculs d'énergie par approximation particulaire
Résumé : En simulation moléculaire, on s'intéresse à des systèmes physiques (configuration de protéines, réactions chimiques) composés d'un grand nombre de constituants. L'espace des configurations du système est alors de très grande dimension. Notre objectif est de décrire le comportement global du système en utilisant un nombre plus restreint de coordonnées, appelées "coordonnées de réaction". Le comportement dynamique et statistique du système est entièrement décrit par une fonction dite d'énergie. On veut alors calculer la fonction dite d'"énergie libre" qui est la meilleure approximation de l'énergie ne dépendant que des coordonnées de réaction. Pour répondre à ce genre de questions, on va introduire une dynamiquede Langevin biaisée par une force ayant tendance à faire sortir le système de ses états métastables (c'est à dire les états où le système risquerait de rester "piégé"). Cette dynamique consistera en une équation différentielle stochastique non linéaire, la non linéarité provenant d'un terme d'espérance conditionnelle. On s'intéressera a la simulation de cette dynamique par un système de particules en intéraction.
Jeudi 28 Janvier 2010 [Salle 201]
[15h] Orateur : Robin Ryder (CEREMADE, Univ. Dauphine)
Titre : Phylogenetic models and MCMC methods for the reconstruction of language history
Résumé : Language diversification is a random process similar in many ways to biological evolution. We model the diversification of so-called "core" lexical data by a stochastic process on a phylogenetic tree. We focus on the Indo-European language family. The age of the most recent common ancestor of these languages is of particular interest and issues of dating ancient languages have been subject to controversy. We use Markov Chain Monte Carlo to estimate the tree topology, internal node ages and model parameters. Our model includes severalaspects specific to language diversification, such as rate heterogeneity and the data registration process, and we show that lexical borrowing does not bias our estimates. We show the robustness of our model and analyse two independent data sets to estimates the age of Proto-Indo-European. (Joint work with Geoff Nicholls.) Article disponible : http://arxiv.org/abs/0908.1735
[16h15] Orateur : Régis Lebrun (EADS)
Titre : Générateurs pseudo aléatoires uniformes et non uniformes
Résumé : La génération déterministe de séquences de nombres mimant une suite de réalisations iid d'une variable aléatoire uniforme sur [0, 1] est une nécessité pour la mise en oeuvre reproductible sur ordinateur d'algorithmes stochastiques. Après un bref rappel des techniques de validation statistique d'un tel générateur, on illustrera les difficultés spécifiques d'utilisation d'un tel générateur dans le contexte de génération de réalisations d'un vecteur aléatoire uniformément distribué sur [0, 1]^d, dès que d est sensiblement élevé (>10). Le résultat central est le théorème de Marsaglia relatif aux générateurs congruentiels. La génération de nombres uniformément répartis sur [0, 1] n'est souvent qu'un intermédiaire pour générer des réalisations de lois non uniformes. La réalisation d'un tel générateur pose des contraintes spécifiques sur le générateur uniforme sous-jacent, ainsi que sur l'algorithme de transformation choisi. Ces aspects seront illustrés dans le cas de la génération de réalisations iid d'une loi normal standard, comparant les techniques d'inversion de la fonction derépartition, de Box et Muller et la méthode Ziggurat.
George Marsaglia; Wai Wan Tsang (2000). "The Ziggurat Method for Generating Random Variables". Journal of Statistical Software 5 (8) http://www.jstatsoft.org/v05/i08/paper.
Luc Devroye, "Non-Uniform Random Variate Generation", Springer, 1986. http://cg.scs.carleton.ca/~luc/rnbookindex.html
Tests statistiques: http://www.phy.duke.edu/~rgb/General/rand_rate.php, http://www.stat.fsu.edu/pub/diehard/ http://www.iro.umontreal.ca/~lecuyer/myftp/papers/testu01.pdf
Théorème de Marsaglia: http://www.ncbi.nlm.nih.gov/pmc/articles/PMC285899/pdf/pnas00123-0038.pdf
Décembre 2009 (pas de séance)
Jeudi 26 Novembre 2009 [Salle 05]
[15h] Orateur : Wojciech Pieczynski (TELECOM SudParis)
Titre : Filtrage exact dans les modèles markoviens à sauts
Résumé : Soit (X, Y) un couple de processus continus à temps discret, où X est caché et Y observé. Dans les modèles markoviens linéaires gaussiens classiques la présence de discontinuité dans les paramètres est habituellement modélisée par un troisième processus markovien R à états finis, dont les réalisations modélisent les sauts. Conditionnellement à R on a ainsi un modèle classique dans lequel le filtrage exact (filtrage de Kalman) est possible. Cependant, lorsque les sauts ne sont pas observables le filtrage exact avec une complexité raisonable n'est plus possible et on doit faire appel à des techniques d'approximation, parmi lesquelles les méthodes particulaires jouent un rôle important. Les problèmes viennent du fait que le couple (R, Y) n'est pas nécessairement markovien. Les développements récents des divers modèles de type « chaînes de Markov triplets » (CMT) ont permis de proposer des triplets (X, R, Y) dans lesquels le filtrage exact avec complexité linéaire en temps est possible. L'objet de l'exposé est de faire le point sur différentes familles des modèles CMT, dont certaines autorisent le filtrage exact et d'autres, généralisant malgré tout les modèles classiques, nécessitent des approximations.
[16h] Orateur : Pierre Vandekerkhove (Univ. Marne-la-Vallée)
Groupe de Travail : Discussion du papier : Sequentially Interacting Markov Chain Monte Carlo Methods (Brockwell, A. et Del Moral, P. et Doucet A.). Article disponible à l'adressehttp://www.math.u-bordeaux1.fr/~delmoral/simcmc.pdf La méthode proposée dans cet article est une alternative aux algorithmes particulaires du type Sequential Monte Carlo (SMC) dont le but est d'approcher des fonctionnelles de lois de processus sur des horizons, généralement, finis de temps. L'originalité de la méthode porte ici sur son caractère itératif (non markovien) qui, contrairement au caractère en ligne des approches particulaires SMC utilisant le principe de mutation/sélection, génère à chaque pas une trajectoire "presque" distribuée suivant la loi cible et dont, au cours des itérations, l'ajustement s'affine grace à l'utilisation de la mesure empirique des itérations passées via un pseudo-mécanisme de Métropolis-Hastings. Nous présenterons en détail l'algorithme esquissé plus haut et énoncerons les principaux résultats de convergence obtenus par les auteurs. Nous mettrons aussi en évidence, au travers de quelques points techniques, les similarités avec les approches dites "adaptive MCMC" comme l'Equi-Energy Sampler déjà présenté au groupe de travail.
Jeudi 22 Octobre 2009 [Salle 201]
[14h] Orateur : Eric Moulines (TELECOM ParisTech)
Groupe de Travail : sur le thème de la convergence de l'algorithme de Wang-Landau. A partir de l'article de Y. Atchadé et J. Liu "The Wang-Landau algorithm in general state spaces : applications and convergence analysis". Disponible à l'adresse http://www.stat.lsa.umich.edu/~yvesa
[15h] Orateur : Scott C. Schmidler (Duke University)
Titre : Some Recent Developments in Adaptive Monte Carlo Sampling
Résumé : Adaptive MCMC methods have recently seen renewed interest in both Bayesian statistics and statistical mechanics, due in part to empirical successes and in part to establishment of supporting theory. However, like most MCMC theory available for statistical problems, these results are asymptotic. Obtaining rates is particularly challenging since despite their name, in the general case these algorithms generate non-Markovian, time-inhomegeneous, irreversible stochastic processes. I will outline our recent results giving lowerbounds on mixing times of two classes of adaptive sampling algorithms. These results also provide useful insight into principles for construction of new algorithms, and I will describe two such algorithms we have recently developed and their applications.
Jeudi 24 Septembre 2009 [Salle 05]
[15h] Orateur : Benjamin Jourdain (ENPC)
Titre : Robust Adaptive Importance Sampling for Normal Random Vectors
Résumé : Adaptive Monte Carlo methods are efficient techniques designed to tune simulation estimators on-line. In this work, we present an alternative to stochastic approximation to tune the optimal change of measure in the context of importance sampling for normal random vectors. Unlike stochastic approximation, which requires very fine tuning in practice, we propose to use sample average approximation and deterministic optimization techniques to devise a robust and fully automatic variance reduction methodology. The same samples are used in the sample optimization of the importance sampling parameter and in the Monte Carlo computation of the expectation of interest with the optimal measure computed in the previous step. We prove that this highly non independent Monte Carlo estimator is convergent and satisfies a central limit theorem with the optimal limiting variance. Numerical experiments confirm the performance of this estimator : in comparison with the crude Monte Carlo method, the computation time needed to achieve a given precision is divided by a factor going from 3 to 15.
[16h15] Orateur : Randal Douc (TELECOM SudParis)
Groupe de travail : sur le thème "Optimal scaling et applications dans les algorithmes de Hasting Metropolis". Je presenterai surtout le papier théorique fondateur: Weak Convergence and Optimal Scaling of Random Walk Metropolis Algorithms; Author(s): G. O. Roberts, A. Gelman, W. R. Gilks, The Annals of Applied Probability, Vol. 7, No. 1 (Feb., 1997), pp. 110-120 disponible en version pdf commenté (!!!) à l adresse: http://www-public.it-sudparis.eu/~douc_ran/RobertsGelmanGilks.pdf puis je ferai un survol de papiers plus récents disponibles à l adresse: http://www.dms.umontreal.ca/~bedard/
Bédard, M. (2007). Weak Convergence of Metropolis Algorithms for Non-/iid/ Target Distributions. /Ann. Appl. Probab. / *17*, 1222-44
Bédard, M. (2008). Efficient Sampling using Metropolis Algorithms: Applications of Optimal Scaling Results. /J. Comput. Graph. Statist. / *17*, 312-32./
Bédard, M. (2006). Optimal Acceptance Rates for Metropolis Algorithms: Moving Beyond 0.234. /To appear in Stochastic Process. Appl./
2008 - 2009
Organisateurs : Nicolas CHOPIN, Pierre VANDEKERKHOVE et Gersende FORT
Jeudi 25 Juin 2009
[16h] Orateur : Gersende Fort
Titre : Méthodes MCMC adaptatives : résultats de convergence
Résumé : Adaptive MCMC algorithms raise a number of theoretical and practical issues: it has been shown (see e.g. Roberts and Rosenthal - 2007 J.Appl.Prob.) that conditions are needed on the adaptive scheme in order to guarantee the convergence of the adaptive procedures. Adaptive strategies can be classified into two sets : the first one is the "internal adaptation strategy" when adaptation is based on the past history of the chain; the second one is the "external adaptation strategy" when the adaptation is based on auxiliary processes. The AdaptiveMetropolis (AM) by Haario et al. (2001, Bernoulli) and the equi-energy sampler by Kou et al. (2006, Ann. Stat.) are examples of these two sets of adaptive MCMC. In this talk, we will show that these two types of adaptation can be cast into a common unifying framework. We will provide sufficient conditions for the convergence of the marginal, that is we will study the way thesimulations approximate the target distribution; and conditions for the (strong) law of large numbers for a wide class of functions. We will discuss how our conditions are related to the "containment condition" defined by Roberts and Rosenthal (2001, J.Appl.Prob) in their pioneering work on the asymptotic behavior of the adaptive MCMC. We will show how to apply these conditions to the AM algorithms and to the equi-energy sampler. This talk is based on common works with Y. Atchadé (Univ. Michigan, US), E.Moulines (TELECOM ParisTech) and P. Priouret (Univ. Paris 6)
[xxx] Groupe de travail : séance annulée car le séminaire est précédé de la soutenance de thèse de J. Cornebise, à 13h, à l'IHP sur le sujet "Méthodes de Monte Carlo séquentielles adaptatives"
Jeudi 4 Juin 2009
[15h] Orateur : Gabriel Stoltz
Titre : Adaptive importance sampling methods
Résumé : I will present a general framework for adaptive importance sampling techniques, such as the Wang-Landau algorithm (well known in the statistics and Monte-Carlo literature), or the Adaptive Biasing Force method (ABF, originally introduced for computational biology). I will also present a proof of the longtime convergence of ABF, discuss the numerical implementation of the methods (using parallel strategies and some selection procedure), and present some applications in computational statistical physics and bayesian statistics.
[16h15] Orateur : Nicolas Chopin
Groupe de travail sur le thème "Nested sampling, theoretical and practical aspects ". Je présenterai le "nested sampling", une nouvelle méthode de Monte Carlo pour le calcul d'intégrales, particulièrement la vraisemblance marginale d'un modèle statistique. Je parlerai notamment de ses propriétés asymptotiques, et des difficultés d'implémentation. Les papiers pertinents sont:
Skilling, 2006, Nested sampling for general Bayesian computation, Bayesian analysis
Chopin and Robert, 2008, Contemplating Evidence: properties, extensions of, and alternatives to Nested Sampling
Jeudi 30 Avril 2009
[15h] Orateur : Nadia Oujdane
Titre : Weighted kernel resampling method: rate of convergence and applications
Résumé : Approximating posterior distributions is a crucial problem in Bayesian statistics with many applications such as efficient simulation of multivariate distributions or computation of multivariate integrals. One approach proposed in the literature consists of approximating the posterior distribution by a weighted sum of kernels.
In this presentation, we use classical density estimation theory to estimate the error of such posterior density estimators. We consider both the convergence in terms of supremum norm and the chi-square divergence. Then we apply those theoretical results to propose a new adaptive importance sampling estimator for computing integrals. We show a super central limit theorem for the resulting estimator and we observe important variance reductions in simulations. Joint work with D. Chauveau and P. Vandekerkhove
[16h15] Orateur : Christian Robert
Groupe de travail : Recent advances in ABC (Approximate Bayesian Computation) methodology. In this talk, we will survey the flurry of recent results on the ABC algorithm that have appeared in the literature, including our owns on the ABC-PMC version of the ABC algorithm and on the use of "exact" ABC algorithms for the selection of Ising models.
Jeudi 12 mars 2009
[15h] Orateur : Miguel Munoz-Zuniga (Paris VII-EDF).
Titre : Stratification Directionnelle Adaptative
Résumé :Nous présenterons une nouvelle méthode de Monte Carlo accélérée, que nous avons nommée SDA - Stratification Directionnelle Adaptative -, et que nous avons conçue pourrépondre aux contraintes industrielles rencontrées en pratique : robustesse de l'estimation de la probabilité de défaillance - potentiellement très faible -, modèle physique complexe et temps de calculs limités.
[16h15] Orateur : Gersende Fort
Groupe de Travail : sur le thème des algorithmes MCMC adaptatifs (présentation de qq exemples d'adaptation interne et d'adaptation externe).
Jeudi 29 Janvier 2009
[15 h] Orateur : Julien Cornebise
Titre : Adaptive proposal kernels in Sequential Monte Carlo
Résumé : The proposal -- or mutation -- step of Sequential Monte Carlo (SMC) methods is the key of their behavior. It critically affects the quality of their resulting estimates, bringing impressive success when optimally designed, or causing dramatic failures, from variance explosion to sample depletion and death of the particle cloud.
A current grand challenge in the SMC community is the design of adaptive algorithms, which would save the user from this choice, as difficult as critical. The aim is to automatically take into account multimodality, possible outlying observations (for state-space models), or even slight errors in the model (for parameter estimation), with still a low computational cost. Several attempts have been done so far, relying on linearizations (EKF-SMC), unscented transforms (Unscented particle filter), or Laplace approximations, of the unnormalized optimal proposal kernel. Though showing on simple models the gigantic wins possibly brought by a good kernel, they have achieved mitigated success on more intricate cases. With the busting use of SMC for models of soaring complexity, this concern is of higher interest than ever.
In this talk, we present cutting-edge algorithms, which stem from the quality criteria studied theoretically in Cornebise, Moulines, Olsson (2008). We minimize a function-free risk criterion (the Kullback-Leibler Discrepancy) between the optimal kernel and a mixture of experts, i.e. a mixture of integrated curved exponential distributions with logistic weights. To this intent, we use powerful and computationally efficient tools deeply related to Cross entropy methods, Monte-Carlo EM, and stochastic approximation.
J. Cornebise, E. Moulines, J. Olsson (2008), Adaptive Methods for Sequential Importance Sampling with Application to State Space Models, Statistics and Computing, 18(4), pp. 461-480.
[16 h 15] Orateur : Benjamin Jourdain
Groupe de travail sur le thème " Simulation exacte d'équations différentielles stochastiques" d'après les travaux de Beskos A., Papaspiliopoulos O. et Roberts G.O.
2007 - 2008
Organisateur : Jean-Michel MARIN et Gersende FORT
Jeudi 5 Juin 2008 [Salle 314]
Orateur :Vivekananda Roy
Titre :Convergence rates and asymptotic standard errors for MCMC algorithms for Bayesian probit regression
Résumé : We study Markov chain Monte Carlo algorithms for exploring the intractable posterior density that results when a probit regression likelihood is combined with a flat prior on the regression coefficient. We prove that the data augmentation algorithm of Albert and Chib (1993) and the PX-DA algorithm of Liu and Wu (1999) both converge at a geometric rate, which ensures the existence of central limit theorems (CLTs) for ergodic averages under a second moment condition. While these two algorithms are essentially equivalent in terms of computational complexity, we show that the PX-DA algorithm is theoretically more efficient in the sense that the asymptotic variance in the CLT under the PX-DA algorithm is no larger than that under Albert and Chib's algorithm. A simple, consistent estimator of the asymptotic variance in the CLT is constructed using regeneration. As an illustration, we apply our results to the lupus data from van Dyk and Meng (2001). In this particular example, the estimated asymptotic relative efficiency of the PX-DA algorithm with respect to Albert and Chib's algorithm is about 65, which demonstrates that huge gains in efficiency are possible by using PX-DA algorithm.
Mercredi 14 Mai 2008 [salle 01]
Orateur :Reuven Rubinstein
Titre : A Generic Randomized Algorithm for Combinatorial Optimization and Counting Using Gibbs Sampler with ``Cloning''
Résumé : We present a generic randomized algorithm for solving quite general NP-hard combinatorial (integer) optimization problems and counting. Our algorithm is based on the Gibbs sampler equipped with importance sampling and a ``cloning'' devise. As usual for randomized algorithms, we design a sequential sampling plan, where a ``difficult'' problem is decomposed into a sequence of ``easy'' related ones. We show that our method, which is closely related to the ones proposed by Diaconis-Holmes and Botev-Kroese, involves estimation of some quantities directly associated with the problems of interest. We also show how our method differs from Diaconis-Holmes and Botev-Kroese and from the standard randomized algorithms, which typically involve estimation of the partition functions for a carefully designed sequence of temperatures (cooling schedules) by generating samples from the Boltzmann distribution via the MCMC method. We finally present efficient numerical results, while solving quite general integer and combinatorial optimization problems as well as counting ones, like SAT and Hamiltonian cycles.
Vendredi 28 Mars [salle 314]
Orateur : Gareth Roberts
Titre : Méthodes adaptatives et/ou Simulation de diffusion
Jeudi 6 Mars 2008 [salle 01]
Orateur : Sylvain Maire
Titre : Méthodes spectrales stochastiques pour l'équation de Poisson
Résumé : On décrit des méthodes d'approximation de la solution de l'équation de Poisson à l'aide de couplages entre la formule de Feynman-Kac et des approximations polynomiales déterministes. On se concentre sur l'optimisation du calcul des représentations probabilistes des solutions à l'aide nouveaux schémas puis des techniques de quantifications. On introduit pour finir une nouvelle formulation spectrale qui a de très bonnes propriétés en termes de conditionnement
Jeudi 7 Février 2008 [salle 314]
Orateurs : Karim Benabed et Simon Prunet
Résumé : We will present some applications of MC sampling methodsin cosmology, with an emphasis on the sampling of the posterior distribution of physical parameters given heterogeneous data sets. We will also present some of the results obtained in the context of the ANR Ecosstat.
Jeudi 6 Décembre 2007 [amphi Darboux]
Orateur : Pierre Etoré
Titre : Méthodes adaptatives pour la stratification
Résumé : La stratification est une méthode de réduction de variance. Soit X une variable aléatoire d'espace d'état A et f une fonction telle que le moment d'ordre 2 de f(X) est fini. On construit un estimateur stratifié de E(f(X)) en se donnant premièrement une partition de A en strates. Pour chaque strate on fait ensuite des tirages de X conditionnellement au fait que X lui appartienne, pour estimer l'espérance de f(X) conditionnellementà la strate. On fait finalement une somme de ces estimations pondérée par les probabilités des strates. L'estimateur stratifié a une variance plus faible que celle l'estimateur Monte Carlo brut de force si on fait un bon choix des strates, et du nombre de tirages conditionnels qu'on décide de faire dans chaque strate (problème de l'allocation). Par exemple pour des strates données on a intérêt a faire dans chaque strate un nombre de tirages proportionnel à sa probabilité et à sa variance conditionnelle (à l'inverse imaginons que la variance conditionnellement à une
strate est petite, on a besoin d'y faire moins de tirages pour être précis). Une telle allocation est optimale. Mais dans bon nombre de situations pratiques on manque d'information pour faire un réglage préalable optimal de l'estimateur stratifié (par exempleles variances conditionnelles permettraient de faire un tel réglage mais elles dépendent au fond de ce qu'on cherche à estimer...). D'où la necessité de développer des méthodes adaptatives où un tel estimateur se règle tout seul en cours de route. Pour un jeu de strates arbitrairement donné, on présente des résultats pour un estimateur stratifié à allocation adaptative, qui se révèle être asymptotiquement optimal, en ce sens qu'il obéit à un TCL qui met en jeu la variance de l'estimateur stratifié non adaptatif avec allocation optimale. On présente ensuite des éléments concernant le problème plus délicat d'une procédure adaptative qui cherche en cours de route les meilleures strates possibles. Ces questions sont illustrées par des exemples numériques issus d'un contexte pricing d'option.
Jeudi 8 Novembre 2007 [salle 314]
Orateur : Pierre Vandekerkhove
Titre : Comment comparer des MCMC ?
Résumé : Nous présentons dans cet exposé une méthode destinée à hiérarchiser l'efficacité de diverses approches/stratégies face à unproblème de simulation par chaine de Markov. Considérons par exemple deux algorithmes de MCMC ayant pour but de simuler la meme loi. Il est alors intéressant de connaitre l'algorithme qui converge le plus rapidement vers sa loi stationnaire. Pour répondre à ce type de question nous devrions etre en mesure d'estimer une distance entre la densité des algorithmes et la densité cible, or cette dernière n'est en général connue qu'à une constante de normalisation près (cadre bayésien). On peut cependant remarquer que la différence des distances de Kullback entre la densité des algorithmes et la densité cible est indépendante de cette constante de normalisation; ainsi l'estimation de ces différences et l'analyse de leur comportement au cours des premières itérations pourrait s'avérer un outil synthétique permettant de mieux appréhender la qualité relative de chaque algorithme. Partant de ce constat, nous avons choisi d'estimer ces différences de distance de Kullback au moyen de plusieurs algorithmes lancés en parallèle (i.i.d.). La méthode d'estimation utilisée repose sur l'estimateur de l'entropie introduit par Gyorfi et Van Der Meulen (1989). La principale difficulté de notre travail a été de montrer que les conditions techniques assurant la consistance des estimateurs étaient satisfaites pour les densités successives de l'algorithme de Hastings-Metropolis au prix de certaines hypothèses (toutes vérifiées dans le cas gaussien). Pour clore l'exposé, nous présenterons quelques applications de notre critère de comparaison à des exemples classiques (mélanges multimensionnels, modèle logit) en dimension modérée, validant de manière précise les intuitions communément admises dans la communauté MCMC.
Jeudi 4 Octobre 2007 [salle 421]
Orateur: Jean-Michel Marin
Titre : Adaptive multiple importance sampling
Résumé : The AMIS algorithm consists of 3 steps. In the initialization step a set of iid uniform points are sampled in the d-dimentional unit box. The logistic transformation with scale parameter S, is used to bring the points back to $R^d$. The scale parameter is chosen using the ESS of the importance weights. Importance sampling estimates of the target mean and variance are constructed. These estimates are used to generate, from a d-dimentional Student-T(3df), the initial set of particles of the second adaptive step. At this stage a temporal dimention is introduced and global adaptation is performed by an importance sampling version of Haario et al. (2001) adaptive Metropolis-Hastings algorithm. To achieve variance reduction an adaptive version of Owen and Zhou (2000), deterministic mixture importance sampling is defined. As a byproduct of the mixture and actualization process we performe on the weights, all particles are on the same weighting scale and can be easily and efficiently combined to get final AMIS estimator. In the final step a clustering algorithm is performed on all generated particles. The number of clusters, K, is chosen via BIC. IS estimators of mean and covariance matrices on each cluster are derived. A K-mixture of Student-T (3df) distributions is used to generate a final set of particles. The mixture proportions are taken to be the number of particles belonging to each cluster. The AMIS estimator is obtained by recycling the particles generated in all 3 steps, with the corresponding importance weights. The strength of AMIS resides in its completely adaptive and multi-purpose nature: no tuning parameter is needed and the same algorithm is proved to perform well on very diverse high-dimentional target distributions (from banana shaped to mixture with very well separated modes).
2006 - 2007
Organisateur : Randal DOUC et Gersende FORT
25 Juin au 29 Juin 2007 : Workshop "New Directions in Monte Carlo methods"
Jeudi 31 Mai 2007 [salle 314], Deux exposés : 15h et 17h
Orateur : Régis Lebrun (EADS)
Transparents de la présentation : AdaptMC.pdf
Titre : Propagation probabiliste d'incertitudes pour la normalisation et la certification.
Résumé : Afin d'avoir une meilleure maîtrise de la fiabilité d'un système physique, le recours à la simulation numérique haute performance (HPC) couplée à la prise en compte de variabilités stochastiques des paramètres d'entrée des modèles numériques est devenu un des principaux enjeux du calcul scientifique industriel. Une grandeur dimensionnante Y du système étudié s'écrit alors Y=f(X) où X est un vecteur aléatoire et f une fonction accessible via la mise en oeuvre d'une chaîne de calcul coûteuse.
Dans ce cadre, se posent deux problèmes connexes:
+ la validation par le calcul de la vérification de critères normatifs de sécurité, qui se traduit par l'évaluation d'une probabilité de dépasser un seuil y: 1-F_Y(y);
+ la détermination de seuils assurant une fiabilité donnée, qui se traduit par l'évaluation d'un majorant garanti d'un quantile: Y_Q tel que P(Y_q<Y_Q)=alpha.
L'utilisation de techniques de simulation élémentaires (Monte Carlo, quantile empirique) est rendue impossible par le coût élevé de simulation de la variable d'intérêt (de plusieurs minutes à plusieurs heures): il convient donc de mettre en oeuvre des techniques plus sophistiquées.
La première partie de l'exposé présente une méthode fréquemment utilisée dans la communauté du calcul HPC probabiliste: la méthode FORM (First Order Reliability Method), dont le principal avantage est le (relatif) faible coût numérique mais dont l'inconvénient est de ne pas fournir d'intervalle de confiance pour l'estimation. On présente alors une technique de simulation de Monte Carlo permettant à la fois de corriger l'approximation FORM et de fournir un intervalle de confiance sur l'estimation proposée.
La seconde partie de l'exposé présente deux méthodes d'estimation de bornes garanties sur un quantile. On commence par présenter une méthode élémentaire due à Wilks, qui permet de déterminer à priori la taille d'un échantillon dont la réalisation maximum sera un majorant garanti du quantile cherché. Dans un second temps, on suppose disposer d'une approximation g de l'opérateur f de telle sorte que les variables Y=f(X) et Z=g(X) soient corrélées de façon significative et que l'évaluation de g soit très peu coûteuse. On met alors en place une technique de stratification pour réduire significativement la dispersion de l'estimation du quantile.
Au cours de l'exposé, selon l'intérêt de l'auditoire, il est possible (et prévu) de faire une digression sur la modélisation de la structure de dépendance du vecteur X par l'utilisation de copules en liaison avec les algorithmes qui sont présentées dans le corps principale de l'exposé. En effet, la qualité du résultat fourni par le HPC probabiliste n'est pas uniquement lié aux performances des algorithmes mis en oeuvre, mais également à la qualité du modèle probabiliste qui alimente ce calcul, à travers la loi jointe de X.
Orateur : Sumeetpal SINGH (Univ. de Cambridge, UK).
Titre : Particle methods for Partially Observed Markov Decision Processes
Résumé : This talk will focus on a class of discrete time optimal control problems known as a Partially Observed Markov Decison Process (POMDP). We consider POMDPs defined on a General State-space and device Particle based methods for computing the optimal controller. Detailed examples and some convergence results are presented.
Jeudi 26 Avril 2007 [Salle 314]
Orateur : Havard Rue (Professeur, Norwegian Univ. of Science and Technology)
Titre : A MCMC case-study
Résumé : MCMC have been around for quite some time and had a tremendous success within (Bayesian) statistics. It has undoubtedly solved a lot of important problems. On the other hand, due to problems with mixing/convergence, is has also ``solved'' quite a few problems wrongly. In this talk, I will discuss various MCMC schemes for a simple latent Gaussian model for binomial count data. The schemes include single-site schemes, auxiliary variables, various blocking schemes and the independence sampler. Despite that this is a quite simple model, many commonly used MCMC-schemes has problems of estimating the uncertainly correctly. At last, I will present a deterministic alternative which computes the ``true'' answer is nearly instantaneously. I will close with some comments on what to be learnt from this exercise.
Jeudi 29 Mars 2007 [Salle 314]
Orateur : Jimmy Olsson
Titre : On particle-based estimation in state space models
Résumé : The talk deals with filtering, smoothing, and maximum likelihood (ML) estimation in general state space models using stochastic particle filters (also referred to as sequential Monte Carlo (SMC) methods). In the first part of the talk the concepts of state space models and particle filters are briefly described, leading to a discussion of asymptotic properties of weighted samples produced by the so-called two-stage sampling (TSS) algorithm. The TSS procedure is a generalization of the auxiliary particle filter proposed by Pitt and Shephard (1999), and a central limit theorem (CLT) for smoothed particle estimates produced by the scheme in question is stated. Setting out from the recursive formula for the asymptotic variance of the CLT we discuss some possible improvements of the TSS filter. When performing ML estimation in state space models the log-likelihood function must be approximated, and the second part of the talk is devoted to such particle-based approximations. A first method is to approximate the likelihood by running parallel particle filters on a grid in the parameter space, yielding a pointwise approximation. After this, extensions to the whole parameter space are formed by means of piecewise constant functions or B-splines. In this setting we formulate criteria for how to increase the number of particles and how to decrease the grid size in order to produce estimates that are consistent and asymptotically normal. Finally, we consider ML estimation based on EM (Expectation-Maximization) methods. In this context, the key ingredient is the computation of smoothed sum functionals of the hidden states for given values of themodel parameters. It has been observed by several authors that using standard SMC methods for this smoothing assignment may be unreliable for larger observations sizes. Hence we discuss a simple variant, based on forgetting ideas of the state space model dynamics, of the basic sequential smoothing approach which is transparent in terms of computation time and reduces the variability of the sum functional approximation. Under suitable regularity assumptions, it is shown that this modification indeed allows a tighter control of the L^p error and thebias of the approximation.
Jeudi 15 Février 2007 [Salle 314]
Orateur : Pierre Etoré
Titre : Approximation de processus de diffusion à coefficients discontinus en dimension un et Applications.
Résumé : Dans cette thèse, on étudie des schémas numériques pour des processus X à coefficients discontinus. Un premier schéma pour le cas unidimensionnel utilise les Equations Différentielles Stochastiques avec Temps Local. En effet en dimension un les processus X sont solutions de telles équations. On construit une grille sur la droite réelle, qu'une bijection adéquate transforme en une grille uniforme de pas h. Cette bijection permet de transformer X en Y qui se comporte localement comme un Skew Brownian Motion, pour lequel on connait les probabilités de transition sur une grille uniforme, et le temps moyen passé sur chaque cellule de cette grille. Une marche aléatoire peut alors être construite, qui converge vers X en h^{1/2}. Toujours dans le cas unidimensionnel on propose un deuxième schéma plus général. On se donne une grille non uniforme sur la droite réelle, dont les cellules ont une taille proportionnelle à h. On montre qu'on peut relier les probabilités de transition de X sur cette grille, ainsi que le temps moyen passé par X sur chacune de ses cellules, à des solutions de problèmes d'EDP elliptiques ad hoc. Une marche aléatoire en temps et en espace est ainsi construite, qui permet d'approcher X à nouveau en h^{1/2}. Ensuite on présente des pistes pour adapter cette dernière approche au cas bidimensionnel et les problèmes que cela soulève. Enfin on illustre par des exemples numériques les schémas étudiés et on évoque des applications possibles en finance.
Jeudi 25 Janvier 2007 [IHP, amphi Darboux]
Orateur : Sylvain Rubenthaler
Titre : Développement limité de l'erreur dans la propogation du chaos pour un système de particules associé a une équation de Feynman-Kac
Résumé : Développement polynomial indexé par des arbres pour des mesures particulaires de Feynman-Kac non normalisées. Nous exposons ici une représentation fonctionnelle d'une classe de mesures particulaires de Feynman-Kac. Cette représentation fonctionnelle inclut une extension de la formule de Wick à des systèmes particulaires en interaction. Nous obtenons un développement faible dont le calcul nécessite des dénombrements originaux et une analyse du groupe des permutations d'une certaine classe de forêts.
Jeudi 30 Novembre 2006 [IHP, salle 314]
Orateur : Estelle Kuhn
Titre : Consistent estimation algorithms for non-rigid deformable models
Résumé : The problem of estimating probabilistic deformable template models in the field of computer vision or of probabilistic atlases in the field of computational anatomy has not yet received a coherent statistical formulation and remains a challenge. In this talk, we provide a careful definition and analysis of a well defined statistical model based on dense deformabletemplates for gray level images of deformable objects. We propose a rigorous Bayesian framework for which we derive a stochastic version of the EM algorithm using MCMC adaptative method for the estimation of the geometric and photometric parameters of the model in a small sample setting, as weel as a proof of consistency. The model is extended to mixtures of finite numbers of such components leading to a fine description of the photometric and geometric variations. We illustrate the results with images of handwritten digits extract of the US postal basis and apply the estimated models to classification through maximum likelihood.
Jeudi 19 Octobre 2006 [IHP, salle 201]
Orateur : Tony Lelièvre
Titre : Méthodes adaptatives en dynamique moléculaire
Résumé : Un des objectifs en dynamique moléculaire est d'échantillonner des mesures de Boltzmann-Gibbs en grande dimension, pour calculer par moyenne statistique dans l'ensemble NVT des quantités macroscopiques (constantes de réactions chimiques, constantes de diffusion, etc...). Les méthodes numériques sont typiquement basées sur des limites ergodiques pour des processus de Markov solutions d'équations différentielles stochastiques. La difficulté provient de l'existence de puits de potentiel qui piègent les particules et ralentissent la convergence des méthodes trop naives. Nous présenterons une classe de méthodes adaptatives qui permettent d'explorer plus rapidement l'espace des configurations, en modifiant au cours du temps le potentiel vu par les particules (processus de Markov non-homogène et non-linéaire). Ces méthodes permettent d'obtenir en temps long des quantités importantes en pratique (loi d'une marginale associée à une variable lente du système). Nous proposerons une preuve de convergence de ces méthodes, basée sur des techniques d'entropie.
Jeudi 28 septembre 2006 : [IHP, salle 01]
Orateur : Nicolas Chopin.
Titre : Extensions of the Cross-Entropy method for Statistical Analysis
Résumé : The Cross-Entropy method is a new Monte Carlo paradigm pioneered by Rubinstein (1999) in Operation Research.
Its primary applications are (i) the calculation of probability of rare events, and (ii) the optimisation of irregular, multi-modal functions. While these two objectives seem to have a little in common, the CE approach manages to express them in a similar framework.
In this talk, we will explain how Statistics can benefit from the CE method, and how the CE method can also benefit in turn from Statistical methodology. We will discuss the following particular applications in Statistics: Monte-Carlo p-values, simulation of truncated distributions, variable selection, and mixture estimation. We will see that in each case CE provides significant improvements over current methods. Interestingly, we will see also vanilla CE rarely works directly, but tandard tools from Statistical Inference allow for developing more efficient algorithms. In particular, we will discuss a CE-EM algorithm for mixture estimation, which outperform any straight CE or EM algorithm, in terms, of finding higher modes of the likelihood function.
2005 - 2006
Mardi 27 Juin 2006
Lieu :
ENPC, 6 et 8 avenue Blaise Pascal - Cité Descartes, Champs-sur-Marne, salle (à préciser), 10h
Programme :
O. Cappé : Simulation d'évènements rares. A partir de
l'article Limit Theorems for the Multilevel Splitting Algorithm in the Simulation of Rare Events, de F. Cérou, P. Del Moral, F. Legland et P. Lezaud
du livre The cross-entropy method, de Rubinstein et Kroese.
Réunion des membres du projet.
Mercredi 24 Mai 2006 [séance annulée]
Mercredi 26 Avril 2006
Lieu :
ENST, 37/39 rue Dareau, 75014, salle (à préciser), 15h.
Programme :
A. Mira : Variance reduction techniques in MCMC
Jeudi 30 Mars 2006
Lieu :
ENPC, 6 et 8 avenue Blaise Pascal - Cité Descartes, Champs-sur-Marne, salle (à préciser), 15h
Programme :
J.M. Marin : Convergence of Adaptive Importance Sampling Schemes, 2006. Support format pdf
Mercredi 1er Mars 2006
Lieu :
ENST, 37/39 rue Dareau 75014, salle DA-107, 15h.
Programme :
Bernard Lapeyre : méthodes de Monte Carlo pour l'ingéniérie financière.
Mercredi 25 Janvier 2006
Lieu :
IHP, rue Pierre et Marie Curie 75005, salle 206, 14h.
Programme :
Eric Moulines : méthodes MCMC adaptatives (sur la base d'un article de C. Andrieu et E. Moulines , 2005On the ergodicity properties of some adaptive MCMC algorithms).
Mardi 3 Janvier 2006
Lieu :
ENST, 37/39 rue Dareau 75014, salle B 312, 14h.
Programme :
Objectifs du projet.
Présentations scientifiques succinctes : Algorithmes Population Monte Carlo, les méthodes MCMC adaptatives, les méthodes de Monte-Carlo pour la finance, les méthodes de Monte-Carlo pourla chimie quantique, learning reinforcement.
Bibliographie
(Articles présentés ou évoqués en séminaire)
C. Andrieu et E. Moulines , 2005On the ergodicity properties of some adaptive MCMC algorithms). Accepté pour publication, Ann. Appl. Prob.
F. Cérou, P. Del Moral, F. Legland et P. Lezaud, 2005, Limit Theorems for the Multilevel Splitting Algorithm in the Simulation of Rare Events.
E. Clément, D. Lamberton et P. Protter, An analysis of the Longstaff-Schwartz algorithm for American option pricing.
R. Rubinstein et D. Kroese, The cross-entropy method, 2004, Springer-Verlag.