Cryptographic Limitations on Learning One-Clause Logic Programs

Abstract

An active area of research in machine learning is learning logic programs from examples. This paper investigates formally the problem of learning a single Horn clause: we focus on generalizations of the language of constant-depth determinate clauses, which is used by several practical learning systems. We show first that determinate clauses of logarithmic depth are not learnable. Next we show that learning indeterminate clauses with at most k indeterminate variables is equivalent to learning DNF. Finally, we show that recursive constant-depth determinate clauses are not learnable. Our primary technical tool is the method of predictionpreserving reducibilities introduced by Pitt and Warmuth [ 1990 ] ; as a consequence our results are independent of the representations used by the learning system. Introduction Recently, there has been an increasing amount of research in learning restricted logic programs, or inductive logic programming (ILP) [ Cohen, 1992; Muggleton and Feng, 1992; Qui...