Julien Cojan
email: julien.cojan@inria.fr

Jean Lieber
email: jean.lieber@loria.fr

Applying belief revision to case-based reasoning

Adaptation is a task of case-based reasoning (CBR) that aims at modifying a case to solve a new problem. Now, belief revision deals also about modifications. This chapter studies how some results about revision can be applied to formalize adaptation and, more widely, CBR. Revision operators based on distances are defined in formalisms frequently used in CBR and applied to define an adaptation operator that takes into account the domain knowledge and the adaptation knowledge. This approach to adaptation is shown to generalize some other approaches to adaptation, such as rule-based adaptation.

Introduction

Case-based reasoning and belief revision are two domains in which the notions of similarity and modification play an important role.

Case-based reasoning (CBR [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]) is a reasoning process using a case base, where a case is a representation of a problem-solving episode, in general, in the form of a problem-solution pair. CBR aims at solving a target problem and generally consists in a retrieval step (selection of one or several case(s) from the case base that is/are similar to the target problem), an adaptation step (modification of the retrieved case(s) to propose a solution to the target problem), and a possible storage of the case formed by the target problem and its solution.

Belief revision is the process of changing a belief base about a static world by incorporating new beliefs while keeping the belief base consistent. When the old beliefs are inconsistent with the new beliefs, the formers have to be modified in order to restore consistency with the latters. Usually, belief revision is based on the minimal change principle [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF]: most of the old beliefs should be kept. One way to measure change (so that it is minimal) is to use a similarity metric (to be maximized) or a distance (to be minimized).

Thus, the question raised is whether the modification performed during CBR could be performed by a belief revision operator. This question has been addressed in several publications and this chapter gives a synthesis of some of them.

The chapter is organized as follows. Some preliminaries about CBR are given in section 2. Section 3 introduces belief revision. In CBR, the modifications are performed during the adaptation step, section 4 is the core of the chapter and describes revision-based adaptation from a theoretical viewpoint and with a few examples. More globally, belief revision can be applied to CBR as a whole as section 5 shows. Several revision operators have been implemented for different formalisms, together with their revision-based adaptation functions. Some of them are gathered in REVISOR (http: //revisor.loria.fr), a system that is briefly described in section 6. Finally section 7 concludes the chapter.

Preliminaries 2.1 Formalism

The approach to CBR presented in this chapter can be applied to a variety of representation languages. It is assumed that there exists a representation language L: a formula is an element of L. The semantics of L is given by a (possibly infinite) set U and by a function Mod : ϕ ∈ L → Mod(ϕ) ∈ 2 U , defining, in a model-theoretical manner, the semantics of L: a is a model of ϕ if a ∈ Mod(ϕ); ϕ 1 entails ϕ 2 (ϕ 1 |= ϕ 2 ) if Mod(ϕ 1 ) ⊆ Mod(ϕ 2 ); ϕ 1 and ϕ 2 are equivalent (ϕ 1 ≡ ϕ 2 ) if Mod(ϕ 1 ) = Mod(ϕ 2 ). A subset A of U is representable in L if there exists a formula ϕ such that Mod(ϕ) = A.

It is assumed that L is stable under conjunction, which means that for every ϕ 1 , ϕ 2 ∈ L there exists a formula denoted by ϕ 1 ∧ ϕ 2 such that Mod(ϕ 1 ∧ ϕ 2 ) = Mod(ϕ 1 ) ∩ Mod(ϕ 2 ).

Some formalisms are stable under negation (or complement), which means that for every ϕ ∈ L, there exists a formula denoted by ¬ϕ such that Mod(¬ϕ) = U \ Mod(ϕ). For such formalisms, ϕ 2 ∨ ϕ 2 is an abbreviation for ¬(¬ϕ 1 ∧ ¬ϕ 2 ), ϕ 1 ⇒ ϕ 2 is an abbreviation for ¬ϕ 1 ∨ϕ 2 and ϕ 1 ⇔ ϕ 2 is an abbreviation for (ϕ 1 ⇒ ϕ 2 )∧(ϕ 2 ⇒ ϕ 1 ).

Propositional logic with n variables is an example of such a formalism: U denotes the set of interpretations on the variables. Every A ⊆ U is representable in this logic.

Case-based reasoning: principles and notations

For CBR, U is called the case universe. A case instance a is, by definition, an element of U: a ∈ U. A case C is a class of case instances: C ∈ 2 U (in this chapter, a case represents a class of experiences, it is what is called an ossified case in [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF] and a generalized case in [START_REF] Maximini | An investigation of generalized cases[END_REF]). For instance, when the formalism is propositional logic with n variables, U is the set of the 2 n interpretations and a case C is represented by a formula ϕ: C = Mod(ϕ).

A source case is denoted by Source: it is a case of CaseBase (the case base). The target case is denoted by Target: it is the input of the CBR system. In many applications, the source cases Source are specific: each of them represents a single case instance a (Source = {a}). By contrast, the target case specifies only its "problem part" and needs to be completed by a "solution part". The aim of the CBR process is to perform this completion:

CBR : (CaseBase, Target) → ComplTarget with ComplTarget ⊆ Target (1)
Usually, this inference is decomposed into two steps:

Retrieval : (CaseBase, Target) → Source ∈ CaseBase Adaptation : (Source, Target) → ComplTarget

In many CBR applications, a case instance a can be decomposed into a problem part x and a solution part y: a = (x, y). Let U pb and U sol be the universes of problem and solution instances: x ∈ U pb , y ∈ U sol , U = U pb × U sol . A source case Source is decomposed in a source problem srce ∈ 2 Upb and its solution Sol(srce) ∈ 2 Usol , thus Source = srce × Sol(srce) that is interpreted as: for all x ∈ srce there exists y ∈ Sol(srce) such that a = (x, y) is a licit case (i.e., y solves x). The solution part of the target problem is unknown, thus Target = tgt × U sol , where tgt is called the target problem. When cases are decomposed in problems and solutions, CBR aims at solving the target problem tgt, thus ComplTarget = tgt × Sol(tgt) where Sol(tgt) ∈ 2 Usol . In general, a target problem is specific: it is a singleton, i.e., tgt = {x t } with x t ∈ U pb . This problem-solution decomposition is not needed to present revision-based adaptation but it is a prerequisite for other approaches to adaptation mentioned in the chapter. When cases are decomposed in problem and solution parts, it is common to consider the adaptation problem as an analogical problem represented by the following diagram:

tgt srce Sol(srce) Sol(tgt)

that can be read as "Sol(tgt) is to Sol(srce) as tgt is to srce" (transformational analogy [START_REF] Carbonell | Learning by analogy: Formulating and generalizing plans from past experience[END_REF]) or "Sol(tgt) is to tgt as Sol(srce) is to srce" (derivational analogy [START_REF] Carbonell | Derivational analogy: A Theory of Reconstructive Problem Solving and Expertise Acquisition[END_REF]). In other words, adaptation aims at solving an analogical problem. The domain knowledge DK is a knowledge base giving a necessary condition for a case instance to be licit. Thus, the domain knowledge can be represented by a subset DK of U and for each a ∈ U, a ∈ DK involves that a is not licit. When the case universe is decomposed in U pb × U sol , a = (x, y) ∈ DK means that y is not a solution of x or that x and/or y are meaningless (i.e., they are objects represented in the language that have no correspondence in the real world, e.g., in the domain of zoology, a cat that is not a mammal). Having no domain knowledge (or not taking it into account) amounts to DK = U.

Each source case is assumed to be consistent with the domain knowledge, i.e.,

DK ∩ Source = ∅ (3)
Similarly, if a target case is inconsistent with the domain knowledge, it has not to be considered for the CBR inference (the system has to reject it before the retrieval). Thus, if Target is an input of the adaptation procedure, it is required that

DK ∩ Target = ∅ (4)
The result of adaptation must also be consistent with DK, therefore:

DK ∩ ComplTarget = ∅ (5)
(It can be noted that ( 4) is a consequence of (1) and ( 5).)

Distances and metric spaces

A distance on a set U is defined in this chapter as a function d :

U × U → [0; +∞] such that d(a, b) = 0 iff a = b
(the properties of symmetry and triangle inequality are not required in this chapter). Let b ∈ U and A, B ∈ 2 U . The usual abbreviations are used:

d(A, b) = inf a∈A d(a, b) d(b, A) = inf a∈A d(b, a) d(A, B) = inf a∈A,b∈B d(a, b)
By convention, the infimum on the empty set is +∞, e.g.,

d(A, ∅) = +∞. A is said to be closed under d if {b ∈ U | d(A, b) = 0} = {b ∈ U | d(b, A) = 0} = A (closeness of A)
A metric space is an ordered pair (U, d) where d is a distance on U. 5If U = IR n (where IR is the set of the real numbers), a L 1 -distance is a distance d parametrized by a base B of the vector space U such that

d(a, b) = n i=1 |v i -u i | (L 1 distance)
where (u 1 , u 2 , . . . , u n ) (resp., (v 1 , v 2 , . . . , v n )) is the representation of a (resp., of b) in B. When B is the canonical base, u i = a i and v i = b i for each i ∈ {1, 2, . . . n}. By extension, if U is a subset of IR n , a distance d on U that is the restriction of a L 1 distance on IR n is also called a L 1 distance on U (for example, if U = Z Z n where Z Z is the set of integers).

If U = IB n where IB = {true, false}, the weighted Hamming distance with weights (w 1 , w 2 , . . . , w n ) (where

w i > 0) is defined, for a = (a 1 , a 2 , . . . , a n ) and b = (b 1 , b 2 , . . . , b n ) by d(a, b) = n i=1 0 if a i = b i w i else
The Hamming distance is the weighted Hamming distance with w i = 1 for each i ∈ {1, 2, . . . , n}. An interpretation in propositional logic with n variables is assimilated to an element of IB n , hence the notion of weighted Hamming distance between such interpretations.

Belief revision in propositional logic

In [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF], postulates of belief revision are proposed in a general logical setting. These postulates are based on the idea of minimal change. They are applied to propositional logic in [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] which presents 6 postulates that a belief operation has to verify in this formalism: given ψ and µ, two belief bases, ψ µ is a revision of ψ by µ. One of these postulates states that is independent to syntax:

if ψ 1 ≡ ψ 2 and µ 1 ≡ µ 2 then ψ 1 µ 1 ≡ ψ 2 µ 2 (6)
where ψ 1 , ψ 2 , µ 1 , and µ 2 are formulas representing beliefs. As a consequence of ( 6), a formula ϕ can be assimilated to Mod(ϕ), the set of its models: in the rest of the chapter, formulas and subsets of U are used indifferently. Then, the other 5 postulates can be rewritten as follows (using subsets of U, the set of interpretations, instead of propositional formulas):

( 1) A B ⊆ B.

(

) If A ∩ B = ∅ then A B = A ∩ B. ( 2
) If B = ∅ then A B = ∅. ( 3
) (A B) ∩ C ⊆ A (B ∩ C). ( 5) If (A B) ∩ C = ∅ then A (B ∩ C) ⊆ (A B) ∩ C. 4
(A, B, and C are subsets of U.) The interpretation of these postulates is made further (in section 4.3), for their application to revision-based adaptation. Intuitively, to revise A by B, the idea is to modify minimally A into A so that A ∩ B = ∅, and then A B = A ∩ B. Now, there are many ways to model minimal modifications. Among them, there is the modification based on a distance d on U (figure 1 illustrates it): given λ ∈ IR with λ ≥ 0, G d λ (A) is the generalization (a kind of modification) of A ⊆ U defined by

G d λ (A) = {b ∈ U | d(A, b) ≤ λ}
Then, the revision operator d is defined by

A d B = G d δ (A) ∩ B where δ = inf{λ | G d λ (A) ∩ B = ∅}
Note that the infima on U are always reached when U is finite, which is the case when U is the set of interpretations over n propositional variables. This kind of revision operators is a direct generalization of the Dalal revision operator [START_REF] Dalal | Investigations into a theory of knowledge base revision: Preliminary report[END_REF], which is based on the Hamming distance between propositional interpretations. The following equivalent definition can be given:

A d B = {b ∈ B | d(A, b) = δ} where δ = d(A, B)
(the δ's in the two definitions are equal).

U A = G d 0 (A) G d 1 (A) G d 2 (A) G d 3 (A) B A d B
Fig. 1: Illustration of a distance-based revision operator in propositional logic. The set of interpretations is mapped to a finite subset of the plan and the distance between interpretations corresponds to a distance in the plan. A is generalized step by step (G d

1 (A), G d 2 (A), etc.) until the generalized step A = G d λ (A) intersects with B. The result is A d B = A ∩ B.

Belief revision in a metric space

The ( 1-5) postulates can be straightforwardly generalized to other formalisms L where U is (a priori) any set and each formula ϕ of L is assimilated to a subset Mod(ϕ) of U. In this generalization, A, B and C are sets assumed to be representable in L.

Given a distance d on U, d can be defined as above but it must be noticed that d may not satisfy the [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF][START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF][START_REF] Maximini | An investigation of generalized cases[END_REF][START_REF] Carbonell | Learning by analogy: Formulating and generalizing plans from past experience[END_REF][START_REF] Carbonell | Derivational analogy: A Theory of Reconstructive Problem Solving and Expertise Acquisition[END_REF] postulates. This issue is considered further, in section 4.4.

The representability issue must also be addressed in this generalization, thus we propose the following postulate: [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] For any ψ, µ ∈ L, there exists ρ ∈ L such that Mod(ρ) = Mod(ψ) Mod(µ).

In propositional logic, for any operator , this postulateis particularly holds, since every subset of the set U of the interpretations of propositional variables is representable in this logic.

Integrity constraint belief merging

Let ψ 1 , ψ 2 , . . . , ψ k , and µ be k + 1 belief bases. Merging ψ 1 , ψ 2 , . . . , ψ k , given the integrity constraint µ consists in building a belief base ϕ such that ϕ |= µ and ϕ keeps "as much as possible" from the ψ i 's. A merging operator

: µ, {ψ i } 1 ≤ i ≤ k → ϕ = µ {ψ i } 1 ≤ i ≤ k
is assumed to satisfy some postulates similar to the postulates for a revision operator (in [START_REF] Konieczny | DA 2 merging operators[END_REF], such postulates are defined in propositional logic but can be easily generalized to metric spaces). Actually, the notion of integrity constraint extends the notion of belief revision in the sense that if is such a merging operator, then defined by ψ µ = µ ({ψ}) satisfies the ( 1-5) postulates.

Revision-based adaptation

This section defines revision-based adaptation (subsection 4.1), presents an example in propositional logic (subsection 4.2), studies its properties (subsection 4.3), describes with details revision-based adaptation in metric spaces (subsection 4.4), mentions briefly an extension to multiple case adaptation (subsection 4.5), relates this approach to adaptation with other approaches to adaptation (subsection 4.6) and gives pointers on other work related to revision-based adaptation (subsection 4.7).

Definition

Let U be the case universe and be a revision operator on U. The -adaptation is defined as follows [START_REF] Lieber | Application of the Revision Theory to Adaptation in Case-Based Reasoning: the Conservative Adaptation[END_REF]:

ComplTarget = (DK ∩ Source) (DK ∩ Target) (7)
(DK ∩ Source) (resp., (DK ∩ Target)) is the source (resp., target) case interpreted within the domain knowledge (i.e., case instances known to be not licit are removed). Thus [START_REF] Dalal | Investigations into a theory of knowledge base revision: Preliminary report[END_REF] can be interpreted as a minimal modification of the source case to satisfy the target case, given the domain knowledge, knowing that the minimality of modification is the one associated with the operator .

Example in propositional logic

Let us consider the following story. Léon is about to invite Thècle and wants to prepare her an appropriate meal. His target problem can be specified by the characteristics of Thècle about food. Let us assume that Thècle is vegetarian (denoted by the propositional variable v) and that she has other characteristics (denoted by o) not detailed in this example:

Target = v ∧ o
From his experience as a host, Léon remembers that he had invited Simone some times ago and he thinks that Simone is very similar to Thècle according to food behavior, except that she is not a vegetarian (¬v ∧ o). He had proposed to Simone a meal with salad (s), beef (b), and a dessert (d), and she was satisfied by the two formers but has not eaten the dessert, thus Léon has retained the source case

Source = (¬v ∧ o) ∧ (s ∧ b ∧ ¬d)
Besides that, Léon has some general knowledge about food: he knows that beef is meat, that meat and tofu are protein foods, and that vegetarians do not eat meat. Moreover, the only protein food that he is willing to cook, apart from meat, is tofu. Thus, his domain knowledge is

DK = b ⇒ m ∧ m ∨ t ⇔ p ∧ v ⇒ ¬m
where b, m, t, and p are the propositional variables for "some beef/meat/tofu/protein food is appreciated by the current guest". According to -adaptation, what meal should be proposed to Thècle? If is the Dalal revision operator, the -adaptation of the meal for Simone to a meal for Thècle is

ComplTarget ≡ DK ∧ Target ∧ (s ∧ t ∧ ¬d)
In [START_REF] Lieber | Application of the Revision Theory to Adaptation in Case-Based Reasoning: the Conservative Adaptation[END_REF], this adaptation is qualified as conservative: the salad and the absence of dessert is reused for the target case and, though the beef is not kept (to ensure a consistent result), the consequence of b that is consistent with DK, i.e., p, is kept, and thus, t is proposed instead of beef (since v ∧ p |= DK t; in other words, some protein food is required, the only vegetarian protein that Léon is willing to cook is tofu, thus there will be tofu in the meal).

Properties

The ( 1-6) postulates entail some properties of revision-based adaptation.

( 1) applied to -adaptation gives ComplTarget ⊆ DK ∩ Target, which entails the property (1) required for the adaptation process (cf. section 2.2) and the fact that ComplTarget ⊆ DK (no instance case a known to be illicit-a ∈ U \ DK-is in the result).

Let us assume that DK ∩ Source ∩ Target = ∅. Then, ( 2) entails that ComplTarget = DK ∩ Source ∩ Target. This means that if the target case is consistent with the source case, given the domain knowledge, then it can be inferred by -adaptation that Source solves Target. This is consistent with the principle of this kind of adaptation: ComplTarget is obtained by keeping from Source as much as possible, and if no modification is needed then no modification is applied.

(

) gives: if DK∩Target = ∅ then ComplTarget = ∅. Since ComplTarget ⊆ DK (cf. ( 1)), DK ∩ ComplTarget = ∅, 3
which is a property required by an adaptation operator (cf. equation ( 5), section 2.2).

According to [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF], ( 4) and ( 5) capture the minimality of modifications. Thus they express the minimality of modification made by a -adaptation. This can be interpreted as follows. The conjunction of ( 4) and ( 5) can be reformulated as:

Either (A B) ∩ C = ∅, Or (A B) ∩ C = A (B ∩ C). (8)
Let F represent some additional features about the target problem: the new target case is Target 2 = Target ∩ F . If ComplTarget is consistent with F , then ( 4) and ( 5) entail that the adaptation of Source to Target 2 gives ComplTarget 2 = ComplTarget∩F . In other words, if F does not involve needs on modifications (corresponding to an inconsistency) then the result of the -adaptation can be reused straightforwardly. [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] involves that ComplTarget is representable in L.

Revision-based adaptation in metric spaces

In this section, d -adaptation is considered on a metric space (U, d). This study is motivated by applications of CBR which are frequently based on attribute-value formalisms, where the attributes range frequently in simple domains (numeric domains, Boolean, etc.). Thus, the first idea was to study revision for such formalisms, but it appeared that the more general framework of metric space was a better level of study (particularities of attribute-value formalisms did not add much to the study). Therefore, this has involved the necessity to study revision in this framework. This section goes from general to specific. First, revision in (U, d) is considered according to the revision postulates. Then, it is applicated to attribute-constraint formalisms (that include attribute-value formalisms), which is further applicated to formalisms of linear constraints, leading to a practical algorithm for revision in this case. Finally, a practical application to the cooking domain is presented.

The ( 1-6) postulates in metric spaces

This section studies the revision postulates for d . Some of these postulates are not satisfied by d and some additional assumptions on the representation language L and on d are proposed that are sufficient conditions for their satisfaction (recall that the subsets A, B, and C of U involved in postulates ( 1-5) are representable in L).

( 1) is always satisfied by d (direct consequence from the definition of d ).

( 2) is not always satisfied by d as the following counterexample shows. Let U = IR and let L be the language of intervals of IR, e.g., Under this assumption, ( 2) is satisfied as proven hereafter. Let A and B be two subsets of U such that A is closed and A ∩ B = ∅. Thus, d(A, B) = 0 and

A d B = {b ∈ B | d(A, b) = 0} = {b ∈ U | d(A, b) = 0} ∩ B = A ∩ B since A is closed Therefore A d B = A ∩ B and ( 2) is satisfied.
( 3) is not always satisfied by d as the following counterexample shows. Let U and d be the same as in the counterexample of ( 2). Let A = [0; 1] and B =]2; 3]. B = ∅ but A d B = ∅. This suggests that A and B should be closed but even if the (L1) assumption was made, ( 3) may be not satisfied. Figure 2 Under this assumption, ( 3) is satisfied as proven hereafter. Let A, B ∈ 2 U such that ( 4) and ( 5) are always satisfied by d as proven hereafter. The conjunction of these postulates is equivalent to [START_REF] Konieczny | DA 2 merging operators[END_REF] A,B). Thus, the following chain of relations can be established: [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] is not always satisfied by d as the following counterexample shows. Let U = IR 2 and let L be the language of horizontal rectangles, i.e., for every ϕ ∈ L, there exists and x is the smallest integer n such that x ≤ n). As illustrated by figure 3,A d B is a subset of U that is not representable in L.

B = ∅. If A = ∅, d(A, B) = d(A, b) = +∞ for every b ∈ B, thus A d B = B = ∅. If A = ∅ and if A and B are representable in L then (L2) entails that d(A, B) = d(a, b) for some (a, b) ∈ A × B. Since d(a, b) ≥ d(A, b) ≥ d(A, B) = d(a, b), d(A, b) = d(a, b). Therefore, b is such that d(A, b) = d(A, B) thus b ∈ A d B and so, A d B = ∅. So ( 3) is satisfied. If U = IR n , if d is a L 1 distance on U,
. Let A, B, C ∈ 2 U . If (A d B) ∩ C = ∅ then (8) is verified. Now, assume that (A d B) ∩ C = ∅ and let b ∈ (A d B) ∩ C. Then b ∈ (B ∩ C) and d(A, b) = d(
d(A, B) ≤ d(A, B ∩ C) ≤ d(A, b) = d(A, B) (cf
A d (B ∩ C) = {b ∈ B ∩ C | d(A, b) = d(A, B ∩ C)} = {b ∈ B ∩ C | d(A, b) = d(A, B)} = {b ∈ B | d(A, b) = d(A, B)} ∩ C = (A d B) ∩ C (
Now, let us consider the following assumption:

(L3) For each A, subset of U representable in L, for each λ ∈ IR with λ ≥ 0, G d λ (A) is representable in L.
It is a sufficient condition for [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF]. Indeed, if

A and B is representable in L then (L3) entails that G d δ (A) is representable in L, with δ = d(A, B). Therefore, G d δ (A) ∩ B = A d B is representable in L,
since this formalism is stable under conjunction. So [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] holds. Note that (L3) is not a necessary condition for [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF].

Table 1 summarizes these results.

Attribute-constraint formalisms

Definitions. In this section, it is assumed that

U = V 1 × V 2 × . . . × V n
where each V i is a "simple value" space, i.e. either IR (the set of real numbers), Z Z (the set of integers), any interval of IR or Z Z, IB = {true, false}, or another set defined in extension. For i ∈ {1, 2, . . . , n}, the attribute a i is the i th projection:

a i : (a 1 , a 2 , . . . , a n ) ∈ U → a i ∈ V i
( 1) is always satisfied. Under assumption (L1), ( 2) is satisfied.

Under assumption (L2), ( 3) is satisfied.

( 4) is always satisfied. ( 5) is always satisfied. Under assumption (L3), ( 6) is satisfied.

Table 1: Conditions for having the revision postulates satisfied by a distance-based revision operator.

A formula ϕ of the representation language is a constraint, i.e., a Boolean expression based on the attributes a i : ϕ = P (a 1 , a 2 , . . . , a n ). The semantics of ϕ is Mod(ϕ) = {a ∈ U | P (a 1 (a), a 2 (a), . . . , a n (a))} These formalisms contain propositional logic with n variables: V i = IB (for each i ∈ {1, 2, . . . , n}), knowing that the Boolean expressions are based on the Boolean operations and, or, and not. For example, if n = 3, and a 1 = o, a 2 = t and a 3 = v:

Mod(¬v ∨ o) = {(a 1 , a 2 , a 3 ) ∈ U | or(not(a 3 ), a 1 )) = true}
These formalisms also contain the attribute-value formalisms often used for representing cases in CBR [START_REF] Kolodner | Case-Based Reasoning[END_REF]

: a specific case C is defined by C = (a 1 = v 1 ) ∧ (a 2 = v 2 ) ∧ . . . ∧ (a n = v n ) and thus C = {(v 1 , v 2 , . . . , v n )}.
When problem-solution decomposition is made, in general, the attributes are split in problem attributes (a 1 , . . . , a p ) and solution attributes (a p+1 , . . . , a n ). Classically, the distance used on U for the retrieval is the weighted sum of distances on each problem attribute.

Application to the numerical case with linear constraints. Now, it is assumed that each V i is either IR or Z Z and each formula is a conjunction of linear constraints on the attributes. A linear constraint is an expression of the form

n i=1 α i • a i ≤ β where α 1 , . . . , α n , β ∈ IR.
Let d be the L 1 distance on U parametrized by a base B. It can be shown that d satisfies all the ( 1-6) postulates (where A, B, and C are defined thanks to conjunctions of linear constraints). d -adaptation amounts to solve the following optimization problem:

a ∈ DK ∩ Source (9) b ∈ DK ∩ Target (10) minimize n i=1 |v i -u i | (11)
where (u 1 , . . . , u n ) and (v 1 , . . . , v n ) are the respective representations of a and b in the base B. ComplTarget is the set of the b that solve this optimization problem.

In this optimization problem, ( 9) and ( 10) are linear constraints, but the function to be minimized in [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF] is not linear. However, this optimization problem can be solved thanks to the solving of the following linear problem (introducing the new variables z 1 , . . . , z n ):

a ∈ DK ∩ Source b ∈ DK ∩ Target v i -u i ≤ z i (1 ≤ i ≤ n) u i -v i ≤ z i (1 ≤ i ≤ n) minimize n i=1 z i
It can be shown that the optimal values of a and b in the two optimization problems are the same. Therefore, in this formalism, d -adaptation amounts to a linear programming problem, which is NP-complete if some V i = Z Z but is polynomial when all V i = IR [START_REF] Karmarkar | A new polynomial-time algorithm for linear programming[END_REF].

More details about this process can be found in [START_REF] Cojan | Belief Merging-based Case Combination[END_REF].

A cooking application. This principle has been applied to a CBR system called Taaable (http://taaable.fr) that has been a contestant of the CCC (Computer Cooking Contest, organized during the ICCBR conferences). The CCC provides a recipe base. A contestant of the CCC is a system that has to solve cooking problems using these recipes (a case of this application is a recipe). These problems are specified by a set of desired ingredients or dish types, and undesired ones (e.g., "I'd like a pear pie but I don't like cinnamon."). Taaable has won the main challenge and the adaptation challenge of this contest in 2010 [START_REF] Blansché | TAAABLE 3: Adaptation of ingredient quantities and of textual preparations[END_REF]. The adaptation of ingredient quantities was made possible thanks to a reduction to linear programming as mentioned before. Details can be found in [START_REF] Blansché | TAAABLE 3: Adaptation of ingredient quantities and of textual preparations[END_REF] but the idea, explained on a simplified example, is as follows. Suppose that the user wants a recipe of a pear pie and that Taaable retrieves an apple pie. The domain knowledge is expressed by linear constraints on these properties, such as: mass fruit = 120 • nb apple + 100 • nb pear mass sweet = mass sugar + 10 • nb apple + 15 • nb pear (these knowledge can be found in a free nutritional database). Each mass • is an attribute on IR and each nb • is an attribute on IN (non negative integers). The source case is a singleton {a} such that nb apple (a) = 4 and mass sugar (a) = 40. The target case corresponds to the constraint nb apple = 0 (the substitution of apples by pears is inferred by a previous step similar to a -adaptation in propositional logic). The d -adaptation leads to a maximal preservation of the attributes mass fruit and mass sugar and since the pears contain more sweet than the apples, the mass of added sugar is lowered (there is a sort of "compensation effect"). More precisely, the d -adaptation (at least for some base B) gives ComplTarget = {b} with nb pear (b) = 5 (the total fruit mass from Source to ComplTarget is modified from 480 to 500) and mass sugar (b) = 5 (the total sweet mass is unchanged).

Multiple case adaptation

Some CBR systems retrieve several cases and then adapt them in order to solve the target case:

Retrieval : (CaseBase, Target) → {Source i } 1 ≤ i ≤ k ⊆ CaseBase Adaptation : {Source i } 1 ≤ i ≤ k , Target → ComplTarget
This adaptation is called multiple case adaptation and is also known as case combination. Multiple case adaptation extends single case adaptation (which is a case combination with k = 1) in the same way as integrity constraint belief merging extends belief revision (cf. section 3.3), hence the idea 6 to use a merging operator on U to define a multiple case adaptation process:

ComplTarget = DK∩Target {DK ∩ Source i } 1 ≤ i ≤ k
which generalizes [START_REF] Dalal | Investigations into a theory of knowledge base revision: Preliminary report[END_REF]. This approach to multiple case adaptation is studied in [START_REF] Cojan | Belief Merging-based Case Combination[END_REF].

Revision-based adaptation and other approaches to adaptation

Other approaches to adaptation have been defined in the CBR literature. This section compares revision-based adaptation to some of them.

Adaptation by generalization and specialization

The principle of this adaptation is to generalize the source case and then to specialize it to the target case. Since the source and target cases must be considered w.r.t. the domain knowledge and this generalization of the source case must be minimal so that it meets the constraints of the target case, this kind of adaptation amounts to generalize minimally A = DK ∩ Source into A such that A ∩ B = ∅ with B = DK ∩ Target. Therefore, it is a -adaptation for which the modification operation A → A is a generalization (A ⊆ A ). Conversely, if is a revision operator and A, B ∈ 2 U , A B = A ∩B such that A has been modified minimally in A . This modification is not necessarily a generalization but if

A = A ∪ A , then A ⊆ A and A B = A ∩ B. Indeed, either A ∩ B = ∅ so A = A and then A = A, or A ∩ B = ∅ so A ∩ B = (A ∪ A ) ∩ B = (A ∩ B) ∪ (A ∩ B) = ∅ ∪ (A ∩ B) = A B.
So, without loss of generality, it can be considered that the modification of A done when revising A by any revision operator on U is a generalization. Hence, -adaptation can be considered as a formalization of the general model of adaptation by generalization and specialization.

When the revision operator is based on a distance d, d -adaptation can be read as the composition of

a generalization DK ∩ Source → G d δ (DK ∩ Source) and a specialization G d δ (DK ∩ Source) → G d δ (DK ∩ Source) ∩ DK ∩ Target.
To illustrate this idea, it can be noticed that the example of section 4.2 (when Léon invites Thècle) of revision-based adaptation in propositional logic, can be redescribed as an adaptation by generalization and specialization. First, the meal is generalized by substituting beef by protein food (generalization motivated by the fact that Thècle is vegetarian). Then, the generalized meal is specialized by substituting protein food by tofu.

For the other approaches to adaptation considered below, the assumptions of problemsolving decomposition (U = U pb × U sol , Source = srce × Sol(srce), Target = tgt × U sol , ComplTarget = tgt × Sol(tgt)) and of specificities of the source case and the target problem (Source = {a} = {(x s , y s )}, tgt = {x t }) are made.

Null adaptation, orthogonal revision operators and conservative adaptation

In [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF], null adaptation is justified by the assertion "People often do little adaptation." This adaptation is defined by Sol(tgt) = Sol(srce). It is often used when the solution space representation is very simple (e.g., a set of predefined categories). It is also used when CBR is assimilated to a simple approximate reasoning method: if Sol(srce) solves srce and srce is similar to tgt then it is likely that Sol(tgt) = Sol(srce) approximately solves tgt. Under the following assumptions, -adaptation coincides with null adaptation: (A1) No domain knowledge is considered (i.e., DK = U); (A2) is orthogonal, 7 i.e. there exists two revision operators, pb on U pb and sol on U sol , such that

(A pb × A sol ) (B pb × B sol ) = (A pb pb B pb ) × (A sol sol B sol ) (12)
for any A pb , B pb ∈ 2 Upb and A sol , B sol ∈ 2 Usol . Indeed, under these assumptions:

ComplTarget = (srce × Sol(srce)) (tgt × U sol ) = (srce pb tgt) × (Sol(srce) sol U sol ) Therefore: Sol(tgt) = Sol(srce) sol U sol = Sol(srce) ∩ U sol (according to postulate ( 2)) = Sol(srce)
The intuition behind this notion of orthogonality of is that the modifications are made independently in the problem space and in the solution space. For example, if d is a distance on U such that there exists a distance d pb on U pb and a distance d sol on U sol with d((x 1 , y 1 ), (

x 2 , y 2 )) = d pb (x 1 , x 2 ) + d sol (y 1 , y 2 ) ( 13
)
for each (x 1 , y 1 ), (x 2 , y 2 ) ∈ U, then d is orthogonal. Note that the reverse is not true. For example, if d((x 1 , y 1 ), (x 2 , y 2 )) = d pb (x 1 , x 2 ) 2 + d sol (y 1 , y 2 ) 2 then d is orthogonal, though d cannot be written as in [START_REF] Blansché | TAAABLE 3: Adaptation of ingredient quantities and of textual preparations[END_REF] in general. Now, let us consider the situation when the assumption (A2) is made but the assumption (A1) is not. Source is a singleton {(x s , x t )} consistent with DK, thus DK ∩ Source = {(x s , x t )}. Target = {x t } × U sol so:

DK ∩ Target = {(x, y) ∈ DK | x = x t } = {x t } × DK sol (x t )
where DK sol (x t ) = {y ∈ U sol | (x t , y) ∈ DK} Therefore: 1) and ( 3)). So, the -adaptation consists in "repairing" the solution Sol(srce) = {y s } according to the constraint DK sol (x t ), the repair being done by sol . Note that, it this process, neither pb nor x s are used.

ComplTarget = {(x s , y s )} ({x t } × DK sol (x t )) = ({x s } pb {x t }) × ({y s } sol DK sol (x t )) (cf. ( 12
)) = {x t } × ({y s } sol DK sol (x t )) ({x s } pb {x t } = {x t } is a consequence of (
In the following, a -adaptation with an orthogonal revision operator is called a conservative adaptation. 8

Rule-based adaptation

Rule-based adaptation is the adaptation based on a set of adaptation rules. Following the formalization of [START_REF] Lieber | Correct and Complete Retrieval for Case-Based Problem-Solving[END_REF], an adaptation rule is an ordered pair (r, A r ) where r is a binary relation on U pb and A r is such that, for x s , x t ∈ U pb and y s ∈ U sol (Source = {(x s , y s )}, Target = {x t } × U sol ):

if x s r x t then A r (x s , y s , x t ) = y t probably solves x t
The rule is not certain (hence the "probably").

The adaptation rules can be composed as explained hereafter. Let AK be the finite set of adaptation rules that are available to the CBR system. Let AK pb = {r | (r, A r ) ∈ AK}. AK pb provides a structure on U pb . A similarity path from x s ∈ U pb to x t ∈ U pb is a path in (U pb , AK pb ): it is a sequence of relations r i ∈ AK pb such that there exist x 0 , x 1 , . . . , x q ∈ U pb with x 0 = x s , x q = x t , and x i-1 r i x i (1 ≤ i ≤ q). Given such a similarity path, y t ∈ U that probably solves x t can be computed by applying successively the rules (r 1 , A r 1 ), . . . , (r q , A r q ): y i = A r i (x i-1 , y i-1 , x i ) for i taking the successive values 1, 2, . . . , q. Finally, y t = y q probably solves x t . This can be graphically represented by the following diagram, composed of q diagrams like the one of (2), section 2.2:

x s = x 0 x 1 x 2 x q-1 x q = x t y s = y 0 y 1 y 2 y q-1 y q = y t r 1 r 2 r q A r 1 A r 2 A r q Figure 4(b)
illustrates such a rule-based adaptation with a similarity path in two steps, using rules of figure 4

(a).

There may be several similarity paths from x s to x t . The choice between them is usually based on a cost function such that if SP 1 and SP 2 are two similarity paths from x s to x t and cost(SP 1 ) < cost(SP 2 ) then SP 1 is preferred to SP 2 , which is interpreted as "SP 1 is more likely to lead to an appropriate solution to x t than SP 2 ." The function cost is usually assumed to be additive, that is cost(SP ) is the sum of cost(r) for r a relation of SP . To each (r, A r ) ∈ AK, cost(r) > 0 is an information associated with this adaptation rule. 9Let d AK be the distance on U defined by

d AK ((x s , y s ), (x t , y t )) = min    cost(SP )
SP : similarity path from x s to x t such that the application of SP on {(x s , y s )} gives y t    with the convention min ∅ = +∞. Let ComplTarget = tgt × Sol(tgt) be the result of dAK -adaptation without domain knowledge (U = DK). If there is no similarity path from x s to x t , then ComplTarget = Target (the adaptation fails: it does not add any information to the target case). Else, b = (x t , y t ) ∈ ComplTarget iff y t is obtained by application of a similarity path of minimal cost. Therefore, revision-based adaptation includes rule-based adaptation. Moreover, DK can be taken into account in dAK -adaptation, thus this enables to specify a rule-based adaptation taking into account the domain knowledge. Conversely, if some adaptation knowledge AK in the form of rules has been acquired (e.g., by means of knowledge discovery and data-mining techniques [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF][START_REF] D'aquin | Case Base Mining for Adaptation Knowledge Acquisition[END_REF]), this can be useful to specify a relevant revision operator. Indeed, there are many possible revision operators and the adaptation knowledge enables to make some choices among them.

Figure 4(c) illustrates how the rule-based adaptation of figure 4(b) can be formalized by a revision-based adaptation using dAK .

A limitation of rule-based reasoning is that it can fail, meaning that there is no similarity path from x s to x t (d(x s , x t ) = +∞), which involves that ComplTarget = Target. This is particularly true when there are few adaptation rules. Indeed, if AK ⊆ AK then d AK (a, b) ≥ d AK (a, b) so if d AK -adaptation fails then dAK -adaptation fails. One way to overcome this limitation is to combine this kind of adaptation with another approach to adaptation and the principle of revision-based adaptation can be used to formalize this combination. This idea is formalized as follows. Let us assume that the other approach to adaptation that has to be combined with rule-based adaptation can be formalized as a revision-based adaptation and let d 0 be a distance on U such that this adaptation coincides with the d0 -adaptation (intuitively, this adaptation is a "novice" adaptation, hence the 0 in d 0 ). The d -adaptation with d defined below combines rulebased adaptation with d0 -adaptation (for a, b ∈ U):

d(a, b) = inf c∈U (W AK • d AK (a, c) + W 0 • d 0 (c, b)) (14)
where W AK and W 0 are two positive constants. When AK = ∅, d = d 0 (intuitively: with no adaptation knowledge, the adaptation process is a novice). If the infimum above is reached on c = (x c , y c ), the d -adaptation consists in a rule-based adaptation of Source = {a} to solve {x c } and then a d0 -adaptation of c to solve the target case. Figure 4(d) presents an example of adaptation that cannot be solved by rule-based adaptation using the two rules of figure 4(a) but can be solved by d -adaptation according to equation [START_REF] Lieber | Correct and Complete Retrieval for Case-Based Problem-Solving[END_REF].

Differential calculus as a -adaptation

First-order differential calculus rely on the equation

dy j = i ∂y j ∂x i dx i
where x → y is a differentiable function from IR p to IR q . dx i and dy j can be interpreted as small differences and substituted respectively by x t i -x s i and y t j -y s j when x s and x t are similar and thus can be seen as a way to adapt Source = {(x s , y s )} in order to solve Target = {x t } × U sol . In this adaptation process, ∂yj ∂xi ij constitutes the adaptation knowledge: it represents how a solution descriptor is modified when a problem descriptor is modified.

In the following, we restrict ourselves to a differentiable function f : IR → IR, though the principle presented below can be generalized to f : IR p → IR q . Thus U pb = U sol = IR.

A first-order approximation approximation of f in x t is

y t = x s + s (x t -x s ) (15)
The best choice for s is s = f (x s ) (where f is the differential of f ): this choice is the best in the sense that f (x s ) is the only s such that

y t -(y s + s (x t -x s )) = x t -→x s o(x t -x s )
(this is a direct consequence of the definition of differentials). The adaptation knowledge of this first-order approximation is s (either defined for each source case or more globally). The adaptation defined in [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF] coincides with the d -adaptation with DK = U and d defined by

d((x s , y s ), (x t , y t )) = |x t -x s | + |y t -y s -s (x t -x s )| (16)
(the value of s when {(x s , y s )} is not a source case does not matter here so it can be chosen arbitrarily).

From this, conclusions similar to the conclusions about rule-based adaptation can be drawn. First, -adaptation makes it possible to incorporate domain knowledge in this first-order approximation. Then, the knowledge of the adaptation knowledge ( s ) can be used to parametrize the revision operator.

Let

( - → ε 1 , - → ε 2 ) be the canonical base of IR 2 : - → ε 1 = (1, 0), - → ε 2 = (0, 1). Let {(x s , y s )}
be a fixed source case. The distance defined by ( 16) is the L 1 distance parametrized by the base

( - → e 1 , - → e 2 ) with - → e 1 = - → ε 1 + s-→ ε 2 and - → e 2 = - → ε 2 ( s is a constant here, since {(x s , y s )} is fixed). The base ( - → e 1 , - → e 2 ) is orthogonal w.r.t. ( - → ε 1 , - → ε 2 ) iff s = 0. Now,
when s = 0, d can be written as in (13) thus d is an orthogonal revision operator (which justifies a posteriori the adjective "orthogonal": cf. note 7). So, if the base B is orthogonal, d -adaptation is a conservative adaptation.

Other approaches to adaptation

There are other adaptation approaches described in the literature. Most of them are domain-specific and defined by their algorithms. However, there is at least one other general approach to adaptation: the case-based adaptation [START_REF] Jarmulak | Using Case-Base Data to Learn Adaptation Knowledge for Design[END_REF][START_REF] Leake | Acquiring Case Adaptation Knowledge: A Hybrid Approach[END_REF] (also known as recursive CBR [START_REF] Stahl | Applying Recursive CBR for the Customization of Structure Products in an Electronic Shop[END_REF]). The idea is that the adaptation of a CBR system can be a CBR system itself where cases are adaptation cases. This approach to adaptation still remains to be formalized in order to be compared to revision-based adaptation.

Other studies related to revision-based adaptation

Some other studies related to revision-based adaptation have been carried out. Two of them are explained below.

Adaptation in the description logic ALC

Description logics (DLs) form a family of formalisms that are equivalent to fragments of first-order logic [START_REF]The Description Logic Handbook[END_REF]. 10 The most used semantics of DLs is based on the theory of models, as this is the case for, e.g., propositional logic. However, given the collection U of all the interpretations of a DL, it is uneasy (if not impossible) to define a distance on U. Therefore, the authors have not considered any more the idea of defining a d revision operator for a DL and have searched in another direction.

In [START_REF] Flouris | On Applying the AGM theory to DLs and OWL[END_REF], the existence of a belief contraction operator satisfying the postulates of contraction is studied for various DLs (belief contraction is an operator on belief bases that has been related to belief revision through the so-called Harper and Levi ties). There are also some research and implementations on the related issue of repairing inconsistent DL knowledge bases [START_REF] Kalyanpur | Debugging unsatisfiable classes in OWL ontologies[END_REF].

In [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF], an approach to adaptation in the DL ALC (the simplest propositionally closed DL) has been proposed that is inspired by the principle of revision-based adaptation (though it has not defined a revision operator dealing with any knowledge bases of this DL). The principle of this adaptation in ALC is based on the semantic tableau method and on inconsistency repairing. The semantic tableau method is used to check the consistency of a DL knowledge base. Roughly said, it consists in applying a set of deductive rules whenever it is possible and then, to detect the clashes (a clash is a contradiction of an easy to detect predefined form). If there is a clash in each reasoning branch, then the knowledge base is inconsistent, otherwise it is consistent (provided that the set of rules have some completeness property). The adaptation in ALC consists in (1) "pretending" that the source case solves the target problem, (2) applying the semantic tableau method which leads to clashes, and (3) applying a clash repairing strategy that minimizes a repair cost.

The following example illustrates this approach to adaptation in ALC, using the first-order logic syntax. This example is in the cooking domain and cases represent recipes. The domain knowledge is expressed by the following formula:

DK = ∀x gratedRawCarrot(x) ⇔ carrot(x) ∧ raw(x) ∧ grated(x) ∧ ∀x root(x) ⇔ carrot(x) ∨ parsnip(x) ∨ celery(x) ∧ ∀x parsnip(x) ⇒ ¬raw(x)
(the first line expresses what grated raw carrots are, the second line means that the only roots that are considered in this example are carrots, parsnips and celeries, the third line means that a parsnip in a recipe must not be raw). The source case is represented by a formula about a constant σ representing a carrot salad, which is a starter with grated raw carrot and vinaigrette as ingredients:

Source = starter(σ) ∧ ∃x ingredient(σ, x) ∧ gratedRawCarrot(x) ∧ ∃x ingredient(σ, x) ∧ vinaigrette(x)
The target case expresses the fact that the user wants the recipe of a starter without carrot in it, by the following formula about the constant θ:

Target = starter(θ) ∧ ¬(∃x ingredient(θ, x) ∧ carrot(x))
The three steps of the adaptation are as follows. [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF] To pretend that the source case solves the target case amounts to identify σ and θ (σ = θ). (2) DK ∧ Source ∧ Target ∧ (σ = θ) is inconsistent; the tableaux method leads to the clash between ∃x, ingredient(σ, x) ∧ carrot(x) [START_REF] Jarmulak | Using Case-Base Data to Learn Adaptation Knowledge for Design[END_REF] and ¬∃x, ingredient(θ, x) ∧ carrot(x)

(3) In order to repair this clash, the piece of knowledge of equation ( 17) is removed but its consequence (given DK)

∃x, ingredient(θ, x) ∧ root(x) ∧ raw(x) ∧ grated(x) (19)
is kept. Thus, from ( 18), ( 19) and the domain knowledge, it can be deduced that

∃x, ingredient(θ, x) ∧ parsnip(x) ∧ raw(x) ∧ grated(x) (20)
or ∃x, ingredient(θ, x) ∧ celery(x) ∧ raw(x) ∧ grated(x)

Now ( 20) leads to another clash, since the parsnip must not be raw. By contrast, the celery can be eaten raw and does not lead to another clash. Therefore, the piece of knowledge ( 20) is disgarded whereas ( 21) is kept and, finally:

ComplTarget ≡ DK ∧ starter(θ) ∧ ∃x ingredient(σ, x) ∧ celery(x) ∧ raw(x) ∧ grated(x) ∧ ∃x ingredient(σ, x) ∧ vinaigrette(x)

Adaptation of qualitative constraint networks

Qualitative algebras (QAs) constitute a family of knowledge representation formalisms. For example, Allen algebra is a well-known QA dedicated to temporal representation [START_REF] Allen | An interval-based representation of temporal knowledge[END_REF] and RCC8 is a well-known QA dedicated to spatial representation [START_REF] Randell | A spatial logic based on regions and connection[END_REF]. A qualitative constraint network (QCN) is a knowledge base of a QA; it is given by a set of constraints between variables. Belief revision has been studied for QAs in [START_REF] Condotta | A Syntactical Approach to Qualitative Constraint Networks Merging[END_REF]: a revision operator associating to a QCN ψ and a QCN µ a QCN ψ µ is defined, following principles of distance-based revision operators. 11Therefore, revision-based adaptation can be applied to a CBR system in which cases are represented by QCNs. This has been studied in [START_REF] Dufour-Lussier | Adapting Spatial and Temporal Cases[END_REF]. In a first application, revision-based adaptation has been applied to adapt the preparation parts of cooking recipes, for the system Taaable. The QA used was INDU [START_REF] Pujari | INDU: An Interval & Duration Network[END_REF], an extension of the Allen algebra. In a second application, revision-based adaptation has been applied to adapt a crop allocation in a farmland. The QA used was RCC8. This work has raised some implementation issues that are addressed in the paper.

The figure 5 illustrates revision-based adaptation in the Allen algebra (the figure represents the different pieces of knowledge in this formalism-using the qualitative constraint network notations for the most part-and the captions describe them in natural language, for reader non familiar with the Allen algebra). The story underlying this example is an attribution of schedule to teachers. The source case corresponds to the previous year. The target case corresponds to the fact that, for some reason, the French teacher and the Math teacher want to avoid each other. The distance used in this example is based on the distance between the Allen basic relations which are the distances in the relation neighbourhood graph of this formalism (see [START_REF] Ligozat | On generalized interval calculi[END_REF]).

Revision-based CBR

Let SOURCE be the union of all the cases from the case base:

SOURCE = i Source i where CaseBase = {Source i } i
The following question can be raised: according to what conditions can the CBR process with SOURCE as only source case be equivalent to the CBR process with CaseBase? This question is addressed below with a d -adaptation.

Let A 1 , A 2 , . . . , A n , and B be n + 1 subsets of U. Let δ i = d(A i , B) and ∆ = min i δ i . The following equation holds:

i A i d B = i,δi=∆ (A i d B) Indeed d( i A i , b) = min i d(A i , b
) for any b ∈ B, and so

( i A i ) B = {b ∈ U | min i d(A i , b) = ∆} = i,δi=∆ (A i B).
From this equation applied to A i = DK ∩ Source i and B = DK ∩ Target, it comes that the d -adaptation of SOURCE to solve Target gives COMPL_TARGET such that

COMPL_TARGET = i,δi=∆ ComplTarget i
where ComplTarget i is the result of the d -adaptation of Source i to solve Target.

First, let us consider that there is only one i such that δ i = ∆. Then COMPL_TARGET = ComplTarget i . Therefore if the retrieval process aims at selecting the source case Source i ∈ CaseBase that minimizes d(DK ∩ Source i , DK ∩ Target) then CBR({SOURCE}, Target) = CBR(CaseBase, Target)

Now, let us consider that there are ex aequo source cases for such a retrieval process: there are several source cases Source such that d(DK ∩ Source, DK ∩ Target) = ∆. Then the equation ( 22

∨ m ∨ bi ∨ mi b ∨ m ∨ bi ∨ mi b ∨ m ∨ bi ∨ mi (
a) DK. For each of the three courses and each of the three slots, either the course coincides with the slot or it has an intersection of length 0 with it, moreover, the course takes place during the morning. The slot 10:00-11:00 (resp., 11:00-12:00) immediatly follows the slot 9:00-10:00 (resp., 10:00-11:00). There is no intersection of length non null between two different courses. 9:00-10:00 10:00-11:00 11:00-12:00 French Math History eq eq eq (b) Source. The previous year, the slot 9:00-10:00 (resp., 10:00-11:00, 11:00-12:00) was attributed to French (resp., Math, resp., History). -Adaptation first performs a d -adaptation of each Source ∈ S and then takes the union of the results.

Therefore, if the distance d used for d -adaptation is also used for the retrieval process as it is described above, the whole CBR inference can be specified by d and DK: DK is the "static" knowledge (stating that some case instances are not appropriate) and d is the "dynamic" knowledge about the modification from a case instance to another one. This can be linked to the general principle of "adaptation-guided retrieval" [START_REF] Smyth | Using adaptation knowledge to retrieve and adapt design cases[END_REF] stating that the adaptation knowledge should be used during retrieval: a source case must be preferred to another one if the former requires less "adaptation effort" (this adaptation effort being measured thanks to d for d -based CBR).

REVISOR: a set of revision-based adaptation engines

REVISOR gathers several adaptation engines under GPL license and is available at http://revisor.loria.fr. In the current version, several engines have been developped.

REVISOR/PL implements d and the corresponding revision-based adaptation, where the formalism is propositional logic with a finite number of variables and where d is the weighted Hamming distance between interpretations. REVISOR/PLAK implements d and the corresponding revision-based adaptation, where the formalism is propositional logic with a finite number of variables and where d is defined by equation ( 14) with d 0 a weighted Hamming distance and AK a set of adaptation rules defined by the user, together with their costs. REVISOR/CLC implements d and the corresponding revision-based adaptation, where formulas are conjunctions of linear constraints with variables on Z Z and on IR and where d is a L 1 distance. REVISOR/QA implements d and the corresponding revision-based adaptation, in one of the following qualitative algebras: the Allen algebra, INDU and RCC8.

REVISOR/CLC and REVISOR/QA have been used for the system Taaable.

Conclusion

Case-based reasoning systems use similarity (usually in the form of a similarity measure or a distance). This is obvious for the retrieval of a case similar to the target case but this chapter shows how it can be used for adaptation: an important class of revision operators is based on distances. Indeed, d -based adaptation can be reformulated as the process of selecting the case instances that are the closest ones to the source case, in the metric space (U, d), with constraints given by DK. Since adaptation aims at solving a certain type of analogical problem (in which two of the four elements in the analogy are problems, the other ones-including the unknown-are solutions), this approach concretely relates analogical reasoning with belief revision. This approach to adaptation has a good level of generality since it captures some other approaches to adaptation. This is useful for at least two reasons. First, it proposes a general framework for specifying adaptation, covering many approaches. Second, it enables to modify an existing adaptation process by taking into account the domain knowledge in this approach. For instance, rule-based adaptation does not consider the domain knowledge (unless it is considered in the adaptation rules): it works on the case universe U. Revision-based adaptation enables to re-specify it and then to have it working in the case universe U ∩ DK (i.e., the case universe without the case instances known to be illicit).

Finally, from our own experience, this way to consider adaptation, has appeared as a useful guide to specify and to realize adaptation procedures.

However, even if revision-based adaptation would capture all the approaches to adaptation (and we do not claim that it is the case), it would not close the investigations about adaptation in CBR. Indeed, a revision operator is parametrized by a topology (usually a distance) and the issue of the choice of an appropriate topology, is far from being completely addressed. In fact, the choice of this topology is an adaptation knowledge acquisition issue and an important aspect of the research on revision-based adaptation is to have related this topology of the case universe with the adaptation knowledge.

  [0; 1[= {a ∈ U | 0 ≤ a < 1}. Let d : (a, b) → |b -a|. It can be shown that [0; 1[ d [0; 1[= [0; 1] ⊆ [0; 1[. Now, let us consider the following additional assumption about the formalism L: (L1) Every subset A of U that can be represented in L is closed under d.

  presents a counterexample of ( 3) with A and B, two closed sets. Now, let us consider the following assumption: (L2) For every A and B non empty subsets of U representable in L, the distance between A and B is always reached: there exist a ∈ A and b ∈ B such that d(A, B) = d(a, b).

A

  Fig.2: A counterexample of[START_REF] Maximini | An investigation of generalized cases[END_REF]. U = IR 2 , d is a L 1 distance on U, L is chosen so that A, B and ∅ are representable in this formalism, which is consistent with assumption (L1), since A and B are closed under d. Finally, B = ∅. Despite these facts, A B = ∅ (since d(A, B) = 0 and no element of B is at distance 0 from an element of A).

  . the infimum appearing in the definition of d(A, •) and the fact that b ∈ B ∩ C). Therefore, these numbers are all equal and d(A, B) = d(A, B ∩ C). Hence

  Fig. 3: A counterexample of ( 6). A = [0; 0] × [0; 0] = {(0, 0)} and B = [1; 4] × [1; 3] are two subsets of U representable in the language L of horizontal rectangles, though A d B = C (where d is the Euclidian distance rounded up to integers) is not representable in L. Indeed, C is the intersection of G d 2 (A), the closed disk of radius 2 and centered on (0, 0), with B.

R1=

  Bacon can be sustituted by smoked tofu R2 = In a salad dish, vinegar can be sustituted by lemon juice and salt (a) Examples of rules. An example of rule-based adaptation. DK = lettuce ⇒ green salad ∧ escarole ⇒ green salad ∧ vegetarian ⇒ ¬meat ∧ bacon ⇒ meat Source = salad dish ∧ lettuce ∧ vinegar ∧ olive oil ∧ bacon Target = salad dish ∧ ¬vinegar ∧ vegetarian AK = {R1, R2} with R1 = bacon smoked tofu and R2 = salad dish ∧ vinegar salad dish ∧ lemon juice ∧ salt ComplTarget ≡ DK ∧ Target ∧ lettuce ∧ lemon juice ∧ salt ∧ olive oil ∧ smoked tofu (c) Formalization of this example as a dAK -adaptation. Target 2 = Target ∧ ¬lettuce (d) A new target case, slightly different from Target but which cannot be solved by rule-based adaptation of Source given DK and AK (i.e., by dAK -adaptation). ComplTarget 2 = (DK ∧ Source) d (DK ∧ Target 2 ) ≡ DK ∧ Target 2 ∧ green salad ∧ lemon juice ∧ salt ∧ olive oil ∧ smoked tofu (e) Solving Target 2 by d -adaptation, where d is defined by equation (14), with d0 the Hamming distance. This adaptation consists in applying R1, R2 and in removing lettuce. ComplTarget 2 |= green salad ∧ ¬lettuce: the lettuce can be replaced by any other kind of green salad, e.g., escarole.

Fig. 4 :

 4 Fig. 4: Rule-based adaptation and revision-based adaptation on an example.

  ) still holds if the two following modifications are made:-Retrieval returns the set S of source cases Source minimizing d(DK∩Source, DK∩ Target);for each x ∈ {French, History, Math} and each y ∈ {9:00-10:00, 10:00-11:00, 11:00-12:00}x (eq ∨ m ∨ mi ∨ b ∨ bi) y x (s ∨ d ∨ f )

  Target. The French course and the Math course must not meet any more. (Technically, ¬m ∧ ¬mi is an abbreviation for eq∨ b ∨ bi ∨ d ∨ di ∨ f ∨ f i ∨ o ∨ oi ∨ s ∨ si.) ComplTarget (without the pieces of knowledge given by DK). The adaptation has consisted in the exchange of slots between the Math teacher and the History teacher.

Fig. 5 :

 5 Fig. 5: Example of revision-based adaptation in the Allen algebra.

  and if each A representable in L is closed and bounded, then (L2) is satisfied. More generally, if d is a distance in the classical mathematical sense (it verifies separation, symmetry, triangle inequality, and d(a, b) < +∞ for every a, b ∈ U), and if every A representable in L is a compact space, then (L2) is satisfied.

Calling it a metric space is an abuse of the usual mathematical language, since d does not necessarily verifies all the postulates of a distance metric. However, the term metric space is used in this chapter with this generalized meaning, for the sake of simplicity.

Once suggested by Pierre Marquis. Thanks Pierre!

In the first publications about -adaptation, the term "conservative adaptation" was used for any -adaptation. Then, it has appeared that some -adaptation could hardly be qualified as conservative (see below), thus, from now on, the term of conservative adaptation is only used for revision-based adaptation using an orthogonal revision operator.

A coarse modeling of this cost is cost(r) = -log P where P is the probability that y t is a licit solution of x s . Thus, the additivity of the cost corresponds to an independence assumption of the q adaptation steps.

Some DLs use constructs that go beyond standard first-order logic, such as concrete domains, but this is not the case for ALC.

U corresponds to the set of scenarios, i.e., fully constrained QCNs. Mod(ϕ) is the set of the scenarios that are more specific than the QCN ϕ. A distance d between scenarios is defined. One problem is that if A = Mod(ψ) and B = Mod(µ), A d B is not necessarily representable by a QCN (i.e., postulate[START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF] does not hold). In this case, to write it in a simplified manner, a most specific QCN χ is chosen such that Mod(χ) ⊇ A d B, and ψ µ = χ.


Tobias Isenberg

An Interaction Continuum for Visualization

Keywords:

It is the year 2039, the desktop is not dead, and it does not look like this situation will change for a while. In any practical application domain in which data visualization is used, the desktop remains to be one of the most important tools for data exploration, analysis, and processing. Since the year 2014, non-desktop platforms for data exploration including large displays, immersive environments, tangible controls, and mobile devices have found their place for data visualization applications-but they have not and will not replace the desktop in many practically relevant tasks. Instead, researchers have finally begun to work toward an interactive visualization continuum that allows researchers and data analysts to transition between the different platforms and to use the tools for those tasks they support best: the desktop for in-depth, single-user analysis and novel platforms for group discussions, mobile data access, and/or good spatial perception.

THE STATE OF THE ART-AN ANTITHESIS

It is the year 2014: The desktop is alive and thriving-at least for many forms of professional work with data and visualizations. Mobile touchenabled devices such as tablets and smart phones may be in the process of replacing PCs for many tasks in personal computer usage including web browsing, e-mail, social media interactions, and second screen applications for media consumption. I would argue, however, that this is largely not the case for applications in which visualizations are explored in professional environments. In these application scenarios, the desktop environment has irrefutable advantages: high processing powers (on the PC itself or in client-server scenarios), high graphics capabilities, precise input, easy data exchange possibilities, robust input processing, and many more. In contrast, immersive environments are difficult to set up, calibrate, and maintain; large displays do not provide similarly precise input modalities; and mobile devices do not have the same computing/graphics powers and also suffer from imprecise input.

I also believe that this situation will not change in the foreseeable future because the mentioned advantages of desktops and disadvantages of novel devices will continue to exists. In my view, the desktop will continue to be a major (if not the most important) platform for visualization use. We can certainly try to address some of the issues in the novel platforms such as working on precise interaction mechanisms for touch input or investigating robust calibration for immersive displays. I believe, however, that it would be better to think about how to use the different platforms for what they support best, and to come up with better ways to transition between the different platforms.

In this position paper I focus, in particular, on 3D spatial data that plays an important role, for example, in medicine (e. g., CT or MRI scans, dwMRI-based fiber tracking, etc.), fluid mechanics (e. g., 3D fluid flow simulations), other domains in physics (e. g., many 3D simulations), astronomy (e. g., 3D particle datasets of mass distributions in the universe), biology (e. g., molecular structures), etc. Interactive visualizations [START_REF] Keefe | Integrating visualization and interaction research to improve scientific workflows[END_REF] in these application domains are particularly interesting and challenging for novel interaction platforms because they not only require good graphics computation support but they also can benefit from stereoscopic 3D displays and/or tangible interactions due to the three-dimensional nature of the data, while at the same time requiring adequate interaction techniques.

These requirements have lead to dedicated display and input environments being developed-not only recently. For example, immersive environments [START_REF] Bryson | Virtual reality in scientific visualization[END_REF] such as the Responsive Workbench [START_REF] Krüger | The responsive workbench[END_REF] and the CAVE [START_REF] Cruz-Neira | The CAVE: Audio visual experience automatic virtual environment[END_REF] have been created and haptic manipulation using force-feedback devices [START_REF] Taylor | The Nanomanipulator: A virtual-reality interface for a scanning tunneling microscope[END_REF] have been explored. The reason that these innovative display environments seemingly have not seen a wide-spread adoption can be seen in the complex nature of their technical setup, the need for calibration and constant re-calibration, and continued need for maintenance. Visualization applications in these environments often need to be specially created and developed, and a transition to the more wide-spread tools on desktop platforms is typically difficult.

More recently, novel touch-based interaction paradigms have also been explored for 3D spatial datasets [START_REF] Isenberg | Visualization on interactive surfaces: A research overview[END_REF][START_REF] Isenberg | Position paper: Touch interaction in scientific visualization[END_REF][START_REF] Keefe | Reimagining the scientific visualization interaction paradigm[END_REF]. A particular challenge here is that the input is inherently two-dimensional, while the data and thus the manipulations have to happen in a three-dimensional space [START_REF] Keefe | Reimagining the scientific visualization interaction paradigm[END_REF]. That means it is necessary to think about the nature of natural interaction [START_REF] Wigdor | Brave NUI World: Designing Natural User Interfaces for Touch and Gesture[END_REF] and, in particular, gestural interaction [START_REF] Isenberg | Gestures vs. postures: 'Gestural' touch interaction in 3D environments[END_REF] that is often advocated to be beneficial in these environments. Precise input that is fundamental to effective and efficient data exploration still remains a challenge. When employed in connection with mobile devices, the processing and graphics power is often an issue in the context of the large datasets that need to be examined. Because many of these challenges remain unsolved to this date there are still only few solutions available and its seems that such platforms are rarely employed in practice. Despite the mentioned challenges, however, the novel platforms do offer numerous advantages in how they support interaction with digital content including visualizations. For example, it is often mentioned that touch input can lead to faster target selection when compared to mouse interaction [START_REF] Kin | Determining the benefits of directtouch, bimanual, and multifinger input on a multitouch workstation[END_REF], that it can be beneficial in collaborative settings [START_REF] Hornecker | Collaboration and interference: Awareness with mice or touch input[END_REF], and that it provides somesthetic feedback important for interaction in real and virtual environments [START_REF] Robles-De-La-Torre | The importance of the sense of touch in virtual and real environments[END_REF]. Most importantly for the interaction with spatial data, however, is that touch input is inherently direct in the data manipulations and thus provides a high degree of immersion through interaction-people often report that they feel in control of the data [START_REF] Yu | FI3D: Direct-touch interaction for the exploration of 3D scientific visualization spaces[END_REF]. Stereoscopic environments, in contrast, offer a high degree of visual immersion which is similar important for the exploration of spatial data. Tangible interfaces combine some of the advantages of touch input and stereoscopic displays: they provide tangible 3D elements to control the interactive exploration with data, albeit without the flexibility of changing the representation (of the tangible) that both touch input on flat screens and stereoscopic displays offer.

VISION: AN INTERACTION CONTINUUM FOR VISUALIZATION

My vision for the future, therefore, is not that the desktop is being replaced by any of the existing or future interactive platforms. My vision, instead, is that that we find a way to combine the different interactive data exploration environments to be able to profit from their respective advantages. I envision an environment that lets researchers transition from their desktop-based data analysis tools to large screens with touch input or tangible controls, to immersive rooms, to mobile devices, and maybe also to combinations of these. I would like this continuum to go beyond the simultaneous use of a few of the named data exploration paradigms as has been explored already (e. g., [START_REF] Coffey | Interactive slice WIM: Navigating and interrogating volume datasets using a multi-surface, multi-touch VR interface[END_REF])-I would like to be able to transition from one environment to another one in a way that is as seamless as possible. This would enable researchers to make use of the different single (or combined) environments for what they support best. For example, touch-based large displays could support collaborations of small groups, complex spatial datasets could be analyzed in immersive rooms, special statistical data analyses and in-depth follow-up explorations could be conducted using the traditional desktop tools, and mobile touch-enabled devices could be used for data presentations in coincidental meetings or as a second screen to control large monoscopic or stereoscopic data displays. In all of these environments, one should be able to access the same data (potentially adjusted in its detail or resolution to the specific display and interaction), use the same or similar interaction paradigms, and be able to access matching data analysis tools adjusted to the respective input device. However, my interaction continuum for visualization needs to go far beyond a simple data transfer as it is being investigated in Ubicomp scenarios for multi-display environments. Instead, we need to understand how the different tasks in visualization [START_REF] Brehmer | A multi-level typology of abstract visualization tasks[END_REF] can be supported in the different environments, how we can capture and transfer insights gained in one environment to be used in another one, and which tasks are supported best in which environments.

This vision is, at this point, still a relatively vague hope for the future and many questions remain unanswered. For example, I am not sure if it is possible to create a set of interaction techniques that not only works in one environment but relates to those used in others and if such a set of interactions can be sufficiently general to be able to apply to all or at least many of the application domains in which 3D data is being analyzed (also see the discussions by Daniel F. Keefe and myself [START_REF] Keefe | Reimagining the scientific visualization interaction paradigm[END_REF]). If not, can we at least create a set of fundamental interaction techniques that can be shared among different disciplines and interaction platforms? Moreover, in the context of novel interactive platforms people often describe the interaction to be "natural." I believe that this term is ill-defined and often badly understood. What does the notion of "natural interaction" really mean in this context is unclear since in data analysis applications we often talk about experts who can spend some time to learn a new tool or technique. A "natural interaction" for them would probably also include one that allows them to easily control a chosen parameter in a precise way, not only gestural control such as pinch-to-zoom which combines four degrees of freedom in a single, imprecise interaction. Of course, for being able to create an interaction continuum we also would need to create an underlying technical platform that supports the intended transitions. Would it be possible to create an API or a toolkit-maybe inspired by how TUIO [START_REF] Kaltenbrunner | TUIO -A protocol for table-top tangible user interfaces[END_REF] supports the processing of many different kinds of touch input and tag sensing for multiple hardware and software platforms?