Foundations of Soft Case-Based Reasoning

Foundations of Soft Case-Based Reasoning\ \ By Sankar K. Pal Simon C. K. Shiu \ John & Wiley Sons\ Copyright © 2004 John Wiley & Sons, Inc.\ All right reserved.\ ISBN: 0-471-08635-5 \ \ \ Chapter One\ INTRODUCTION\ 1.1 BACKGROUND\ The field of case-based reasoning (CBR), which has a relatively young history, arose out of the research in cognitive science. The earliest contributions in this area were from Roger Schank and his colleagues at Yale University. During the period 1977-1993, CBR research was highly regarded as a plausible high-level model for cognitive processing. It was focused on problems such as how people learn a new skill and how humans generate hypotheses about new situations based on their past experiences. The objectives of these cognitive-based researches were to construct decision support systems to help people learn. Many prototype CBR systems were built during this period: for example, Cyrus, Mediator, Persuader, Chef, Julia, Casey, and Protos. Three CBR workshops were organized in 1988, 1989, and 1991 by the U.S. Defense Advanced Research Projects Agency (DARPA). These formally marked the birth of the discipline of case-based reasoning. In 1993, the first European workshop on case-based reasoning (EWCBR-93) was held in Kaiserslautern, Germany. It was a great success, and it attracted more than 120 delegates and over 80 papers. Since then, many international workshops and conferences on CBR have beenheld in different parts of the world, such as the following:\ Second European Workshop on CBR (EWCBR-94), Chantilly, France\ First International Conference on CBR (ICCBR-95), Sesimbra, Portugal\ Third European Workshop on CBR (EWCBR-96), Lausanne, Switzerland\ Second International Conference on CBR (ICCBR-97), Providence, Rhode Island\ Fourth European Workshop on CBR (EWCBR-98), Dublin, Ireland\ Third International Conference on CBR (ICCBR-99), Seeon Monastery, Munich, Germany\ Fifth European Workshop on CBR (EWCBR-00), Trento, Italy\ Fourth International Conference on CBR (ICCBR-01), Vancouver, Canada\ Sixth European Conference on CBR (ECCBR-02), Aberdeen, Scotland\ Fifth International Conference on CBR (ICCBR-03), Trondheim, Norway\ Seventh European Conference on CBR (ECCBR-04), Madrid, Spain\ Other major artificial intelligence conferences, such as ECAI (European Conference on Artificial Intelligence), IJCAI (International Joint Conference on Artificial Intelligence), and one organized by the AAAI (American Association for Artificial Intelligence), have also had CBR workshops as part of their regular programs. Recently, CBR has drawn the attention of researchers from Asia, such as the authors of this book, from countries such as Hong Kong and India.\ The rest of this chapter is organized as follows. In Section 1.2 we describe the various components and features of CBR. The guidelines and advantages of using CBR are explained in Sections 1.3 and 1.4, respectively. In Section 1.5 we address the tasks of case representation and indexing, and in Section 1.6 we provide basic concepts in case retrieval. The need and process of case adaptation are explained briefly in Section 1.7. The issues of case learning and case-base maintenance are discussed in Section 1.8. In Section 1.9 an example is provided to demonstrate how a CBR system can be built. The question of whether CBR is a methodology or a technology is discussed in Section 1.10. Finally, in Section 1.11 the relevance to CBR of soft computing tools is explained.\ 1.2 COMPONENTS AND FEATURES OF CASE-BASED REASONING\ Let us consider a medical diagnosis system as a typical example of using case-based reasoning in which the diagnosis of new patients is based on physicians' past experience. In this situation, a case could represent a person's symptoms together with the associated treatments. When faced with a new patient, the doctor compares the person's current symptoms with those of earlier patients who had similar symptoms. Treatment of those patients is then used and modified, if necessary, to suit the new patient (i.e., some adaptation of previous treatment may be needed). In real life there are many similar situations that employ the CBR paradigm to build reasoning systems, such as retrieving preceding law cases for legal arguments, determining house prices based on similar information from other real estate, forecasting weather conditions based on previous weather records, and synthesizing a material production schedule from previous plans.\ From the examples above we see that a case-based reasoner solves new problems by adapting solutions to older problems. Therefore, CBR involves reasoning from prior examples: retaining a memory of previous problems and their solutions and solving new problems by reference to that knowledge. Generally, a case-based reasoner will be presented with a problem, either by a user or by a program or system. The case-based reasoner then searches its memory of past cases (called the case base) and attempts to find a case that has the same problem specification as the case under analysis. If the reasoner cannot find an identical case in its case base, it will attempt to find a case or multiple cases that most closely match the current case.\ In situations where a previous identical case is retrieved, assuming that its solution was successful, it can be offered as a solution to the current problem. In the more likely situation that the case retrieved is not identical to the current case, an adaptation phase occurs. During adaptation, differences between the current and retrieved cases are first identified and then the solution associated with the case retrieved is modified, taking these differences into account. The solution returned in response to the current problem specification may then be tried in the appropriate domain setting.\ The structure of a case-based reasoning system is usually devised in a manner that reflects separate stages: for example, for retrieval and adaptation, as described above. However, at the highest level of abstraction, a case-based reasoning system can be viewed as a black box (see Fig. 1.1) that incorporates the reasoning mechanism and the following external facets:\ The input specification or problem case\ The output that defines a suggested solution to the problem\ The memory of past cases, the case base, that are referenced by the reasoning mechanism\ In most CBR systems, the case-based reasoning mechanism, alternatively referred to as the problem solver or reasoner, has an internal structure divided into two major parts: the case retriever and the case reasoner (see Fig. 1.2). The case retriever's task is to find the appropriate cases in the case base, while the case reasoner uses the cases retrieved to find a solution to the problem description given. This reasoning process generally involves both determining the differences between the cases retrieved and the current case, and modifying the solution to reflect these differences appropriately. The reasoning process may or may not involve retrieving additional cases or portions of cases from the case base.\ 1.2.1 CBR System versus Rule-Based System\ The approach of case-based reasoning can be contrasted with that used in other knowledge-based systems, such as rule-based or combined frame-rule-based systems. In rule-based systems, one has a rule base consisting of a set of production rules of the form: IF A, THEN B, where A is a condition and B is an action. If the condition A holds true, the action B is carried out. Condition A can be a composite condition consisting of, say, a conjunction of premises [A.sub.1]; [A.sub.2]; ... ; [A.sub.n]. In addition, a rule-based system has an inference engine that compares the data it holds in working memory with the condition parts of rules to determine which rules to fire. Combined frame-rule-based systems also utilize frames, in addition to rules, to capture stereotypical knowledge. Frames consist of slots that can have default values, actual values, or attached daemons. Frames use a procedure or a rule set to determine the values required when they are triggered. Rule-based and combined frame-rule-based systems require one to acquire the symbolic knowledge that is represented in these rules or frames using manual knowledge engineering or automated knowledge acquisition tools. Sometimes, one utilizes a model of the problem as a basis for reasoning about a situation, where the model can be qualitative or quantitative. These systems are referred to as model-based systems.\ Case-based reasoning systems are an alternative, in many situations, to rule-based systems. In many domains and processes, referring to cases as a means of reasoning can be an advantage due to the nature of this type of problem solving. One of the most time-consuming aspects when developing a rule-based system is the knowledge acquisition task. Acquiring domain-specific information and converting it into some formal representation can be a huge task and in some situations, especially those with less well understood domains, formalization of the knowledge cannot be done at all. Case-based systems usually require significantly less knowledge acquisition, since it involves collecting a set of past experiences without the added necessity of extracting a formal domain model from these cases. In many domains there are insufficient cases to extract a domain model, and this is another benefit of CBR: A system can be created with a small or limited amount of experience and then developed incrementally, adding more cases to the case base as they become available.\ 1.2.2 CBR versus Human Reasoning\ The processes that make up case-based reasoning can be seen as a reflection of a particular type of human reasoning. In many situations, the problems that human beings encounter are solved with a human equivalent of CBR. When a person encounters a new situation or problem, he or she will often refer to a past experience of a similar problem. This previous experience may be one that they have had or one that another person has experienced. If the experience originates from another person, the case will have been added to the (human) reasoner's memory through either an oral or a written account of that experience.\ In general, we have referred to case-based reasoning as being applied to problem solving. Case-based reasoning can also be used in other ways, most notably that of arguing a point of view. For example, many students will come to their teacher with various requests. A request might be for an extension to a deadline or for additional materials. It is a common experience of a teacher, after refusing one of these requests, to have a student argue the point. One of the common techniques that a student will use is to present evidence that in another course, or with another lecturer or teacher, their request has been granted in a similar situation, with similar underlying rules.\ This sort of reasoning, very common in law domains, illustrates another way in which case-based reasoning systems can be implemented. Just as an attorney argues a point in court by references to previous cases and the precedents they set, CBR systems can refer to a case base containing court cases and find cases that have characteristics similar to those of the current one. The similarities may cover the entire case or only certain points that led to a portion of the ruling. Cases can therefore be discovered that may support some portions of the current case while opposing other parts. Case-based systems that perform this sort of argument are generally referred to as interpretive reasoners.\ The idea of CBR is intuitively appealing because it is similar to human problem-solving behavior. People draw on past experience while solving new problems, and this approach is both convenient and effective, and it often relieves the burden of in-depth analysis of the problem domain. This leads to the advantage that CBR can be based on shallow knowledge and does not require significant effort in knowledge engineering when compared with other approaches (e.g., rule-based).\ 1.2.3 CBR Life Cycle\ The problem-solving life cycle in a CBR system consists essentially of the following four parts (see Fig. 1.3):\ 1. Retrieving similar previously experienced cases (e.g., problem-solution- outcome triples) whose problem is judged to be similar\ 2. Reusing the cases by copying or integrating the solutions from the cases retrieved\ 3. Revising or adapting the solution(s) retrieved in an attempt to solve the new problem\ 4. Retaining the new solution once it has been confirmed or validated\ In many practical applications, the reuse and revise stages are sometimes difficult to distinguish, and several researchers use a single adaptation stage that replaces and combines them. However, adaptation in CBR systems is still an open question because it is a complicated process that tries to manipulate case solutions. Usually, this requires the development of a causal model between the problem space (i.e., the problem specification) and the solution space (i.e., the solution features) of the related cases.\ In Figure 1.3, the cases stored in the case library (i.e., previous cases) were supplemented by general knowledge, which is usually domain dependent. This support may range from very weak to very strong, depending on the type of CBR method. For example, in using previous patient records for medical diagnosis, a causal model of pathology and anatomy may constitute the general knowledge used by a CBR system. This knowledge may be in the form of a set of IF-THEN rules or some preconditions in using the cases. Therefore, each stage in the CBR life cycle is associated with some tasks (see Fig. 1.4).\ The process-oriented view of the CBR life cycle provides a global and external view of what is happening, while a task-oriented view is good for describing the actual mechanisms. Tasks are set up depending on the goals of the system, and a particular task is performed by applying one or more methods. In Figure 1.4, tasks are shown by node names, and the possible constituting methods appear in italic type. The links between task nodes (solid lines) represent various task decompositions. For example, the retrieval task is decomposed into the following tasks: identifying relevant descriptors, searching a set of past cases, matching the relevant descriptors to past cases, and selecting the most similar case(s). The methods under each task (dashed lines) indicate possible ways of completing the task. A method specifies an algorithm that identifies and controls execution of the particular subtask. The list of methods corresponding to a task shown in Figure 1.4, is not exhaustive. Selection of a suitable method depends on the problem at hand and requires knowledge of the application domain.\ \ Continues...\ \ \ \ Excerpted from Foundations of Soft Case-Based Reasoning by Sankar K. Pal Simon C. K. Shiu Copyright © 2004 by John Wiley & Sons, Inc.. Excerpted by permission.\ All rights reserved. No part of this excerpt may be reproduced or reprinted without permission in writing from the publisher.\ Excerpts are provided by Dial-A-Book Inc. solely for the personal use of visitors to this web site. \ \

ForewordPrefaceAbout the Authors1Introduction12Case Representation and Indexing343Case Selection and Retrieval754Case Adaptation1365Case-Base Maintenance1616Applications201App. AFuzzy Logic231App. BArtificial Neural Networks242App. CGenetic Algorithms253App. DRough Sets262Index271