Scalability Issues in Inductive Logic Programming

Abstract

Inductive Logic Programming is concerned with a difficult problem: learning in first-order representations. If stated in an unrestricted fashion, ILP’s classical learning task, the inductive acquisition of first-order predictive theories from examples, is undecidable; even the more restricted practical tasks are known to be not polynomially PAC-learnable. The idea of using ILP techniques for Knowledge Discovery in Databases (KDD), or Data Mining, where very large datasets need to be analyzed, thus seems impossible at first sight. However, a number of recent advances have allowed ILP to make significant progress on the road to scalability. In this paper, we will give an illustrative overview of the basic aspects of scalability in ILP, and then described recent advances in theory, algorithms and system implementations. We will give examples from implemented algorithms and briefly introduce M idos , a recent first-order subgroup discovery algorithm and its scalability ingredients.