Learnability of Probabilistic Automata via Oracles
Abstract
Efficient learnability using the state merging algorithm is known for a subclass of probabilistic automata termed μ -distinguishable. In this paper, we prove that state merging algorithms can be extended to efficiently learn a larger class of automata. In particular, we show learnability of a subclass which we call μ _2-distinguishable. Using an analog of the Myhill-Nerode theorem for probabilistic automata, we analyze μ -distinguishability and generalize it to μ _ p -distinguishability. By combining new results from property testing with the state merging algorithm we obtain KL-PAC learnability of the new automata class.
Cite
Text
Guttman et al. "Learnability of Probabilistic Automata via Oracles." International Conference on Algorithmic Learning Theory, 2005. doi:10.1007/11564089_15Markdown
[Guttman et al. "Learnability of Probabilistic Automata via Oracles." International Conference on Algorithmic Learning Theory, 2005.](https://mlanthology.org/alt/2005/guttman2005alt-learnability/) doi:10.1007/11564089_15BibTeX
@inproceedings{guttman2005alt-learnability,
title = {{Learnability of Probabilistic Automata via Oracles}},
author = {Guttman, Omri and Vishwanathan, S. V. N. and Williamson, Robert C.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2005},
pages = {171-182},
doi = {10.1007/11564089_15},
url = {https://mlanthology.org/alt/2005/guttman2005alt-learnability/}
}