Inductive Strengthening: The Effects of a Simple Heuristic for Restricting Hypothesis Space Search

This paper examines the effects on a learning program of using a simple heuristic for restricting hypothesis space search and suggests the desirability of making the heuristic explicit so that it can be altered easily.  The heuristic is: only consider new hypotheses that cover at least one example not covered by the current concept description.  We study the use of the heuristic for three tasks: (i) restricting subsequent search after part of a concept description is learned, (ii) restricting search when partial concept descriptions are provided as initial knowledge, and (iii) restricting search when the heuristic is used as a constant bias to a higher level program that adjusts the bias of the learning program along different dimensions.  We show that not only does this heuristic reduce the number of nodes searched, it also reduces the size of the resultant concept description and increases its predictive accuracy.