Neue Methoden des Case-Based Reasoning

Das diesjährige Seminar im Sommersemester stellt neue Methodiken des 4R-Zyklus in den Mittelpunkt. Jede(r) Seminarteilnehmer(in) bekommt eine wissenschaftliche Publikation als Thema bereitgestellt. Zu dem in der Publikation beschriebenen Thema soll dann eine Seminarausarbeitung erstellt werden. Dazu soll nach weiteren Publikationen aus dem Bereich recherchiert werden.

Ziel der Ausarbeitung ist es, einen Überblick über das von den Autoren behandelte Thema zu geben und die konkreten Fragestellungen hinsichtlich der Retrieve-, Reuse-, Revise- oder Retain-Phase zu behandeln. Die meisten Themen können sowohl als Bachelor- oder Masterthemen im Seminar Intelligente Informationssysteme (IIS) oder Systematische Entwicklung Wissensbasierter Systeme (SE-WBS) angerechnet werden. Je nach Studiengang (BSc oder MSc) erwarten wir Eigenständigkeit bei der Recherche nach weiterführender oder verwandter Literatur, Ausformulierung der Arbeit sowie der Aufbereitung der Themen.

Jedes Thema kann nur einmal vergeben werden – daher wählen Sie sich bitte in Vorbereitung auf die Themenvergabe Mittwoch, dem 13.04.2011, 12-13:00 Uhr im Raum C135 (Spl) 2-3 Themen aus.

Zeitplan:               Themenvergabe:            Mittwoch 13.04.2011, 12-13:00 Uhr im C 135 Spl

Abgabe der ersten Fassung der Ausarbeitung: 15. Juni 2011 (Mi)

Abgabe der Endfassung der Ausarbeitung
und erste Fassung der Präsentationsfolien:       05.August 2011 (Fr)

Vorträge:                            Blockseminar 22.-24. August 2011 (Mo-Mi)

Das Seminar wird als Blockseminar 22.-24. August 2011 (Mo-Mi) in der Jugendherberge Goslar stattfinden. Es ist mit einem Unkostenbeitrag in Höhe von ca. 25-30 € für Übernachtung und Verpflegung zu rechnen.

Bei Rückfragen wenden Sie sich bitte an Prof. Dr. Klaus-Dieter Althoff (althoff(at)

Maximum Likelihood Hebbian Learning Based Retrieval Method for CBR Systems

Juan M. Corchado, Emilio S. Corchado, Jim Aiken, Colin Fyfe, Florentino Fernandez und Manuel Gonzalez

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: CBR systems are normally used to assist experts in the resolution of problems. During the last few years researchers have been working in the development of techniques to automate the reasoning stages identified in this methodology. This paper presents a Maximum Likelihood Hebbian Learning-based method that automates the organisation of cases and the retrieval stage of case-based reasoning systems. The proposed methodology has been derived as an extension of the Principal Component Analysis, and groups similar cases, identifying clusters automatically in a data set in an unsupervised mode. The method has been successfully used to completely automate the reasoning process of an oceanographic forecasting system and to improve its performance.

Case Retrieval Using Nonlinear Feature-Space Transformation

Rong Pan, Qiang Yang und Lei Li

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Good similarity functions are at the heart of effective case-based reasoning. However, the similarity functions that have been designed so far have been mostly linear, weighted-sum in nature. In this paper, we explore how to handle case retrieval when the case base is nonlinear in similarity measurement, in which situation the linear similarity functions will result in the wrong solutions. Our approach is to first transform the case base into a feature space using kernel computation. We perform correlation analysis with maximum correlation criterion (MCC) in the feature space to find the most important features through which we construct a feature-space case base. We then solve the new case in the feature space using the traditional similarity-based retrieval. We show that for nonlinear case bases, our method results in a performance gain by a large margin. We show the theoretical foundation and empirical evaluation to support our observations.

Feature Selection and Generalisation for Retrieval of Textual Cases

Nirmalie Wiratunga, Ivan Koychev und Stewart Massie

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Textual CBR systems solve problems by reusing experiences that are in textual form. Knowledge-rich comparison of textual cases remains an important challenge for these systems. However mapping text data into a structured case representation requires a significant knowledge engineering effort. In this paper we look at automated acquisition of the case indexing vocabulary as a two step process involving feature selection followed by feature generalisation. Boosted decision stumps are employed as a means to select features that are predictive and relatively orthogonal. Association rule induction is employed to capture feature co-occurrence patterns. Generalised features are constructed by applying these rules. Essentially, rules preserve implicit semantic relationships between features and applying them has the desired effect of bringing together cases that would have otherwise been overlooked during case retrieval. Experiments with four textual data sets show significant improvement in retrieval accuracy whenever generalised features are used. The results further suggest that boosted decision stumps with generalised features to be a promising combination.

Case Based Representation and Retrieval with Time Dependent Features

Stefania Montani und Luigi Portinale

Zielgruppe: SE-WBS, BSc oder MSc

Zusammenfassung: The temporal dimension of the knowledge embedded in cases has often been neglected or oversimplified in Case Based Reasoning systems. However, in several real world problems a case should capture the evolution of the observed phenomenon over time. To this end, we propose to represent temporal information at two levels: (1) at the case level, if some features describe parameters varying within a period of time (which corresponds to the case duration), and are therefore collected in the form of time series; (2) at the history level, if the evolution of the system can be reconstructed by retrieving temporally related cases. In this paper, we describe a framework for case representation and retrieval able to take into account the temporal dimension, and meant to be used in any time dependent domain. In particular, to support case retrieval, we provide an analysis of similarity-based time series retrieval techniques; to support history retrieval, we introduce possible ways to summarize the case content, together with the corresponding strategies for identifying similar instances in the knowledge base. A concrete application of our framework is represented by the system RHENE, which is briefly sketched here, and extensively described in [20].

Self-organising Hierarchical Retrieval in a Case-Agent System

Ian Watson und Jens Trotzky

Zielgruppe: SE-WBS, BSc oder MSc

Zusammenfassung: This paper describes the implementation of a distributed case-agent system where a case-base is comprised of a set of agents, where each computational agent is a case, rather than the standard case-base reasoning model where a single computational agent accesses a single case-base. This paper demonstrates a set of features that can be modelled in a case-agent system focusing on distributed self-organising hierarchical retrieval. The performance of the system is evaluated and compared to that of a well recognised hierarchical retrieval method (i.e., footprint-based retrieval). The emergent properties of the case-agent architecture are discussed.

Retrieval over Conceptual Structures

Pablo Beltrán-Ferruz, Belén Díaz-Agudo und Oscar Lagerquist

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: The aim of the research conducted is to investigate how the knowledge in Ontologies can be used to acquire and refine the weights required in Case Retrieval Networks (CRNs). CRNs are designed to perform efficient retrieval processes even in large case bases but they lack from the flexibility and over restrict the circumstances under which the cases are retrieved. We investigate how ontologies can be used to relax these restrictions. We propose a retrieval method where the cases are embedded in a CRN but the weights are dynamically computed using the knowledge from the domain ontology and from the query description.

A Methodology for Analyzing Case Retrieval from a Clustered Case Memory

Albert Fornells, Elisabet Golobardes, Josep Maria Martorell, Josep Maria Garrell, Núria Macià und Ester Bernadó

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Case retrieval from a clustered case memory consists in finding out the clusters most similar to the new input case, and then retrieving the cases from them. Although the computational time is improved, the accuracy rate may be degraded if the clusters are not representative enough due to data geometry. This paper proposes a methodology for allowing the expert to analyze the case retrieval strategies from a clustered case memory according to the required computational time improvement and the maximum accuracy reduction accepted. The mechanisms used to assess the data geometry are the complexity measures. This methodology is successfully tested on a case memory organized by a Self-Organization Map.

Supporting Case-Based Retrieval by Similarity Skylines: Basic Concepts and Extensions

Eyke Hüllermeier, Ilya Vladimirskiy, Belén Prados Suárez und Eva Stauch

Zielgruppe: IIS, MSc

Zusammenfassung: Conventional approaches to similarity search and case-based retrieval, such as nearest neighbor search, require the specification of a global similarity measure which is typically expressed as an aggregation of local measures pertaining to different aspects of a case. Since the proper aggregation of local measures is often quite difficult, we propose a novel concept called similarity skyline. Roughly speaking, the similarity skyline of a case base is defined by the subset of cases that are most similar to a given query in a Pareto sense. Thus, the idea is to proceed from a d-dimensional comparison between cases in terms of d (local) distance measures and to identify those cases that are maximally similar in the sense of the Pareto dominance relation [2]. To refine the retrieval result, we propose a method for computing maximally diverse subsets of a similarity skyline. Moreover, we propose a generalization of similarity skylines which is able to deal with uncertain data described in terms of interval or fuzzy attribute values. The method is applied to similarity search over uncertain archaeological data

A General Introspective Reasoning Approach to Web Search for Case Adaptation

David Leake und Jay Powell

Zielgruppe: SE-WBS, BSc

Zusammenfassung: Acquiring adaptation knowledge for case-based reasoning systems is a challenging problem. Such knowledge is typically elicited from domain experts or extracted from the case-base itself. However, the ability to acquire expert knowledge is limited by expert availability or cost, and the ability to acquire knowledge from the case base is limited by the the set of cases already encountered. The WebAdapt system [20] applies an alternative approach to acquiring case knowledge, using a knowledge planning process to mine it as needed from Web sources. This paper presents two extensions to WebAdapt’s approach, aimed at increasing the method’s generality and ease of application to new domains. The first extension applies introspective reasoning to guide recovery from adaptation failures. The second extension applies reinforcement learning to the problem of selecting knowledge sources to mine, in order to manage the exploration/exploitation tradeoff for system knowledge. The benefits and generality of these extensions are assessed in evaluations applying them in three highly different domains, with encouraging results.

Case Retrieval with Combined Adaptability and Similarity Criteria: Application to Case Retrieval Nets

Nabila Nouaouria und Mounir Boukadoum

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: In Case Based Reasoning (CBR), case retrieval is generally guided by similarity. However, the most similar case may not be the easiest one to adapt, and it may be helpful to also use an adaptability criterion to guide the retrieval process. The goal of this paper is twofold: First, it proposes a method of case retrieval that relies simultaneously on similarity and adaptation costs. Then, it illustrates its use by integrating adaptation cost into the Case Retrieval Net (CRN) memory model, a similarity-based case retrieval system. The described retrieval framework optimizes case reuse early in the inference cycle, without incurring the full cost of an adaptation step. Our results on a case study reveal that the proposed approach yields better recall accuracy than CRN’s similarity only-based retrieval while having similar computational complexity.

Analogical Reasoning for Reuse of Object-Oriented Specifications

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Software reuse means to use again software components built successfully for previous projects. To be successful, techniques for reuse should be incorporated into the development environment. This paper presents an approach where analogical reasoning is used to identify potentially reusable analysis models. A prototype implementation with focus on the repository and analogical reasoning mechanism is presented. All models in the repository are described in terms of their structure. Semantic similarity among models is found by identifying distance in a semantic net built on WordNet, an electronic, lexical database. During retrieval of potential analogies, information about structure and semantics of models is used. During mapping, genetic algorithms are used to optimize the mapping between two models based on their structure and semantics. Experiments are described in which analogies are identified from the models in the repository. The results reported show that this approach is viable.

Adaptation Guided Retrieval Based on Formal Concept Analysis

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

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: In previous papers [5, 4] we have proved the usefulness of Formal Concept Analysis (FCA) as an inductive technique that elicits knowledge embedded in a case library. The dependency knowledge implicitly contained in the case base is captured during the FCA process in the form of dependence rules among the attributes describing the cases. A substitution-based adaptation process is proposed that profits from these dependence rules since substituting an attribute may require to substitute dependant attributes. Dependence rules will guide an interactive query formulation process which favors retrieving cases where successful adaptations can be accomplished. In this paper we exemplify the use of FCA to help query formulation in an application to generate Spanish poetry versions of texts provided by the user.

Optimal Case-Based Refinement of Adaptation Rule Bases for Engineering Design

Hans-Werner Kelbassa

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Rule-based systems have been successfully applied for adaptation. But the rule-based adaptation knowledge for engineering design has no static characteristic. Therefore the adaptation problem emerges also as a validation and refinement problem to be solved by global CBR approaches in an optimal way. The optimal refinement of engineering rule bases for adaptation improves the performance of expert systems for engineering design and provides a basis for the revision of the similarity function for the adaptation-guided retrieval. However, selecting optimal rule refinements is an unsolved problem in CBR; the employed classical SEEK2-like hill-climbing procedures yield local maxima only, not global ones. Hence for the case-based optimization of rule base refinement a new operations research approach to the optimal selection of normal, conflicting, and alternative rule refinement heuristics is presented here. As the current rule validation and rule refinement systems usually rely on CBR, this is a relevant novel contribution for coping with the maintenance problem of large CBR systems for engineering design. The described global mathematical optimization enables a higher quality in the case-based refinement of complex engineering rule bases and thereby improves the basis for the adaptation-guided retrieval.

An Empirical Analysis of Linear Adaptation Techniques for Case-Based Prediction

Colin Kirsopp, Emilia Mendes, Rahul Premraj und Martin Shepperd

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: This paper is an empirical investigation into the effectiveness of linear scaling adaptation for case-based software project effort prediction. We compare two variants of a linear size adjustment technique and (as a baseline) a simple k-NN approach. These techniques are applied to the data sets after feature subset optimisation. The three data sets used in the study range from small (less than 20 cases) through medium (approximately 80 cases) to large (approximately 400 cases). These are typical sizes for this problem domain. Our results show that the linear scaling techniques studied, result in statistically significant improvements to predictions. The size of these improvements is typically about 10% which is certainly of value for a problem domain such as project prediction. The results, however, include a number of extreme outliers which might be problematic. Additional analysis of the results suggests that these adaptation algorithms might potentially be refined to cope better with the outlier problem.

Measures of Solution Accuracy in Case-Based Reasoning Systems

William Cheetham und Joseph Price

Zielgruppe: SE-WBS, BSc

Zusammenfassung: The case-based reasoning (CBR) methodology can be augmented with the ability to determine the confidence in the correctness of individual solutions. A confidence calculation can be added to the REUSE portion of the CBR methodology. The confidence calculation takes confidence indicators, like number of cases retrieved with best solution and average similarity of cases which suggest an alternative solution, and generates a confidence value. The information gain algorithm C4.5 can be used to select the best confidence indicators by evaluating their usefulness in historical cases. A genetic algorithm can be used to optimize and maintain the confidence calculation.

Case-Base Injection Schemes to Case Adaptation Using Genetic Algorithms

Alicia Grech und Julie Main

Zielgruppe: IIS oder SE-WBS, MSc

Zusammenfassung: Case adaptation has always been a difficult process to engineer within the case-based reasoning (CBR) cycle. To combat the difficulties of CBR adaptation, such as its domain dependency, computational cost and the inability to produce novel cases to solve new problems, genetic algorithms (GAs) have been applied to CBR adaptation. As the quality of cases stored in a case library has a significant effect on the solutions produced by a case-based reasoner, it is important to investigate the impact of the quality and quantity of cases injected into a GA initial population for adapting fitter solutions to new problems. This work explores a method applying a GA to CBR adaptation, where a learning mechanism is applied to feed knowledge back from the CBR revision stage into the reuse stage, allowing the GA to learn which mutations result in invalid solutions. In collaboration with this learning mechanism, the number of cases to be injected, and the fitness of cases to be injected from retrieval into reuse is explored. The fitness of adapted cases and their response to our developed learning feedback is also trialled through varying the size and quality of the GA initial population.

Cooperative Reuse for Compositional Cases in Multi-agent Systems

Enric Plaza                  

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: We present a form of case-based reuse conducive to the cooperation of multiple CBR agents in problem solving. First, we present a form of constructive adaptation for configuration tasks with compositional cases. We then introduce CoopCA, a multi-agent constructive adaptation technique for case reuse. The agents suggest possible components to be added to the ongoing configuration problem, allowing an open, distributed process where components used in cases of different agents are pooled together in a principled way. Moreover, the agents can use their case base to inform about a similarity-based likelihood that the suggested component will be adequate for the current problem. We illustrate CoopCA by applying it to the task of agent team formation.

Case Adaptation by Segment Replanning for Case-Based Planning Systems

Flavio Tonidandel und Marcio Rillo

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: An adaptation phase is crucial for a good and reasonable Case-Based Planning (CBP) system. The adaptation phase is responsible for finding a solution in order to solve a new problem. If the phase is not well designed, the CBP system may not solve the desirable range of problems or the solutions will not have appropriate quality. In this paper, a method called CASER – Case Adaptation by Segment Replanning – is presented as an adaptation rule for case-based planning system. The method has two phases: the first one completes a retrieved case as an easy-to-generate solution method. The second phase improves the quality of the solution by using a generic heuristic in a recursive algorithm to determine segments of the plan to be replanned. The CASER method does not use any additional knowledge, and it can find as good solutions as those found by the best generative planners.

Opportunistic Acquisition of Adaptation Knowledge and Cases — The IakA Approach

Amélie Cordier, Béatrice Fuchs, Léonardo Lana de Carvalho, Jean Lieber und Alain Mille

Zielgruppe: IIS, BSc oder MSc

Zusammenfassung: A case-based reasoning system relies on different knowledge containers, including cases and adaptation knowledge. The knowledge acquisition that aims at enriching these containers for the purpose of improving the accuracy of the CBR inference may take place during design, maintenance, and also on-line, during the use of the system. This paper describes IakA, an approach to on-line acquisition of cases and adaptation knowledge based on interactions with an oracle (a kind of “ideal expert”). IakA exploits failures of the CBR inference: when such a failure occurs, the system interacts with the oracle to repair the knowledge base. IakA-NF is a prototype for testing IakA in the domain of numerical functions with an automatic oracle. Two experiments show how IakA opportunistic knowledge acquisition improves the accuracy of the CBR system inferences. The paper also discusses the possible links between IakA and other knowledge acquisition approaches.

Four Heads Are Better than One: Combining Suggestions for Case Adaptation

David Leake und Joseph Kendall-Morwick

Zielgruppe: IIS, BSc oder MSc

Zusammenfassung: How to automate case adaptation is a classic problem for case-based reasoning. Given the difficulty of developing reliable case adaptation methods, it is appealing to consider methods which can exploit the strengths of a set of alternative adaptation methods. This paper presents a framework for combining suggestions from multiple adaptation methods, and illustrates and evaluates the approach in the context of interactive support for user modification of scientific workflows. The paper presents four adaptation methods for this domain, describes a method for assessing their confidence, proposes four strategies for suggestion combination, and evaluates the performance of the approach. The evaluation suggests that, for this domain, results depend more strongly on the adaptation methods chosen than on the specific combination method used, and that they depend especially strongly on a confidence threshold used for limiting irrelevant and incorrect suggestions.

Adaptation versus Retrieval Trade-Off Revisited: An Analysis of Boundary Conditions

Stephen Lee-Urban und Héctor Muñoz-Avila

Zielgruppe: IIS, BSc oder MSc

Zusammenfassung: In this paper we revisit the trade-off between adaptation and retrieval effort traditionally held as a principle in case-based reasoning. This principle states that the time needed for adaptation reduces with the time spent searching for an adequate case to be retrieved. In particular, if very little time is spent in retrieval, the adaptation effort will be high. Correspondingly, if the retrieval effort is high, the adaption effort is low. We analyzed this principle in two boundary conditions: (1) when very bad and (2) when highly capable adaptation procedures are used. We conclude that in the first boundary condition the adaptation-retrieval trade-off does not necessarily exist. We also claim that the second does not hold for a class of planning domains frequently used in the literature. To validate this claim, we performed experiments on two domains of this type.

Towards Case-Based Adaptation of Workflows

Mirjam Minor, Ralph Bergmann, Sebastian Görg und Kirstin Walter

Zielgruppe: IIS oder SE-WBS, BSc oder MSc

Zusammenfassung: Creation and adaptation of workflows is a difficult and costly task that is currently performed by human workflow modeling experts. Our paper describes a new approach for the automatic adaptation of workflows, which makes use of a case base of former workflow adaptations. We propose a general framework for case-based adaptation of workflows and then focus on novel methods to represent and reuse previous adaptation episodes for workflows. An empirical evaluation demonstrates the feasibility of the approach and provides valuable insights for future research.

Using Case Provenance to Propagate Feedback to Cases and Adaptations

David Leake und Scott A. Dial

Zielgruppe: IIS, BSc oder MSc

Zusammenfassung: Case provenance concerns how cases came into being in a case-based reasoning system. Case provenance information has been proposed as a resource to exploit for tasks such as guiding case-based maintenance and estimating case confidence [1]. The paper presents a new bidirectional provenance-based method for propagating case confidence, examines when provenance-based maintenance is likely to be useful, and expands the application of provenance-based methods to a new task: assessing the quality of adaptation rules. The paper demonstrates the application of the resulting quality estimates to rule maintenance and prediction of solution quality.

Adaptive case-based reasoning using retention and forgetting strategies

Maria Salamó and Maite López-Sánchez

Zielgruppe: IIS oder SE-WBS, MSc

Zusammenfassung: Case-based reasoning systems need to maintain their case base in order to avoid performance degradation. Degradation mainly results from memory swamping or exposure to harmful experiences and so, it becomes vital to keep a compact, competent case base. This paper proposes an adaptive case-based reasoning model that develops the case base during the reasoning cycle by adding and removing cases. The rationale behind this approach is that a case base should develop over time in the same way that a human being evolves her overall knowledge: by incorporating new useful experiences and forgetting invaluable ones. Accordingly, our adaptive case-based reasoning model evolves the case base by using a measure of "case goodness" in different retention and forgetting strategies. This paper presents empirical studies of how the combination of this new goodness measure and our adaptive model improves three different performance measures: classification accuracy, efficiency and case base size.

Experience-Based Critiquing: Reusing Critiquing Experiences to Improve Conversational Recommendation

Kevin McCarthy, Yasser Salem und Barry Smyth

Zielgruppe: IIS oder SE-WBS, BSc

Zusammenfassung: Product recommendation systems are now a key part of many e-commerce services and have proven to be a successful way to help users navigate complex product spaces. In this paper, we focus on critiquing-based recommenders, which permit users to tweak the features of recommended products in order to refine their needs and preferences. In this paper, we describe a novel approach to reusing past critiquing histories in order to improve overall recommendation efficiency.