A Spectral Algorithm for Inference in Hidden semi-Markov Models

Igor Melnyk, Arindam Banerjee

Research output: Contribution to journalArticle


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 data sets.

Original languageEnglish (US)
Pages (from-to)1-39
Number of pages39
JournalJournal of Machine Learning Research
StatePublished - Apr 1 2017


  • Aviation safety
  • Graphical models
  • Hidden semi-Markov model
  • Spectral algorithm
  • Tensor analysis

Fingerprint Dive into the research topics of 'A Spectral Algorithm for Inference in Hidden semi-Markov Models'. Together they form a unique fingerprint.

  • Cite this