Abstract
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 language | English (US) |
|---|---|
| Pages (from-to) | 1-39 |
| Number of pages | 39 |
| Journal | Journal of Machine Learning Research |
| Volume | 18 |
| State | Published - Apr 1 2017 |
Bibliographical note
Funding Information:We thank Nikunj Oza and Bryan Matthews at NASA for their helpful comments and suggestions at several stages of the work. We thank the editor and reviewers for helpful comments and suggestions which led to improvements in the paper. We also thank the Minnesota Supercomputing Institute (MSI) for the computing support. This work was supported by NASA grant NNX12AQ39A, and by NSF grants IIS-1563950, IIS-1447566, IIS-1447574, IIS-1422557, CCF-1451986, CNS- 1314560, IIS-0953274, IIS-1029711, and gifts from Adobe, IBM, and Yahoo.
Publisher Copyright:
© 2017 Igor Melnyk and Arindam Banerjee.
Keywords
- Aviation safety
- Graphical models
- Hidden semi-Markov model
- Spectral algorithm
- Tensor analysis