Robust learning of automatic classes of languages
No Thumbnail Available
Date
2010-04-22T05:28:14Z
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
This paper adapts and investigates the paradigm of robust learning, originally defined in the framework of inductive inference of classes of recursive functions, to learning languages from positive data.
Robustness is a very desirable property, as it captures a form of invariance of learnability under admissible transformations of the object of study.The classes of languages of interest are automatic, that is, recognisable by finite automata. A class of first-order definable operators - called translators - is introduced as natural transformations that preserve automaticity of a class of languages and the inclusion relationships between languages in the class. For many learning criteria, we provide a characterization of the classes of languages all of whose translations are learnable under that criterion. The learning criteria have been chosen from the literature on both explanatory learning and query learning, and include consistent and conservative learning, strong-monotonic learning, strong-monotonic consistent learning, finite learning, learning from subset queries, learning from superset queries and learning from membership queries.