It’s time for Sunday Reading Notes again! This week I am discussing another computational statistics paper: ‘Auxiliary-variable Exact Hamiltonian Monte Carlo Samplers for Binary Distributions’ by Ari Pakman and Liam Paninski from Columbia University. This paper is published at NIPS 2013.

In the previous Hamming Ball sampler SRN post, the algorithm uses data augmentation to sample from discrete distributions. In this week’s paper, the goal is to sample from generic binary distributions with data augmentation into continuous variables.

Let’s say we want to sample from the distribution defined over given an un-normalized density The authors propose augmenting with a continuous variable with joint density where is a density we can design but it must satisfy for all The marginal distribution of $y$ is $p(y) = p(s)p(y|s)$ as a result of this constraint. It turns out that at this point we transformed a d-dimentional binary problem on into a d-dimensional continuous problem on .

To sample from , the authors suggest using Hamiltonian Monte Carlo, the potential energy is and the kinetic energy terms is The HMC sampler involves simulating a trajectory of that preserves the Hamiltonian and typically leap-frog simulation is used. With the constraint in , the potential function is defined only piece-wise and we need to be careful when the trajectory crosses regions. o this end, the authors insist we choose such that is quadratic, so that the trajectory is deterministic and approximations methods are not necessary.

Because has a jump at , the value of momentum should change when we cross boundaries. This is, in my opinion, the most interesting part of the paper. Suppose at time we have , then a change in trajectory must happen and let’s say the momentum just before and after are and Conservation of energy says we must have if before the From this equation, if then we continue the trajectory with ; however, if then the particle is reflected from a wall at and the trajectory gets reflected with

The two augmentations mentioned in this paper are Gaussian augmentation and exponential augmentation. Both results in quadratic log likelihood. The Gaussian augmentation is very interesting because there is a fixed order that each coordinate reaches zero and the successive hits occur at The authors makes an observation that:

Interestingly, the rate at which wall is crossed coincides with the acceptance rate in a Metropolis algorithm that samples uniformly a value for and makes a proposal of flipping the binary variable

To me this is a sanity check rather than a surprise because each coordinate hits the boundary the same number of times and making a decision to continue or to bounce back in is the same as deciding whether we should flip the sign of But I think the authors give a very help comment pointing out that although the acceptance probability is the same, the method proposed is still different from Metropolis because

in HMC the order in which the walls are hit is fixed given the initial velocity, and the values of at successive hits of within the same iteration are not independent.

What’s interesting for the exponential augmentation method is that

particles moves away faster from areas of lower probability.

This is certainly a nice feature to have so that the sample mixes well.

In the simulation examples, the authors compared Gaussian HMC and Metropolis on 1d and 2d ising models and showed that:

- ‘the HMC sampler explores faster the samples space once chain has reached equilibrium distribution.’
- ‘the HMC sampler is faster in reaching the equilibrium distribution.’

I think the take away from this paper is the continuous data augmentation to sample discrete variables and their dealing with piece-wise defined potential function.

Reference:

- Pakman, A., & Paninski, L. (2013). Auxiliary-variable exact Hamiltonian Monte Carlo samplers for binary distributions. In
*Advances in neural information processing systems*(pp. 2490-2498). - Neal, R. M. (2011). MCMC using Hamiltonian dynamics.
*Handbook of Markov Chain Monte Carlo*,*2*(11), 2.

Pingback: SRN – Informed proposals for local MCMC in discrete spaces by Zanella (Part I) – Phyllis with data