Case-Based Reasoning Research and Development

The central idea behind Case-Based Reasoning has always been the notion that reasoning can be supported using memories of past problem solving. One bottleneck in this work has often been the development of case libraries needed to support this reasoning rather than the transformation of the cases themselves. In much of our work, we have taken an approach in which we treat web-recourses as the distributed knowledge engineering that can be integrated into memory- or case-based reasoning systems. We have been working on how we can take the core view of “Reasoning as Remembering” and transform it into “Reasoning as Search”. The primary issues in this work are how to map problem-solving or task needs onto the queries required to find initial candidates, filter those candidates for relevance and then manage the exploitation of the results. I will outline how we have done this in two systems we have built recently, News at Seven and Baleen, systems that track the world of social media, news and the Web to support narrative generation.

The Jeopardy! television quiz show asks natural-language questions and requires natural-language answers. One useful source of information for answering Jeopardy! questions is text from written sources such as encyclopedias or news articles. A text passage may partially or fully indicate that some candidate answer is the correct answer to the question. Recognizing whether it does requires determining the extent to which what the passage is saying about the candidate answer is similar to what the question is saying about the desired answer. This paper describes how structure mapping [1] (an algorithm originally developed for analogical reasoning) is applied to determine similarity between content in questions and passages. That algorithm is one of many used in the Watson question answering system [2]. It contributes a significant amount to Watson’s effectiveness.

Ontologies [9] comprise a definition of concepts describing their commonalities (genus proximum) as well as their differences (differentia specifica). One might think that with the definition of commonalities and differences, the definition of similarities in and for ontologies should follow immediately. Traditionally, however, the contrary is true, because the method background of ontologies, i.e. logics-based representations, and similarity, i.e. geometry-based representations, have been explored in disjoint communities that have mixed only to a limited extent. In this short paper we survey how our own work touches on the intersection between ontologies and similarity. While this cannot be a comprehensive account of the interrelationship between ontologies and similarity, we aim it to be a stepping stone for inspiration and for indicating entry points for future investigations.

We describe a new model for representing semantic workflows as semantically labeled graphs, together with a related model for knowledge intensive similarity measures. The application of this model to scientific and business workflows is discussed. Experimental evaluations show that similarity measures can be modeled that are well aligned with manual similarity assessments. Further, new algorithms for workflow similarity computation based on A* search are described. A new retrieval algorithm is introduced that goes beyond traditional sequential retrieval for graphs, interweaving similarity computation with case selection. Significant reductions on the overall retrieval time are demonstrated without sacrificing the correctness of the computed similarity.

Plan diversity has practical value in multiple planning domains, including travel planning, military planning and game planning. Existing methods for obtaining plan diversity fall under two categories: quantitative and qualitative. Quantitative plan diversity is domain-independent and does not require extensive knowledge-engineering effort, but can fail to reflect plan differences that are truly meaningful to users. Qualitative plan diversity is based on domain-specific characteristics which human experts might use to differentiate between plans, thus being able to produce results of greater practical value. However, the previous approach to qualitative plan diversity assumes the availability of a domain metatheory. We propose a case-based planning method for obtaining qualitative plan diversity through the use of distance metrics which incorporate domain-specific content, without requiring a domain metatheory. To our knowledge, this is the first time qualitative plan diversity is being explored in a case-based planning context.

We present what is, to the best of our knowledge, the first analysis that uses dataset complexity measures to evaluate case base editing algorithms. We select three different complexity measures and use them to evaluate eight case base editing algorithms. While we might expect the complexity of a case base to decrease, or stay the same, and the classification accuracy to increase, or stay the same, after maintenance, we find many counter-examples. In particular, we find that the RENN noise reduction algorithm may be over-simplifying class boundaries.

One way of processing case retrieval in a case-based reasoning (CBR) system is using an ontology in order to generalise the target problem in a progressive way, then adapting the source cases corresponding to the generalised target problem. This paper shows how enriching this ontology improves the retrieval and final results of the CBR system. An existing ontology is enriched by automatically adding new classes that will refine the initial organisation of classes. The new classes come from a data mining process using formal concept analysis. Additional data about ontology classes are collected specially for this data mining process. The formal concepts generated by the process are introduced into the ontology as new classes. The new ontology, which is better structured, enables a more fine-grained generalisation of the target problem than the initial ontology. These principles are tested out within T

aaable

, a CBR system that searches cooking recipes satisfying constraints given by a user, or adapts recipes by substituting certain ingredients for others. The ingredient ontology of T

aaable

has been enriched thanks to ingredient properties extracted from recipe texts.

Building on recent research on preference handling in artificial intelligence and related fields, our general goal is to develop a coherent and universally applicable methodological framework for CBR on the basis of formal concepts and methods for knowledge representation and reasoning with preferences. A preference-based approach to CBR appears to be appealing for several reasons, notably because case-based experiences naturally lend themselves to representations in terms of preference relations, even when not dealing with preference information in a literal sense. Moreover, the flexibility and expressiveness of a preference-based formalism well accommodate the uncertain and approximate nature of case-based problem solving. In this paper, we make a first step toward a preference-based formalization of CBR. Apart from providing a general outline of the framework as a whole, we specifically address the step of case-based inference. The latter consists of inferring preferences for candidate solutions in the context of a new problem, given such preferences in similar situations. Our case-based approach to predicting preference models is concretely realized for a scenario in which solutions are represented in the form of subsets of a reference set. First experimental results are presented to demonstrate the effectiveness of this approach.

Case acquisition is the primary learning method for case-based reasoning (CBR), and the ability of a CBR system’s case-base to cover the problems it encounters is a crucial factor in its performance. Consequently, the ability to assess the current level of case-base coverage and to predict the incremental benefit of adding cases could play an important role in guiding the case acquisition process. This paper demonstrates that such tasks require different strategies from those of existing competence models, whose aim is to guide selection of competent cases from a known pool of cases. This paper presents initial steps on developing methods for predicting how unseen future cases will affect a system’s case-base. It begins by discussing case coverage as defined in prior research, especially in methods based on the representativeness hypothesis. It then compares alternative methods for assessing case-base coverage, including a new Monte-Carlo method for prediction early in case-base growth. It evaluates the performance of these approaches for three tasks: estimating competence, predicting the incremental benefit of acquiring new cases, and predicting the total number of cases required to achieve maximal coverage.

In this paper we focus on how to use CBR for making collective decisions in groups of agents. Moreover, we show that using CBR allows us to dispense with standard but unrealistic assumptions taken in these kind of tasks. Typically, social choice studies voting methods but assumes complete knowledge over all possible alternatives. We present a more general scenario called

open-ended deliberative agreement with rational ignorance (ODARI)

, and show how can CBR be used to deal with rational ignorance. We will apply this approach to the

Banquet Agreement

scenario, where two agents deliberate and jointly agree on a two course meal. Rational ignorance makes sense in this scenario, since it would be unreasonable for the agents to know all the alternatives. Unknown alternatives, as well as a strategy to increase chances of reaching an agreement, are problems addressed using case-based methods.

Different agents in a multiagent system might have different solution quality or preference criteria. Therefore, when solving problems collaboratively using CBR, case reuse must take this into account. In this paper we propose

ABARC

, a model for multiagent case reuse, which divides case reuse in two stages:

individual reuse

, where agents generate full solutions internally, and

multiagent reuse

, where agents engage in a deliberation process in order to reach an agreement on a final solution. Specifically,

ABARC

is based on the idea of

amalgam

, which is a way to generate solutions by combining multiple solutions into one. We illustrate

ABARC

in the domain of interior room design.

This paper presents the 4 Diabetes Support System

TM

(4DSS) project as a case study in case-based reasoning (CBR) research and development. This project aims to help patients with type 1 diabetes on insulin pump therapy achieve and maintain good blood glucose control. Over the course of seven years and three clinical research studies, a series of defining cases altered the research and development path. Each of these cases suggested a new, unanticipated research direction or clinical application. New AI technologies, including naive Bayes classification and support vector regression, were incorporated. New medical research into glycemic variability and blood glucose prediction was undertaken. The CBR research paradigm has provided a strong framework for medical research as well as for artificial intelligence (AI) research. This new work has the potential to positively impact the health and wellbeing of patients with diabetes. This paper shares the 4DSS project experience.

Recent concerns about the effects of feedback delays on solution quality in case-based reasoning (CBR) have prompted research interest in feedback propagation as an approach to addressing the problem. We argue in this paper that the ability of CBR systems to learn from experience in the absence of immediate feedback is limited by eager commitment to the adaptation paths used to solve previous problems. Moreover, it is this departure from lazy learning in CBR that creates the need for maintenance interventions such as feedback propagation. We also show that adaptation path length has no direct effect on solution quality in many adaptation methods and examine the implications for problem solving and learning in CBR. For such “path invariant” adaptation methods, we demonstrate the effectiveness of a “lazier” approach to learning/problem solving in CBR that avoids commitment to previous adaptation paths and hence the need for feedback propagation.

This paper addresses the automated acquisition of adaptation cases for the modification of scientific workflows. Pairs of workflow versions from community repositories are analysed to extract transformation pathways from one workflow version to another. An algorithmic solution is provided and investigated by experiments with promising results.

Case-based planning (CBP) is usually considered a good solution to solve the knowledge acquisition problem that arises when developing AIs for real-time strategy games. Unlike more classical approaches, such as state machines or rule-based systems, CBP allows experts to train AIs directly from games recorded by expert players. Unfortunately, this simple approach has also some drawbacks, for example it is not easy to refine an existing case base to learn specific strategies when a long game session is needed to create a new trace. Furthermore, CBP may be too reactive to small changes in the game state and, at the same time, do not respond fast enough to important changes in the opponent’s strategy. We propose to alleviate these problems by letting experts to

inject

decision making knowledge into the system in the form of

behavior trees

, and we show promising results in some experiments using Starcraft.

This paper explores how background knowledge from freely available web resources can be utilised for Textual Case Based Reasoning. The work reported here extends the existing Explicit Semantic Analysis approach to representation, where textual content is represented using concepts with correspondence to Wikipedia articles. We present approaches to identify Wikipedia pages that are likely to contribute to the effectiveness of text classification tasks. We also study the effect of modelling semantic similarity between concepts (amounting to Wikipedia articles) empirically. We conclude with the observation that integrating background knowledge from resources like Wikipedia into TCBR tasks holds a lot of promise as it can improve system effectiveness even without elaborate manual knowledge engineering. Significant performance gains are obtained using a very small number of features that have very strong correspondence to how humans describe the domain.

In this paper we introduce our application

HappyMovie

, a Facebook application for movie recommendation to groups. This system takes advantage of social data available in this social network to promote fairness for the provided recommendations. Group recommendations are based in the individual satisfaction of each individual. The (in)satisfaction of users modifies the typical aggregation functions used to estimate the value of an item for the group. This paper proposes a memory of past recommendations to compute the satisfaction of users when similar items (movies, in this case) are recommended several times.

Our recent work analyses the accuracy of group recommenders when using information about the personality and the social connections between the members of the group. The goal in this paper is the use of personality and trust as the mean to define alliances to reach agreements inside a group of people. The approach reproduces the behaviour of real users when negotiating a common item to consume using three variables: personality, trust and personal preferences. We run an experiment in the movie recommendation domain where we use a personality test to identify the group leaders and test the number of people they are able to convince about a certain item to consume.

Among the diverse processes at work in human cognition, the ability to establish analogies plays a crucial role and is often evaluated via IQ tests where an incomplete sequence has to be completed with a suitable item. This has motivated the AI community for developing various computational models of analogy-making. A Boolean logic view of analogical proportions (a basic form of analogical statements of the form “

a

is to

b

as

c

is to

d

”) has been recently proposed and extended to another logical proportion, namely paralogical proportion (stating that “what a and b have in common, c and d have it also”). When used in combination, these 2 proportions provide an enhanced power to complete IQ tests. This Boolean modeling essentially relies on the assessment of the differences and similarities between the items involved, and in the case of analogy, satisfies the expected properties of an analogical proportion. An extension to multiple-valued features has also been defined, reinforcing their scope of applications. It is then possible to complete, in a deterministic manner, some incomplete proportions where the last item

d

is missing. In this paper, we show how this can be the basis of a simple inference paradigm that provides a rigorous way to solve representative analogy-based IQ tests by computing the missing items rather than by choosing in a list of options. The result of the analogical/paralogical inference depends on the way the items are represented. The paper discusses how this approach can be used in analogy-making for both determining missing items in proportions and laying bare the relation linking the components of such proportions. The novelty of the approach is stressed w.r.t. other proposals existing in the literature.

Black Swans are surprising, exceptional, provocative cases that instigate major change. Gray Cygnets follow a Black Swan, are highly similar to it, are also exceptional in outcome, and continue to provoke change. We discuss experiments with a family of tests designed to detect Gray Cygnet (GC) cases in a stream of cases following a known Black Swan case. Using the two classic CBR measures of lattice-based and nearest neighbor similarity, the tests use positional information about the Black Swan in the analysis of a new case, such as its being a supreme on-point case (sopc), a Level 1 (L1) case, or in the first ring of nearest neighbors (NN#1), to determine if it is a potential GC. The idea is that a case very similar to a known Black Swan might be a GC. Experiments performed on a corpus of cases from a well-known episode in legal history spanning the era from mid-1800’s to mid-1900’s showed tests using sopc’s were very precise, while those using L1 cases had good recall.

For the main part, when it comes to questions of retrieval, the focus of CBR research has been on the retrieval of cases from a repository of experience knowledge or case base. In this paper we consider a complementary retrieval issue, namely the retrieval of case bases themselves in scenarios where experience may be distributed across multiple case repositories. We motivate this problem with reference to a deployed social web search service called

HeyStaks

, which is based on the availability of multiple repositories of shared search knowledge, known as

staks

, and which is fully integrated into mainstream search engines in order to provide a more collaborative search experience. We describe the case base retrieval problem in the context of HeyStaks, propose a number of case base retrieval strategies, and evaluate them using real-user data from recent deployments.

Similarity assessment is a key operation in many artificial intelligence fields, such as case-based reasoning, instance-based learning, ontology matching, clustering, etc. This paper presents a novel measure for assessing similarity between individuals represented using Description Logic (DL). We will show how the ideas of

refinement operators

and

refinement graph

, originally introduced for inductive logic programming, can be used for assessing similarity in DL and also for abstracting away from the specific DL being used. Specifically, similarity of two individuals is assessed by first computing their

most specific concepts

, then the

least common subsumer

of these two concepts, and finally measuring their distances in the refinement graph.

Expressiveness of natural language is a challenge for text representation since the same idea can be expressed in many different ways. Therefore, terms in a document should not be treated independently of one another since together they help to disambiguate and establish meaning. Term-similarity measures are often used to improve representation by capturing semantic relationships between terms. Another consideration for representation involves the importance of terms. Feature selection techniques address this by using statistical measures to quantify term usefulness for retrieval. In this paper we present a framework that combines term-similarity and weighting for text representation. This allows us to comparatively study the impact of term similarity, term weighting and any synergistic effect that may exist between them. Study of term similarity is based on approaches that exploit term co-occurrences within document and sentence contexts whilst term weighting uses the popular Chi-squared test. Our results on text classification tasks show that the combined effect of similarity and weighting is superior to each technique independently and that this synergistic effect is obtained regardless of co-occurrence context granularity.

In this paper we present a method for a graph-based retrieval and its application in architectural floor plan retrieval. The proposed method is an extension of a well-known method for subgraph matching. This extension significantly reduces the storage amount and indexing time for graphs where the nodes are labeled with a rather small amount of different classes. In order to reduce the number of possible permutations, a weight function for labeled graphs is introduced and a well-founded total order is defined on the weights of the labels. Inversions which violate the order are not allowed. A computational complexity analysis of the new preprocessing is given and its completeness is proven. Furthermore, in a number of practical experiments with randomly generated graphs the improvement of the new approach is shown. In experiments performed on random sample graphs, the number of permutations has been decreased to a fraction of 10

− 18

in average compared to the original approach by Messmer. This makes indexing of larger graphs feasible, allowing for fast detection of subgraphs.

Biologically inspired design is an increasingly popular design paradigm. Biologically inspired design differs from many traditional case-based reasoning tasks because it employs cross-domain analogies. The wide differences in biological source cases and technological target problems present challenges for determining what would make good or useful schemes for case representation, indexing, and adaptation. In this paper, we provide an information-processing analysis of biologically inspired design, a scheme for representing knowledge of designs of biological systems, and a computational technique for automatic indexing and retrieval of biological analogues of engineering problems. Our results highlight some important issues that a case-based reasoning system must overcome to succeed in supporting biologically inspired design.

In this paper we present a

k

-Nearest Neighbour case-based reasoning system for classifying products into an ontology of classes. Such a classifier is of particular use in the business-to-business electronic commerce industry, where maintaining accurate products catalogues is critical for accurate spend-analysis and effective trading. Universal classification schemas, such as the United Nations Standard Products and Services Code hierarchy, have been created to aid this process, but classifying items into such a hierarchical schema is a critical and costly task. While (semi)-automated classifiers have previously been explored, items not initially classified still have to be classified by hand in a costly process. To help overcome this issue, we develop a conversational approach which utilises the known relationship between classes to allow the user to come to a correct classification much more often with minimal effort.

This paper presents a case-based reasoning system that has been applied in a machine diagnosis customer support scenario. Complex machine problems are solved by sharing machine engineers’ experiences among technicians. Within our approach we made use of existing service reports, extracted machine diagnosis information and created a case base out it that provides solutions faster and more efficient than the traditional approach. The problem solving knowledge base is a data set that has been collected over about five years for quality assurance purposes and we explain how existing data can be used to build a case-based reasoning system by creating a vocabulary, developing similarity measures and populating cases using information extraction techniques.

Mediation is an important method in dispute resolution. We implement a case based reasoning approach to mediation integrating analogical and commonsense reasoning components that allow an

artificial mediation agent

to satisfy requirements expected from a human mediator, in particular: utilizing experience with cases in different domains; and structurally transforming the set of issues for a better solution. We utilize a case structure based on ontologies reflecting the perceptions of the parties in dispute. The analogical reasoning component, employing the Structure Mapping Theory from psychology, provides a flexibility to respond innovatively in unusual circumstances, in contrast with conventional approaches confined into specialized problem domains. We aim to build a mediation case base incorporating real world instances ranging from interpersonal or intergroup disputes to international conflicts.

Bioinformatics offers an interesting challenge for data mining algorithms given the high dimensionality of its data and the comparatively small set of samples. Case-based classification algorithms have been successfully applied to classify bioinformatics data and often serve as a reference for other algorithms. Therefore this paper proposes to study, on some of the most benchmarked datasets in bioinformatics, the performance of different reuse strategies in case-based classification in order to make methodological recommendations for applying these algorithms to this domain. In conclusion, k-nearest-neighbor (kNN) classifiers coupled with between-group to within-group sum of squares (BSS/WSS) feature selection can perform as well and even better than the best benchmarked algorithms to date. However the reuse strategy chosen played a major role to optimize the algorithms. In particular, the optimization of both the number k of neighbors and the number of features accounted was key to improving classification accuracy.

In this paper we present a methodology based on combining sequence learning and case-based reasoning. This methodology has been applied in the analysis, mining and recognition of sequential data provided by complex systems with the aim of anticipating failures. Our objective is to extract valuable sequences from log data and integrate them on a case-based reasoning system in order to make predictions based on past experiences. We have used an

Apriori–style

algorithm (CloSpan) to extract patterns from original data. Afterwards, we have extended our own tool (eXiT*CBR) to deal with sequences in a case-based reasoning environment. The results have shown that our methodology anticipated correctly the failures in most of the cases.

This paper describes an approach to Case Based Reasoning (CBR) for image categorisation. The technique is founded on a time series analysis mechanism whereby images are represented as time series (curves) and compared using time series similarity techniques. There are a number of ways in which images can be represented as time series, this paper explores two. The first considers the entire image whereby the image is represented as a sequence of histograms. The second considers a particular feature (region of interest) contained across an image collection, which can then be represented as a time series. The proposed techniques then use dynamic time warping to compare image curves contained in a case base with that representing a new image example. The focus for the work described is two medical applications: (i) retinal image screening for Age-related Macular Degeneration (AMD) and (ii) the classification of Magnetic Resonance Imaging (MRI) brain scans according to the nature of the corpus callosum, a particular tissue feature that appears in such images. The proposed technique is described in detail together with a full evaluation in terms of the two applications.

This contribution describes a case-based decision support system which is intended for being used in the field of Structural Health Monitoring to support the assessment of structures (by using the example of lamp posts). Interpreting measuring data manually is a very complex task, time-consuming and influenced by the subjectivity of civil engineers. Therefore, the engineers shall be supported in assessing measuring data by using a case-based decision support system. A measurement of a structure and a manual assessment by an engineer represent a case in a case base. Similar cases/structures shall be retrieved and made available for assessing new measurements. For supporting the assessment of simple structures (lamp posts), a case-based system shall be provided for interpreting measuring data semi-automatically to make suggestions about lamp posts’ condition. Thereby, time and costs can be reduced more than 90% by the use of computer-aided assessment in comparison with the manual interpretation.

We apply case based reasoning techniques to build an intelligent authoring tool that can assist nontechnical users with authoring their own digital movies. In this paper, we focus on generating dialogue lines between two characters in a movie story. We use Darmok2, a case based planner, extended with a hierarchical plan adaptation module to generate movie characters’ dialogue acts with regard to their emotion changes. Then, we use an information state update approach to generate the actual content of each dialogue utterance. Our preliminary study shows that the extended planner can generate coherent dialogue lines which are consistent with user designed movie stories using a small case base authored by novice users. A preliminary user study shows that users like the overall quality of our system generated movie dialogue lines.

Given a set of data, recorded by observing the decisions of an

expert

player, we present a case-based framework that allows the successful generalisation of those decisions in the game of no limit Texas Hold’em. The transition from a

limit

betting structure to a

no limit

betting structure offers challenging problems that are not faced in the limit domain. In particular, we address the problems of determining a suitable

action abstraction

and the resulting

state translation

that is required to map real-value bet amounts into a discrete set of abstract actions. We also detail the similarity metrics used in order to identify similar scenarios, without which no generalisation of playing decisions would be possible. We show that we were able to successfully generalise no limit betting decisions from recorded data via our agent, SartreNL, which achieved a 2nd place finish at the 2010 Annual Computer Poker Competition.

To help end-users master complex applications, it is often efficient to enable them to “replay” what they have done before. In some situations, it is even more useful to enable them to modify some values of the actions they are replaying so that they can see the consequences of the modification. Unfortunately, it is not always possible to replay series of actions after a modification of a prerequisite. Hence, the replay process has to deal with impact propagation of changes. In this paper, we describe our models to enable replay of user’s interactions and to manage impact propagation of changes during the replay process using impact rules to perform the adaptation. These models are built upon traces, i.e. digital objects that enable us to record user interactions and to reuse them in different ways. We have implemented the replay process in a Web application called SAP-BO Explorer, an application assisting business users in managing large amounts of information. Our tool helps users to better understand the application.