Constraining Learning with Search Control

Many learning systems must confront the problem of run time after learning being greater than run time before learning. This utility problem has been a particular focus of research in explanation-based learning. In past work we have examined an approach to the utility problem that is based on restricting the expressiveness of the rule language so as to guarantee polynomial bounds on the cost of using learned rules. In this article we propose a new approach that limits the cost of learned rules without guaranteeing an a priori bound on the match process or restricting the expressibility of rule conditions. By making the learning mechanism sensitive to the control knowledge utilized during the problem solving that led to the creation of the new rule - i.e., by incorporating such control knowledge into the explanation - the cost of using the learned rule becomes bounded by the cost of the problem solving from which it was learned.