PAC-Learnability of Probabilistic Deterministic Finite State Automata
Abstract
We study the learnability of Probabilistic Deterministic Finite State Automata under a modified PAC-learning criterion. We argue that it is necessary to add additional parameters to the sample complexity polynomial, namely a bound on the expected length of strings generated from any state, and a bound on the distinguishability between states. With this, we demonstrate that the class of PDFAs is PAC-learnable using a variant of a standard state-merging algorithm and the Kullback-Leibler divergence as error function.
Cite
Text
Clark and Thollard. "PAC-Learnability of Probabilistic Deterministic Finite State Automata." Journal of Machine Learning Research, 2004.Markdown
[Clark and Thollard. "PAC-Learnability of Probabilistic Deterministic Finite State Automata." Journal of Machine Learning Research, 2004.](https://mlanthology.org/jmlr/2004/clark2004jmlr-paclearnability/)BibTeX
@article{clark2004jmlr-paclearnability,
title = {{PAC-Learnability of Probabilistic Deterministic Finite State Automata}},
author = {Clark, Alexander and Thollard, Franck},
journal = {Journal of Machine Learning Research},
year = {2004},
pages = {473-497},
volume = {5},
url = {https://mlanthology.org/jmlr/2004/clark2004jmlr-paclearnability/}
}