Hamiltonian Monte Carlo

From Wikipedia, the free encyclopedia
  (Redirected from Hybrid Monte Carlo)
Jump to navigation Jump to search

In computational physics and statistics, the Hamiltonian Monte Carlo algorithm (also known as hybrid Monte Carlo), is a Markov chain Monte Carlo method for obtaining a sequence of random samples which converge to being distributed according to a target probability distribution for which direct sampling is difficult. This sequence can be used to estimate integrals with respect to the target distribution (expected values).

Hamiltonian Monte Carlo corresponds to an instance of the Metropolis–Hastings algorithm, with a Hamiltonian dynamics evolution simulated using a time-reversible and volume-preserving numerical integrator (typically the leapfrog integrator) to propose a move to a new point in the state space. Compared to using a Gaussian random walk proposal distribution in the Metropolis–Hastings algorithm, Hamiltonian Monte Carlo reduces the correlation between successive sampled states by proposing moves to distant states which maintain a high probability of acceptance due to the approximate energy conserving properties of the simulated Hamiltonian dynamic when using a symplectic integrator. The reduced correlation means fewer Markov chain samples are needed to approximate integrals with respect to the target probability distribution for a given Monte Carlo error. The algorithm was originally proposed by Simon Duane, Anthony Kennedy, Brian Pendleton and Duncan Roweth in 1987[1] for calculations in lattice quantum chromodynamics.

Algorithm[edit]

Suppose the target distribution to sample is and a chain of samples is required. The Hamilton's equations are

and

where and are the th component of the position and momentum vector respectively and is the Hamiltonian. Let be a mass matrix which is symmetric and positive definite, then the Hamiltonian is

where is the potential energy. The potential energy for a target is given as

which comes from the Boltzmann's factor.

The algorithm requires a positive integer for number of leap frog steps and a positive number for the step size . Suppose the chain is at . Let . First, a random Gaussian momentum is drawn from . Next, the particle will run under Hamiltonian dynamics for time , this is done by solving the Hamilton's equations numerically using the leap frog algorithm. The position and momentum vectors after time using the leap frog algorithm are

These equations are to be applied to and times to obtain and .

Because the leap frog algorithm is a numerical method and does not solve the Hamilton's equations exactly, a Metropolis–Hastings step is used. The transition from to is

where

This is repeated to obtain .

No U-Turn Sampler[edit]

The No U-Turn Sampler (NUTS)[2] is an extension by controlling automatically. Tuning is critical. For example in the one dimensional case, the potential is which corresponds to the potential of a simple harmonic oscillator. For too large, the particle will oscillate and this waste computational time. For too small, the particle will behave like a random walk.

Loosely, NUTS runs the Hamiltonian dynamics both forwards and backwards in time randomly until a U-Turn condition is satisfied. When that happens, a random point from the path is chosen for the MCMC sample and the process is repeated from that new point.

In detail, a binary tree is constructed to trace the path of the leap frog steps. To produce a MCMC sample, an iterative procedure is conducted. A slice variable is sampled. Let and be the position and momentum of the forward particle respectively. Similarly, and for the backward particle. In each iteration, the binary tree selects at random uniformly to move the forward particle forwards in time or the backward particle backwards in time. Also for each iteration, the number of leap frog steps increase by a factor of 2. For example, in the first iteration, the forward particle moves forwards in time using 1 leap frog step. In the next iteration, the backward particle moves backwards in time using 2 leap frog steps.

The iterative procedure continues until the U-Turn condition is met, that is

or when the Hamiltonian becomes inaccurate

or

where, for example, .

Once the U-Turn condition is met, the next MCMC sample, , is obtained by sampling uniformly the leap frog path traced out by the binary tree which satisfies

This is usually satisfied if the remaining HMC parameters are sensible.

See also[edit]

References[edit]

  1. ^ Duane, Simon; Kennedy, Anthony D.; Pendleton, Brian J.; Roweth, Duncan (3 September 1987). "Hybrid Monte Carlo". Physics Letters B. 195 (2): 216–222. Bibcode:1987PhLB..195..216D. doi:10.1016/0370-2693(87)91197-X.
  2. ^ Hoffman, Matthew D; Gelman, Andrew (2014). "The No-U-turn sampler: adaptively setting path lengths in Hamiltonian Monte Carlo". Journal of Machine Learning Research. 15 (1): 1593-1623.

Further reading[edit]

External links[edit]