Operationality Criteria for Recursive Predicates

Abstract

Current explanation-based generalization (EBG) tech-niques can perform badly when the problem being solved involves recursion. Often an infinite series of learned concepts are generated that correspond to the expansion of recursive solutions over every finite depth. Previous attempts to address the problem, such as Shavlik’s generalization-to-N EBG method, are overly reluctant to expand recursions; this reluctance can lead to inefficient rules. In this paper EBG is viewed as a program transformation technique on logic programs. Within that framework an improved operationality cri-terion for controlling the expansion of recursions is presented. This criterion prevents certain infinite and combinatorially explosive rule classes from being gen-erated, yet permits expansion in some useful circum-stances, allowing more efficient rules to be learned.