Learning Overcomplete HMMs
Learning Overcomplete HMMs
复制标题
DOI：
--
复制
发表时间：
2017-11
期刊：
影响因子：
--
通讯作者：
Vatsal Sharan;S. Kakade;Percy Liang;G. Valiant
中科院分区：
文献类型：
--
作者：
Vatsal Sharan;S. Kakade;Percy Liang;G. Valiant
我们研究了学习过完备Hacks的问题-那些有许多隐藏状态但输出字母表很小的Hacks。尽管具有重大的实际重要性，但人们对此类隐马尔可夫模型的了解很少，对于高效学习没有已知的积极或消极结果。在本文中，我们提出了几个新的结果-积极的和消极的-这有助于定义之间的边界易处理和难处理的设置。具体来说，我们显示出积极的结果，一个大的子类的HALGORITHM的过渡矩阵是稀疏的，良好的条件，并有小概率质量短周期。另一方面，我们表明，学习是不可能的，只有一个多项式数量的样本，一个小的输出字母表，其过渡矩阵是随机的正则图与大的程度的障碍。我们还讨论了这些结果的背景下，学习的阻碍，可以捕捉长期的依赖关系。
We study the problem of learning overcomplete HMMs---those that have many hidden states but a small output alphabet. Despite having significant practical importance, such HMMs are poorly understood with no known positive or negative results for efficient learning. In this paper, we present several new results---both positive and negative---which help define the boundaries between the tractable and intractable settings. Specifically, we show positive results for a large subclass of HMMs whose transition matrices are sparse, well-conditioned, and have small probability mass on short cycles. On the other hand, we show that learning is impossible given only a polynomial number of samples for HMMs with a small output alphabet and whose transition matrices are random regular graphs with large degree. We also discuss these results in the context of learning HMMs which can capture long-term dependencies.