Utility Generalization and Composability Problems in Explanation-Based Learning.
Saved in:
| Title: | Utility Generalization and Composability Problems in Explanation-Based Learning. |
|---|---|
| Language: | English |
| Authors: | Gratch, Jonathan M., DeJong, Gerald F., Illinois Univ., Urbana. Dept. of Computer Science. |
| Peer Reviewed: | N |
| Page Count: | 24 |
| Publication Date: | 1991 |
| Sponsoring Agency: | National Science Foundation, Washington, DC. |
| Document Type: | Information Analyses Reports - Research |
| Descriptors: | Artificial Intelligence, Computer System Design, Design Requirements, Learning Strategies, Mathematical Models, Planning, Probability, Problem Solving, Search Strategies, Statistical Analysis, Systems Development |
| Abstract: | 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) |
| Entry Date: | 1993 |
| Accession Number: | ED353956 |
| Database: | ERIC |
| FullText | Text: Availability: 0 CustomLinks: – Url: https://eric.ed.gov/contentdelivery/servlet/ERICServlet?accno=ED353956 Name: ERIC Full Text Category: fullText Text: Full Text from ERIC |
|---|---|
| Header | DbId: eric DbLabel: ERIC An: ED353956 AccessLevel: 3 PubType: Report PubTypeId: report PreciseRelevancyScore: 0 |
| IllustrationInfo | |
| Items | – Name: Title Label: Title Group: Ti Data: Utility Generalization and Composability Problems in Explanation-Based Learning. – Name: Language Label: Language Group: Lang Data: English – Name: Author Label: Authors Group: Au Data: <searchLink fieldCode="AR" term="%22Gratch%2C+Jonathan+M%2E%22">Gratch, Jonathan M.</searchLink><br /><searchLink fieldCode="AR" term="%22DeJong%2C+Gerald+F%2E%22">DeJong, Gerald F.</searchLink><br /><searchLink fieldCode="AR" term="%22Illinois+Univ%2E%2C+Urbana%2E+Dept%2E+of+Computer+Science%2E%22">Illinois Univ., Urbana. Dept. of Computer Science.</searchLink> – Name: PeerReviewed Label: Peer Reviewed Group: SrcInfo Data: N – Name: Pages Label: Page Count Group: Src Data: 24 – Name: DatePubCY Label: Publication Date Group: Date Data: 1991 – Name: SourceSuprt Label: Sponsoring Agency Group: SrcSuprt Data: National Science Foundation, Washington, DC. – Name: TypeDocument Label: Document Type Group: TypDoc Data: Information Analyses<br />Reports - Research – Name: Subject Label: Descriptors Group: Su Data: <searchLink fieldCode="DE" term="%22Artificial+Intelligence%22">Artificial Intelligence</searchLink><br /><searchLink fieldCode="DE" term="%22Computer+System+Design%22">Computer System Design</searchLink><br /><searchLink fieldCode="DE" term="%22Design+Requirements%22">Design Requirements</searchLink><br /><searchLink fieldCode="DE" term="%22Learning+Strategies%22">Learning Strategies</searchLink><br /><searchLink fieldCode="DE" term="%22Mathematical+Models%22">Mathematical Models</searchLink><br /><searchLink fieldCode="DE" term="%22Planning%22">Planning</searchLink><br /><searchLink fieldCode="DE" term="%22Probability%22">Probability</searchLink><br /><searchLink fieldCode="DE" term="%22Problem+Solving%22">Problem Solving</searchLink><br /><searchLink fieldCode="DE" term="%22Search+Strategies%22">Search Strategies</searchLink><br /><searchLink fieldCode="DE" term="%22Statistical+Analysis%22">Statistical Analysis</searchLink><br /><searchLink fieldCode="DE" term="%22Systems+Development%22">Systems Development</searchLink> – Name: Abstract Label: Abstract Group: Ab Data: 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) – Name: DateEntry Label: Entry Date Group: Date Data: 1993 – Name: AN Label: Accession Number Group: ID Data: ED353956 |
| PLink | https://search.ebscohost.com/login.aspx?direct=true&site=eds-live&db=eric&AN=ED353956 |
| RecordInfo | BibRecord: BibEntity: Languages: – Text: English PhysicalDescription: Pagination: PageCount: 24 Subjects: – SubjectFull: Artificial Intelligence Type: general – SubjectFull: Computer System Design Type: general – SubjectFull: Design Requirements Type: general – SubjectFull: Learning Strategies Type: general – SubjectFull: Mathematical Models Type: general – SubjectFull: Planning Type: general – SubjectFull: Probability Type: general – SubjectFull: Problem Solving Type: general – SubjectFull: Search Strategies Type: general – SubjectFull: Statistical Analysis Type: general – SubjectFull: Systems Development Type: general Titles: – TitleFull: Utility Generalization and Composability Problems in Explanation-Based Learning. Type: main BibRelationships: HasContributorRelationships: – PersonEntity: Name: NameFull: Illinois Univ., Urbana. Dept. of Computer Science. – PersonEntity: Name: NameFull: Gratch, Jonathan M. – PersonEntity: Name: NameFull: DeJong, Gerald F. IsPartOfRelationships: – BibEntity: Dates: – D: 01 M: 08 Type: published Y: 1991 |
| ResultId | 1 |
