Inductive Learning from Good Examples

Abstract

We study what kind of data may ease the computational complexity of learning of Horn clause theories (in Gold's paradigm) and Boolean functions (in PAC-learning paradigm). We give several definitions of good data (basic and generative representative sets), and develop data-driven algorithms that learn faster from good examples, and degenerate to learn in the limit from the "worst" possible examples. We show that Horn clause theories, kterm DNF and general DNF Boolean functions are polynomially learnable from generative representative presentations. 1 Introduction In any inductive learning model, how data of the target theory are supplied to the learning programs is a crucial assumption. Identification in the limit [ Gold, 1967 ] assumes that the series of examples is an admissible enumeration of all (positive and/or negative) examples of the target concept, and requires the learning algorithm to produce a correct hypothesis in some finite time. However, the computational time and th...