Automatic Learning from Positive Data and Negative Counterexamples
Abstract
We introduce and study a model for learning in the limit by finite automata from positive data and negative counterexamples. The focus is on learning classes of languages with a membership problem computable by finite automata (so-called automatic classes). We show that, within the framework of our model, finite automata (automatic learners) can learn all automatic classes when memory of a learner is restricted by the size of the longest datum seen so far. We also study capabilities of automatic learners in our model with other restrictions on the memory and how the choice of negative counterexamples (arbitrary, or least, or the ones whose size is bounded by the longest positive datum seen so far) can impact automatic learnability.
Cite
Text
Jain and Kinber. "Automatic Learning from Positive Data and Negative Counterexamples." International Conference on Algorithmic Learning Theory, 2012. doi:10.1007/978-3-642-34106-9_9Markdown
[Jain and Kinber. "Automatic Learning from Positive Data and Negative Counterexamples." International Conference on Algorithmic Learning Theory, 2012.](https://mlanthology.org/alt/2012/jain2012alt-automatic/) doi:10.1007/978-3-642-34106-9_9BibTeX
@inproceedings{jain2012alt-automatic,
title = {{Automatic Learning from Positive Data and Negative Counterexamples}},
author = {Jain, Sanjay and Kinber, Efim B.},
booktitle = {International Conference on Algorithmic Learning Theory},
year = {2012},
pages = {66-80},
doi = {10.1007/978-3-642-34106-9_9},
url = {https://mlanthology.org/alt/2012/jain2012alt-automatic/}
}