Exploring Discrete Analogs of Hamiltonian Monte Carlo
share
Hamiltonian Monte Carlo (HMC) has emerged as a powerful way to sample from continuous distributions. However, a fundamental limitation of HMC is that it can't be applied to discrete distributions. In this paper, we propose the momentum sampler as a general framework for exploring the idea of building discrete analogs of HMC. The momentum sampler is a novel family of Markov Chain Monte Carlo (MCMC) algorithms that extends arbitrary single-site Metropolis Hastings (MH) samplers for discrete distributions with an auxiliary momentum process. It connects and generalizes a variety of existing methods, and points to a more general framework where we can mix stochastic evolution of discrete variables with deterministic evolution of continuous variables. The auxiliary momentum process can be integrated exactly, resulting in a rejection-free sampling process. The various trade-offs involved in picking different proposal distributions and kinetic energies have clear physical interpretations, and are demonstrated by numerical experiments on a simple Potts model.
READ FULL TEXT