Minimal Realization Problems for Hidden Markov Models

Journal Article (Journal Article)

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.

Full Text

Duke Authors

Cited Authors

  • Huang, Q; Ge, R; Kakade, S; Dahleh, M

Published Date

  • April 1, 2016

Published In

Volume / Issue

  • 64 / 7

Start / End Page

  • 1896 - 1904

International Standard Serial Number (ISSN)

  • 1053-587X

Digital Object Identifier (DOI)

  • 10.1109/TSP.2015.2510969

Citation Source

  • Scopus