Concept learning using explanation-based generalization as an abstraction mechanism
William W. Cohen · 1991
Concept learning is the problem of finding an unknown concept given positive and negative examples of members of that concept. Often, in order to make concept learning feasible, it is necessary to use an abstract representation of the examples. This thesis investigates learning algorithms which explicitly change the representation of examples using abstraction functions based on the process of explanation based generalization (Mitchell et al., 1986). In the first section of the thesis, a framework for analysis of abstraction functions for concept learners is presented and employed to analyze a particular abstraction function. A hypothesis space and learning algorithm for the abstract space imposed by this function are then described and analyzed using Valiant's model of pac-learnability (Valiant, 1984). An implementation and several applications of this learning system are also described. In the second section of the thesis, three extensions of this basic learning system are considered. First, an incremental version of the learning system based on an extension of the perceptron learning algorithm is described and analyzed, and its convergence is compared to the convergence of the nonincremental learning system. Second, a version of the system that forms approximate hypotheses is described, and shown to produce substantially better results than either the previous learning system or standard explanation based techniques when applied to the problem of learning control rules for a problem solver. Finally, a version of the system that performs generalization-to-N (i.e., that learns concepts described using recursive rules) is described. The problem of loop induction over trees is defined, and a method is given of integrating the basic learning system with any loop induction algorithm that meets certain formal properties. One suitable loop induction algorithm is described in an appendix; using this loop induction algorithm, the integrated learning system is successfully applied to several examples taken from the literature on generalization-to-N.