Learning Recursive Theories in the Normal ILP Setting

Article type: Research Article

Authors: Malerba, Donato

Affiliations: Dipartimento di Informatica, via Orabona 4, I-70126 Bari, Italy

Abstract: Induction of recursive theories in the normal ILP setting is a difficult learning task whose complexity is equivalent to multiple predicate learning. In this paper we propose computational solutions to some relevant issues raised by the multiple predicate learning problem. A separate-and-parallel-conquer search strategy is adopted to interleave the learning of clauses supplying predicates with mutually recursive definitions. A novel generality order to be imposed on the search space of clauses is investigated, in order to cope with recursion in a more suitable way. The consistency recovery is performed by reformulating the current theory and by applying a layering technique, based on the collapsed dependency graph. The proposed approach has been implemented in the ILP system ATRE and tested on some laboratory-sized and real-world data sets. Experimental results demonstrate that ATRE is able to learn correct theories autonomously and to discover concept dependencies. Finally, related works and their main differences with our approach are discussed.

Keywords: machine learning, inductive logic programming (ILP), learning recursive theories, multiple predicate learning

Journal: Fundamenta Informaticae, vol. 57, no. 1, pp. 39-77, 2003