A Spectral Algorithm for Inference in Hidden semi-Markov Models

Igor Melnyk, Arindam Banerjee
Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, PMLR 38:690-698, 2015.

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. Our approach is based on estimating certain sample moments, whose order depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few spectral decompositions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the promise of the algorithm.

Cite this Paper


BibTeX
@InProceedings{pmlr-v38-melnyk15, title = {{A Spectral Algorithm for Inference in Hidden semi-Markov Models}}, author = {Melnyk, Igor and Banerjee, Arindam}, booktitle = {Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics}, pages = {690--698}, year = {2015}, editor = {Lebanon, Guy and Vishwanathan, S. V. N.}, volume = {38}, series = {Proceedings of Machine Learning Research}, address = {San Diego, California, USA}, month = {09--12 May}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v38/melnyk15.pdf}, url = {https://proceedings.mlr.press/v38/melnyk15.html}, 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. Our approach is based on estimating certain sample moments, whose order depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few spectral decompositions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the promise of the algorithm.} }
Endnote
%0 Conference Paper %T A Spectral Algorithm for Inference in Hidden semi-Markov Models %A Igor Melnyk %A Arindam Banerjee %B Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2015 %E Guy Lebanon %E S. V. N. Vishwanathan %F pmlr-v38-melnyk15 %I PMLR %P 690--698 %U https://proceedings.mlr.press/v38/melnyk15.html %V 38 %X 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. Our approach is based on estimating certain sample moments, whose order depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few spectral decompositions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the promise of the algorithm.
RIS
TY - CPAPER TI - A Spectral Algorithm for Inference in Hidden semi-Markov Models AU - Igor Melnyk AU - Arindam Banerjee BT - Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics DA - 2015/02/21 ED - Guy Lebanon ED - S. V. N. Vishwanathan ID - pmlr-v38-melnyk15 PB - PMLR DP - Proceedings of Machine Learning Research VL - 38 SP - 690 EP - 698 L1 - http://proceedings.mlr.press/v38/melnyk15.pdf UR - https://proceedings.mlr.press/v38/melnyk15.html AB - 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. Our approach is based on estimating certain sample moments, whose order depends only logarithmically on the maximum length of the hidden state persistence. Moreover, the algorithm requires only a few spectral decompositions and is therefore computationally efficient. Empirical evaluations on synthetic and real data demonstrate the promise of the algorithm. ER -
APA
Melnyk, I. & Banerjee, A.. (2015). A Spectral Algorithm for Inference in Hidden semi-Markov Models. Proceedings of the Eighteenth International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 38:690-698 Available from https://proceedings.mlr.press/v38/melnyk15.html.

Related Material