Minimal Realization Problems for Hidden Markov Models
Minimal Realization Problems for Hidden Markov Models
复制标题
隐马尔可夫模型的最小实现问题
DOI：
--
复制
发表时间：
2014
影响因子：
5.4
通讯作者：
M. Dahleh
中科院分区：
文献类型：
--
作者：
Qingqing Huang;Rong Ge;S. Kakade;M. Dahleh
本文解决了隐马尔可夫模型 (HMM) 背景下的两个基本问题。第一个问题涉及最小阶 HMM 的表征和计算，该最小阶 HMM 仅基于此类密度的有限字符串实现输出过程的精确联合密度（称为 HMM 部分实现问题）。第二个问题涉及从随机过程的有限输出观察中学习 HMM。我们回顾并连接了两个研究领域：HMM 的实现理论，以及用于学习潜变量模型的谱方法的最新发展。我们在本文中的主要结果集中于一般情况，即对于几乎所有 HMM 都成立的陈述，不包括参数空间中的测量零集。在主定理中，我们证明了最小准 HMM 实现和最小 HMM 实现都可以基于长度为 N 个字符串的联合概率进行有效计算，其中 N 的量级为 O(logd(k))。换句话说，对于几乎所有 HMM 来说，学习准 HMM 和 HMM 都具有相当的复杂性。
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.