Small-Variance Asymptotics for Hidden Markov Models
Small-variance asymptotics provide an emerging technique for obtaining scalable combinatorial algorithms from rich probabilistic models. We present a smallvariance asymptotic analysis of the Hidden Markov Model and its infinite-state Bayesian nonparametric extension. Starting with the standard HMM, we first derive a "hard" inference algorithm analogous to k-means that arises when particular variances in the model tend to zero. This analysis is then extended to the Bayesian nonparametric case, yielding a simple, scalable, and flexible algorithm for discrete-state sequence data with a non-fixed number of states. We also derive the corresponding combinatorial objective functions arising from our analysis, which involve a k-means-like term along with penalties based on state transitions and the number of states. A key property of such algorithms is thatparticularly in the nonparametric setting-standard probabilistic inference algorithms lack scalability and are heavily dependent on good initialization. A number of results on synthetic and real data sets demonstrate the advantages of the proposed framework.
The paper provides a small-variance asymptotics 
      analysis for the standard HMM as well as the infinite HMM, and in 
      particular uses the asymptotic analysis to derive "hard clustering" 
      optimization programs for learning and inference in both kinds of HMMs. 
      The exposition in the paper is excellent, and it deftly explains 
      the framework and algorithm derivation (with two approaches, providing 
      extra intuition pumps). The paper also explains connections to existing 
      algorithms (for standard HMMs, Viterbi re-estimation corresponds to 
      setting the algorithm parameter lambda to 1) and previous work in 
      small-variance asymptotics. It clearly delineates the challenges in 
      adapting the small-variance algorithm approaches to the (infinite) HMM 
      (Section 3.2) and explains good methods to overcome those challenges. 
      These HMM fitting methods are likely to be very interesting to the 
      community, and the development here (and in the supplementary materials) 
      is really great. However, the experiments are weak. The data, 
      both real and synthetic, are very easy, and it seems unlikely that the 
      only comparison to existing techniques (the beam sampler) does justice to 
      existing techniques. Despite the fact that synthetic data is 
      especially easy, the beam sampler does very poorly, yet I ran the same 
      experiment using a library that came up as the first result for 'python 
      hmm sampling' (pyhsmm), which primarily uses weak limit samplers (which 
      have been used in many application papers and certainly seem to fit these 
      experiments well), and got much better results in a fraction of the time. 
      Direct comparison to the results in the paper is hard because there is no 
      formula or citation provided for the NMI performance metric, and the 
      timing plot in Figure 1 has no units (just "log of the time" on the 
      vertical axis), but it seems the weak limit sampler is decoding the 
      synthetic sequences nearly perfectly in just 0.03 seconds per Gibbs sweep 
      on my laptop. Given the papers showing successful applications of weak 
      limit samplers (many times without dependence on good initializations or 
      slow convergence, as mentioned in this paper's abstract and introduction) 
      and the easy availability of code (there are several libraries online), it 
      seems misleading not to provide any comparison or comment, yet this paper 
      only provides a surprisingly weak showing of the beam sampler. 
      There are other weaknesses and points to clarify in the 
      experiments section: (1) "For these datasets, we also observe that 
      the EM algorithm for the standard HMM (not reported in the figure) can 
      easily output a smaller number of states than the ground truth, which 
      yields a smaller NMI score." Why not show the results? The synthetic 
      dataset should be easy for EM, so the omission is strange and unexplained. 
      (2) "Next we demonstrate... along with comparison to the standard 
      HMM." I don't see any lines in Figure 2 corresponding to the standard HMM 
      methods. Were they left out accidentally? (3) Was the time for the 
      grid search over algorithm parameters (mentioned in the third paragraph of 
      Section 4) included in the reported run times (which seems appropriate, 
      since the iHMM methods are supposedly fitting concentration parameters)? 
      What are the units for the vertical axis in the right-hand panel of Figure 
      2? Timing experiments can be a rabbit hole and a line must be 
      drawn somewhere, but it's not clear what can be learned from the given 
      experimental results, and as presented they do not support the paper's 
      relative algorithm performance claims. These issues with the experimental 
      evaluation provided could be easily remedied by toning down the claims 
      about existing methods and focusing instead on the fact that the 
      experiments demonstrate the proposed method is competitive with an iHMM 
      sampling method (and perhaps also with EM if those results were reported). 
      Despite those issues, the paper remains a great treatment of 
      an exciting new analytical and algorithmic perspective on the well-loved 
      (i)HMM.