Authors: Steffen Lange, Gunter Grieser and Thomas Zeugmann
|
Source:
Theoretical Computer Science Vol. 348, Issue 1, 2005, 15-40. (Special Issue Algorithmic Learning Theory (ALT 2000)). 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 relations of all models of learning with and without anomalies mentioned above is derived.
©Copyright 2005, Elsevier Science B.V. |