An Incremental Deductive Strategy for Controlling Constructive Induction in Learning from Examples

摘要

This article describes LAIR, a constructive induction system that acquires conjunctive concepts by applying a domain theory to introduce new features into the evolving concept description. Each acquired concept is added to the domain theory, making LAIR a closed-loop learning system that weakens the inductive bias with each iteration of the learning loop. LAIR's novel feature is the use of an incremental deductive strategy for constructive induction, reducing the amount of inference required for learning. A series of experiments manipulated features of learning tasks to assess this incremental method of constructive induction relative to an uncontrolled constructive induction process that extends each example description with all derivable features. These learning tasks differed in global characteristics of the domain theory, the training sequence, and the percentage of irrelevant features in the example descriptions. The results show that LAIR's constructive induction approach saves considerable inferencing effort, with little or no cost in the number of examples needed to reach a learning criterion. The experimental results also underscored the importance of viewing a domain theory as a search space, identifying several factors that impact the deductive and inductive aspects of constructive induction, such as concept definition overlap, density of features, and fan-in and fan-out of inference chains. The paper also discusses LAIR's operation as a pac-learner and its relation to other constructive induction techniques.