Bounding the cost of learned rules: A transformational approach
Jihie Kim · University of Southern California Digital Library · 2017
My dissertation research centers on application of machine learning techniques to speed up problem solving. In fact, many speed-up learning systems suffer from the utiliv problem; time after learning is greater than time before learning. Discovering how to assure 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 that cost after learning is bounded by cost of problem solving is to analyze all the sources of cost increase in the learning process and then eliminate these sources. I began on this task by decomposing the learning process 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. This transformational analysis itself is important to understand the characteristics of the learning system, including cost changes through learning. Such an analysis has been performed for Soar/EBL(Kim & Rosenbloom 1995). The learning process has been decomposed into a sequence of transformations from the problem solving to learned rule. By analyzing these transformations, I have identified three sources which can make the output rule expensive. First, ignoring search-control rules which constrained the problem solving can increase the cost. For example, PRODIGY/EBL (Minton 1993) and Soar ignore a large part of the search-control rules in learning to increase the generality of the learned rules. The consequence of this omission is that the learned rules are not constrained by the path actually taken in the problem space, and thus can perform an exponential amount of search even when the original problem-space search was highly directed (by the control rules). By incorporating search control in the explanation structure, this problem can be avoided (Kim & Rosenbloom 1993). Second, when the structure of the problem solving differs from the structure of the match process for the learned rules, time after learning can be greater than time before learning. During problem solving, the rules that fire tend to form a hierarchical structure in which the ewly rules provide information upon which the firing of later rules depends. This hierarchical structure is reflected in EBL most obviously in the structure of the explanation (an1 the more general