Monday, 14 July 2014

Case-Base Reasoning (CBR)

Case-Base Reasoning (CBR)  
In the last years Case-Based Reasoning research has led to the development of numerous concepts, techniques, and algorithms to implement the CBR paradigm in practice. This section gives a brief overview of the main aspects of CBR as an AI technology. Since a detailed description would go beyond the scope of this thesis, we restrict the summary only on the fundamental aspects relevant for the work described in the subsequent sections. More detailed information about the CBR technology can be found, for example, in publications by Kolodner (1993); Aamodt and Plaza (1994); Lenz et al. (1998); Bergmann et al. (1999a). First, it is shown how situation-specific knowledge can be used to solve problems. In order to illustrate the general functionality of CBR systems, an overview of a commonly accepted process model of CBR is given. In the following, the role of knowledge in this process model is pointed out in more detail. Finally, basic terms and definitions representing the foundation for the subsequent parts of this work are introduced.

2.2.1. Case-Based Problem-Solving
In CBR situation-specific knowledge originally was seen as experience about particular problem-solving episodes observed in the past. Typically, such an episode, called case, is represented by a pair consisting of a problem description and a description of the corresponding solution.


According to the basic CBR model, case knowledge can be used to solve a new, still unsolved problem. For this, the description of the new problem is compared to the problem parts contained in the available cases. The set of all available cases is also called case base. The case with the problem description being most similar to the new problem then is selected as a candidate to solve the current problem. For this, the solution part of the candidate case is tried to be reused to solve the new problem. If the solution cannot be applied directly, it has to be adapted in order to fit the new situation.

2.2.2. The Case-Based Reasoning Cycle
The general procedure when applying CBR, is commonly described by the classical Case-Based Reasoning cycle introduced by Aamodt and Plaza (1994).
The starting point of a new problem solving-process is a given problem for which a solution is required. This problem can be characterized as a new case for which the solution part is still unknown. This new “case” often also called “query” is then processed in four consecutive steps.

Retrieve:
The first step is the retrieval of one or several cases considered to be useful to support solving the current problem. The hope is to retrieve one or several cases that contain solutions that can be easily reused in the current problem-solving context. Because it is usually very unlikely that the case base already contains a problem description that matches the new problem exactly, a method to estimate the utility of available cases is required. According to the basic CBR assumption (cf. Section 1), here the concept of similarity is used. This means, the task of the retrieval phase is to select cases whose problem descriptions are similar to the current problems’ description. The underlying assumption is that these cases contain solutions being very similar to the searched—but still unknown—solution of the current problem.
            To realize this retrieval task, CBR systems employ special similarity measures that allow the computation of the similarity between two problem descriptions. Because the interpretation of this similarity strongly depends on the particular domain, similarity measures are part of the general knowledge of the system.
Depending on the size of the case base, the information amount contained in single cases, and the complexity of the used similarity measure, the retrieval step is often a challenging task with respect to computation time. In order to manage this complexity, a large number of different retrieval strategies have been developed, e.g. see Lenz (1999); Wess (1993); Schaaf (1996); Schumacher and Bergmann (2000).
            
Reuse
After selecting one or several similar cases, the reuse step tries to apply the contained solution information to solve the new problem. Often a direct reuse of a retrieved solution is impossible due to differences between the current and the old problem situation. Then the retrieved solution(s) have to be modified in order to fit the new situation. How this adaptation is performed strongly depends on the particular application scenario. An overview of existing approaches to adaptation is, for example, given by Wilke and Bergmann (1998).
In general, adaptation methods require additional general knowledge about the application domain. Because this leads to additional knowledge acquisition effort, many CBR systems used today do not perform case adaptation automatically, but leave this task to the user. Then, of course, the quality of the retrieval step influences the problem-solving capabilities of the entire CBR system primarily. Even if automatic adaptation is provided, the quality of the retrieval result will strongly influence the efficiency of the system due to its impact on the required adaptation effort.
After adapting the retrieved case automatically or manually to fit the current situation, a solved case is obtained containing a suggested solution for the current problem.

  Revise
Depending on the employed adaptation procedure, the correctness of the suggested solution often cannot be guaranteed immediately. Then it becomes necessary to revise the solved case. How such a revision is performed, strongly depends on the particular application scenario. For example, it might be possible to apply the suggested solution in the real world to see whether it works or not. However, often a direct application of an uncertain solution is impossible due to the corresponding risks (e.g. medical diagnosis systems). Then the revision has to be performed manually by a human domain expert or by alternative methods such as computer simulation.
If the revise step fails, the case has to be repaired or a new attempt to generate a valid solution has to be carried out. This new attempt can be realized in different ways. One possibility is to apply another adaptation alternative (if existing). Other possibilities are adapting another retrieved case or executing a new retrieval in order to obtain hopefully more useful cases.
Usually, the focus of the revise phase lays on the detection of errors or inconsistencies in the suggested solution and the initiation of further problem-solving attempts. Unfortunately, up to now less research has been carried out to enable CBR systems to recognize the reasons for failed problem-solving processes. If the system would be able to detect these reasons, it could react and, for example, adapt its internal knowledge resources in order to avoid similar failures in the future.

Retain
If the solved case has passed the revise step successfully, a tested/repaired case will be available representing a new experience that might be used to solve similar problems in the future. The task of the CBR cycle’s last step is to retain this new case knowledge for future usage. Therefore, the new case may be added to the case base. However, it has been shown that a general storage of all generated cases is not always useful. In order to enable better control of the retain process; various approaches for selecting cases to be retained have been developed (Aha, 1991; Smyth and Keane, 1995b; Leake and Wilson, 2000; Ferrario and Smyth, 2000; Reinartz et al., 2000). These approaches often imply a reorganization of the entire case base when adding a new case, for example, by removing other cases.

Generally, the capability to acquire new case knowledge during a CBR system’s lifetime principally adds these systems to the class of learning systems. However, many CBR systems developed so far do not exploit this concept of the CBR cycle at all. This holds especially for the commercially employed systems. Further, the original idea of the CBR cycle focuses on learning case knowledge. 

No comments:

Post a Comment