Skip to main content

Minimal realization problem for Hidden Markov Models

Publication ,  Journal Article
Huang, Q; Ge, R; Kakade, S; Dahleh, M
Published in: 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014
January 30, 2014

In this paper, we study the problem of finding a minimal order (quasi-) Hidden Markov Model for a random process, which is the output process of an unknown stationary HMM of finite order. In the main theorem, we show that excluding a measure zero set in the parameter space of transition and observation probability matrices, both the minimal quasi-HMM realization and the minimal HMM realization can be efficiently constructed based on the joint probabilities of length N output strings, for N > max(4 logd(k) + 1,3), where d is the size of the output alphabet size, and k is the minimal order of the realization. We also aim to connect the two lines of literature: realization theory of HMMs / automatas, and the recent development in learning latent variable models with tensor techniques.

Duke Scholars

Published In

2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014

DOI

Publication Date

January 30, 2014

Start / End Page

4 / 11
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Huang, Q., Ge, R., Kakade, S., & Dahleh, M. (2014). Minimal realization problem for Hidden Markov Models. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014, 4–11. https://doi.org/10.1109/ALLERTON.2014.7028428
Huang, Q., R. Ge, S. Kakade, and M. Dahleh. “Minimal realization problem for Hidden Markov Models.” 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014, January 30, 2014, 4–11. https://doi.org/10.1109/ALLERTON.2014.7028428.
Huang Q, Ge R, Kakade S, Dahleh M. Minimal realization problem for Hidden Markov Models. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014. 2014 Jan 30;4–11.
Huang, Q., et al. “Minimal realization problem for Hidden Markov Models.” 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014, Jan. 2014, pp. 4–11. Scopus, doi:10.1109/ALLERTON.2014.7028428.
Huang Q, Ge R, Kakade S, Dahleh M. Minimal realization problem for Hidden Markov Models. 2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014. 2014 Jan 30;4–11.

Published In

2014 52nd Annual Allerton Conference on Communication, Control, and Computing, Allerton 2014

DOI

Publication Date

January 30, 2014

Start / End Page

4 / 11