PAC-LearnabiIit y of Determinate Logic Programs

The field of Inductive Logic Programming (ILP) is concerned with inducing logic pr~ grams from examples in the presence of back-ground knowledge. This paper defines the ILP problem, and describes the various syntactic restrictions that are commonly used for learn-ing first-order representations. We then de-rive some ~ositive results concerning the learn-ability of these restricted classes of lo~ic pro-gram;, by reduction to a standard ~roposi-tional learning problem. More specifically, k-clause predicate definitions consisting of de-terminate, function-free, non-recursive Horn clauses with variables of bounded det)th are polynomially learnable under simple distribu-tions. Similarly, recursive k-clause definitions are polynomially learnable under simple distri-butions if we allow existential and membership queries about the target concept.