A new role for training problems in EBL

著者: M. Alicia Perez, Oren Etzioni
タイトル: A new role for training problems in EBL
日時: March 1992
概要: Most Explanation-Based Learning (EBL) systems construct explanation 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 probrems pinpoint learning opportunities but do not determine EBL's explanations. Based on this design principle, we developed DYNAMIC, a module that learns control rues 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 probrem distrebution, 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 probrems used by PRODIGY/EBL.
カテゴリ: CMUTR

Category: CMUTR Institution: Department of Computer Science, Carnegie Mellon University Abstract: Most Explanation-Based Learning (EBL) systems construct explanation 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 probrems pinpoint learning opportunities but do not determine EBL's explanations. Based on this design principle, we developed DYNAMIC, a module that learns control rues 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 probrem distrebution, 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 probrems used by PRODIGY/EBL. Number: CMU-CS-92-124 Bibtype: TechReport Month: mar Author: M. Alicia Perez Oren Etzioni Title: A new role for training problems in EBL Year: 1992 Address: Pittsburgh, PA Super: @CMUTR