Dynamic memory for design

Abstract

This thesis addresses the problem of providing an efficient case memory suitable for use with case-based reasoning in design. First, the requirements of a case memory for design are identified. Then a formal specification of a dynamic memory which satisfies these requirements is produced based on the idea of the memory organization packet presented in Schank’s model of dynamic memory and the assumption that design cases are decomposed into excerpts. Memory organization packets are used to represent both the excerpts themselves and the generalizations that may be formed from them. The term trace is used to refer to a memory organization packet that represents an excerpt and the term epitome is used for one that represents a generalization. A memory organization packet may be both a trace and an epitome simultaneously. The memory organization packets are the nodes of a structure and are linked together by links from more general nodes to their specializations indexed by their differences. Minimum storage requirements to meet this specification are identified and it is shown that, after a short period of exponential growth, this requirement increases linearly with the number of case excerpts processed and that the rate of growth is exponentially related to the maximum length of an excerpt. Algorithms, based on this specification, which perform efficient retrieval of complete and partial matches to queries are presented. Complete match retrieval takes time proportional to the size of the query and retrieval of partial matches is optimal in the sense that the minimum number of nodes necessary to find all partial matches are visited. A method for retrieving approximate matches by using partial match procedures is also presented. A mechanism for choosing between multiple responses to retrieval requests that takes into account both how frequently excerpts have been seen (or generalizations have been supported) and how recently they have been seen (or supported) is presented. The dynamic memory is then implemented in a series of increasingly sophisticated implementations culminating in one that is optimal in terms of the number of nodes used. The series of implementations are used so that problems associated with formation of generalizations, exploitation of inheritance, multiple indexing and removal of node redundancy can be addressed separately and as simply as possible. In particular problems with exploitation of inheritance and multiple indexing which could lead to selective forgetting and spurious erroneous recollections (respectively) are identified and corrected. An empirical evaluation of the trade-offs between processing time increases due to the more complex algorithms of the final implementation and the savings in storage space that they allow is made. The results of this evaluation showed that the reduction in the number of nodes to be processed more than compensated for the increased complexity of the insertion algorithms. Excerpt insertion times for the final implementation are slightly less than for any of the other three. The average time to process retrievals is slightly longer for the final implementation than the others due to the complications with inheritance when node redundancy is eliminated. Additionally, an empirical evaluation of the effects of increasing the maximum length of excerpts was made. This evaluation confirmed the hypothesis that the number of nodes required increases dramatically as the maximum size of excerpts grows and that this is a more important factor in determining feasibility than the number of excerpts. The application of this kind of memory structure to classification problems is briefly discussed. In this area it has the advantage of being able to identify further tests that could be performed to resolve a classification problem when the existing data is insufficient to produce a unique solution. Additionally, the undifferentiated strength can be used to guide the choice between two competing classifications where it is not possible to gather more data.