Extensions of Logic Programming as a Representation Language for Machine Learning

The representation language of Machine Learning has undergone a substantial evolution, starting from numerical descriptions to an attribute-value representations and finally to first order logic languages. In particular, Logic Programming has recently been studied as a representation language for learning in the research area of Inductive Logic Programming. The contribution of this thesis is twofold. First, we identify two problems of existing Inductive Logic Programming techniques: their limited ability to learn from an incomplete background knowledge and the use of a two-valued logic that does not allow to consider some pieces of information as unknown. Second, we overcome these limits by prosecuting the general trend in Machine Learning of increasing the expressiveness of the representation language. Two learning systems have been developed that represent knowledge using two extensions of Logic Programming, namely abductive logic programs and extended logic programs. Abductive logic programs allow abductive reasoning to be performed on the knowledge. When dealing with an incomplete knowledge, abductive reasoning can be used to explain an observation or a goal by making some assumptions about incompletely specified predicates. The adoption of abductive logic programs as a representation language for learning allows to learn from an incomplete background knowledge: abductive reasoning is used during learning for completing the available knowledge. The system ACL (Abductive Concept Learning) for learning abductive logic programs has been implemented and tested on a number of datasets. The experiments show that the performance of the system when learning from incomplete knowledge are superior or comparable to those of ICL-Sat, mFOIL and FOIL. Extended logic programs contain a second form of negation (called explicit negation) besides negation by default. They allow the adoption of a three-valued model and the representation of both the target concept and its opposite. The two-valued setting that is usually adopted in Inductive Logic Programming can be a limitation in some cases, for example in the case of a robot that autonomously explores the surrounding world and that acts on the basis of the partial knowledge it posseses. For such a robot is important to distinguish what is true from what is false and what is unknown and therefore it needs to adopt a three-valued logic. The system LIVE (Learning In a three-Valued Environment) has been implemented that is able to learn extended logic programs containing a definition for both the concept and its opposite. Moreover, the definitions learned may allow exceptions. In this case, a definition for the class of exceptions is learned and for exceptions to exceptions, if present. In this way, hierarchies of exceptions can be learned.