A catalytic Metropolis-Hastings algorithm


The Metropolis-Hastings algorithm produces a sequence of samples from a probability distribution. It's based on a random walk.

One problems with this algorithm is choosing good random steps to take. If the algorithm generates steps in uniformly random direction, it will not be able to move quickly along ridge shaped probability density functions.

A possible way around this: Instead of sampling one instance at a time, sample several instances. Then let a step involve changes to only one of these samples at a time. This allows information from the other samples to be used when choosing this step, as this information will not be altered in taking the step (in the Metropolis-Hastings algorithm the probability of choosing a step from one point to another must equal the probability of choosing a step back from that destination, so we can't use information that will be altered by the step to choose the step).

For example, you could choose a step parallel to the difference between two of the other samples (perhaps plus a little random noise). On a ridge, the effect will be for the samples to spread along the ridge. As this spread increases the step chooser will become more and more likely to choose steps parallel to the ridge.

Thus the other samples can be seen as "catalysing" the movement of a sample, allowing it to mutate faster.

For density functions more complex than a single ridge, more elaborate forms of catalysis might be devised.