Bounding the Cost of Learned Rules: A Transformational Approach.
Abstract
Efficiency is a major concern for all problem solving systems. One way of achieving efficiency is the application of learning techniques to speed up problem solving. However, many speed-up learning systems suffer from the utility problem: the cost of using the learned knowledge often overwhelms its benefit so that the problem solving time after learning is greater than the problem solving time before learning. Assuring that learned knowledge will in fact speed up system performance has been a focus of research in explanation based learning (EBL). One way of finding a solution which can guarantee the cost boundedness is to analyse all the sources of cost increase in the learning process and then eliminate these sources. This thesis demonstrates how the cost increase of a learned rule in an EBL system can be analyzed by characterizing the learning process as a sequence of transformations. The learning process is decomposed into a sequence of transformations that go from a problem solving episode, through a sequence of intermediate problem solving rule hybrids, to a learned rule. Such an analysis has been performed on Soar (a problem solving system with a variant of EBL). By decomposing the learning process into a sequence of transformations, and analyzing these transformations, the causes which can make the output rule expensive have been identified. This analysis has also pointed the way toward a set of modifications of the transformational sequence that could potentially eliminate these causes. These modifications have been applied to Soar, and the original sequence of transformations has been converted into a new sequence of transformations. The experimental results, at least for the domains investigated, indicate that the time after learning is consistently less than the time before learning with the new learning algorithm.
Document Details
- Document Type
- Technical Report
- Publication Date
- Dec 01, 1996
- Accession Number
- ADA326445
Entities
People
- Jihie Kim
Organizations
- University of Southern California