ERIC Number: ED353956
Record Type: Non-Journal
Publication Date: 1991-Aug
Reference Count: N/A
Utility Generalization and Composability Problems in Explanation-Based Learning.
Gratch, Jonathan M.; DeJong, Gerald F.
The PRODIGY/EBL system [Minton88] was one of the first works to directly attack the problem of strategy utility. The problem of finding effective strategies was reduced to the problem of finding effective rules. However, this paper illustrates limitations of the approach. There are two basic difficulties. The first arises from the fact that the utility of a control rule cannot be accurately determined from a single instance of the rule. This is a manifestation of a more basic problem which we term the utility generalization problem. The difficulty is that generalization techniques employed by speed-up learning systems are accuracy preserving but not utility preserving. The second difficulty is that control rules interact such that the utility of one control rule is a function of the other control rules in the system. This composability problem means that systems cannot reduce the problem of learning effective strategies to the problem of identifying rule utility in isolation. We document the seriousness of these problems with an example domain theory. With this theory, PRODIGY/EBL generates control strategies which are up to 17 times slower than the original planner. While this raises serious questions about the effectiveness of PRODIGY/EBL, we also claim that the utility generalization and composability problems are basic issues which are not adequately addressed by current speed-up learning techniques. We introduce an alternative technique called COMPOSER. This system is based on a sound statistical model which is validated with a series of experiments. COMPOSER successfully avoids the utility generalization and composability problems. (Contains 33 references.) (Author/ALF)
Publication Type: Information Analyses; Reports - Research
Education Level: N/A
Sponsor: National Science Foundation, Washington, DC.
Authoring Institution: Illinois Univ., Urbana. Dept. of Computer Science.