Induction in logic
Luc De Raedt · 1996
Various inductive machine learning approaches and problem specificstious are analysed from s logical perspective. This results in a unifying framework for the logical aspects of inductive machine learning and data mining. The framework exp]~R logical ,~m;l,~Tities s~d differences between different machine learning settings, and allows us to relate past and present work on inductive machine learning using logic (such as structural matching, inductive logic programming, data ~;-;~g, etc.). Central to the unifying framework are three dimansions: learning from enta;lment versus learning from interpretations, learning CNF versus DNF, learning characteristic versus dlscriminsnt descriptions. Though the exposition handles both first order and propositional logic, it is meant to be understandable for everyone familiar with propositional logic. Motivation Most machine learning and knowledge discovery in databases approaches use logical representation languages to represent data and hypotheses. Despite this uniform representation language, it is often hard to appreciate the differences and similarities in this approaches. In my oppinion this is not only due to the technical nature of some of these papers (in particular in the field of inductive logic programming (Muggieton and De Raedt 1994; Muggleton 1992; De Raedt 1996)), but also to the lack of a unifying framework for these approaches. In this paper, an attempt is made to build such a unifying framework. The unifying framework builds on past work along at least three different dimensions. The first dimension, learning from entailment versus learning from interpretations (Angluin et 6l. 1992; Frazier and Pitt 1993), determines whether the observations are logical statements that are (resp. are not) logically entailed by the target theory, or are interpretations (or variable-assignments) that satisfy (resp. do not satify) the target theory. Whereas propositional learners learn from interpretations (as for instance in computational learning theory and attribute value |earning, (Valiant 1984)), most first der learners learn from entailment (in particular the field of inductive logic programming). Past work along this dimension includes (Anglnin eta/. 1992; Frasier and Pitt 1993; De Raedt and Lavra~ 1993). The second dimension distinguishes conjunctive versus disjunctive normal forms, e.g. (Mooney 1995; Haussler 1988; De Raedt and Van Laer 1995). The third dimension is based on the type of learning, i.e. characteristic versus discriminant versus data-mining, and is derived from the work of Michalski (Michalski 1983). Furthermore, the unifying framework allows to give in logical terms precise definitions of what is meant by deduction, induction, generalization, specialization, and their relations, not only formalising these terms but also showing how their relation can be exploited. At the same time, some links between different machine learning settings are formulated in a novel way, in particular inductive logic programming versus structural matching (as studied by e.g. (Vere 1975; Vraln 1990)), and concept-learning versus data-mining. Though the unifying framework offers some new insights, it extensively borrows from previous work, in particular from (Michalski 1983; 1994) on generalization and specialisation and various other aspects, from (Niblett 1988; Kodratoff 1988) on logic and generalization, and from (De Raedt st ,q. 1996; Mooney 1995; De Raedt and Van Laer 1995) on the relation between CNF and DNF. Though the exposition handles first order as well as propositional logic, it is meant to be understandable for everyone familiar with propositional logic. This paper is structured as follows: first, a short review of logic is presented, followed by a short review of concept-learning; second, learning from entailment and from interpretations is formalized; third, the relation between generality, induction and logic is discussed, fourth, the differences and relations between CNF and DNF are analysed; fifth, characteristic concept-learning is reformulated as data mining; finally, some conclusions are drawn and relations to de Raedt 27 From: Proceedings of the Third International Conference on Multistrategy Learning. Copyright © 1996, AAAI (www.aaai.org). All rights reserved. earlier work are presented.