Scalable Adaptation of State Complexity for Nonparametric Hidden Markov Models
Bayesian nonparametric hidden Markov models are typically learned via fixed truncations of the infinite state space or local Monte Carlo proposals that make small changes to the state space. We develop an inference algorithm for the sticky hierarchical Dirichlet process hidden Markov model that scales to big datasets by processing a few sequences at a time yet allows rapid adaptation of the state space cardinality. Unlike previous point-estimate methods, our novel variational bound penalizes redundant or irrelevant states and thus enables optimization of the state space. Our birth proposals use observed data statistics to create useful new states that escape local optima. Merge and delete proposals remove ineffective states to yield simpler models with more affordable future computations. Experiments on speaker diarization, motion capture, and epigenetic chromatin datasets discover models that are more compact, more interpretable, and better aligned to ground truth segmentations than competitors. We have released an open-source Python implementation which can parallelize local inference steps across sequences.
This paper applies to the sticky HDP-HMM some recently developed machinery for split/merge style adaptation of the truncation level for variational inference in Bayesian nonparametric models and evaluates the resulting algorithm on several tasks, emphasizing identifying the true number of states present in a dataset. The algorithm is an improvement over the algorithm presented in [7] particularly because of these extra steps, and possibly due to the improved treatment of the variational factor on the top-level HDP weights.The paper is written very clearly. However, given previous work on these subjects the novel contributions here are incremental. Furthermore, the experiments are unenlightening and the synthetic experiment is very confusing.## Experiments ## The synthetic data results presented in the first experiment don't look correct. The data, which I understand are shown in the top-left panel, are trivially separable and any algorithm, even a GMM without any temporal dynamics let alone sticky bias, would separate these clusters perfectly in just a few iterations (unless perhaps it had some adversarial initialization). Yet the reported experiment shows that a sampler (presumably operating on the entire dataset in each iteration) required 1000 iterations just to find these obvious clusters? Or that SVI (without split/merge moves) couldn't get away from modeling the data with 60 clusters after 1000 full passes through the data? These results contradict both reported performance in the literature and my own experience with related models, even vanilla GMMs.The other experiments are believable but they don't provide much insight into the potential tradeoffs here or failure modes of the proposed algorithm; each figure just serves to show that the proposed method always works great. Studying Hamming error and the number of recovered states is okay, but those metrics probably favor the proposed method's emphasis on searching explicitly over the model size; why not show predictive likelihood as well to measure whether the predictive distributions are converging for these other methods (as expected)? When does this method do badly, and when might its extra computational burden not be worthwhile? Instead of shedding light on these kinds of questions, these experiments are all salesmanship.## Originality / significance ## The originality of this work relative to [13] and [14] is minimal. The authors helpfully enumerate contributions over [14] in the conclusion section. Three of the four seem incremental while the last (an implementation with parallelism) isn't relevant to deciding the merits of the paper.The extension from the HDP-HMM to the Sticky HDP-HMM is pretty much the first thing to try: the sticky bias amounts to just adding an extra weight to a particular entry in each second-level weight vector in the HDP, and so the extent of the contribution here is just using the bound from [14] and splitting a logarithm over a sum (Eq. (36) in the supplement). (The algebra would be clearer if it were written as log(alpha beta_k + kappa) = log(beta (alpha + kappa) + (1-beta) kappa) >= beta log(alpha+kappa) + (1-beta) log(kappa).)The merge selection and delete acceptance rules are an improvement over [14], but they simply amount to a better heuristic. The birth moves also seem like a reasonable choice but the idea is pretty straightforward given the use of birth moves in [13].Parallelization would be a merit of the implementation, but not the method as described in the paper, especially since all the comparable methods admit the same (easy) parallel implementations. If we're meant to evaluate the quality of the implementation as a contribution of this paper, the implementation should be included.## Misc ## - The comments on model selection don't make sense (Lines 049 and 174). Are these comments meant to refer to using the variational lower bound on the model evidence to compare the HDP-HMM to other models? If so, it's not been made clear that these bounds for these models are useful proxies compared to direct estimates via AIS or SIS, and if that's a claimed merit of this approach, it should be investigated in the experiments. The comment on Line 174 that bounds which use a delta factor on the top-level weights "can favor models with redundant states" is not demonstrated; indeed, those do provide valid bounds on model evidence with just the top-level weights fixed instead in precisely the same way that the each majorization bound used in the EM algorithm is a bound on the likelihood of the data with the hidden variables marginalized out (but the parameters fixed). - Around line 236 it is claimed that memoized variational inference with one pass (one lap) is identical to SVB. Is that essentially a choice to use SVB to start the algorithm as opposed to initializing the cached statistics (M, S)? Since [13] was published at the same time as [20] and does not cite [20], it's surprising to learn that memoized variational inference actually contains streaming variational inference as a special case. - Is memoized variational inference just regular batch mean field with a different update schedule? Caching sufficient statistics, instead of keeping around individual factors' parameters only to throw them out when they are updated, seems to be the straightforward implementation strategy for such an update schedule. - In supplement C.1, a line reads "Here, all the infinite sums are convergent. This allows some regrouping" but infinite sums need to be *absolutely* convergent to allow regrouping. If all terms are nonnegative, regrouping is always okay. If the series is convergent but with indefinite terms, regrouping does not hold in general.