Skip to main content

Minimal Realization Problems for Hidden Markov Models

Publication ,  Journal Article
Huang, Q; Ge, R; Kakade, S; Dahleh, M
Published in: IEEE Transactions on Signal Processing
April 1, 2016

This paper addresses two fundamental problems in the context of hidden Markov models (HMMs). The first problem is concerned with the characterization and computation of a minimal order HMM that realizes the exact joint densities of an output process based on only finite strings of such densities (known as HMM partial realization problem). The second problem is concerned with learning a HMM from finite output observations of a stochastic process. We review and connect two fields of studies: realization theory of HMMs, and the recent development in spectral methods for learning latent variable models. Our main results in this paper focus on generic situations, namely, statements that will be true for almost all HMMs, excluding a measure zero set in the parameter space. In the main theorem, we show that both the minimal quasi-HMM realization and the minimal HMM realization can be efficiently computed based on the joint probabilities of length N strings, for N in the order of O (logd(k)). In other words, learning a quasi-HMM and an HMM have comparable complexity for almost all HMMs.

Duke Scholars

Published In

IEEE Transactions on Signal Processing

DOI

ISSN

1053-587X

Publication Date

April 1, 2016

Volume

64

Issue

7

Start / End Page

1896 / 1904

Related Subject Headings

  • Networking & Telecommunications
 

Citation

APA
Chicago
ICMJE
MLA
NLM
Huang, Q., Ge, R., Kakade, S., & Dahleh, M. (2016). Minimal Realization Problems for Hidden Markov Models. IEEE Transactions on Signal Processing, 64(7), 1896–1904. https://doi.org/10.1109/TSP.2015.2510969
Huang, Q., R. Ge, S. Kakade, and M. Dahleh. “Minimal Realization Problems for Hidden Markov Models.” IEEE Transactions on Signal Processing 64, no. 7 (April 1, 2016): 1896–1904. https://doi.org/10.1109/TSP.2015.2510969.
Huang Q, Ge R, Kakade S, Dahleh M. Minimal Realization Problems for Hidden Markov Models. IEEE Transactions on Signal Processing. 2016 Apr 1;64(7):1896–904.
Huang, Q., et al. “Minimal Realization Problems for Hidden Markov Models.” IEEE Transactions on Signal Processing, vol. 64, no. 7, Apr. 2016, pp. 1896–904. Scopus, doi:10.1109/TSP.2015.2510969.
Huang Q, Ge R, Kakade S, Dahleh M. Minimal Realization Problems for Hidden Markov Models. IEEE Transactions on Signal Processing. 2016 Apr 1;64(7):1896–1904.

Published In

IEEE Transactions on Signal Processing

DOI

ISSN

1053-587X

Publication Date

April 1, 2016

Volume

64

Issue

7

Start / End Page

1896 / 1904

Related Subject Headings

  • Networking & Telecommunications