Learning Approximations of Recursive Concepts

Authors: Steffen Lange, Gunter Grieser and Thomas Zeugmann

Source: Schriftenreihe der Institute für Informatik/Mathematik, SIIM-TR-A-01-03, Medizinische Universität zu Lübeck, March 4, 2001.

Abstract. This paper provides a systematic study of inductive inference of indexable concept classes in learning scenarios where the learner is successful if its final hypothesis describes a finite variant of the target concept, i.e., learning with anomalies. Learning from positive data only and from both positive and negative data is distinguished.

The following learning models are studied: learning in the limit, finite identification, set-driven learning, conservative inference, and behaviorally correct learning.

The attention is focused on the case that the number of allowed anomalies is finite but not a priori bounded. However, results for the special case of learning with an a priori bounded number of anomalies are presented, too. Characterizations of the learning models with anomalies in terms of finite tell-tale sets are provided. The observed varieties in the degree of recursiveness of the relevant tell-tale sets are already sufficient to quantify the differences in the corresponding learning models with anomalies. Finally, a complete picture concerning the relation of all models of learning with and without anomalies mentioned above is derived.

©Copyright 2001 Authors