Case-Based and Multimodal Reasoning: the contribution of Piero Torasso

1 Introduction

In the early 1980s, one of the fathers of AI, Roger Schank introduced the idea of systems able to learn and reason from past experience, by explicitly keeping in their memory the cases they solved, and by exploiting analogical (i.e., by similarity) reasoning to solve new problems. His theory of dynamic memory [28], developed while he was at Yale University, was the basis for the birth of a new discipline later called Case-Based Reasoning (CBR) [1, 26].

Case-Based Reasoning is a problem solving paradigm where new problems (called target or query problems) are solved by retrieving similar problems already solved, possibly by adapting the solutions of such retrieved problems. The main data structure is the case, that is an entity describing a particular problem (in the simplest situation just a collection of 〈feature, value〉 pairs), together with an associated solution. The original idea by Schank and Kolodner was later refined by Aamodt and Plaza [1], resulting in the so-called 4R process, based on four fundamental steps:

Retrieve: a set of solved cases similar to the target are retrieved from a case library;

The CBR methodology quickly found important applications in tasks like diagnosis [11, 13], planning [10], design [9] and legal reasoning [3].

Piero’s interest in CBR was definitely triggered by three main reasons:

the application of the paradigm to diagnostic problem solving;

All the 4R steps were addressed by Piero’s research, with particular attention to the adaptation and retain phases, considered the most challanging ones. Indeed, retrieval and reuse were the phases that received most attention in both the Machine Learning and Information Retrieval communities, even in situations not strictly related to the CBR field (consider for example the so-called “lazy learning” approaches to machine learning [2] and the various implementations of k-NN algorithms and methods [29]).

In the late 80s/early 90s, Piero was hardly working on a formal characterization of diagnostic problems (see the paper by Console et al. in the present issue) and, at the same time, he was one of the most active proponent of the so-called Second Generation Expert Systems architectures [6]. The introduction of a case-based component in a model-based diagnostic system was conceived as a way to address both interests. In Piero’s idea, CBR had to play a role of “lazy learner”, able to deal with potential model incompleteness, as well as to improve computational efficiency. The term multi-modal reasoning becomes a keyword for all the related research activity.

In 1993, the First European Workshop on Case-Based Reasoning took place in Kaiserslautern (Germany) and we presented our first attempt to combine case-based and model-based diagnosis [21]; this was greatly influenced by some previous visits to Kolodner’s group at Georgia Tech and to Peter Szolovitz at MIT. Szolovitz had been the advisor of Phyllis Koton whose thesis’ main result was the Casey system [13], the first multi-modal diagnostic system exploiting both CBR and MBR (Model-Based Reasoning), from which we were definitely inspired. The Kaiserslautern workshop marked the beginning of a new CBR era, with a great switch of interest from US to Europe. A new International Conference on Case-Based Reasoning (ICCBR) was then established in 1995 (joined later with the European conference); at the first ICCBR meeting Piero presented ADAPtER [15] a multi-modal diagnostic system where case-based reasoning and abductive reasoning were integrated, and the adaptation of the solution of old cases was used to focus the reasoning process. The approach stressed the fact that the solution to a diagnostic problem had to follow a formal definition (the one proposed in the well-known spectrum of logical definitions of diagnosis [7]), and thus also the adaptation process of the CBR module had to take this into account. A heuristic function was proposed, able to rank the solutions associated to retrieved cases with respect to the adaptation effort needed to transform such solutions into possible solutions for the current case. Experiments performed on ADAPtER persuaded Piero that “multi-modal” was the right path to follow [17]; the role of CBR in intelligent system construction becomes then a research focus in Piero’s activity, as also evidenced by his interest in disseminating such ideas in different communities [35].

Since ADAPtER was one of the first multi-modal systems to be based on a formal charaterization of the problem solving methodology, particular attention was then devoted to theoretical complexity issues as well. In particular, the mainstream idea that adaptation is always better than solving problems from scratch was refuted by Nebel and Koehler for planning tasks [14]. They showed that plan re-use and plan generation may have the same degree of computational complexity, even when dealing with very similar problems. The idea we pursued with Piero was then to investigate the same kind of issues applied to diagnosis. We proposed a theoretical complexity analysis coupled with some experimental tests, intended to evaluate the adequacy of adaptation strategies which re-use the solutions of past diagnostic problems, in order to build a solution to the problem to be solved. Results from such analysis showed that, even if diagnosis revision and adaptation fall into the same complexity class of diagnosis generation (they are both NP-complete problems) [16], practical advantages can be obtained by exploiting a hybrid architecture combining case-based and model-based diagnostic problem solving in a unifying framework [18].

Performance issues related to such multi-modal architectures triggered also the collaboration of Piero with Marteen Van Someren in Amsterdam. They started to consider in more detail the utility problem associated to the caching of cases in the case library, in order to construct a “cost model” of the system that could be used to predict the effect of changes to the system itself, and in particular in the case library [33, 34].

In the same period, we also decided to consider more in details performance aspects related to retrieval; the current trend was to tackle the retrieval problem in CBR by:

avoiding an exhaustive search of the (structured) case library, while having the guarantee of retrieving the most similar cases [27];

Again by starting from the ADAPtER architecture, we designed an innovative retrieval algorithm called Pivoting-Based Retrieval (PBR), having the property of exploiting the estimated adaptation cost of a solution to guide the retrieval only in the relevant part of the case library [22]. The original idea of PBR was to exploits a heuristic estimate of the adaptability cost of a solution; during retrieval, lower and upper bounds for such an estimate are computed for relevant cases and a pivot case is selected, determining which cases have to be considered and which have not. By iteratively pruning cases based on pivot case selection, the algorithm is able to find the most adaptable cases with respect to the target one. The algorithm has also been applied in a different setting, since the intervals on which the pruning is based can be defined on any measure of interest; in particular, an implementation of PBR based on standard distance measures [4] has been released as a retrieval component in the JColibri framework from the Universidad Complutense de Madrid [8].

The last part of Piero’s reasearch on CBR and multi-modal reasoning was finally devoted to the Retain step, and in particular to the problem of defining suitable approaches to case-base maintanance. In the late 90s and in the first years of 2000, the main focus of the CBR community moved toward the definition of suitable case-base maintenance policies, by recognizing this problem as a major key to success for case-based systems. The utility or “swamping” problem already addressed by Piero in the work on the cost model, was then deeply analyzed in the context of multi-modal problem solving, by identifying three main sources of system performance: response time, quality of the proposed solutions and system competence [25]. The idea of improving system competence by indiscriminately adding new cases in the case library had been already debated and refuted by Smyth and Keane in their IJCAI 95 paper [31], but a principled approach to the problem was still missing, especially in the context of multi-modal CBR. We addressed the problem from the latter perspective, by considering the refinements of different case base maintanance strategies [19, 24]. We finally proposed and compared two different methodologies; the first was a competence-based strategy aimed at replacing a set of stored cases with the current one, if the latter exhibits an estimated competence comparable with the estimated competence of the considered set of stored cases. The second one, called Learning by Failure with Forgetting (LFF), was based on incremental learning of cases interleaved with an off-line processes of case elimination; cases whose usage does not fulfill specific utility conditions are deleted from the case library. The experimental results demonstrated the practical usefulness of both strategies, with respect to the maintenance of suitable performance levels for the target system [20].

The activity of Piero on CBR and multi-modal reasoning had its epilogue in two important contributions. The first is a summary of Piero’s work on multiple representations and multi-modal reasoning in one of the areas where his scientific contribution has been most relevant: medical AI [36]. With his unique capacity of framing a complex and pluriannual activity, he described the motivations for developing medical diagnostic systems exploiting multiple representations and multi-modal reasoning, starting from the early experiences with the system Check, to the issues related to knowledge compilation and to the integration of CBR with MBR, by summarizing the experience gained in developing the other systems Aid (an abductive diagnostic system [5]) and ADAPtER.

The last work is the “final” chapter of the ADAPtER story [23]; in this paper, together with Diego Magro, we reported in a unified framework the whole theoretical and (updated) experimental work related to all the issues we have tackled during the exciting CBR season we have faced, since we had the opportunity of getting acquinted with the rising CBR methodology at the beginning of the 90s. In particular, we discussed the different facets of the integration of CBR and MBR, the theoretical complexity of the different sub-tasks of a multi-modal system, the performance aspects affecting such an integration, and the way in which a flexible problem solver with learning from past experience capacity should perfom its task.

This has been my last work with Piero and definitely one of the most important of my whole scientific career. We can no doubt state that all the issues related to advances in the CBR research have seen a contribution by Piero; also thanks to him, the Italian AI research community had been the opportunity of being suitably represented inside the very dynamic international CBR community.