Bounding the cost of learned rules

In this article we approach one key aspect of the utility problem in explan ation-based learning (EBL)-the expensive-role problem-as an avoidable defec t in the learning procedure, In particular, we examine the relationship bet ween the cost of solving a problem without learning versus the cost of usin g a learned rule to provide the same solution, and refer to a learned rule as expensive if its use is more costly than the original problem solving fr om which it was learned. The key idea we explore is that expensiveness is i nadvertently and unnecessarily introduced into learned rules by the learnin g algorithms themselves. This becomes a particularly powerful idea when com bined with an analysis tool which identifies these hidden sources of expens iveness, and modifications of the learning algorithms which eliminate them. The result is learning algorithms for which the cost of learned rules is b ounded by the cost of the problem solving that they replace. (C) 2000 Elsev ier Science B.V. All rights reserved.