Learning Overcomplete HMMs

Understand

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.