TA3: Theory, implementation, and applications of similarity-based retrieval for case-based reasoning

Similarity plays a central role in theories of human problem solving and thus is important for artificial intelligence research. Although there are different approaches to similarity assessment, the underlying idea is to classify information according to some features, so that we can use it in similar situations. Depending on the application domain, the task at hand, and user preferences, the relevance of individual features may vary, and so will the similarity of the concepts they represent. It is paramount to know what affects feature relevance and how to represent such information explicitly.; The objective of this thesis is to improve case-based reasoning by: (1) achieving better accuracy during classification; (2) retrieving cases that are more relevant to a given problem; and (3) obtaining scalability with respect to case base size, case and query complexity. We achieve this goal by introducing a new theory of similarity-based retrieval that uses variable-context similarity assessment, and by defining an efficient iterative retrieval algorithm that employs ideas of incremental view maintenance algorithms from database management systems. Context is a parameter of similarity that specifies what attributes are involved in similarity assessment between cases, and what set of values may be considered for these attributes. It defines which aspects of a case are important in a particular situation. We also define a set of operations, namely relaxation and restriction, which enable to control the relevance of retrieved cases.; We evaluate competence, scalability and algorithmic complexity of a prototype system on diverse real-world domains. We show how the proposed similarity measure supports flexible computation by trading off the accuracy or precision of the computation process for time and space resources. In addition, the case representation used supports case base organization so that cases similar in a given context can be grouped into clusters. This representation also lends itself to attribute-oriented discovery, a technique that finds relevant attributes and their values. The discovery process improves the representation by grouping together relevant, removing unneeded or adding essential attributes. Performance evaluation shows how the discovery process improves system's competence. Iterative retrieval of cases is efficiently handled by the adoption of incremental view maintenance algorithms from database management systems. Performance evaluation shows that this approach improves efficiency of case retrieval and thus helps to achieve system scalability with respect to case base size, case representation and query complexity.