Archive for Wang-Landau algorithm

Luke and Pierre at big’MC

Posted in Linux, pictures, Statistics, Travel, University life with tags , , , , , , , , , , , on May 19, 2014 by xi'an

crossing Rue Soufflot on my way to IHP from Vieux Campeur, March 28, 2013Yesterday, Luke Bornn and Pierre Jacob gave a talk at our big’MC ‘minar. While I had seen most of the slides earlier, either at MCMski IV,  Banff, Leuven or yet again in Oxford, I really enjoyed those talks as they provided further intuition about the techniques of Wang-Landau and non-negative unbiased estimators, leading to a few seeds of potential ideas for even more potential research. For instance, I understood way better the option to calibrate the Wang-Landau algorithm on levels of the target density rather than in the original space. Which means (a) a one-dimensional partition target (just as in nested sampling); (b) taking advantage of the existing computations of the likelihood function; and (b) a somewhat automatic implementation of the Wang-Landau algorithm. I do wonder why this technique is not more popular as a default option. (Like, would it be compatible with Stan?) The impossibility theorem of Pierre about the existence of non-negative unbiased estimators never ceases to amaze me. I started wondering during the seminar whether a positive (!) version of the result could be found. Namely, whether perturbations of the exact (unbiased) Metropolis-Hastings acceptance ratio could be substituted in order to guarantee positivity. Possibly creating drifted versions of the target…

One request in connection with this post: please connect the Institut Henri Poincaré to the eduroam wireless network! The place is dedicated to visiting mathematicians and theoretical physicists, it should have been the first one [in Paris] to get connected to eduroam. The cost cannot be that horrendous so I wonder what the reason is. Preventing guests from connecting to the Internet towards better concentration? avoiding “parasites” taking advantage of the network? ensuring seminar attendees are following the talks? (The irony is that Institut Henri Poincaré has a local wireless available for free, except that it most often does not work with my current machine. And hence wastes much more of my time as I attempt to connect over and over again while there.) Just in connection with IHP, a video of Persi giving a talk there about Poincaré, two years ago:

MCqMC 2014 [day #4]

Posted in pictures, Running, Statistics, Travel, University life with tags , , , , , , , , , , on April 11, 2014 by xi'an

Leuven7

I hesitated in changing the above title for “MCqMSmaug” as the plenary talk I attended this morning was given by Wenzel Jakob, who uses Markov chain Monte Carlo methods in image rendering and light simulation. The talk was low-tech’, with plenty of pictures and animations (incl. excerpts from recent blockbusters!), but it stressed how much proper rending relies on powerful MCMC techniques. One point particularly attracted my attention, namely the notion of manifold exploration as it seemed related to my zero measure recent post. (A related video is available on Jakob’s webpage.) You may then wonder where the connection with Smaug could be found: Wenzel Jakob is listed in the credits of both Hobbit movies for his contributions to the visual effects! (Hey, MCMC made Smaug [visual effects the way they are], a cool argument for selling your next MCMC course! I will for sure include a picture of Smaug in my next R class presentation…) The next sessions of the morning opposed Sobol’s memorial to more technical light rendering and I chose Sobol, esp. because I had missed Art Owen’s tutorial on Sunday, as he gave a short presentation on using Sobol’s criteria to identify variables contributing the most to the variability or extreme values of a function, an extreme value kind of ANOVA, most interesting if far from my simulation area… The afternoon sessions saw MCMC talks by Luke Bornn and Scott Schmidler, both having connection with the Wang-Landau algorithm. Actually, Scott’s talk was the one generating the most animated discussion among all those I attended in MCqMC! (To the point of the chairman getting rather rudely making faces…)

published in Brazilian Journal of Probability and Statistics, esplêndido!

Posted in Statistics, University life with tags , , , , on September 24, 2013 by xi'an

Our paper “Bayesian computation for statistical models with intractable normalizing constants” written with Yves Atchadé and Nicolas Lartillot has now appeared in the Brazilian Journal of Probability and Statistics! (This is my first paper in this journal.) Although we could have used ABC steps to approximate the posterior, we chose instead a Wang-Landau approach that has exact convergence properties and extends the 1992 Read Paper by Charlie Geyer and Elisabeth Thompson.

Hamilton confronting intractability (with a li’le help from Metropolis)

Posted in Mountains, pictures, Statistics, Travel, University life with tags , , , , , , , , , , on April 20, 2012 by xi'an

Last day of a great workshop! I filled more pages of my black notebook (“bloc”) than in the past month!!! This morning started with an Hamiltonian session, Paul Fearnhead presenting recent developments in this area. I liked his coverage very much, esp. because it went away from the physics analogies that always put me off. The idea of getting away from the quadratic form had always seemed natural to me and provided an interesting range for investigations. (I think I rediscovered the topic during the talks, rephrasing almost the same questions as for Girolami’s and Calderhead’s Read Paper!) One thing that still intrigues me is the temporal dimension of the Hamiltonian representation. Indeed, it is “free” in the sense that the simulation problem does not depend on the time the pair (x,p) is moved along the equipotential curve. (In practice, there is a cost in running this move because it needs to be discretised.) But there is no clear target function to set the time “right”. The only scale I can think of is when the pair comes back by its starting point. Which is less silly than it sounds because the discretisation means that all intermediate points can be used, as suggested by Paul via a multiple try scheme. Mark then presented an application of Hamiltonian ideas and schemes to biochemical dynamics, with a supplementary trick of linearisation. Christian Lorenz Müller gave an ambitious grand tour of gradient free optimisation techniques that sounded appealing from a simulation perspective (but would require a few more hours to apprehend!), Geoff Nicholls presented on-going research on approximating Metropolis-Hastings acceptance probabilities in a more general perspective than à la Andrieu-Robert, i.e. accepting some amount of bias, an idea he has explained to me when I visited Oxford. And Pierre Jacob concluded the meeting in the right tone with a pot-pourri of his papers on Wang-Landau. (Once again a talk I had already heard but that helped me make more sense of a complex notion…)

Overall and talk-by-talk, a truly exceptional meeting. Which also set the bar quite high for us to compete at the ICMS meeting on advances in MCM next Monday! Esp. when a portion of the audience in Bristol will appear in Edinburgh as well!an In the meanwhile, I have to rewrite my talk for the seminar in Glasgow tomorrow in order to remove the overlap with my talk there last year(I note that I have just managed to fly to Scotland with no lost bag, a true achievement!)

Wang, Landau, Markov, and others…

Posted in pictures, Statistics, University life with tags , , , , , , , , , on April 11, 2012 by xi'an

On Thursday, the “Big’MC” seminar welcomes two talks (at 3pm and 4pm, resp., in IHP, Amphi Darboux):

  • 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


and

  • 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
Follow

Get every new post delivered to your Inbox.

Join 598 other followers