DYNAMIC: A New Role for Training Problems in EBL

Abstract

Most Explanation-Based Learning (EBL) systems construct explanations by directly translating a trace of their problem solver's search, on training problems, into proofs. This approach makes proof derivation tractable, but can focus EBL on incidental aspects of its training problems, yielding overly-specific control knowledge. Previous work has described the other extreme: static, a system that generates more general control knowledge by statically analyzing problem-space definitions. However, since static does not utilize training problems, it has a number of potential disadvantages compared with EBL. This paper advocates an intermediate approach in which training problems pinpoint learning opportunities but do not determine EBL's explanations. Based on this design principle, we developed dynamic, a module that learns control rules for the prodigy problem solver. In dynamic, choosing what to explain and how to explain it are independent, dynamic utilizes the analysis algorithms introduced by static, but relies on training problems to achieve the distribution-sensitivity of EBL. On a highly skewed problem distribution, dynamic was almost four times as effective as static in speeding up prodigy. When tested in prodigy/ebl's benchmark problem spaces, dynamic ran considerably faster than prodigy/ebl and produced control rules that were close to three times as effective. In addition, dynamic required only a fraction of the training problems used by prodigy/ebl.