Learning High Utility Rules

Learning High Utility Rules

Efficiency is a major concern for all problem solving systems. One of the ways of achieving efficiency is gradual improvement in performance by learning. However, in some EBL systems the cost of learned knowledge often overwhelms its benefit. This phenomenon is called the utility problem, and it has turned out to be pervasive in many learning systems which are intended to speed up the problem solving. The research on this problem has focused on two key issues. The first issue is the expensive chunk problem, in which individual learned rules are so expensive to match that the system suffers a slow down from learning. The second issue is the average growth effect, in which the interactions across the rules slow down the system, even if none of the rules individually are all that expensive. This research focuses on the expensive chunk problem in EBL --- a representative form of speed-up learning.

The goal of this research is to understand how EBL systems can prevent the slowdown after learning. By analyzing the learning process and comparing the cost after learning with the cost before learning, we are trying to reveal why some learned rules become expensive than the problem solving. The analysis is performed in the context of Soar. Learning in Soar, called chunking, is a variant of EBL, and also suffers from the expensive chunk problem.

Relevant Publications

Jihie Kim (jihie@isi.edu)