On the Computational Complexity of Approximating Distributions by Probabilistic Automata.
Naoki AbeManfred K. WarmuthPublished in: COLT (1990)
Keyphrases
- probabilistic automata
- computational complexity
- finite automata
- relative entropy
- markov chain
- probability distribution
- random variables
- finite state automata
- kullback leibler divergence
- special case
- np hard
- sound theoretical
- graphical models
- decision problems
- closed form
- pattern matching
- grammatical inference
- feature selection
- principal component analysis
- active learning
- metadata