Discontinuous Hamiltonian Monte Carlo for discrete parameters and discontinuous likelihoods

摘要

Hamiltonian Monte Carlo (HMC) is a powerful sampling algorithm employed byseveral probabilistic programming languages. Its fully automaticimplementations have made HMC a standard tool for applied Bayesian modeling.While its performance is often superior to alternatives under a wide range ofmodels, one weakness of HMC is its inability to handle discrete parameters. Inthis article, we present discontinuous HMC, an extension that can efficientlyexplore discrete parameter spaces as well as continuous ones. The proposedalgorithm is based on two key ideas: embedding of discrete parameters into acontinuous space and simulation of Hamiltonian dynamics on a piecewise smoothdensity function. The latter idea has been explored under special cases in theliterature, but the extensions introduced here are critical in turning the ideainto a general and practical sampling algorithm. Discontinuous HMC isguaranteed to outperform a Metropolis-within-Gibbs algorithm as the twoalgorithms coincide under a specific (and sub-optimal) implementation ofdiscontinuous HMC. It is additionally shown that the dynamics underlyingdiscontinuous HMC have a remarkable similarity to a zig-zag process, acontinuous-time Markov process behind a state-of-the-art non-reversiblerejection-free sampler. We apply our algorithm to challenging posteriorinference problems to demonstrate its wide applicability and superiorperformance.