Accession Number:

ADA326445

Title:

Bounding the Cost of Learned Rules: A Transformational Approach.

Descriptive Note:

Research rept.,

Corporate Author:

UNIVERSITY OF SOUTHERN CALIFORNIA MARINA DEL REY INFORMATION SCIENCES INST

Personal Author(s):

• Kim, Jihie

Report Date:

1996-12-01

Pagination or Media Count:

174.0

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.

Descriptors:

• *ALGORITHMS
• *LEARNING MACHINES
• *KNOWLEDGE BASED SYSTEMS
• COMPUTERIZED SIMULATION
• DECISION MAKING
• THESES
• RULE BASED SYSTEMS
• PROBLEM SOLVING
• DECISION THEORY
• MAPPING(TRANSFORMATIONS)
• GAME THEORY
• DECISION SUPPORT SYSTEMS
• TRANSFORMATIONAL GRAMMARS

Subject Categories:

• Cybernetics
• Bionics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE