Skip to main content
main-content

Über dieses Buch

The 2001 International Conference on Case-Based Reasoning (ICCBR 2001, www.iccbr.org/iccbr01), the fourth in the biennial ICCBR series (1995 in Sesimbra, Portugal; 1997 in Providence, Rhode Island (USA); 1999 in Seeon, Germany), was held during 30 July – 2 August 2001 in Vancouver, Canada. ICCBR is the premier international forum for researchers and practitioners of case based reasoning (CBR). The objectives of this meeting were to nurture significant, relevant advances made in this field (both in research and application), communicate them among all attendees, inspire future advances, and continue to support the vision that CBR is a valuable process in many research disciplines, both computational and otherwise. ICCBR 2001 was the first ICCBR meeting held on the Pacific coast, and we used the setting of beautiful Vancouver as an opportunity to enhance participation from the Pacific Rim communities, which contributed 28% of the submissions. During this meeting, we were fortunate to host invited talks by Ralph Bergmann, Ken Forbus, Jaiwei Han, Ramon López de Mántaras, and Manuela Veloso. Their contributions ensured a stimulating meeting; we thank them all.

Inhaltsverzeichnis

Frontmatter

Invited Papers

Highlights of the European INRECA Projects

INduction and REasoning from CAses was the title of two large European CBR projects funded by the European Commission from 1992 – 1999. In total, the two projects (abbreviated INRECA and INRECA-II) have obtained an overall funding of 3 MEuro, which enabled the 5 project partners to perform 55 person years of research and development work. The projects made several significant contributions to CBR research and helped shaping the European CBR community. The projects initiated the rise of three SMEs that base their main business on CBR application development, employing together more than 100 people in 2001. This paper gives an overview of the main research results obtained in both projects and provides links to the most important publications of the consortium.

Ralph Bergmann

The Synthesis of Expressive Music: A Challenging CBR Application

This paper is based on an invited talk, given at ICCBR’01, about the research performed at the IIIA on the problem of synthesizing expressive music. In particular, describes several extensions and improvements of a previously reported system [5,4,6,3] capable of generating expressive music by imitating human performances. The system is based on Case-Based Reasoning (CBR) and Fuzzy techniques.

Ramon López de Mántaras, Josep Lluís Arcos

Why Case-Based Reasoning is Attractive for Image Interpretation

The development of image interpretation systems is concerned with tricky problems such as a limited number of observations, environmental influence, and noise. Recent systems lack robustness, accuracy, and flexibility. The introduction of case-based reasoning (CBR) strategies can help to overcome these drawbacks. The special type of information (i.e., images) and the problems mentioned above provide special requirements for CBR strategies. In this paper we review what has been achieved so far and research topics concerned with case-based image interpretation. We introduce a new approach for an image interpretation system and review its components.

Petra Perner

Research Papers

Similarity Assessment for Relational CBR

Reasoning and learning from cases are based on the concept of similarity often estimated by a distance. This paper presents LAUD, a distance measure that can be used to estimate similarity among relational cases. This measure is adequate for domains where cases are best represented by relations among entities. An experimental evaluation of the accuracy of LAUD is presented for the task of classifying marine sponges.

Eva Armengol, Enric Plaza

Acquiring Customer Preferences from Return-Set Selections

This paper describes LCW, a procedure for learning customer preferences by observing customers’ selections from return sets. An empirical evaluation on simulated customer behavior indicated that an uninformed hypothesis about customer weights leads to low ranking accuracy unless customers place some importance on almost all features or the total number of features is quite small. In contrast, LCW’s estimate of the mean preferences of a customer population improved as the number of customers increased, even for larger numbers of features of widely differing importance. This improvement in the estimate of mean customer preferences led to improved prediction of individual customer’s rankings, irrespective of the extent of variation among customers and whether a single or multiple retrievals were permitted. The experimental results suggest that the return set that optimizes benefit may be smaller for customer populations with little variation than for customer populations with wide variation.

L. Karl Branting

The Role of Information Extraction for Textual CBR

The benefits of CBR methods in domains where cases are text depend on the underlying text representation. Today, most TCBR approaches are limited to the degree that they are based on efficient, but weak IR methods. These do not allow for reasoning about the similarities between cases, which is mandatory for many CBR tasks beyond text retrieval, including adaptation or argumentation. In order to carry out more advanced CBR that compares complex cases in terms of abstract indexes, NLP methods are required to derive a better case representation. This paper discusses how state-of-the-art NLP/IE methods might be used for automatically extracting relevant factual information, preserving information captured in text structure and ascertaining negation. It also presents our ongoing research on automatically deriving abstract indexing concepts from legal case texts. We report progress toward integrating IE techniques and ML for generalizing from case texts to our CBR case representation.

Stefanie Brüninghaus, Kevin D. Ashley

Case-Based Reasoning in Course Timetabling: An Attribute Graph Approach

An earlier Case-based Reasoning (CBR) approach developed by the authors for educational course timetabling problems employed structured cases to represent the complex relationships between courses. The retrieval searches for structurally similar cases in the case base. In this paper, the approach is further developed to solve a wider range of problems. We also attempt to retrieve those cases that have common similar structures with some differences. Costs that are assigned to these differences have an input upon the similarity measure. A large number of experiments are performed consisting of different randomly produced timetabling problems and the results presented here strongly indicate that a CBR approach could provide a significant step forward in the development of automated systems to solve difficult timetabling problems. They show that using relatively little effort, we can retrieve these structurally similar cases to provide high quality timetables for new timetabling problems.

Edmund K. Burke, Bart MacCarthy, Sanja Petrovic, Rong Qu

Ranking Algorithms for Costly Similarity Measures

Case retrieval for e-commerce product recommendation is an application of CBR that demands particular attention to efficient implementation. Users expect quick response times from on-line catalogs, regardless of the underlying technology. In FindMe systems research, the cost of metric application has been a primary impediment to efficient retrieval. This paper describes several types of general and special-purpose ranking algorithms for case retrieval and evaluates their impact on retrieval efficiency with the Entree restaurant recommender.

Robin Burke

A Fuzzy-Rough Approach for Case Base Maintenance

This paper proposes a fuzzy-rough method of maintaining Case- Based Reasoning (CBR) systems. The methodology is mainly based on the idea that a large case library can be transformed to a small case library together with a group of adaptation rules, which take the form of fuzzy rules generated by the rough set technique. In paper [1], we have proposed a methodology for case base maintenance which used a fuzzy decision tree induction to discover the adaptation rules; in this paper, we focus on using a heuristic algorithm, i.e., a fuzzy-rough algorithm [2] in the process of simplifying fuzzy rules. This heuristic, regarded as a new fuzzy learning algorithm, has many significant advantages, such as rapid speed of training and matching, generating a family of fuzzy rules which is approximately simplest. By applying such a fuzzy-rough learning algorithm to the adaptation mining phase, the complexity of case base maintenance is reduced, and the adaptation knowledge is more compact and effective. The effectiveness of the method is demonstrated experimentally using two sets of testing data, and we also compare the maintenance results of using fuzzy ID3, in [1], and the fuzzy-rough approach, as in this paper.

Guoqing Cao, Simon Shiu, Xizhao Wang

Learning and Applying Case-Based Adaptation Knowledge

Adaptation is an important step in CBR when applied to design tasks. However adaptation knowledge can be difficult to acquire directly from an expert. Nevertheless, CBR tools provide few facilities to assist with the acquisition of adaptation knowledge. This paper considers a special class of design task, where a component-based solution can be developed in stages, and suggests adaptation knowledge that is suited to CBR systems for component-based design. A case-based adaptation is proposed where the adaptation cases are generated from the original problem-solving case-base, and so knowledge acquisition is automated. Both numeric and nominal targets are adapted, although a different case-based adaptation is applied for each. The gains of adaptation are presented for a tablet formulation application, although the approach is suited for other formulation and configuration tasks that apply a component-based approach to design. The learned adaptation knowledge is understandable to the expert, with the effect that he can criticise the content and refine the knowledge if necessary. Results are promising but the case-based adaptation systems offer many opportunities for optimisation and further learning.

Susan Craw, Jacek Jarmulak, Ray Rowe

Case Representation Issues for Case-Based Reasoning from Ensemble Research

Ensembles of classifiers will produce lower errors than the member classifiers if there is diversity in the ensemble. One means of producing this diversity in nearest neighbour classifiers is to base the member classifiers on different feature subsets. In this paper we show four examples where this is the case. This has implications for the practice of feature subset selection (an important issue in CBR and data-mining) because it shows that, in some situations, there is no single best feature subset to represent a problem. We show that if diversity is emphasised in the development of the ensemble that the ensemble members appear to be local learners specializing in sub-domains of the problem space. The paper concludes with some proposals on how analysis of ensembles of local learners might provide insight on problem-space decomposition for hierarchical CBR.

Pádraig Cunningham, Gabriele Zenobi

A Declarative Similarity Framework for Knowledge Intensive CBR

This paper focuses on the design of knowledge intensive CBR systems and introduces a domain-independent architecture to help it. Our approach is based on acquiring the domain knowledge by reusing knowledge from a library of ontologies and integrating it with CBROnto, a task based ontology comprising common CBR terminology. In this paper we focus in retrieval and similarity assessment processes taking advantage of this domain knowledge. We describe our CBROnto based similarity representation framework and explain how it is used to represent similarity measures and retrieval processes.

Belén Díaz-Agudo, Pedro A. González-Calero

Classification Based Retrieval Using Formal Concept Analysis

This paper shows how the use of Formal Concept Analysis (FCA) can support CBR application designers, in the task of discovering knowledge embedded in a case base. FCA application provides an internal sight of the case base conceptual structure and allows finding regularity patterns among the cases. Moreover, it extracts dependence rules between the attributes describing the cases, that will be used to guide the query formulation process. In this paper we focus in classification based retrieval and the utility of Galois lattices as structures to classify and retrieve cases.

Belén Díaz-Agudo, Pedro A. González-Calero

Conversational Case-Based Planning for Agent Team Coordination

This paper describes a prototype in which a conversational case-based reasoner, NaCoDAE, was agentified and inserted in the RET- SINA multi-agent system. Its task was to determine agent roles within a heterogeneous society of agents, where the agents may use capability- based or team-oriented agent coordination strategies. There were three reasons for assigning this task to NaCoDAE: (1) to relieve the agents of the overhead of determining, for themselves, if they should be involved in the task, or not; (2) to convert seemingly unrelated data into contextually relevant knowledge — as a case-based reasoning system, NaCo-DAE is particularly suited for applying apparently incoherent data to a wide variety of domain-specific situations; and (3) as a conversational CBR system, to both unobtrusively listen to human statements and to proactively dialogue with other agents in a more goal-directed approach to gathering relevant information. The cases maintained by NaCoDAE have question and answer components, which were originally intended to maintain the textual representations of questions and answers for humans. By associating agent capability descriptions and queries with the case questions, NaCoDAE also assumed the team role of a capability- based coordinator. By encoding fragments of HTN plan objectives in its case actions, we were able to convert NaCoDAE into a conversational case-based planner that served compositionally-generated HTN plan objectives, already populated with situation-relevant knowledge, for use by the RETSINA team-oriented agents.

Joseph A. Giampapa, Katia Sycara

A Hybrid Approach for the Management of FAQ Documents in Latin Languages

Essential for the success of FAQ systems is their ability to systematically manage knowledge, including the intelligent retrieval of useful FAQ documents and the continuous evolution of the knowledge base. Based on our experience, we propose a hybrid approach for the management of FAQ documents on programming languages written in Portuguese, Spanish or other latin languages. Our approach integrates various types of knowledge and provides intelligent mechanisms for knowledge access as well as the continuous evolution and improvement of the FAQ system throughout its life cycle. The principal strength of this approach lies in the integration of Case-Based Reasoning and Information Retrieval techniques, customized to the specific requirements and characteristics of FAQ document management. Our work is currently being implemented and evaluated in the context of an international research project.

Christiane Gresse von Wangenheim, Andre Bortolon, Aldo von Wangenheim

Taxonomic Conversational Case-Based Reasoning

Conversational Case-Based Reasoning (CCBR) systems engage a user in a series of questions and answers to retrieve cases that solve his/her current problem. Help-desk and interactive troubleshooting systems are among the most popular implementations of the CCBR methodology. As in traditional CBR systems, features in a CCBR system can be expressed at varying levels of abstraction. In this paper, we identify the sources of abstraction and argue that they are uncontrollable in applications typically targeted by CCBR systems. We contend that ignoring abstraction in CCBR can cause representational inconsistencies, adversely affect retrieval and conversation performance, and lead to case indexing and maintenance problems. We propose an integrated methodology called Taxonomic CCBR that uses feature taxonomies for handling abstraction to correct these problems. We describe the benefits and limitations of our approach and examine issues for future research.

Kalyan Moy Gupta

A Case-Based Reasoning View of Automated Collaborative Filtering

From some perspectives Automated Collaborative Filtering (ACF) appears quite similar to Case-Based Reasoning (CBR). It works on data organised around users and assets that might be considered case descriptions. In addition, in some versions of ACF, much of the induction is deferred to run time — in the lazy learning spirit of CBR. On the other hand, because of its lack of semantic descriptions it seems to be the antithesis of case-based reasoning — a learning approach based on case representations. This paper analyses the characteristics shared by ACF and CBR, it highlights the differences between the two approaches and attempts to answer the question “When is it useful or valid to consider ACF as CBR?”. We argue that a CBR perspective on ACF can only be useful if it offers insights into the ACF process and supports a transfer of techniques. In conclusion we present a case retrieval net model of ACF and show how it allows for enhancements to the basic ACF idea.

Conor Hayes, Pádraig Cunningham, Barry Smyth

A Case-Based Approach to Tailoring Software Processes

Software development is a knowledge-intensive activity involving the integration of diverse knowledge sources that undergo constant change. The volatility of knowledge in software development demands approaches that retrieve episodic knowledge and support the continuous knowledge acquisition process. To address these issues, case-based technology is used in combination with an organizational learning process to create an approach that turns Standard Development Methodologies (SDM) into living documents that capture project experiences and emerging requirements as they are encountered in an organization. A rule-based system is used to tailor the SDM to meet the characteristics of individual projects and provide relevant development knowledge throughout the development lifecycle.

Scott Henninger, Kurt Baumgarten

The Conflict Graph for Maintaining Case—Based Reasoning Systems

The maintenance of case—based reasoning systems is remarkably important for the continuous working ability of case—based reasoning applications. To ensure the utility of these applications case properties like correctness, consistency, incoherence, minimality, and uniqueness are applied to measure the quality of the underlying case base. Based on the case properties, the conflict graph presents a novel visualization of conflicts between cases and provides a technique on how to eliminate these conflicts and therefore maintain the quality of a case base. An evaluation on ten real world case bases shows the applicability of the introduced technique.

Ioannis Iglezakis

Issues on the Effective Use of CBR Technology for Software Project Prediction

This paper explores some of the practical issues associated with the use of case-based reasoning (CBR) or estimation by analogy for software project effort prediction. Different research teams have reported varying experiences with this technology. We take the view that the problems hindering the effective use of CBR technology are twofold. First, the underlying characteristics of the datasets play a major role in determining which prediction technique is likely to be most effective. Second, when CBR is that technique, we find that configuring a CBR system can also have a significant impact upon predictive capabilities. In this paper we examine the performance of CBR when applied to various datasets using stepwise regression (SWR) as a benchmark. We also explore the impact of the choice of number of analogies and the size of the training dataset when making predictions.

Gada Kadoda, Michelle Cartwright, Martin Shepperd

Incremental Case-Based Plan Recognition Using State Indices

We describe a case-based approach to the keyhole plan-recognition task where the observed agent is a state-space planner whose world states can be monitored. Case-based approach provides means for automatically constructing the plan library from observations, minimizing the number of extraneous plans in the library. We show that the knowledge about the states of the observed agent’s world can be effectively used to recognize agent’s plans and goals, given no direct knowledge about the planner’s internal decision cycle. Cases (plans) containing state knowledge enable the recognizer to cope with novel situations for which no plans exist in the plan library, and to further assist in effective discrimination among competing plan hypothesis.

Boris Kerkez, Michael T. Cox

A Similarity-Based Approach to Attribute Selection in User-Adaptive Sales Dialogs

For dynamic sales dialogs in electronic commerce scenarios, approaches based on an information gain measure used for attribute selection have been suggested. These measures consider the distribution of attribute values in the case base and are focused on the reduction of dialog length. The implicit knowledge contained in the similarity measures is neglected. Another important aspect that has not been investigated either is the quality of the produced dialogs, i.e. if the retrieval result is appropriate to the customer’s demands. Our approach takes the more direct way to the target products by asking the attributes that induce the maximum change of similarity distribution amongst the candidate cases, thereby faster discriminating the case base in similar and dissimilar cases. Evaluations show that this approach produces dialogs that reach the expected retrieval result with fewer questions. In real world scenarios, it is possible that the customer cannot answer a question. To nevertheless reach satisfactory results, one has to balance between a high information gain and the probability that the question will not be answered. We use a Bayesian Network to estimate these probabilities.

Andreas Kohlmaier, Sascha Schmitt, Ralph Bergmann

When Two Case Bases Are Better than One: Exploiting Multiple Case Bases

Much current CBR research focuses on how to compact, refine, and augment the contents of individual case bases, in order to distill needed information into a single concise and authoritative source. However, as deployed case-based reasoning systems become increasingly prevalent, opportunities will arise for supplementing local case bases on demand, by drawing on the case bases of other CBR systems addressing related tasks. Taking full advantage of these case bases will require multi-case-base reasoning: Reasoning not only about how to apply cases, but also about when and how to draw on particular case bases. This paper begins by considering tradeoffs of attempting to merge individual case bases into a single source, versus retaining them individually, and argues that retaining multiple case bases can benefit both performance and maintenance. However, achieving the benefits requires methods for case dispatching—deciding when to retrieve from external case bases, and which case bases to select—and for cross-case-base adaptation to revise suggested solutions from one context to apply in another. The paper presents initial experiments illustrating how these procedures may a ect the benefits of using multiple case bases, and closes by delineating key research issues for multi-case-base reasoning.

David B. Leake, Raja Sooriamurthi

COBRA: a CBR-Based Aproach for Predicting Users Actions in a Web Site

In this paper we describe an original case-based reasoning (CBR) approach, called Cobra, that aims at predicting users requests in a web site. The basic idea underlying the Cobra approach is to model users navigational behavior in a web site by a set of cases. Typically, in a CBR system a case is composed of at least two parts: the situation or the problem part and the solution one. In the Cobra approach the situation part of a case captures a navigation experience within a user navigation session. The solution part is composed of a set of actions that may explain the transition (i.e. the move from one page to another) which follows the navigation experience described in the case situation part. The proposed case structure and the reuse phase enable to predict the access to pages that have never been visited before by any user. This is a very useful feature that matches prediction requirements in real web sites where the structure and the content change frequently over time.

Maria Malek, Rushed Kanawati

Similarity vs. Diversity

Case-based reasoning systems usually accept the conventional similarity assumption during retrieval, preferring to retrieve a set of cases that are maximally similar to the target problem. While we accept that this works well in many domains, we suggest that in others it is misplaced. In particular, we argue that often diversity can be as important as similarity. This is especially true in case-based recommender systems. In this paper we propose and evaluate strategies for improving retrieval diversity in CBR systems without compromising similarity or efficiency.

Barry Smyth, Paul McClave

Collaborative Case-Based Reasoning: Applications in Personalised Route Planning

Distributed case-based reasoning architectures have the potential to improve the overall performance of case-based reasoning systems. In this paper we describe a collaborative case-based reasoning architecture, which allows problem solving experiences to be shared among multiple agents.We demonstrate how this technique can be used successfully to solve an important challenge in the area of personalised route planning; the problem of how to generate route plans that conform to a user’s implicit travel preferences in an unfamiliar map territory.

Lorraine Mc Ginty, Barry Smyth

Helping a CBR Program Know What It Knows

Case-based reasoning systems need to know the limitations of their expertise. Having found the known source cases most relevant to a target problem, they must assess whether those cases are similar enough to the problem to warrant venturing advice. In experimenting with SIROCCO, a twostage case-based retrieval program that uses structural mapping to analyze and provide advice on engineering ethics cases, we concluded that it would sometimes be better for the program to admit that it lacks the knowledge to suggest relevant codes and past source cases. We identified and encoded three strategic metarules to help it decide. The metarules leverage incrementally deeper knowledge about SIROCCO’s matching algorithm to help the program “know what it knows.” Experiments demonstrate that the metarules can improve the program’s overall advice-giving performance.

Bruce M. McLaren, Kevin D. Ashley

Precision and Recall in Interactive Case-Based Reasoning

Often in interactive case-based reasoning (CBR), the case library is irreducible in the sense that the deletion of a single case means that a unique product or fault is no longer represented in the case library. We present empirical measures of precision and recall for irreducible case libraries, identify sources of imperfect precision and recall, and establish an upper bound for the level of precision that can be achieved with any retrieval strategy. Finally, we present a retrieval strategy for irreducible case libraries that gives better precision and recall than inductive retrieval or nearest-neighbour retrieval based on the number of matching features in a target case.

David McSherry

Meta-Case-Based Reasoning: Using Functional Models to Adapt Case-Based Agents

It is useful for an intelligent software agent to be able to adapt to new demands from an environment. Such adaptation can be viewed as a redesign problem; an agent has some original functionality but the environment demands an agent with a slightly different functionality, so the agent redesigns itself. It is possible to take a case-based approach to this redesign task. Furthermore, one class of agents which can be amenable to redesign of this sort is case-based reasoners. These facts suggest the notion of "meta-case-based reasoning," i.e., the application of case-based redesign techniques to the problem of adapting a case-based reasoning process. Of course, meta-case-based reasoning is a very broad topic. In this paper we focus on a more specific issue within meta-case- based reasoning: balancing the use of relatively efficient but knowledge intensive symbolic techniques with relatively flexible but computationally costly numerical techniques. In particular, we propose a mechanism whereby qualitative functional models are used to efficiently propose a set of design alternatives to specific elements within a meta-case and then reinforcement learning is used to select among these alternatives. We describe an experiment in which this mechanism is applied to a case- based disassembly agent. The results of this experiment show that the combination of model-based adaptation and reinforcement learning can address meta-case-based reasoning problems which are not effectively addressed by either approach in isolation.

J. William Murdock, Ashok K. Goel

Exploiting Interchangeabilities for Case Adaptation

While there are many general methods for case retrieval, case adaptation usually requires problem-specific knowledge and it is still an open problem. In this paper we propose a general method for solving case adaptation problems for the large class of problems which can be formulated as Constraint SatisfactionProblems. This method is based on the concept of interchangeability between values in problem solutions. The method is able to determine how change propagates in a solution set and generate a minimal set of choices which need to be changed to adapt an existing solution to a new problem.The paper presents the proposed method, algorithms and test results for a resource allocation domain.

Nicoleta Neagu, Boi Faltings

Ensemble Case-Based Reasoning: Collaboration Policies for Multiagent Cooperative CBR

Multiagent systems offer a new paradigm to organize AI applications. Our goal is to develop techniques to integrate CBR into applications that are developed as multiagent systems. CBR offers the multiagent systems paradigm the capability of autonomously learning from experience. In this paper we present a framework for collaboration among agents that use CBR and some experiments illustrating the framework. We focus on three collaboration policies for CBR agents: Peer Counsel, Bounded Counsel and Committee policies. The experiments show that the CBR agents improve their individual performance collaborating with other agents without compromising the privacy of their own cases. We analyze the three policies concerning accuracy, cost, and robustness with respect to number of agents and case base size.

Enric Plaza, Santiago OntaÑón

MaMa: A Maintenance Manual for Case—Based Reasoning Systems

In this paper, we consider Case—Based Reasoning (CBR) as a complex process. In order to perform such a complex process in a specific project, we argue that an appropriate process model helps to accomplish the process in a well—structured manner. We briefly review some existing process models to define the necessary concepts to specify a process model for CBR. Thereby, we identify several levels of abstraction for process definitions, and explain the role of concrete manuals at one of these levels. For one particular phase of the CBR process, namely the maintenance phase, we outline a maintenance manual and characterize some of its components. Initial experiences with the maintenance manual called MaMa illustrate the purpose of such a manual and indicate the usefulness of its application in specific projects.

Thomas Roth—Berghofer, Thomas Reinartz

Rough Sets Reduction Techniques for Case-Based Reasoning

Case Based Reasoning systems are often faced with the problem of deciding which instances should be stored in the case base. An accurate selection of the best cases could avoid the system being sensitive to noise, having a large memory storage requirements and, having a slow execution speed. This paper proposes two reduction techniques based on Rough Sets theory: Accuracy Rough Sets Case Memory (AccurCM) and Class Rough Sets Case Memory (ClassCM). Both techniques reduce the case base by analysing the representativity of each case of the initial case base and applying a different policy to select the best set of cases. The first one extracts the degree of completeness of our knowledge. The second one obtains the quality of approximation of each case. Experiments using different domains, most of them from the UCI repository, show that the reduction techniques maintain accuracy obtained when not using them. The results obtained are compared with those obtained using well-known reduction techniques.

Maria Salamó, Elisabet Golobardes

sequential Instance-Based Learning for Planning in the Context of an Imperfect Information Game

Finding sequential concepts, as in planning, is a complex task because of the exponential size of the search space. Empirical learning can be an effective way to find sequential concepts from observations. Sequential Instance-Based Learning (SIBL), which is presented here, is an empirical learning paradigm, modeled after Instance-Based Learning (IBL) that learns sequential concepts, ordered sequences of state-action pairs to perform a synthesis task. SIBL is highly effective and learns expert-level knowledge. SIBL demonstrates the feasibility of using an empirical learning approach to discover sequential concepts. In addition, this approach suggests a general framework that systematically extends empirical learning to learning sequential concepts. SIBL is tested on the domain of bridge.

Jenngang Shih

Learning Feature Weights from Case Order Feedback

Defining adequate similarity measures is one of the most difficult tasks when developing CBR applications. Unfortunately, only a limited number of techniques for supporting this task by using machine learning techniques have been developed up to now. In this paper, a new framework for learning similarity measures is presented. The main advantage of this approach is its generality, because its application is not restricted to classification tasks in contrast to other already known algorithms. A first refinement of the introduced framework for learning feature weights is described and finally some preliminary experimental results are presented.

Armin Stahl

Adaptation by Applying Behavior Routines and Motion Strategies in Autonomous Navigation

This paper presents our current efforts toward development of highlevel behavior routines and motion strategies for the stepwise case-based reasoning (SCBR) approach. The SCBR approach provides an appropriate architectural framework for autonomous navigation system in which situation cases are used to support the situation module, and route cases are used to support the high-level route planning module. In the SCBR approach, adaptation knowledge comes in the form of high-level behavior routines and motion strategies. The SCBR system determines next action based on an analysis of the generated view in terms of positions of relevant objects. Thus, higher-level case-based symbolic reasoning intervenes at the action selection points to determine which action vector is appropriate to control the SCBR system. In order to qualitatively evaluate the SCBR approach, we have developed a simulation environment. This simulation environment allows us to visually evaluate the progress of an SCBR system while it runs through a predefined virtual world.

Haris Supic, Slobodan Ribaric

An Accurate Adaptation-Guided Similarity Metric for Case-Based Planning

In this paper, we present an adaptation-guided similarity metric based on the estimate of the number of actions between states, called ADG (Action Distance-Guided). It is determined by using a heuristic calculation extracted from the heuristic search planning, called FF, which was the fastest planner in the AIPS’2000 competition. This heuristic provides an accurate estimate of the distance between states that is appropriated for similarity measures. Consequently, the ADG becomes a new approach, suitable for domain independent case-based planning systems that perform state-space search.

Flavio Tonidandel, Márcio Rillo

Releasing Memory Space Through a Case-Deletion Policy with a Lower Bound for Residual Competence

The number of techniques that focuses on how to create compact casebase in case-base maintenance has been increasing over the last few years. However, while those techniques are concerned with choosing suitable cases to improve the system performance, they do not deal with the problem of a limited memory space, which may affect the performance as well. Even when a CBR system admits only a limited number of stored cases in memory, there will still exist the storage-space problem if it has cases that vary in size, as in most of case-based planning domains. This paper focuses on case-deletion policy to release space in the case memory, which can guarantee the competencepreserving property and establish a theoretical lower bound for residual competence.

Flavio Tonidandel, Márcio Rillo

Using Description Logics for Designing the Case Base in a Hybrid Approach for Diagnosis Integrating Model and Case-Based Reasoning

In this paper we propose an approach of how to use description logics for modeling the case base for case-based reasoning. We illustrate our approach by applying it to hybrid diagnosis. Integrating model-based and case-based reasoning for diagnostic problem solving we contribute to the domain of real time diagnosis. We describe the architecture of this approach, and present some preliminary experimental results. The case-based reasoning component of the hybrid diagnosis system is enabled to exploit description logic inferences for classifying and querying the case base. As description logic interpreter we use the system CICLOP, whereas the diagnosis system is implemented in G2. The description logic system runs as a server application and can thus be queried by the diagnosis system.

Yacine Zeghib, FranÇois De Beuvron, Martina Kullmann

Application Papers

T-Air: A Case-Based Reasoning System for Designing Chemical Absorption Plants

In this paper we describe a case-based reasoning application developed for aiding engineers in the design of chemical absorption plants. Based on the notion of flow sheet, the paper describes how the application uses a highly structured representation of cases and similarity criteria based on chemical knowledge for designing solutions following an interactive case-based reasoning approach.

Josep Lluìs Arcos

Benefits of Case-Based Reasoning in Color Matching

GE Plastics has a case-based reasoning tool that determines color formulas which match requested colors that has been in use since 1995. This tool, called FormTool, has saved GE millions of dollars in productivity and colorant costs. The technology developed in FormTool has been used to create an on-line color selection tool for our customers called, ColorXpress Select. A customer innovation center has been developed around the FormTool software.

William Cheetham

CBR for Dimensional Management in a Manufacturing Plant

Dimensional management is a form of quality assurance for the manufacture of mechanical structures, such as vehicle bodies. Establishing and maintaining dimensional control is a process of adjusting complex machinery for environmental and material changes to manufacture product to specifications within very small tolerances. It involves constant monitoring of the process as well as responding to crises. A good deal of undocumented “folk wisdom” is built up by the dimensional management teams on how to diagnosis and cure problems, but this knowledge tends to be lost over time (people can’t remember, people move on) and is rarely shared from shop to shop. Our project involves establishing a case-based diagnostic system for dimensionalmanagement problems, which can also serve as a system for systematically documenting solved dimensional-control problems. It is intended that this documentation should be meaningful over time and be shareable between plants. The project includes defining a workable case structure and matching ontology, especially to establish the context and generic language to accomplish this. A prototype system has been launched in a vehicle assembly plant.

Alexander P. Morgan, John A. Cafeo, Diane I. Gibbons, Ronald M. Lesperance, Gülcin H. Sengir, Andrea M. Simon

Real-Time Creation of Frequently Asked Questions

This paper analyzes the case duration of product defects in high-tech product customer support. User inquiries about new defects often increase very rapidly within a few weeks. They continue to increase until corresponding solutions are provided or new versions appear. Typical user inquiries are added into FAQ (frequently-asked questions) case bases using conventional case-based reasoning (CBR) tools by expert engineers later on. However, some additions take too much time. Such knowledge may really be necessary within a few weeks after a problem first appears. This paper describes SignFinder, which analyzes textual user inquiries stored in a database of a call tracking sys-tem and extracts remarkably increasing cases between two user-specified time periods. If SignFinder is given a problem description, it displays a list of recently increasing keywords in the cases that include the problem description. These keywords can signal new defects. An empirical experiment shows that such increasing keywords can become salient features for retrieving signs of new defects not yet recognized by expert engineers. SignFinder is not a general-purpose case retriever. It only retrieves frequency-increasing similar-looking cases to a user’s problem description. SignFinder fills in the time gap between the first appearing time of a new defect and the time when the defect and its solution are added into a FAQ case base using a conventional CBR system.

Hideo Shimazu, Dai Kusui

Managing Diagnostic Knowledge in Text Cases

A valuable source of field diagnostic information for equipment service resides in the text notes generated during service calls. Intelligent knowledge extraction from such textual information is a challenging task. The notes are characterized by misspelled words, incomplete information, cryptic technical terms, and non-standard abbreviations. In addition, very few of the total number of notes generated may be diagnostically useful. We present an approach for identifying diagnostically relevant notes from the many raw field service notes and information is presented in this paper. N-gram matching and supervised learning techniques are used to generate recommendations for the diagnostic significance of incoming service notes. These techniques have potential applications in generating relevant indices for textual CBR.

Anil Varma

Emerging Applications

CBR Adaptation for Chemical Formulation

Solution adaptation of previously solved cases to fit new situations is one of the basic tasks of the Case-Based Reasoning (CBR) approach for problem solving. The central issue of the paper is to present a formal computational model for the chemical formulation as innovative adaptation of previously developed products for new scenario and/or constraints in product design process. This general model (called Abstract Compound Machine - ACM) allows knowledge about chemical formulation to be explicitly represented, computed, integrated and performed in a CBR architecture. The specific domain that is presented as an example for the implementation of the ACM model regards the creation of rubber compounds. Its generality allows it to be adopted in cases of chemical formulation where basic ingredients are expressed in discrete quantities.

Stefania Bandini, Sara Manzoni

A Case-Based Reasoning Approach for Due-Date Assignment in a Wafer Fabrication Factory

This study explores a new application of Case-Based Reasoning (CBR) in the due-date assignment problem of the wafer fabrication factory. Owing to the complexity of the wafer fabrication, the manufacturing processes of the wafer are very complicated and time-consuming. Thus, the due-date assignment of each order presents a challenging problem to the production planning and scheduling people. Since the product of each order is closely related to the products manufactured before, the CBR approach provides a good tool for us to apply it to the due-date assignment problem. The CBR system could potentially replace the human decision in the estimation of the due-date. Therefore, a CBR system is developed in this study using the similarity coefficient of each order with previous orders. The experimental results show that the proposed approach is very effective and comparable with a neural network approach.

Pei-Chann Chang, Jih-Chang Hsieh, T. Warren Liao

DubLet: An Online CBR System for Rental Property Recommendation

Searching for accommodation in Dublin’s fast-moving rental market can be a difficult and frustrating process. Ideally, the accommodation seeker would have access to a support system that could consolidate available rental information, recommend suitable properties, and always be at hand with the most current information. This paper describes the fully implemented DubLet system to provide just such support. DubLet is an application that employs core CBR methods to recommend rental properties drawn from a number of online sources using Information Extraction techniques. User interaction is provided both via web-browser and via WAP mobile phone. The paper gives an overview of the DubLet system implementation, presents an evaluation of the extraction and recommendation methods, and describes future system directions.

Gareth Hurley, David C. Wilson

Improved Performance Support through an Integrated Task-Based Video Case Library

Case-based retrieval and other decision support systems typically exist separately from the tools and tasks they support. Users are required to initiate searches and identify target case features manually, and as a result the systems are not used to their full extent. We describe an approach to integrating an ASK system—a type of video case library—with a performance support tool. This approach uses model-based task tracking to retrieve cases relevant to how a user is performing a task, not just to the artifacts that are created during the process.

Christopher L. Johnson, Larry Birnbaum, Ray Bareiss, Tom Hinrichs

Transforming Electronic Mail Folders into Case Bases

This paper analyzes instant knowledge sharing among customer support agents. Customer support agents effectively exchange useful information through electronic mail and electronic bulletin board services. Empirical analyses have taught us that the direct use of electronic mail is the key towards instant knowledge sharing in busy organizations like high-tech product customer support organizations. The authors have developed “Interaction Viewer”, an instant CBR tool that runs with commercial electronic mail management systems such as Microsoft Outlook Express. The tool analyzes the relations among electronic mail messages by tracing the body texts and extracting quotation descriptions inserted in the bodies. A pair of a question mail message and its answer mail message is integrated into a case. Because all mail messages are automatically modified into cases and mail folders are transformed into a case base, instant knowledge sharing is easily achieved. Although the case retrieval performance is not as good as more integrated CBR systems, the easy-to-adopt feature of the approach should be welcome by busy organizations. It should also be welcome by marketing divisions to analyze various customers opinions.

Dai Kusui, Hideo Shimazu

Case-Based Reasoning in the Care of Alzheimer’s Disease Patients

Planning the ongoing care of Alzheimer’s Disease (AD) patients is a complex task, marked by cases that change over time, multiple perspectives, and ethical issues. Geriatric interdisciplinary teams of physicians, nurses and social workers currently plan this care without computer assistance. Although AD is incurable, interventions are planned to improve the quality of life for patients and their families. Much of the reasoning involved is case-based, as clinicians look to case histories to learn which interventions are effective, to document clinical findings, and to train future health care professionals.There is great variability among AD patients, and within the same patient over time. AD is not yet well enough understood for universally effective treatments to be available. The case-based reasoning (CBR) research paradigm complements the medical research approach of finding treatments effective for all patients by matching patients to treatments that were effective for similar patients in the past.The Auguste Project is an effort to provide decision support for planning the ongoing care of AD patients, using CBR and other thought processes natural to members of geriatric interdisciplinary teams. System prototypes are used to explore the reasoning processes involved and to provide the forerunners of practical clinical tools. The first system prototype has just been completed. This prototype supports the decision to prescribe neuroleptic drugs to AD patients with behavioral problems. It uses CBR to determine if a neuroleptic drug should be prescribed and rule-based reasoning to select one of five approved neuroleptic drugs for a patient. The first system prototype serves as proof of concept that CBR is useful for planning ongoing care for AD patients. Additional prototypes are planned to explore the research issues raised.

Cindy Marling, Peter Whitehouse

Prototype of an Intelligent Failure Analysis System

The investigation of commercial/industrial failures is a vital, but complex task. This paper presents an Intelligent Failure Analysis System (aIFAS). It is a system designed by a failure analyst with the goal of making failure investigation easier. The knowledge base for aIFAS comes from commercial laboratory reports. The methodologies employed represent the experience gained from over six years of development. One goal of aIFAS is to provide a case-based expert system tool to help find answers. Functionality ranges from matching a new case against stored example cases to extracting relational data from the aIFAS knowledge base.

Claude Mount, T. Warren Liao

Applying CBR and Object Database Techniques in Chemical Process Design

The aim of this paper is to introduce a new method for finding and reusing process equipment design and inherently safer process configurations by case-based reasoning (CBR) and object database techniques. CBR is based on finding most alike existing solutions and applying the knowledge of their properties for solving new problems in the early phases of design. This supports design engineer’s knowledge by allowing a systematic reuse of existing experience in order to improve the quality and safety of new designs. The possibilities of CBR and object database techniques in chemical process engineering field have been illustrated by two prototype applications.

Timo Seuranen, Elina Pajula, Markku Hurme

Mining High-Quality Cases for Hypertext Prediction and Prefetching

Case-based reasoning aims to use past experience to solve new problems. A strong requirement for its application is that extensive experience base exists that provides statistically significant justification for new applications. Such extensive experience base has been rare, limiting most CBR applications to be confined to small-scale problems involving single or few users, or even toy problems. In this work, we present an application of CBR in the domain of web document prediction and retrieval, whereby a server-side application can decide, with high accuracy and coverage, a user’s next request for hypertext documents based on past requests. An application program can then use the prediction knowledge to prefetch or presend web objects to reduce latency and network load. Through this application, we demonstrate the feasibility of CBR application in the web-document retrieval context, exposing the vast possibility of using web-log files that contain document retrieval experiences from millions of users. In this framework, a CBR system is embedded within an overall web-server application. A novelty of the work is that data mining and case-based reasoning are combined in a seamless manner, allowing cases to be mined efficiently. In addition we developed techniques to allow different case bases to be combined in order to yield a overall case base with higher quality than each individual ones. We validate our work through experiments using realistic, large-scale web logs.

Qiang Yang, Ian Tian-Yi Li, Henry Haining Zhang

Backmatter

Weitere Informationen