Minimal Realization Problems for Hidden Markov Models
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 (kn...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Institute of Electrical and Electronics Engineers (IEEE)
2017
|
| Online Access: | http://hdl.handle.net/1721.1/110794 https://orcid.org/0000-0002-9113-7269 https://orcid.org/0000-0002-1470-2148 |
| _version_ | 1826198790122504192 |
|---|---|
| author | Ge, Rong Kakade, Sham Huang, Qingqing Dahleh, Munther A |
| author2 | Massachusetts Institute of Technology. Institute for Data, Systems, and Society |
| author_facet | Massachusetts Institute of Technology. Institute for Data, Systems, and Society Ge, Rong Kakade, Sham Huang, Qingqing Dahleh, Munther A |
| author_sort | Ge, Rong |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T11:10:02Z |
| format | Article |
| id | mit-1721.1/110794 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T11:10:02Z |
| publishDate | 2017 |
| publisher | Institute of Electrical and Electronics Engineers (IEEE) |
| record_format | dspace |
| spelling | mit-1721.1/1107942022-09-27T17:35:57Z Minimal Realization Problems for Hidden Markov Models Ge, Rong Kakade, Sham Huang, Qingqing Dahleh, Munther A Massachusetts Institute of Technology. Institute for Data, Systems, and Society Massachusetts Institute of Technology. Laboratory for Information and Decision Systems Huang, Qingqing Dahleh, Munther A 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. 2017-07-20T20:41:09Z 2017-07-20T20:41:09Z 2015-12 Article http://purl.org/eprint/type/JournalArticle 1053-587X 1941-0476 http://hdl.handle.net/1721.1/110794 Huang, Qingqing, Rong Ge, Sham Kakade, and Munther Dahleh. “Minimal Realization Problems for Hidden Markov Models.” IEEE Transactions on Signal Processing 64, no. 7 (April 2016): 1896–1904. https://orcid.org/0000-0002-9113-7269 https://orcid.org/0000-0002-1470-2148 en_US http://dx.doi.org/10.1109/tsp.2015.2510969 IEEE Transactions on Signal Processing Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Institute of Electrical and Electronics Engineers (IEEE) arXiv |
| spellingShingle | Ge, Rong Kakade, Sham Huang, Qingqing Dahleh, Munther A Minimal Realization Problems for Hidden Markov Models |
| title | Minimal Realization Problems for Hidden Markov Models |
| title_full | Minimal Realization Problems for Hidden Markov Models |
| title_fullStr | Minimal Realization Problems for Hidden Markov Models |
| title_full_unstemmed | Minimal Realization Problems for Hidden Markov Models |
| title_short | Minimal Realization Problems for Hidden Markov Models |
| title_sort | minimal realization problems for hidden markov models |
| url | http://hdl.handle.net/1721.1/110794 https://orcid.org/0000-0002-9113-7269 https://orcid.org/0000-0002-1470-2148 |
| work_keys_str_mv | AT gerong minimalrealizationproblemsforhiddenmarkovmodels AT kakadesham minimalrealizationproblemsforhiddenmarkovmodels AT huangqingqing minimalrealizationproblemsforhiddenmarkovmodels AT dahlehmunthera minimalrealizationproblemsforhiddenmarkovmodels |