Hamming Ball Auxiliary Sampling for Factorial Hidden Markov Models
We introduce a novel sampling algorithm for Markov chain Monte Carlo-based Bayesian inference for factorial hidden Markov models. This algorithm is based on an auxiliary variable construction that restricts the model space allowing iterative exploration in polynomial time. The sampling approach overcomes limitations with common conditional Gibbs samplers that use asymmetric updates and become easily trapped in local modes. Instead, our method uses symmetric moves that allows joint updating of the latent sequences and improves mixing. We illustrate the application of the approach with simulated and a real data example.
This paper introduces a new sampling algorithm for Factorial Hidden Markov models. The standard algorithm for sampling the hidden chains in any HMM type of model is the forward filtering backward sampling algorithm. For many HMM like models this works very well; however for the FHMM, exact sampling from the joint distribution of all random variables in the hidden chain takes exponential time. One possible solution is to sample one or a few chains at a time keeping the other chains fixed. The problem with this approach is that this doesn't easily allow for multiple changes in multiple chains in one sampling pass.This paper introduces a new algorithm called Hamming Ball Auxiliary Sampling. The idea of this sampling algorithm, is starting from the current sample X of all variables of the hidden chain, to introduce an auxiliary variable U which is a sample from the Hamming ball of a certain radius from the current sample where the Hamming ball is defined as any time step of all joint chain variables to be within Hamming distance m from the current sample. Next, the sample X is resampled conditional on U again by condition on being Hamming distance m away from U. As such, between two samples of X, at least 2*m bits can be flipped.The paper is very well written and explains the algorithm well. There is a good empirical evaluation.From experience, one problem with sampling from FHMM's is that if two parallel chains have very similar states, then it is likely that the parameters for those two chains will be very similar. Essentially, what should be one feature ends up being duplicated. This sampling algorithm does not make it more likely that this local maxima is escaped. I think it is still important to point out that that is still an issue (say around line 126).l197: My only real complaint about the paper is that I'd like to see some algorithmic details on how this sampler can be efficiently implemented. I'm curious to know if the authors use an efficientl algorithm to sample from the Hamming ball? I.o.w. I'd add a section on implementation (and really I'd like to see some code published).l215 - l230: I think this can easily be made an appendix or extension of the paper. It's a bit trivial and doesn't really make the paper that more impressive.Section 4.1 As you pointed out, the different algorithms have different time complexities. I'd like to see Figure 3 scaled w.r.t. real complexity (rather than iterations which gives the HB algorithms an unfair advantage).Nice work!