A Spectral Algorithm for Inference in Hidden Semi-Markov Models
This provides a computationally efficient method for researchers and practitioners working with time-series data, though it is incremental as it builds on existing spectral techniques for latent variable models.
The paper tackles inference in hidden semi-Markov models by introducing a spectral algorithm that correctly estimates observation probabilities, showing empirical advantages over EM in speed and accuracy for large datasets.
Hidden semi-Markov models (HSMMs) are latent variable models which allow latent state persistence and can be viewed as a generalization of the popular hidden Markov models (HMMs). In this paper, we introduce a novel spectral algorithm to perform inference in HSMMs. Unlike expectation maximization (EM), our approach correctly estimates the probability of given observation sequence based on a set of training sequences. Our approach is based on estimating moments from the sample, whose number of dimensions depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few matrix inversions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the advantage of the algorithm over EM in terms of speed and accuracy, especially for large datasets.