Inductive Inference of Approximations for Recursive Concepts

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.

Keywords: Learning theory; Inductive inference; Learning with anomalies; Conservative learning; Set-driven learning; Indexed families; Learning from examples; Characterization theorems

©Copyright 2005, Elsevier Science B.V.