On the Computational Complexity of Approximating Distributions by Probabilistic Automata

We introduce a rigorous performance criterion for training algorithms for probabilistic automata (PAs) and hidden Markov models (HMMs), used extensively for speech recognition, and analyze the comp...