A Formal Approach to Learning From Examples

Abstract

This paper presents a formal. foundational approach to learning from examples in machine learning. It is assumed that a learning system is presented with a stream of facts describing a domain of application. The task of the system is to form and modify hypotheses characterising the relations in the domain. based on this information . Presumably the set of hypotheses that may be so formed will require continual revision as further information is received. The emphasis in this paper is to characterise those hypotheses that may potentially be formed . rather than to specify the subset of the hypotheses that . for whatever reason. should be held. To this end, fo rmal systems are derived from which the set of potential hypotheses that may be formed is precisel y specified. A procedure is also derived for restoring the consistency of a set of hypotheses after contlicting evidence is encountered. In addition . this work is extended to where a learning <; y stem may be "told" arbitrary sentences concerning a Jomain . The approach is intended to provide a basic framework for the development of sy stems that learn from examples. as well as a neutral point from which such systems may be viewed and .umpared .