# Statisfaction

## Density exploration and Wang-Landau algorithms [with R package]

Posted in R, Statistics by Pierre Jacob on 21 September 2011

Hey,

Since a new paper that I’ve co-written has appeared on arXiv, here is a quick post summarizing it. The paper is named:

An Adaptive Interacting Wang-Landau Algorithm for Automatic Density Exploration

and describes improvements over the Wang-Landau algorithm described by Atchadé and Liu, which is itself a generalization of the work of Wang and Landau (which itself is commonly used in computational physics and well deserves its Wikipedia article). It is joint work with Luke Bornn from UBC, Arnaud Doucet from Oxford and Pierre Del Moral from INRIA Bordeaux.

We focus on the utility of this kind of “exploratory” algorithms for statistical inference. More precisely, suppose that you want to explore (e.g. by simulating from) a complex probability distribution, complex in the sense that most standard algorithms would fail to sample precisely from it, either because it is defined on a very high dimensional state space, or because there are many local modes. The general idea of the Wang-Landau algorithm is that the parts of the state space that have been explored already (e.g. the Markov chain generated by the algorithm has spent some time there) are “penalized”, so that they are less likely to be explored further. Hence, the other parts of the space are “favoured”. That goes on until all the parts (in some sense) have been explored enough. A pretty natural idea!

Now defining these “parts” of the space is a bit tricky, and has proved to be a limit of the method: if the parts are not well designed, the Wang-Landau algorithm does not provide very useful results compared to classical MCMC methods. Part of our work was to design a somewhat “automatic” method to partition the space dynamically during the algorithm, so that the generated chains explore the whole space of interest indeed. Other improvements include the use of parallel chains and adaptive proposal distributions. On top of algorithmic improvements, we argue for a more general use of exploratory methods to prevent getting stuck in local modes without even noticing it.

We try our improved Wang-Landau on four models: a toy example involving a mixture of three bi-variate Gaussian distributions, a variable selection problem, a challenging mixture model with lots of well-separated modes (that’s the figure above), and an Ising model applied to image analysis, where the difficulty is to design efficient moves to travel around the very big space. In all cases we compare to adaptive MCMC with parallel chains, matching the computational cost in terms of target density evaluations.

To make things easier, we provide an R package (my very first!) here:

Hence the graphs of the article can be easily reproduced by launching a few files. We hope that it can also be easily adapted to a lot of target distributions, if you want to try the method on your model! We’ll probably submit to CRAN after some clean-up.

I’m also working on more theoretical aspects of the Wang-Landau algorithm with Robin Ryder, so I’ll blog more on that soon.

### 6 Responses

1. […] Pierre Jacob and Robin Ryder (from Paris-Dauphine, CREST, and Statisfaction) have just arXived (and submitted to the Annals of Applied Probability) a neat result on the Wang-Landau algorithm. (This algorithm, which modifies the target in a sort of reweighted partioned sampling to achieve faster convergence, has always been perplexing to me.)  They show that some variations of the Wang-Landau algorithm meet the flat histogram criterion in finite time, and, just as importantly that other variations do not reach this criterion. The proof uses elegant Markov chain arguments and I hope the paper makes it through, as there are very few theoretical results on this algorithm. (Pierre also wrote recently a paper with Luke Bornn, Arnaud Doucet, and Pierre Del Moral, on An Adaptive Interacting Wang-Landau Algorithm for Automatic Density Exploration last week, with an associated R package. Not yet on CRAN.) Share:Share […]

2. PAWL package on CRAN « Statisfaction said, on 26 October 2011 at 15:55

[…] PAWL package (which I talked about there, and which implements the parallel adaptive Wang-Landau algorithm and adaptive Metropolis-Hastings […]

3. […] very happy to participate by presenting the Parallel Adaptive Wang Landau algorithm I’ve been blogging about lately, and Christian Robert is going to present our parallel Independent Metropolis-Hastings paper, so I […]

4. […] area that I’ve blogged about here. Xian and I are going to talk about Parallel IMH and Parallel Wang Landau. We’ll be able to interact with top researchers in methodological statistics and early […]

5. […] to penalize already-visited regions of the state space, in order to explore yet unvisited regions (see this old post for instance, which was about a related paper now accepted in […]

6. […] thanks to the awesome wesanderson package on CRAN. Obviously it is now very tempting to launch the Wang-Landau algorithm on this target with a spatial binning strategy, in order to try out the various palettes provided […]