Stochastic Variational Inference for Hidden Markov Models
Variational inference algorithms have proven successful for Bayesian analysis in large data settings, with recent advances using stochastic variational inference (SVI). However, such methods have largely been studied in independent or exchangeable data settings. We develop an SVI algorithm to learn the parameters of hidden Markov models (HMMs) in a time-dependent data setting. The challenge in applying stochastic optimization in this setting arises from dependencies in the chain, which must be broken to consider minibatches of observations. We propose an algorithm that harnesses the memory decay of the chain to adaptively bound errors arising from edge effects. We demonstrate the effectiveness of our algorithm on synthetic experiments and a large genomics dataset where a batch algorithm is computationally infeasible.
The paper presents stochastic variational inference (SVI)  for HMMs. Unlike LDA, in HMMs the chain-based dependence structure poses problems for SVI. Subsampling in each iteration cannot assume independence between series data, and skipping any data outside the chain can lead to errors.  (Network models present somewhat different difficulties, replacing chain-based with pair-wise dependence. Subsampling in this setting has been handled in prior work (Gopalan et al. (2012)).)In this work, the authors show how to scale the noisy subsample gradients for unbiased estimates and bound error induced by updating only variables corresponding to subchain samples. They augment subsampled subchains with extra observations to achieve this. They argue that this buffering and the forward-backward computations can be done incrementally, and therefore efficiently. They apply their algorithm to a large genomics data set, and demonstrate similar performance to VB.pros:the paper is written well; contributions through developing an SVI algorithm are clear and significant.cons:- my main criticism of this work is that a comparison to Johnson et al. (2014) is not provided. That paper develops an algorithm for large collections of independent series. surely, the SVI algorithm in your paper makes better (and correct) assumptions; but it's hard to know if these additional complexities are worth it, in practice, when running on real data. comparison to an EM algorithm is insufficient, as your gains could derive from using SVI. - You mention "significant gains" in computation for the genomic data compared to the EM algorithm, but no runtime evidence is provided. - computational complexity of the batch vs. SVI algorithm is not mentioned (although it's evaluated); i assume the SVI is still has quadratic per-iteration complexity in terms of states? - what is the worst-case cost when L is set poorly? the algorithm requires a good choice of subchain lengths (L) and number of chains per mini-batch. this is not unusual for SVI algorithms, where mini-batch size can plays a key role (Hoffman et al., (2010)). however, choosing a good L is critical, as it may cause the "buffering" algorithm to add too many observations for a good approximation. the authors state that this is not the case, but it's not convincing, as it's in the case of simulated data.