Learning Classes of Probabilistic Automata
Abstract
Probabilistic finite automata (PFA) model stochastic languages, i.e. probability distributions over strings. Inferring PFA from stochastic data is an open field of research. We show that PFA are identifiable in the limit with probability one. Multiplicity automata (MA) is another device to represent stochastic languages. We show that a MA may generate a stochastic language that cannot be generated by a PFA, but we show also that it is undecidable whether a MA generates a stochastic language. Finally, we propose a learning algorithm for a subclass of PFA, called PRFA.
Cite
Text
Denis and Esposito. "Learning Classes of Probabilistic Automata." Annual Conference on Computational Learning Theory, 2004. doi:10.1007/978-3-540-27819-1_9Markdown
[Denis and Esposito. "Learning Classes of Probabilistic Automata." Annual Conference on Computational Learning Theory, 2004.](https://mlanthology.org/colt/2004/denis2004colt-learning/) doi:10.1007/978-3-540-27819-1_9BibTeX
@inproceedings{denis2004colt-learning,
title = {{Learning Classes of Probabilistic Automata}},
author = {Denis, François and Esposito, Yann},
booktitle = {Annual Conference on Computational Learning Theory},
year = {2004},
pages = {124-139},
doi = {10.1007/978-3-540-27819-1_9},
url = {https://mlanthology.org/colt/2004/denis2004colt-learning/}
}