Iterative versionspaces with an application in inductive logic programming
Author:
Abstract:
This thesis consists of two parts: in the first part we develop a language-independent framework for efficiently solving concept learning problems; in the second part we apply this framework to Inductive Logic Programming. We view concept learning as a search problem. In the well-known framework of Versionspaces a bi-directional depth-first search algorithm that learns a maximally general and maximally specific concept representation is presented, and contrasted to the breadth-first approach of Mellish's Description Identification algorithm. In this context, we identify redundant information elements, in order to reduce the memory needed for storing information elements. We describe how automatically generated information elements can replace less informative ones. Next, we extend this framework to describe the more complex versionspaces that originate from introducing disjunctions. To be practically useful, we gradually restrict these disjunctive versionspaces by imposing preference criteria, based on notions of minimality. This leads to extensions of the non-disjunctive algorithms to the disjunctive case. In the second part of the thesis we show in detail how this general framework can be instantiated to Inductive Logic Programming. In this respect we also discuss the integration of machine learning in a planning system based on Horn clause logic. This illustrates that the use of a logical representation allows a smooth integration of Machine Learning and Problem Solving. In summary, the thesis contributes to the understanding and the development of search algorithms for concept learning in general, by developing a language independent framework, and by introducing several novel and generally applicable concept learning techniques. The application in the second part of the thesis shows that the framework is practically useful, and that it contributes to the field of Inductive Logic Programming.