Learning Overcomplete HMMs
This addresses a poorly understood challenge in machine learning with practical importance, providing both tractable and intractable boundaries, but it is incremental in defining specific subclasses rather than a general solution.
The paper tackles the problem of learning overcomplete HMMs with many hidden states and small output alphabets, showing positive results for sparse, well-conditioned transition matrices and negative results for random regular graphs with large degree.
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.