Toward a Probabilistic Formalization of Case-Based Inference

1 Introduction

The approach of case-based reasoning (CBR). r~lies on the hypothesis that "similar problems have similar so­ lutions." This assumption, which we subsequently re­ fer to as the "CBR hypothesis," is the guiding princi­ ple underlying most CBR systems. Until recently, ?~w­ ever, there have been only few attempts at formahzmg this hypothesis [Dubois et al., 1998; Esteva et al., 1997; Plaza et al., 1998] and, thus, at making an important step toward a theoretical foundation of CBR.

In this paper, we develop a formalization in which we proceed from a constraint-based interpretation of the CBR hypothesis, according to which the similarity of problems imposes a constraint on the similarity o~ as­ sociated solutions in form of a lower bound [Dubms et al., 1998]. We then propose a generalization of this ap­ proach, according to which the similarity of p~o?lems allows for deriving conclusions about the (conditiOnal) probability distribution of the similarity of associated solutions. A probabilistic formalization of the CBR hy­ pothesis according to which "similar proble~s d~ pro~­ ably have similar solutions" seems appropnate ~mce. It emphasizes the heuristic character of CBR and IS smt­ able for modelling the "exception to the rule."

·This work has been supported by a TMR research grant funded by the European Commission.

The formal model we are .going to propose is not re­ lated to the complete methodological framework of case­ based reasoning in the sense of the so-called "CBR cy­ cle." Rather, we focus on CBR as case-based inference (CBI), which essentially corresponds to the REUSE pro­ cess within the (informal) R 4 model of the CBR cycle [Aamodt and Plaza, 1994]. More precisely, we emphasize the idea of case-based reasoning as a prediction method [Dubois et al. , 1998; Faltings, 1997], which is close to the idea of instance-based reasoning [Aha et al., 1991]. According to this point of view, the main task of CBI is to exploit past experience in the form of observed cases in order to predict or characterize the solution of a new problem. In this narrow sense, CBR may not even cover the complete process of problem solving, i.e. , the proce~s of ultimately finding the solution, but may only consti­ tute the first part thereof. Typically, the characteriza­ tion of the solution provided via CBI will be utilized by methods applied in subsequent stages of the overall prob­ lem solving procedure. Indeed, these subsequent stages, which roughly correspond to the REVISE part of the R 4 model, are often not directly "case-based" but make use of domain-specific knowledge or user input.

According to the point of view represented above, CBI has important aspects in common with statistical meth­ ods, and, more generally, with approaches to machine learning. An important difference, however, concerns structural assumptions about an underlying data gen­ erating process, which machine learning algorithms are based on, and which are generally represented in form of a hypothesis space 11. . As a simple example con­ sider the case where 11. is given as a class of functions h : X -+ Y . Each of these functions corresponds to a certain hypothesis which is considered for explaining ob­ served data { (x1, yt), .. . , (xn, YnH· As in this example, the hypotheses h typically relate properties (attributes) of the instances (x, y) E X x Y. The CBR hypothe­ sis, however, concerns the (supplementary) concept of similarity, which can be seen as a derived property re­ lated to pairs of instances. Thus, CBR makes structural assumptions about the data generating process not di­ rectly at the system or instance level but at the, say, sim­ ilarity level. Seen from this perspective, the process of Csr should mainly take place in some kind of similarity space instead of instance space (such as, e.g., instance­ based reasoning.) Consequently, a formalization of CBI, whether probabilistic or not, should proceed from this level.

The remaining part of the paper is organized as fol­ lows: Section 2 introduces the basic framework of case­ based inference. CBI is realized in the form of constraint­ based inference in Section 3. Section 4 is devoted to the probabilistic generalization of this approach. The paper is concluded with a summary in Section 5.

2 The Basic Framework

Within our framework, the primitive concept of a case is defined as a tuple consisting of a situation and a result or outcome associated with the situation. 1

Definition 1 (CBI set-up). A CBI set-up is defined as a 6-tuple

where S is a countable set of situations, n is a set of results, and t.p : S -+ n assigns results to situations. The functions as : s X s -+ llho and a'R : n X n -+ llho define similarity measures over the set of situations and the set of results, respectively. M is a finite memory

of cases c = (s, t.p(s)) E S x n.

We do not make particular assumptions concerning the characterization of situations or results, which will generally be marked using an attribute-value represen­ tation. As far as similarity measures are concerned we suppose them to be reflexive, symmetric and normalized in the sense that degrees of similarity are elements of the unit interval [0, 1), where a value of 1 corresponds to perfect similarity. Observe that card(S) ~ No implies the same to be true for the sets

of actually attained similarity de~rees.

Clearly, the assumption that a situation determines the associated outcome does not imply that the latter is known as soon as the situation is characterized. For ex­ ample, let situations correspond to instances Or a-ctassof combinatorial optimization problems. Moreover, define the result associated with a situation as the (unique) op­ timal solution of the respective problem. Deriving this solution from the description of the problem might in­ volve a computationally complex process. In this con­ nection, we refer to case-based inference as a method supporting the overall process of problem solving by pre­ dicting the result associated with a certain situation. To this end, CBI performs according to the CBR principle: it exploits experience in form of precedent cases to which it "applies" background knowledge in form of the heuristic CBR hypothesis.

1 We prefer these slightly more general expressions to the terms "problem" and "solution."

Definition 2 (CBI problem). A CBI problem is a tuple (E, s0 ) consisting of a Csr set-up E and a new situation so E S. The task is to exploit the similarity structure 2 of E in conjunction with observed cases in order to predict resp. characterize the result r 0 = t.p(s0 ) associated with so. 0

3 CBI as Constraint Propagation

The hypothesis of "similar situations having similar re­ sults" is interpreted in this section from a constraint­ based point of view, according to which the similarity of situations constrains the similarity of the associated results (at a minimum level.)

Definition 3 (similarity profile). For a CBI set-up E, the function hr; : Ds -+ [0, 1) is defined by

and called the similarity profile of the set-up E. 0

The similarity profile hr; is the "fingerprint" of the system (S, n, t.p) at the similarity level and (partly) rep­ resents the similarity structure of the set-up E. It can be seen as a condensed representation of knowledge con­ cerning the system structure t.p. Indeed, the domain and the range of hr; are one-dimensional, whereas S and n will generally be of higher dimension. Consequently, a hypothesis related to the similarity structure of a sys­ tem will generally be less constraining than a hypothesis related to t.p directly. On the other hand, a similarity profile has a relatively simple structure which facilitates the formulation, derivation, and adaptation of hypothe­ ses.

Definition 4 (similarity hypothesis). A similarity hypothesis is identified by a function h : [0, 1) -+ [0, 1) (and similarity measures as, a'R.) The intended meaning of the hypothesis h (or, more precisely, the hypothesis (h,as,aR)) is that

holds true for all s, s' E S. A hypothesis h is called stronger than a hypothesis h' if h' ~ h and h ~ h'. We say that a CBI set-up E satisfies the hypothesis h if h(x) ~ hr;(x) for all x E Ds. 0

A similarity hypothesis h is thought of as an approxi­ mati!?n of the similarity profile hr; and can be interpreted as a quantification of the CBR hypothesis for the set-up ~- This hypothesis is often formulated as "the more similar two situations are, the more similar are the cor­ responding results." Returning to the concept of a sim­ ilarity profile such as introduced above, it becomes ob­ vious that this formulation implicitely makes a stronger assumption than the formulation used at the beginning of this section. Namely, it suggests the function hr:, as­ sociated with a set-up ~ to be increasing, or at least non-decreasing. We, therefore, call h a strict hypothesis if it is a non-decreasing function.

2 This expression will be defined formally in Section 4.

Now, consider a Csr problem(~, so), and suppose that ~ satisfies the hypothesis h. If the memory M contains a case (s, r) such that s =so, the outcome ro = r can sim­ ply be retrieved. Otherwise, we can derive the following restriction:

where the a-neighborhood of a result r E R is defined as the set of all outcomes which are at least a-similar to r:

Thus, in connection with the constraint-based view, the task of Csr can be seen as one of deriving and represent­ ing the set Ch in (3), or an approximation thereof. This may become difficult if, e.g., the definition of the simi­ larity an and, hence, the derivation of a neighborhood is complicated. The sets ( 4) may also become large, in which case they cannot be represented by simply enu­ merating their elements.

In the context of Csr it must generally be assumed that the similarity profile hr:, of a Csr set-up ~ is un­ known. Consequently, we cannot guarantee that ~ sat­ isfies a certain hypothesis h. Nevertheless, taking for granted that h is indeed a (more or less) good approxi­ mation of hr;, it seems reasonable to utilize it for deriv­ ing a Set Ch aCCOrding tO (3) as an apprOXimatiOn Of chE (while keeping the hypothetical character of h in mind.) This situation, which reflects the heuristic character of Csr as a problem solving method, is closely related to the aspect of learning. Within our framework, one rea­ sonable way of realizing case-based learning is that of finding a good approximation of a similarity profile hr:,. An obvious approach, for instance, is to start from a hypothesis space 1i and to look for the most favorable (e.g. , strongest) among those hypotheses h E 1i which are consistent with the memory M in the sense that (2) is satisfied for all (s, <p(s)) , (s', <p(s')) EM.

Remark 5. According to (3), the set Ch depends only on the relation of degrees of the (linearly ordered) simi­ larity scales D s and Dn, as specified by the hypothesis h. Hence, the measures as and an can be considered as ordinal concepts. 0

The overall Csr process, as introduced in this section, is illustrated by Figure 1:

· In a first step, the problem (~,so) is characterized at the similarity level by means of its similarity struc­ ture, consisting of the similarity profile hr; resp. a cor­ responding hypothesis h and the similarity structure zs = Sstr(M, s0 ) of the (extended) memory (M, s0 ). The latter can be thought of as the set of values {as(so,s) I (s,r) E M}. In fact, hr:, resp. zs can be seen as the "image" of the system ( S , R , <p) resp. the (extended) memory under the transformation defined by the similarity measures as and an.

• The main step of the Csr process is then to utilize the similarity structure of the problem for constraining the unknown outcome r0 at the similarity level. The corresponding constraints C are implicit in the sense that they refer to the derived (bilateral) property of similarity, not to the result itself.
• By applying the function a:;2 : R x [0, 1]-+ 2n, which is inversely related to an via a-R 1 (r,a) = N 01 (r), to the observed outcomes rk (k = 1, .. . , n), the similarity con­ straints C are transformed into constraints on outcomes, Which are COmbined Via (3) tO a COnStraint chE resp. Ch at the system level.

Remark 6. Two characteristics of Csr, as introduced above, are worth mentioning. Firstly, Csr is indirect in the sense that constraints on outcomes are obtained via constraints on similarity degrees an(r0 , rk). Secondly, CBI is local in the sense that the rules (2) associated with a hypothesis h derive evidence concerning the value r0 from single cases only. These pieces of evidence still have to be combined in order to obtain the constraint implied by the complete memory M. Within the deterministic framework of this section the combination of evidence is simply accomplished by (3) . 0

Of course, the more "convenient" the similarity struc­ ture of a set-up ~ is, the more successful Csr will be. Within our framework, we have quantified this conve­ nience, i.e., the degree to which the CBR hypothesis holds true for the set-up ~' by means of the similar­ ity profile hr:,. This quantification, however, may appear rather restrictive. The existence of some "exceptional" pairs of cases, for instance, might call for small values hE(x) of the similarity profile hr:, in order to guaran­ tee the validity of (3). Then, the predictions (3) which reflect the success of the Csr process might become im­ precise even though the similarity structure of ~ is oth­ erwise strongly developed. This motivates the proba­ bilistic generalization of the constraint-based approach as proposed in the next section.

4 CBI as Probabilistic Reasoning

4.1 Basic probabilistic concepts

We now extend the definition of a Csr set-up such that the set S of situations is endowed with a probability measure tts (defined on 2s.) This measure models the occurence of situations. Thus, we assume that the sit­ uations resp. the associated cases which constitute the memory M are chosen repeatedly (and independently) according to tts. 3 The assumption of this kind of proba­ bilistic setting is a typical one for, e.g., machine learning, and can also be found in recent (more formally oriented) approaches to CBR [Bergmann and Wilke, 1998]. It is less restrictive than it might appear and should, there­ fore, not be overrated. In connection with probabilistic reasoning schemes, for instance, it will generally not be necessary to make explicite assumptions about ItS·

Now consider a Csr problem (:E, so) with (1) the ' . . memory of the set-up :E. According to our assumptiOn, the sequence (s1, ... , sn, s0 ) of involved situations can be seen as the realization of a corresponding random se­ quence characterized by the measure

This measure defines the (discrete) probability space csn+1' (p,s)n+ 1 ) underlying the CBI problem. ~in~e c:sR is particularly concerned with modelling the (s1m1lanty) relation between two cases let us consider a random tu­ ple (T, T') E S x S of situations. The random variable Z = (X, Y), where X is the similarity CJs(T, T') of the situations and Y denotes the similarity of the associ­ ated outcomes, is then defined on the probability space ( S x S, tts 181 tts) as the mapping

Let p,z := Z(tts 181 p,s) be the associated measure over Ds x Dn, and define ttx over Ds and p,y over Dn in the same way. We use notations such as (X= x) for events x- 1 (x) and ltYI(X=x) to denote correspondin? c~n~i­ tional probabilities. Moreover, we make use of mtmtJve notations such as P(Y = yiX = x) for ltYI(X=x)(y).

Definition 1 (probabilistic similarity profile). Consider a Csr set-up :E and let P([O, 1]) denote the class of probability measures over [0, 1]. 4 The function

is called the probabilistic similarity profile of :E.

0

The probabilistic similarity profile Hr. provides a much more precise picture of the similarity structure of a Csr set-up :E than a (deterministic) profile hr. does. For each degree of similarity x E Ds it spec­ ifies the probability distribution /tYI(X=x) of the simi­ larity of results, i.e., of the random variable Y, given that the similarity of two situations is x. Compared to this, the function hr. specifies only the lower bound inf {y E Dn lttYI(X=x)(Y) > 0}.

3 This means that M is actually a sequence of not neces­ sarily different cases.

4 That is, the class of measures on ((0, 1], B) with B the Borel CJ-field over (0, 1].

Definition 8 (stochastic dominance). For a prob­ ability measure p, E P([O, 1]) define the decumulative distribution function G,_. : [0, 1] -+ [0, 1] by G,_.(x) := p,([x, 1]). We write J-L 1 ~ J-L and say that the measure J-L dominates the measure p,' stochastically if G ,_., ~ G ,_.. 0 Definition 9 (probabilistic hypothesis). A prob­ abilistic (similarity) hypothesis is identified by a func­ tion H : [0, 1] -+ P([O, 1]). Let E be a Csr set-up with probabilistic similarity profile Hr.. E satisfies the hy­ pothesis H if Hr.(x) dominates H(x) stochastically for all x E Ds. H is called strict if H(x) ~ H(x') for all 0 < x < x' < 1. A hypothesis H' is called stronger than Hi£ H(x) _:; H'(x) for all x E [0, 1] and H'(xo) ~ H(xo) for at least one x0 E [0, 1]. 0

The -<-relation over P([O, 1]) is a natural generaliza­ tion of the ~-relation over [0, 1]. Again, a Csr set-up :E satisfies a hypothesis H if the latter is "pessimistic" enough in the sense that it never over-estimates the prob­ ability that, for any 0 ~ a ~ 1, the degree of similarity of the outcomes associated with two situations is equal to or larger than a. The strict version of the CBR hypothe­ sis now means that "the more similar two situations are, the larger is the probability that the associated results are at least a-similar."

Let us finally introduce the concept of a generalized hy­ pothesis which turns out to be useful in connection with (approximate) probabilistic inference ( cf. Section 4.2).

Definition 10 (generalized hypothesis). A gener­ alized (similarity) hypothesis is identified by a function G : [0, 1]-+ F([O, 1]). Here, F([O, 1]) denotes the class of normalized uncertainty measures (fuzzy measures) over [0, 1], i.e., the class of measures TJ such that TJ(0) = 0, TJ([O, 1]) = 1, and (A c B c [?, 1])-+ (TJ(A) . ~ TJ(B)). 0

In Section 4.2, a generalized hypothesis G will be used for modelling upper bounds of probability mea­ sures. Thus, it is associated with rules of the form

whereas a probabilistic hypothesis H defines rules

4.2 Probabilistic inference

It has already been mentioned that Csr is not based directly on the information provided at the system level. Rather, the concept of similarity, quantified in form of similarity functions CJs and CJn, is exploited in order to transform this information and to represent it at the similarity level. The following definition specifies this kind of transformation.

Definition 11 (similarity structure). The similarity structure of the Csr problem (:E, so) is defined as the similarity profile (Hr.,CJs,CJn) of :E, together with the similarity structure Sstr(M, so) := { Zij = (Xij, YiJ) 11 ~ i < j ~ n} U {xj 11 ~ j ~ n} of the extended memory (M,s0 ) . Here, Xij := CJs(si,Sj) , Yij := CJn(ri, rj) , and Xj := CTs(so, si)· We generally assume Hr. to be given and simply call Sstr(M, so) the similarity structure of (:E, so). In order to take information about observed results into account, we define the outcome structure as Ostr(M,so) := Sstr(M,so) U {rk 11:::; k:::; n}. 0

The values Zij = ( Xij, Yii) and xi define realizations of corresponding random variables Zij = (Xij, Yii) and Xi. We combine these variables into one vector Zs. Hence, the similarity structure of a CBI problem can be thought of as a random variable Zs defined on the probability space (Sn+l, (J.ts)n+l ). In the same way, a random vari­ able Zo is associated with the outcome structure of a CBI problem.

The structure Zs can be seen as statistical data at the similarity level. The measure (5) determines the prob­ ability of the occurence of such structures completely. Thus, given the "observation" zs = Sstr(M, so), it is principally possible to derive (conditional) probabilities such as, e.g.,

or the likelihood L(r) := P (Zs = zs I Ro = r) of results r E R in connection with the unknown outcome, which is now treated as a random variable Ro. The indirect and local character of CBI (cf. Remark 6 and Figure 1,) however, has important consequences for probabilistic reasoning. Firstly, results such as (7) will not be de­ rived directly. Rather, evidence concernig Ro is ob­ tained indirectly via evidence concerning similarity vec­ tors V = (Yl,··· ,Yn) E (DR)n, where Yk = CTs(Ro,rk)· Secondly, the local inference rules (6) do not allow for the direct specification of probabilities such as P(V = vI Zs = zs), which condition on a complete similar­ ity structure as an event. This leads to the problem of combining probabilistic evidence derived from differ­ ent cases. Due to the stochastic dependency of the random variables which constitute a similarity struc­ ture, this problem is more involved than the combina­ tion of evidence in the deterministic approach of Sec­ tion 3. Thirdly, the transformation of a measure over (DR)n in accordance with CTn 1 does not necessarily yield a (unique) probability measure over R.

As a consequence of the characteristics just mentioned, probabilistic CBI will often be approximative. We can establish, for instance, the following result. 5

Proposition 12. Consider a CBI problem (:E, s0 ) and suppose the generalized hypothesis G to satisfy G(x) ~ VrE'R I"YI(X=x,R=r) for all x E Ds, where J.t V J.t 1 denotes the upper envelope of the measures J.t and J.t 1 · Moreover, let TJx := G(x) for x E Ds. The function

is an upper approximation of the likelihood function

5 The proof of this result can be found in the full version of this paper [Hiillermeier, 1999].

This proposition provides a natural generalization of the constraint-based inference scheme (3). Indeed, were­ cover (3) as a special case of (8) with TJxi[O, 1] = 1[h(z) ,l]· Expression (8) also suggests to represent a generalized hypothesis G as a parametrized class of fuzzy measures such as, e.g., possibility measures and, hence, to realize probabilistic CBI by means of fuzzy set-based approxi­ mate reasoning techniques.

Figure 2 provides an overview of the probabilistic ap­ proach to CBI. Essentially, this approach realizes a pro­ cess of probabilistic reasoning in similarity space. The similarity structure Zs or the outcome structure Zo of a CBI problem plays the role of the statistical data. A hypothesis H defines the stochastic model which explains the occurence of such structures and which underlies the reasoning process. The task of case-based learning, un­ derstood as the estimation of the similarity profile Hr., thus corresponds to statistical inference.

5 Summary

The main concern of this paper was to establish a frame­ work for modelling CBI, rather than to derive formal results related to particular inference schemes. The fol­ lowing points deserve mentioning:

• We have introduced a formal framework in which the task of case-based inference has been defined as one of predicting resp. characterizing the outcome r 0 associated with a new situation s0 . The distinction between reason­ ing at the instance level and reasoning at the similarity level has been emphasized.
• We have adopted a constraint-based view of CBI, ac­ cording to which the CBR hypothesis imposes constraints on the relation between the similarity of situations and the similarity of corresponding outcomes.
• The concept of a similarity profile has been introduced, which establishes a connection between the instance level and the similarity level, and represents the similarity structure of a CBI set-up. A similarity hypothesis is thought of as an approximation of the similarity profile and, hence, defines a quantification of the CBR hypoth­ esis. It allows for realizing a constraint-based inference procedure.
• A probabilistic generalization of the constraint-based

approach has been proposed. The similarity structure is now represented by means of a probabilistic similarity profile. It allows for replacing the constraint-based in­ ference scheme by more general probabilistic reasoning procedures based on, e.g., the derivation of conditional probabilities or likelihood functions. An exemplary re­ sult concerning the approximation of a certain likelihood function has been established.

Finally, we would like to point out some additional aspects and make some remarks concerning related and future work.

· It should be noted that the probabilistic formalization developed here does not rely on very specific assump­ tions but emerges quite naturally as a generalization of the constraint-based approach in connection with the probabilistic modelling of the occurence of situations. It should also be stressed that this formalization does not correspond to a particular inference scheme. Rather, it provides the basic concepts for "translating" a CBI prob­ lem into one of probabilistic reasoning and case-based learning into statistical inference. This way, it makes the powerful methodology of statistics accessible to CaR. The investigation of particular inference schemes such as, e.g., those emerging from Proposition 12, is an important aspect of further research.

· The probabilistic point of view and the idea of (proba­ bilistic) constraint-based inference guarantee for a clear semantics underlying our approach to CBI, in which sim­ ilarity should be seen as an essential but at the same time auxiliary concept. Indeed, the inference procedure prin­ cipally works with all pairs of similarity functions as and an, each of which defines a certain similarity structure. Of course, the more suitably these functions are chosen, the better the inference results will be. The interpreta­ tion as an auxiliary concept contrasts with other formal­ izations of CBI [Dubois et al., 1998; Esteva et al., 1997; Plaza et al., 1998], in which similarity is awarded a con­ siderable semantical meaning.

· Probabilistic models, particularly Bayesian networks, have been used in connection with case-based reasoning by several authors (see, e.g., [Aha and Chang, 1996]). As main differences between most of these approaches and our work let us emphasize two points. Firstly, the concept of similarity is often derived from that of prob­ ability or vice versa. In [Rodriguez et al., 1997], for in­ stance, similarity is interpreted as a certain probability related to a classification task. Instead, probability and similarity are treated as different concepts in our model. Secondly, a probabilistic model is often related to the fea­ tures (attributes) of cases (at the system level) directly, whereas our formalization proceeds from the similarity level. For example, the problem considered in [Rodriguez et al., 1997] is to estimate the (conditional) probability P(Ci I c) for a case c =(!I, ... , fn) to belong to category Ci as a function of the features fk· Seen from this per­ spective, such approaches are rather case-based, whereas our approach is similarity-based: inference results are derived from similarity structures at the similarity level instead of cases at the system level.

· The question of how to define suitable hypotheses for concrete applications is an important topic of future work. Closely related with this question is the realization of case-based learning as the adaptation of hypotheses. Furthermore, it seems interesting to explore the relation between probabilistic inference and (fuzzy set-based) ap­ proximate reasoning mentioned in Section 4.

· In this paper, CBI utilizes the complete memory M. Often, however, one will only take the most similar case(s) into account. The approach should therefore be generalized in this direction.

• The concepts developed in this paper have already been applied successfully to (repititive) combinatorial optimization problems. The thorough investigation of such applications is a further topic of future work.