## Hamming Ball Sampler

**M**ichalis Titsias and Christopher Yau just arXived a paper entitled the Hamming Ball sampler. Aimed at large and complex discrete latent variable models. The completion method is called after Richard Hamming, who is associated with code correcting methods (reminding me of one of the Master courses I took on coding, 30 years ago…), because it uses the Hamming distance in a discrete version of the slice sampler. One of the reasons for this proposal is that conditioning upon the auxiliary slice variable allows for the derivation of normalisation constants otherwise unavailable. The method still needs some calibration in the choice of blocks that partition the auxiliary variable and in the size of the ball. One of the examples assessed in the paper is a variable selection problem with 1200 covariates, out of which only 2 are relevant, while another example deals with a factorial HMM, involving 10 hidden chains. Since the paper compares each example with the corresponding block Gibbs sampling solution, it means this Gibbs sampling version is not intractable. It would be interesting to see a case where the alternative is not available…

September 3, 2018 at 1:29 am

[…] high-dimensional discrete-valued vectors or matrices.Â While reading this paper, I also found a blog post about it from Xi’an’s OG, which provided some high-level intuitions and background […]

May 7, 2015 at 10:30 am

A similar sampling approach was proposed in “Finite Adaptation and Multistep Moves in the Metropolis-Hastings Algorithm for Variable Selection in Genome-Wide Association Analysis”

http://journals.plos.org/plosone/article?id=10.1371/journal.pone.0049445

Example problem in that paper has over one million covariates.

The code is also available https://github.com/to-mi/bmagwa