Béatrice Fuchs
email: beatrice.fuchs@liris.cnrs.fr

Jean Lieber
email: jean.lieber@loria.fr

Laurent Miclet
email: laurent.miclet@gmail.com

Alain Mille
email: alain.mille@liris.cnrs.fr

Amedeo Napoli
email: amedeo.napoli@loria.fr

Henri Prade
email: prade@irit.fr

Gilles Richard
email: richard@irit.fr

Case-based reasoning, analogical reasoning, and interpolation

This chapter presents several types of reasoning based on analogy and similarity. Case-based reasoning, presented in Section 2, consists in searching a case (where a case represents a problem-solving episode) similar to the problem to be solved and to adapt it to solve this problem. Section 3 is devoted to analogical reasoning and to recent developments based on analogical proportion. Interpolative reasoning, presented in Section 4 in the formal setting of fuzzy set representations, is another form of similarity-based reasoning.

Introduction

Charles S. Peirce (1839Peirce ( -1914) ) distinguished three main forms of logical inference, namely deduction, abduction and induction, in relation with scientific inquiry (see [Peirce, 1955]). Each of these three inference forms involves generic knowledge in their patterns, in a way or another. There exist other modes of reasoning that only deal with factual information and that are still useful for producing plausible conclusions, although they may turn to be false. These later modes are based on the idea of comparing cases and the notion of similarity. This chapter covers two important forms of such inference: case-based reasoning and analogical reasoning. The chapter also includes another form of similarity-based reasoning that provides interpolation capabilities. It is based on fuzzy rules, where a fuzzy set may be viewed as a particular value associated with the values that are more or less close to this value.

The paper is organized into three main sections that are respectively devoted to case-based reasoning, analogical reasoning, and interpolative reasoning.

Case-Based Reasoning

Case-based reasoning (CBR) relies on experience in the form of problem-solving episodes (or cases) in order to solve new problems [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]]. It can be differentiated from other approaches of problem-solving in artificial intelligence (AI) which mainly exploit general domain knowledge to generate solutions. By contrast, a CBR system is mainly based on concrete chunks of experience, with specific contexts. Such chunks are represented by source cases stored in a case base.

When a new problem-the target problem-is given as input to a CBR system, this latter searches in the case base a source case (or, sometimes, several source cases) similar to the target problem that is reused in order to solve it thanks to an adaptation process. The new chunk of experience (the target problem together with its solution), once validated, can be stored in the case base and the system knowledge can gain problem-solving competence this way.

CBR is based on the idea that for solving a problem, the problem-solving experience is often useful, when a "direct" solution is not easily found. For example, if someone wants a pear pie recipe, has not the experience of such a recipe, but has the similar experience of an apple pie recipe, he/she can adapt this latter to cook a pear pie. The underlying principle relates to the analogical proportion "A is to B as C is to D". In the framework of CBR, A and C are problems and B and D are solutions. Figure 1 illustrates this idea. An overview of works on analogical reasoning which is concomitant with the emergence of CBR is given in [Hall, 1989]. Analogical reasoning in itself, independently from CBR, is presented in Section 3.

The origins of CBR can be found in works of M. Minsky and R. Schank. In the work about perception of M. Minsky, a knowledge representation formalism able to explain to some extent the efficiency of human mental activities has been defined [Minsky, 1975]. This formalism is based on structures called frames that Fig. 1 The analogical proportion applied to CBR. can be dynamically reused and that represent models of situations. The matching of frames can be used to recognize situations. The studies of R. Schank on natural language understanding [Schank, 1982] argued that cognitive processes of understanding and learning are linked with the way the human experience is organized. In his theory, meaning is captured thanks to semantic constructs that are independent from syntax and are represented by sequences that are used to predict how future sequences can be extended. Then, he designed the model of scripts for an improved description of episodes by a set of actions structured by relations. This model has then evolved towards the model of dynamic memory, able to reorganize itself dynamically as new episodes are learned, generating generalized episodes that factorize the common features of actual specific episodes (actual in the sense that they are representation of actual facts). In [START_REF] Riesbeck | Inside Case-Based Reasoning[END_REF]], the episodes are described with the help of memory organization packets (MOPs) and the understanding of a situation depends on the way MOPs are related in the memory. Later, Janet Kolodner has implemented one of the first CBR systems based on the model of dynamic memory [Kolodner, 1993].

Basic Notions Related to CBR

In a given application domain, the notions of problem and of solution are given. Problems denotes the problem space and Solutions, the solution space: a problem is by definition an element of Problems, a solution is by definition an element of Solutions. The existence of a binary relation on Problems × Solutions that is read "has for solution" is assumed though the complete knowledge of this relation is usually not known. Solving a problem pb amounts to find (or build) sol ∈ Solutions such that pb has for solution sol. Since the problemsolution relation is usually not completely known, sol is, for most CBR systems, only a solution hypothesis. CBR systems can be categorized according to the type of problems they aim at solving. For example, if a problem is given by an initial stage init and a goal to reach goal, and if a solution is a path in the search space from init to a state satisfying goal, this is a planning problem (see Chapter 10 of Volume 2) and the use of CBR to tackle such a problem is called case-based planning (see Section 2.4). A decision problem is described by a situation for which a decision is required. Other types of problems can be distinguished like configuration diagnosis, or scheduling problems [START_REF] Riesbeck | [END_REF]Schank, 1989, Stefik, 1995].

A case is the representation of a problem-solving episode. Let pb ∈ Problems. In general, a case is given by an ordered pair (pb, sol(pb)) where pb ∈ Problems, sol(pb) ∈ Solutions and pb has for solution sol(pb). Often, pieces of information useful to its reuse are associated with a case. In particular, the available information on the links between pb and sol(pb) is called dependency.

A case base, denoted CaseBase in the following, is a finite set of cases. A source case (srce, sol(srce)) is an element of CaseBase and srce is called a source problem. The target problem, denoted by tgt, is the problem to be solved. CBR is usually modeled by a "cycle" that specifies the sequence of its steps. This cycle contains four general steps having profit of a knowledge base including a case base [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]. This cycle has been enriched by an elaboration step, which gives the cycle presented in Figure 2.

The Process Model of CBR

During the elaboration step, the query expressed by the user is transformed into a problem understandable by the system, and the target problem tgt is generated. During the retrieval step, a case (srce, sol(srce)) similar to the target problem tgt is searched in the case base. Then this case is modified during the adaptation step (also know as reuse step). The solution sol(tgt) can be validated (e.g., by experts) and, if validated or corrected, the newly formed case (tgt, sol(tgt)) can be stored in the case base (validation and case storage steps).

This process model has variants. One of them is the possibility to retrieve and adapt (or combine) several source cases similar to the target problem.

The Knowledge Model of CBR

A CBR system is based on several knowledge containers (see [Richter, 1998] and [START_REF] Richter | Case-based reasoning[END_REF]). One of them is the case base. Another one constitutes the domain knowledge (or domain ontology), that contains the vocabulary used to express the cases and also expresses sufficient conditions for a problem, a solution or a case to be licit (for the notion of ontology, see chapters 6 and 23 of this volume). The third one is the retrieval knowledge or similarity, that enables to prefer a source case to another, given the target problem. Similarity is often implemented thanks to a similarity measure. Finally, the adaptation knowledge is used by adaptation. It is often represented by adaptation rules.

An important feature of CBR is that these knowledge containers are complementary, in the sense that the "weakness" of one of them can be compensated by "strength" of the other ones. For example, if the case base is large, then little adaptation knowledge is necessary. Conversely, with a lot of adaptation knowledge, fewer cases are needed.

The next section describes with more details the different steps of CBR with their use of the knowledge containers.

The CBR Steps

Elaboration

A CBR system is triggered by a query given by the user, that is treated by the elaboration step. Elaboration prepares case retrieval by enriching the problem description in order to obtain a target problem. This preliminary step points out in particular the problem features that may have an impact on the solution. These features can be inferred from domain knowledge in order to ease the problem-solving, in particular the retrieval and adaptation steps.

Retrieval

Retrieval consists in searching in the case base a case (srce, sol(srce)) whose reuse is useful to solve the target problem:

retrieval : (CaseBase, tgt) -→ (srce, sol(srce)) ∈ CaseBase
It is based on the knowledge of the similarity between problems, according to the following principle: similar problems have (or may have) similar solutions.

Similarity measure

A frequent way to represent similarity is to use a similarity measure S : Problems×Problems → [0; 1] in which the features are weighted according to their estimated importance in the problem solving. This way, it can be expressed

• That two problems srce and tgt are similar: S (srce, tgt) S min , where S min is a predefined similarity threshold; • That, given the target problem tgt, retrieval prefers a case (srce 1 , sol(srce 1 ))

to a case (srce 2 , sol(srce 2 )): S (srce 1 , tgt) > S (srce 2 , tgt).

Sometimes, a measure of dissimilarity (e.g., a distance function) d : Problems× Problems -→ [0; +∞[ is used instead of a similarity measure, knowing that S must be maximized when d must be minimized. A classical way to associate a dissimilarity measure d to a similarity measure S (and conversely) consists in writing S (srce, tgt) = 1/(1 + d(srce, tgt)).

A frequent class of similarity measure is defined as follows. First, the features of srce and tgt are matched (e.g., if the case representation is a simple attributevalue representation, two features with the same attribute are matched). Then, a local similarity measure is computed between each of the matched descriptors. Then, the global similarity measure S (srce, tgt) is computed by an aggregation of the values of the local similarity measures, using weights according to the feature importance. One way to choose these weights is to use a machine learning technique: the best set of weights is the one that best fits a training set of preference relations.

In the approach developed by E. Hüllermeier [Hüllermeier, 2007], gradual similarity relations are used. They are inspired from approximate reasoning based on fuzzy rules (cf. section 4.1).

Classification and indexing

In many CBR system, retrieval has profit of a structure on the case base. The idea is to organize the case base in classes along several features. In particular, the use of an index hierarchy is frequent, an index of a source case being considered as a kind of summary of this case (sometimes expressed in a less expres-sive formalism [Koehler, 1996]). This hierarchy gathers cases having common features in a class. Let idx(tgt) be the index associated to the target problem and idx(srce) be the index associated to each (srce, sol(srce)) ∈ CaseBase. Then, the source cases whose indexes are the closest ones to idx(tgt) in the hierarchy (according to some distance function between nodes of a graph) are the first candidates (e.g., if idx(srce) shares with idx(tgt) a direct superclass, srce and tgt are considered to be close).

In Resyn/CBR, an application of CBR to synthesis in organic chemistry, the index idx(srce) of (srce, sol(srce)) is a generalization of srce and retrieval is performed by a classification process [START_REF] Lieber | Using Classification in Case-Based Planning[END_REF]. Retrieval returns a source case (srce, sol(srce)) associated with a similarity path S(srce, tgt) that ensures the adaptability of the source case to solve the target problem. A similarity path is a sequence of relations from srce to C 0 = tgt, with the index I 0 = idx(srce) as intermediate of the hierarchy that generalizes the source case:

srce I 0 1 -→ I 1 2 -→ . . . p -→ I p C q r q ←-. . . r 2 ←-C 1 r 1 ←-C 0 = tgt
Building a similarity path from srce to tgt is a matching process. A cost is associated to any similarity path. It is used to choose the source case for which a similarity path with the lowest cost can be built. Each relation r of a similar-

ity path (r ∈ { , 1 -→, 2 -→, . . . , p -→, , r q ←-, . . . r 2 ←-, r 1
←-} where the i 's and the r j 's are transformation rules) is associated to an adaptation function A r : the pair (r, A r ) constitutes an adaptation rule (also called reformulation in [Melis et al., 1998]). For example, the relation ("is more specific than") is associated to a solution generalization function A and the relation ("is more general than") is associated to a solution specialization function A . Each of these relations are exploited in the adaptation step and retrieval ensures the adaptability of the retrieved source case. For this reason, this approach belongs to the family of adaptation-guided approaches to retrieval [START_REF] Smyth | Using adaptation knowledge to retrieve and adapt design cases[END_REF].

In [Koehler, 1996], a case-based planner is described in which the plans are described in a complex temporal logic but retrieval is done in a tractable description logic: cases are indexed in this more abstract and more tractable formalism and the source cases whose index are the closest ones to the index of the target problem are retrieved.

Adaptation

After retrieval, the solution of the source case is proposed as a solution to the target problem. Usually, this solution needs to be adapted in order to take into account differences between source and target problems. The objective of adaptation is to solve tgt on the basis of the retrieved case (srce, sol(srce)): adaptation : ((srce, sol(srce)), tgt) -→ sol(tgt)

Note that only the adaptation of a single case is considered in this section.

Adaptation is essential when the solution of the source problem cannot be reused as such for solving the target problem. It consists in modifying the source case using domain knowledge and adaptation knowledge, taking into account differences between the source and target problems (which are frequently highlighted during retrieval).

Adaptation can be considered as an analogical problem solving that can be read in two different ways: "sol(tgt) is to sol(srce) as tgt is to srce" and "sol(tgt) is to tgt as sol(srce) is to srce" . These two ways correspond to two general approaches to adaptation:1

• Transformational adaptation [Carbonell, 1983] consists in modifying directly the source solution. It aims at modifying either the values of some solution features (this is called adaptation by substitution) or complex parts of the solution (this is called structural adaptation); • Derivational adaptation [Carbonell, 1986] consists in building entirely the solution of the target problem by applying the method that was used to generate the source solution (which often requires a modification of this method to take into account specificities of the target problem).

This can be read on the schema of Figure 1. Indeed, when the horizontal relations are considered (i.e., between problems and between solutions), this corresponds to transformational adaptation. The principle of adaptation is then to find the variations between solution features from variations between problem features. When vertical relations are considered (i.e., from a problem to a solution), this corresponds to derivational adaptation.

Transformational adaptation

First, the solution of the source case is copied in order to constitute a first solution of the target problem. This "first draft" is then modified according to the differences between the source and target problems pointed out by the matching process. The approaches to adaptation vary according to the types of operations. The adaptation by substitution simply replaces elements of the solution by other elements, while structural adaptation modifies with more depth the structure of the solution by deleting and adding elements.

In the case-based planner CHEF [Hammond, 1986] dedicated to cooking recipes, the adaptation by substitution modifies some ingredients in order to satisfy constraints of the target problem. CHEF also makes structural modifications on the steps of the recipe. The system Déjà Vu [START_REF] Smyth | Retrieval and adaptation in déjà vu, a case-based reasoning system for software design[END_REF] uses adaptation strategies and adaptation specialists. An adaptation specialist uses transformation operations to perform local adaptations, whereas adaptation strategies solve the conflicts between adaptation specialists. Model-based adaptation (such as the CASEY system [Koton, 1988]) exploits transformations that are controlled by a causal reasoning.

Derivational adaptation

Derivational adaptation wholly regenerates the solution of the target problem by replaying the reasoning having led to the solution of the source case (when an operator cannot be applied, some local search is generated). Its application usually requires that a strong domain knowledge is available (ideally, a complete domain knowledge in the sense that the relation "has for solution" between problems and solutions is completely known to the system).

Some unifying approaches to adaptation

From the development of ad hoc approaches of adaptation, some general principles and approaches have been pointed out, proposing general models of adaptation.

In [START_REF] Fuchs | A knowledge-level task model of adaptation in case-based reasoning[END_REF]], a general model of tasks has been introduced to characterize the operations realized in the framework of formal models of adaptations. Adaptation consists in choosing a difference, in applying the corresponding modification and then in checking the consistency of the result. A modification can be a substitution, a deletion or an addition of elements. A substitution or an addition requires the search of an adequate element and this is done thanks to the domain knowledge.

In [START_REF] Fuchs | An Algorithm for Adaptation in Case-Based Reasoning[END_REF], the authors propose an approach to adaptation based on the notion of influence of the problem descriptors to the solution descriptors which, combined with the matchings performed during retrieval, makes possible to highlight differences of solution descriptors that can be applied to the source solution in order to obtain a target solution. This approach makes a strong connection between retrieval knowledge (based on problem differences) and adaptation knowledge (based on solution differences). It has been applied to numerical problems in the so-called differential adaptation approach (see [START_REF] Fuchs | Differential Adaptation: an Operational Approach to Adaptation for Solving Numerical Problems with CBR[END_REF]).

Adaptation and belief revision

The issue of adaptation and the issue of belief revision (see Chapter 14 of this volume) are both based on the notion of modification and change, hence the idea to exploit a revision operator for performing adaptation.

An agent having beliefs ψ on a static world can be confronted to new beliefs µ in conflict with ψ: ψ ∧ µ is inconsistent (∧ being the operator of conjunction of belief bases in the considered formalism). If µ are assumed to have priority over ψ, then the problem of incorporating µ to ψ is the one of the revision of ψ by µ. The result ψ µ depends on the revision operator . In [START_REF] Alchourrón | On the Logic of Theory Change: partial meet functions for contraction and revision[END_REF] are defined postulates that must (or should) satisfy, in particular, predicates expressing that ψ µ has to be computed with a minimal change of ψ into ψ such that ψ ∧ µ is consistent. In [START_REF] Katsuno | Propositional knowledge base revision and minimal change[END_REF], revision has been studied in a propositional framework and it has been studied more recently is other formalisms, such as the qualitative algebras (for these algebras, see Chapter 5 of this volume).

Revision-based adaptation can be defined as follows. Let L be a formalism in which can be expressed the domain knowledge DK, the source case to be adapted Source (i.e., the problem srce and its solution sol(srce)) and the target case Target (i.e., Target is given by the target problem tgt, the solution being initially unknow). Let be a revision operator on L . -adaptation consists in modifying minimally the source case (this minimality being the one of the chosen revision operator ) in order to make it consistent with the target case, keeping in mind the fact that these cases have to be considered with the integrity constraints given by the domain knowledge:

(DK ∧ Source) (DK ∧ Target)
This general approach to adaptation constitutes a general framework including different approaches to adaptation including the adaptation by similarity paths. The idea is that the adaptation knowledge AK associated with this type of adaptation enables to define an operator AK . Therefore, the AK -adaptation adapts cases using both adaptation knowledge and domain knowledge.

Revision-based adaptation has been studied in propositional logic [Lieber, 2007] then in a larger framework [START_REF] Cojan | Conservative adaptation in metric spaces[END_REF]. A similar adaptation has also been studied in the framework of the expressive description logic A L C [START_REF] Cojan | An Algorithm for Adapting Cases Represented in ALC[END_REF] and in the tractable description logic E L ⊥ [START_REF] Chang | Algorithm for adapting cases represented in a tractable description logic[END_REF] (for description logics, see Chapter 6 of this volume).

Validation and Case Storage

Once the target problem solved, the new case (tgt, sol(tgt)) has to be tested and evaluated. This evaluation is generally done by a human, in particular when the CBR system has incomplete problem-solving knowledge, and aims at answering the question "Is sol(tgt) a correct solution of tgt?" If the result of this evaluation is positive, then the new case can be stored in the case base. Else, the solution sol(tgt) has to be repaired and an explanation of this failure may be pointed out to avoid such a failure in the future. This is the role of the validation step (sometimes called revision) to question the system knowledge that has led to this failure, hence its relation with knowledge acquisition issues, presented in the next section.

Knowledge acquisition for a CBR system

In order to implement a CBR system (or any kowledge-based system, denoted by KBS in the following [Stefik, 1995]), its knowledge base has to be acquired and to evolve over time. In this section, "knowledge acquisition" (KA) is used as a general term for getting knowledge: from experts, from a machine learning process, or from both, and constitutes a field of knowledge engineering (see Chapter 23 of this volume). A CBR system knowledge base consists of four containers, the issue of KA for such a system can be described by four interrelated issues.

Case base KA

The case acquisition, or case authoring, consists mainly in the representation of informal problem-solving episodes. A classical way to do it consists in interviewing an expert about the way he/she solved a problem in the past and then in formalizing it. Sometimes, there are many available data that are stored informally on machines, but requires to be automatically transformed into actual cases, handable by a CBR process. For example, if problem-solving episodes are available in a textual form, natural language processing techniques can be used to interpret them into a formal representation [START_REF] Dufour-Lussier | Automatic case acquisition from texts for process-oriented case-based reasoning[END_REF].

Acquisition of the domain knowledge (or domain ontology)

The issue of KA of ontologies has been studied a lot in the KA community (see Chapter 23 of this volume) and CBR systems benefit from it. The specificity of the acquisition of domaine ontology is its close links with the other containers, as detailed hereafter (actually, this can be argued for each pairs of knowledge containers).

The case acquisition involves the need to define a vocabulary for representing cases. This vocabulary constitutes an important part of the domain knowledge, or domain ontology.

As mentioned above, the adaptation process uses both adaptation knowledge and domain knowledge (see, e.g., revision-based adaptation). In particular, it is frequent to substitute a class with another one that is close (e.g., an apple by a pear in a recipe), this closeness being often related to the ontology (e.g., apples and pears are both fruits).

In a similar way, the retrieval process often uses an ontology (e.g., to compare to values of the same attribute).

Acquisition of similarity (retrieval knowledge)

Retrieval knowledge is often represented thanks to a similarity measure, acquisition of this case container frequently amounts to the acquisition of such a measure, based on known preferences between cases, given target problems. In [Stahl, 2005], a learning of similarity measure procedure is defined for this purpose.

Adaptation knowledge acquisition

A knowledge-light approach uses mainly the case base for generating adaptation knowledge [START_REF] Wilke | A Framework for Learning Adaptation Knowledge Based on Knowledge Light Approaches[END_REF].

In [Hanney, 1996], the case base is exploited to generate inductively adaptation rules in the condition-action form. The training set is given by pairs of cases from the case base: such a case pair ((srce 1 , sol(srce 1 )), (srce 2 , sol(srce 2 )) is read as an adaptation adaptation((srce 1 , sol(srce 1 )), srce 2 ) = sol(srce 2 ). The conditions express differences between problems that are related to differences between solutions. In [START_REF] Craw | Learning adaptation knowledge to improve case-based reasoning[END_REF], the same principle has been applied using decision tree induction algorithms. In [Mc Sherry, 1999], adaptation is performed by searching in the case base case pairs whose differences are similar to the differences between the retrieved case and the target problem. The adaptation consists in applying this difference between solutions in order to obtain a solution to tgt. In [d' [START_REF] Aquin | Case base mining for adaptation knowledge acquisition[END_REF], a knowledge discovery process using an algorithm of closed frequent itemset extraction (see Chapter 13 of Volume 2) is used in order to acquire adaptation knowledge on all the pairs of source cases. The adaptation rules are based on the differences between cases, represented by descriptors labelled with the type of variations (constant, added or removed) from the source to the target.

The approaches presented above are off-line, but, as can be seen in the following, some on-line approaches have been developed that exploit the steps of the CBR cycle to extract new pieces of knowledge.

Opportunistic knowledge acquisition for CBR

This form of knowledge acquisition consists in having profit of failures during the building of a solution. The approach relies on interactions between the domain expert and the system in order to acquire missing information that would have prevented the failure. It is an online approach that takes place during the validation step and is only triggered in case of failure, when the output of the adaptation process is not a valid solution of the target problem, hence the adjective "opportunistic".

The system CHEF was probably the first system to apply an opportunistic knowledge acqusition process from failures [Hammond, 1990]. DIAL was another early system using this principle [START_REF] Leake | Acquiring case adaptation knowledge: A hybrid approach[END_REF]. In [Hall, 1986], a previous work on learning by failure, outside CBR, was presented.

The FIKA (Failure-driven Interactive Knowledge Acquisition) approach defines general principles for interactive and opportunistic knowledge acquisition in CBR that has been applied to the systems FRAKAS and IAKA. The FRAKAS system [START_REF] Cordier | Failure analysis for domain knowledge acquisition in a knowledge-intensive cbr system[END_REF] is a decision support system that exploits failures of revision-based adaptations in order to highlight gaps in the domain knowledge of the system (with respect to the expert knowledge). The knowledge acquisition process is triggered during which the interactive analysis of the failure leads to new units of knowledge that are in accordance with the expert knowledge. In IAKA, these principes have been applied to adaptation knowledge acquisition [START_REF] Cordier | Opportunistic Acquisition of Adaptation Knowledge and Cases -The IAKA Approach[END_REF]. The goal is to exploit the corrections performed by the expert on the solution during the validation phase in order to trigger an interactive knowledge acquisition process. This process consists in identifying and correcting the adaptation knowledge at the origin of the failure.

Some CBR Systems

This section describes some CBR systems for the purpose of illustration. First, some generic tools useful for CBR are presented. Then, several application-dependent CBR systems are presented according to the categories they belong to.

Some generic tools for CBR

The system jColibri is a logical framework for developing CBR systems [Recio-Garcia, 2008]. In order to build a CBR application in jColibri, a task model has to be configurated and the methods associated to each task has to be implemented. This system uses an ontology of tasks and methods that defines an extendable base of the framework design. For a particular application, it is sufficient to instanciate this base and to determine the necessary extensions.

MyCBR [START_REF] Stahl | Rapid prototyping of CBR applications with the open source tool myCBR[END_REF] is another tool for building CBR systems that is focused on various way of modeling similarity.

Tuuurbine [START_REF] Gaillard | Tuuurbine: A Generic CBR Engine over RDFS[END_REF] is a tool for case retrieval when cases and domain knowledge are represented within the semantic web standard RDFS: the target problem is translated into one or several SPARQL queries (a SPARQL query can be used to query an RDFS base) whose execution returns an exact match (for semantic web, see Chapter 6 of Volume 3). If no exact match is found, then the query is modified minimally in new queries for which an exact match is found.

Revisor (revisor.loria.fr) is a tool for revision-based adaptation in various formalisms (propositional logic, linear constraints and qualitative algebras).

Case-based planning

A CBR system solving planning problems (usually given by an initial state, a goal statement and a set of operators on states) and thus, building plans, is a casebased planning system. A case-based planner relying only on the search in the state space does what is sometimes called planning from first principles or planning from scratch. By contrast, some authors qualify the action of a case-based planner as planning from second principles [Koehler, 1996].

The system CHEF, already mentionned above, is such a system: for CHEF, a recipe is represented by a preparation plan [Hammond, 1986].

Prodigy/Analogy is a case-based planner working on a classical representation of operators (condition, del-list, add-list) working with the assumption of completeness of the problem-solving relation (the system can check whether a plan sol is a correct solution of a planning problem pb, without help from a human) [Veloso, 1994]. This planner is based on derivational adaptation [Carbonell, 1986], on retrieval/adaptation of multiple cases, on the use of a planner from first principles for replaying the retrieved plans, and on the notion of footprint. The footprint of the initial state e 0 of a plan P is an abstraction of e 0 obtained by removing pieces of information that are not necessary for the execution of P. This notion of footprint has been reused, in particular, for the indexing process of the Resyn/CBR system mentioned above.

Many case-based planning approaches have been developed in the CBR community using different principles. Let us mention the use of plan abstraction for case-based planning [START_REF] Bergmann | Building and Refining Abstract Planning Cases by Change of Representation Language[END_REF]: plans are described at several levels of abstraction, and this approach uses abstraction and refinement processes to travel from one level to another one. Finally, let us mention [START_REF] Cox | Case-based planning[END_REF] and [Spalazzi, 2001] that are syntheses on case-based planning.

Process-oriented CBR (PO-CBR)

A PO-CBR system is a CBR system in which cases represent processes. PO-CBR has some similarities with case-based planning but differs in the same way as processes differ from plans: the latters are usually strongly related with formal operators (defined by conditions and actions), whereas a process is a structured set of tasks which are in general atomic objects (names). The most classical representation of cases in PO-CBR is the one of workflows. A selection of papers on PO-CBR has been published in [START_REF] Minor | Information Systems volume 40, Special Section on Process-Oriented Case-based Reasoning[END_REF].

Conversational CBR (CCBR)

Classically, in a CBR system, the target problem is given entirely to the system and then solved by the CBR process. By contrast, in conversational CBR, the target problem is interactively built through a human-machine dialog [START_REF] Aha | Conversational casebased reasoning[END_REF], using the case base: based on the initial query, the case base is searched and specific questions are posed to the user. Then, the process repeats itself until a sufficiently detailed target problem is given. This approach to CBR is used in particular for help-desk applications.

Textual CBR (TCBR)

In many applications, cases are, at the start of the development, available in an informal way, for instance in the form of texts in natural language. The issue of TCBR is to apply CBR to cases encoded as texts [START_REF] Weber | Textual case-based reasoning[END_REF]. One way to do this consists in translating (semi-)automatically these texts into formal cases using natural language processing techniques (see, e.g., [START_REF] Dufour-Lussier | Automatic case acquisition from texts for process-oriented case-based reasoning[END_REF]), such as information extraction (as in [START_REF] Brüninghaus | The role of information extraction for textual CBR. Case-based reasoning research and development[END_REF]). Another way consists in manipulating directly textual cases. For this purpose, similarity measures between texts are used, for example, compression-based similarity measures [Cunningham, 2009, §5.1].

Trace-based reasoning (TBR)

TBR is a reasoning type similar to CBR, with some differences. If CBR considers so-called problem-solving episodes, CBR systems exploiting the temporal facets of an episode are rare, just as the descriptors involved are not necessarily temporally located in relation to one another. Moreover, in CBR, a problem-solving episode is considered independently of the different "contexts" in which the episodes were held.

Human experience, when it is considered as temporal by essence, can be represented by a temporal trace revealing elements of an underlying implicit process. For instance, the trace of use of a computer device or program captures some of the user knowledge needed by his/her task. The trace theory gives a definition of this notion of trace, how it can be represented together with the way the retrieval of episodes of use are computed. When the traces are exploited on the basis of retrieval and adaptation, TBR can be seen as a variation on CBR [START_REF] Georgeon | Supporting activity modelling from activity traces[END_REF], Mille, 2006, Zarka et al., 2011] and is based on a cycle similar to the one of Figure 2.

CBR applied to particular fields

There has been many applications of CBR to medical domains as well as to other fields of health science, for various tasks such as assisting diagnosis or treatment, for tasks in medical engineering, etc. This can be explained in part by the fact that the knowledge of physician combine theoretical knowledge (comparable to the domain knowledge in CBR) and experience (that is represented by cases in CBR). The papers [START_REF] Bichindaritz | Case-based reasoning in the health sciences: What's next?[END_REF]] and [START_REF] Begum | Casebased reasoning systems in the health sciences: a survey of recent trends and developments[END_REF] present syntheses of work on CBR to health science.

In a similary way, CBR has been applied to the legal domain (see, e.g., [START_REF] Brüninghaus | The role of information extraction for textual CBR. Case-based reasoning research and development[END_REF]), in which laws correspond to domain knowledge and legal precedents to cases.

In fact, CBR has been widely applied to many domains in which an important part of the knowledge consists in specific experience, such as architecture [START_REF] Dave | Case-Based Spatial Design Reasoning[END_REF], cooking [START_REF] Cordier | Taaable: a Case-Based System for personalized Cooking[END_REF], design [Goel, 1989], forest fires [Rougegrez, 1994], games [START_REF] Woolford | SCOUT: A Case-Based Reasoning Agent for Playing Race for the Galaxy[END_REF], music [de Mántaras, 1998], running [START_REF] Smyth | Running with Cases: A CBR Approach to Running Your Best Marathon[END_REF], theorem prooving [Melis, 1995] (to cite only a few of such domains with particular examples).

Reasoning by Analogy and Analogical Proportions

The role of analogy in human reasoning has been acknowledged for a long time. Analogical reasoning exploits parallels between situations. It refers to the reasoning with which the human mind infers from an observed similarity another similarity that is not known. While the induction goes from several specific situations to a general rule, analogy goes from one similarity between specific situations to another one. It enables us to state analogies for explanation purposes, for drawing plausible conclusions, or for creating new devices by transposing old ones in new contexts. For this reason, analogical reasoning has been studied for a long time, in philosophy, e.g., [Hesse, 1966], in cognitive psychology, e.g., [START_REF] Gentner | The Analogical Mind: Perspectives from Cognitive Science[END_REF], Hofstadter and Sander, 2013, Holyoak, 2005], and in artificial intelligence, e.g., [START_REF] Helman | [END_REF], Hofstadter and Mitchell, 1995, Melis and Veloso, 1998a], under various approaches [French, 2002, Prade and Richard, 2014a, McGreggor et al., 2014]. Thus, since the beginnings of artificial intelligence, researchers have been interested in analogical reasoning as a basis for efficient heuristics for solving puzzles where a series has to be completed [Evans, 1964], or for speeding up automatic deduction processes [Becker, 1969, Kling, 1972]. This latter idea has then been resumed and systematically explored in studies such as the ones of [Melis and Veloso, 1998b] or [START_REF] Sowa | Analogical reasoning[END_REF]. At the modeling level, analogy can be envisaged at least in two different manners, either i) as a matter of mapping two situations, one considered as a source of information, the other as a target about which one would like to draw some inference, or ii) in terms of analogical proportions, i.e., statements of the form "A is to B as C is to D". In the two following subsections, we consider these two views in sequence.

It should be also pointed out that case-based reasoning, as presented above, can be viewed as a form of analogical reasoning. As explained in the first part of this chapter, CBR uses a base of known cases often stored as (problem, solution) pairs. When confronted to a new problem B, the problems A similar to B such that A appears in a problem-solution pair (A,C) are retrieved from the case base. Using a so-called adaptation technique, the solution C of the problem A is transformed into a candidate solution D of B (see, e.g., [START_REF] Aamodt | Case-based reasoning: Foundational issues, methodological variations, and system approaches[END_REF]). Thus, one can say that the target pair (B, D) parallels pairs (A,C) retrieved from the information source, but we may also state that "solution D is to solution C as problem B is to problem A", which corresponds to the two above-mentioned views of analogy.

Analogy in Terms of Mappings

The classical view of analogy relies on the establishment of a parallel between two situations (or universes), which are described in terms of objects, properties of the objects, and relations linking the objects. It amounts to identifying one-to-one correspondences between objects in situation 1 and objects in situation 2, on the basis of similar properties and relations that hold both for the objects in situation 1 and for the objects in situation 2. This is the basis of approaches proposed in cognitive psychology. Usual illustrations of this view are Rutherford's analogy between the atom structure and the solar system, or the similarity between electricity and hydraulics equations.

At the forefront of the proposals coming from cognitive science in the last three decades, three leading approaches should be especially mentioned: the structure mapping theory (SMT) proposed by D. Gentner [Gentner, 1983, Gentner, 1989], the analogical constraint mapping approach proposed by K. Holyoak and P. Thagard [Holyoak andThagard, 1989, Thagard et al., 1990]), and the model of analogy making based on the idea of the parallel terraced scan developed by D. Hofstadter and M. Mitchell [START_REF] Hofstadter | The Copycat project: A model of mental fluidity and analogy-making[END_REF], Mitchell, 1993, Mitchell, 2001].

Structure mapping theory views an analogy as a mapping between a source and a target domain.

The associated structure-mapping engine (SME) [START_REF] Falkenhainer | The structuremapping engine: algorithm and examples[END_REF] returns the correspondences between the constituents of the base and target descriptions (expressed in terms of relations, properties, and functions), a set of candidate inferences about the target according to the mapping, and a structural evaluation score. Such a view is closely related to the idea of structural similarity [Syrovatka, 2000], and has been also advocated early in artificial intelligence [Winston, 1980]; see also [START_REF] Gust | Metaphors and heuristicdriven theory projection (HDTP)[END_REF] for a presentation of the HDTP model based on a second order logical modeling of SMT, and [Weitzenfeld, 1984] for a discussion about the interest of isomorphic structures when comparing situations. Besides, the view of analogy as a constraint satisfaction process, also defended in [Indurkhya, 1987, Van Dormael, 1990], is at work in the analogical constraint mapping engine (ACME) [Holyoak andThagard, 1989, Holyoak et al., 1994], which represents constraints by means of a network of supporting and competing hypotheses regarding what elements to map, and where an algorithm identifies mapping hypotheses that collectively represent the overall mapping that best fits the interacting constraints.

Roughly speaking, following [French, 2002], one may distinguish between three broad groups: i) the symbolic models that establish a structural similarity between the source and target descriptions generally expressed in formal logic terms, as SME ; ii) the connectionist models well suited for representing relational structures with nodes and links between nodes, as in ACME from using a kind of neuron networklike structure, or in LISA [START_REF] Hummel | Distributed representations of structure: a theory of analogical access and mapping[END_REF] the strong constraint of pairwise connection between objects is relaxed to partial and dynamic connections (see [French, 2002] for other references); iii) the hybrid models relying on a combination of the previous approaches. These latter models generally use constraint satisfaction networks, explore competing hypotheses and are stochastic in nature.

They rather focus on the optimization process at work to extract the most plausible solution. Moreover, this type of approach naturally embeds a graded view of similarity, while symbolic approaches have generally difficulties to handle similarity beyond mere identity. The COPYCAT project [Hofstadter andMitchell, 1995, Mitchell, 1993] is probably one of the most well-known attempt of analogy-making program falling in the hybrid category. Based on a similar paradigm, let us also mention Tabletop [French andHofstadter, 1991, French, 1995], and NARS [Wang, 2009].

In the recent years, SMT (structure-mapping theory) has proved to be effective for handling several AI problems [START_REF] Forbus | Extending SME to handle large-scale cognitive modeling[END_REF], for instance for solving IQ tests. They have dealt with the Raven Progressive Matrices test [Raven, 2000], which are non-verbal tests supposedly measuring general intelligence: A 3 × 3 Raven matrix exhibits 8 geometric pictures displayed as its 8 first cells: the remaining 9th cell is empty. In these tests, a set of 8 candidate pictures is also given among which the subject is asked to identify the solution. The approach uses a sketch understanding system named CogSketch [START_REF] Forbus | Cogsketch: Sketch understanding for cognitive science research and for education[END_REF]. It takes a sketch drawn by the user as input, which has to be segmented into objects, and generates a qualitative representation of those objects (or their edges and groups of objects), and their relations (relative position, topology, etc.). For instance, CogSketch can tell which objects are placed side by side, whether two objects intersect, or whether one is located inside another. At the end of the process, each picture is represented as an entity with attributes and relations with other entities. At this stage, we have obtained a representation of the relative position of the objects.

CogSketch uses this edge level representation (which identifies the corresponding edges in two distinct objects) to compare two objects in a sketch, with the aim of determining if there is a transformation (rotation, size modification) or even a deformation (total shape change) between these two objects. With this information, the objects with equivalent or strict shapes in common, are grouped together. At this stage, we have a representation of the modification between objects.

In order to select the correct answer for the target test, the system described in [START_REF] Lovett | A structure-mapping model of Raven's progressive matrices[END_REF] proceeds as follows:

1. The first two rows of the current matrix are evaluated via SME in order to generate some rules for both of them, which are called pattern of variance and are a representation of how the objects change across the row of images. There are four different strategies available to build up these patterns of variances. 2. SME is then used again, but now for comparing the two patterns of variance previously found for the top two rows, and obtaining a similarity score. This comparison is called second-order comparison as it operates on patterns instead of object representations. 3. This similarity score is compared to a threshold to determine its validity. 4. If the patterns of variance are considered similar enough, an analogical generalization (which is a new pattern) is built describing what is common to both rows. 5. Each one of the 8 candidate answers is scored by inserting that answer into the bottom row, computing a pattern of variance, and then using SME to compare this pattern to the generalization pattern for the top two rows. The final answer is the one with the highest score. 6. In the case where the two patterns of variance corresponding to the top rows are not similar enough, another strategy is applied.

Analogy in Terms of Proportions

The word analogy is also associated with the notion of analogical proportions, i.e., statements of the form "A is to B as C is to D". The idea of this type of statement goes back (at least) to Aristotle, and was inspired by geometric proportions ( A B = C D ) and arithmetic proportions (A -B = C -D) between numbers. As can be seen, such proportion involve four elements, considered by pairs. Here are examples of such proportions: "calf is to bull as foal is to stallion", "colibri is to birds as mouse is to mammals", "beer is to Germany as wine is to France". In the first example, the four items involved are animals, which are thus pairwise comparable using the same features. In the second example, we have still animals, but species and orders. In the last example, the four items clearly belong to two different categories: here A and C are drinks while B and D are countries. In that latter case, the 'is to' refers to some relationship(s) existing between two items belonging to two distinct categories respectively, A and B on the one hand, C and D on the other hand, and the 'as' expresses the identity of this/these relationship(s). In the first example, 'is to' may be understood as referring to a mere comparison, moreover B and C commute leading to a new acceptable proportion, which is much more debatable in the last two examples, and especially the last one. In the following, we mainly address the first kind of proportion where the four items belong to the same category. Regarding the second kind of proportion, one may mention a preliminary work that bridges formal concept analysis with analogical proportions and look for metaphors in a formal context (an example of metaphor is "Dugléré is the Mozart of (French) cooking" (in the XIX th century!), which is clearly related to the proportion "Dugléré is to (French) cooking as Mozart is to music") [START_REF] Miclet | From analogical proportions in lattices to proportional analogies in formal concepts[END_REF]. Some of the artificial intelligence studies on analogical reasoning have focused on analogical proportions. This is the case for two already mentioned works. The ANALOGY program [Evans, 1964] which was able -in an empirical way not directly applicable to other domains -to properly select a figure composed of geometrical elements, among different proposed choices, in order to give an "analogical" solution to three figures of the same nature. Some 30 years later, the COPYCAT system [START_REF] Hofstadter | The Copycat project: A model of mental fluidity and analogy-making[END_REF] was able to make a similar solving for triples of character strings to be completed by a fourth string, using a different approach based on artificial neural nets (see [French, 2002] for a detailed discussion).

An attempt to formalize analogical reasoning started from the idea that Q(t) can be inferred from (P(s), Q(s)) and P(t) (where P and Q are predicates). This can be read as the proportion "P(s) is to Q(s) as P(t) is to Q(t), and indeed the analogical jump from (P(s), Q(s)) and P(t) to Q(t) can be seen as a form of analogical proportion-based inference [Bounhas et al., 2017a]. However, the idea developed in [Davies andRussell, 1987, Russell, 1989] was to add additional information in order to make the inference pattern valid by requiring the implicit hypothesis that P determines Q inasmuch as xP(x) ∧ ¬Q(x). This may be ensured if there exists an underlying functional dependency, or more generally, if it is known for instance that when something is true for an object of a certain type, then it is true for all objects of that type. Besides, the statement "P determines Q" which can be possibly translated into ∀x(P(x) ⇒ Q(x)). If this functional dependence is considered too strong, it may be weakened, for instance into "The more similar P(s) and P(t) are, the more it is guaranteed as possible that Q(s) and Q(t) are similar" (where P and Q are now gradual predicates) [START_REF] Dubois | Fuzzy set-based methods in instance-based reasoning[END_REF]. This leads to a potential formalization of casebased reasoning. More recently, it has been presented in [START_REF] Weller | Solving proportional analogies by E-generalization[END_REF] an approach based on anti-resolution w.r.t. an equational theory for solving analogical proportions of the form "A is to B as C is to D" where D is unknown, by applying the same transformation to B as the one that enables us to go from A to C.

For about two decades, a series of European studies [START_REF] Federici | A dynamic approach to paradigm-driven analogy[END_REF], Lepage, 2001, Yvon et al., 2004[START_REF] Stroppa And Yvon ; Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF], summarized below, has aimed at developing formal models of analogical proportions and at showing their interest, in particular in computational linguistics (see [Stroppa and Yvon, 2005a], [START_REF] Lepage | A measure of the number of true analogies between chunks in japanese[END_REF] and [START_REF] Langlais | Translating unknown words by analogical learning[END_REF]). These studies start from the fact that analogical proportions obey postulates. Indeed, it has been observed for a long time that an analogical proportion "A is to B as C is to D", denoted by A : B :: C : D in the following, should satisfy the following remarkable properties: In addition, [Lepage, 2001] has contributed to a model based on set theory of proportional analogies, where A, B, C and D are considered as situations characterized by sets of binary features. This model has been somewhat simplified in [START_REF] Miclet | Handling analogical proportions in classical logic and fuzzy logics settings[END_REF] and has led to the following definition:

A : B :: C : D ⇔ A \ B = C \ D and B \ A = D \C
where \ denotes the set difference. This means that A differs from B as C differs from D and that B differs from A as D differs from C. This has a direct counterpart in a propositional logic modeling.

Proportional Analogy in Boolean Logic

When the terms of an analogical proportion take their values in {0, 1} (i.e., the focus is on whether a description feature is true or false), the proportion becomes a relation between 4 truth values, and can be expressed by the Boolean logic formula.

a : b :: c : d if and only if ((a ∧ ¬b ≡ c ∧ ¬d) ∧ (b ∧ ¬a ≡ d ∧ ¬c))
which obviously fits with the above reading in terms of difference (x ∧ ¬y is the logical difference between x and y). The 6 truth assignments of (a, b, c, d) making the proportional analogy a : b :: c : d true appear in bold font in the table below.

The truth values obey the logical expression given above [Miclet andPrade, 2009, Prade andRichard, 2013].

a 0 0 0 0 0 0 0 0 1 1 1 1 1 1 1 1 b 0 0 0 0 1 1 1 0 0 0 0 1 1 1 1 c 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1 d 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 a : b :: c : d 1 0 0 1 0 1 0 0 0 0 1 0 1 0 0 1
The Boolean analogical proportion is a particular case of so-called logical proportions that are built from similarity and dissimilarity indicators [START_REF] Prade | From analogical proportion to logical proportions[END_REF]. When comparing two Boolean variables a and b there are two similarity indicators, namely a positive one a ∧ b and a negative one ¬a ∧ ¬b, and two dissimilarity indicators ¬a ∧ b and a ∧ ¬b2 . Logical proportions connect four Boolean variables through a conjunction of two equivalences between similarity or dissimilarity indicators pertaining respectively to two pairs (a, b) and (c, d). More precisely a logical proportion is the conjunction of two equivalences between indicators for (a, b) on one side and indicators for (c, d) on the other side. In the case of analogical proportion only dissimilarity operators are used. There are 120 syntactically and semantically distinct logical proportions. All these proportions share a remarkable property: they are true for exactly 6 patterns of values of abcd among 2 4 possible values. This is only a small subset of the 16 6 = 8008 quaternary Boolean operators true for only 6 patterns. For instance, ((a ∧ ¬b) ≡ (c ∧ ¬d)) ∧ ((a ∧ b) ≡ (c ∧ d)) is a logical proportion, expressing that "a differs from b as c differs from d" and that "a is similar to b as c is similar to d", which is true for the 6 patterns 0000, 1111, 1010, 0101, 0001, and 0100. The reader is referred to [START_REF] Prade | From analogical proportion to logical proportions[END_REF] for a thorough study of the different types of logical proportions.

Among logical proportions LP(a, b, c, d) those satisfying the code independence property are of particular interest. This property expresses that there should be no distinction when encoding information positively or negatively. In other words, encoding truth (resp. falsity) with 1 or with 0 (resp. with 0 and 1) is just a matter of convention, and should not impact the final result. Thus we should have the following entailment between the two logical expressions: LP(a, b, c, d) ⇒ LP(¬a, ¬b, ¬c, ¬d). There only exist eight logical proportions that satisfy the above property [START_REF] Prade | From analogical proportion to logical proportions[END_REF]. The code independent proportions split into 4 homogeneous proportions that are symmetrical (one can exchange (a, b) with (c, d)) and 4 heterogeneous ones that are not symmetrical. Homogeneity here refers to the fact that in the expression of the proportions, both equivalences link indicators of the same kind (similarity or dissimilarity), while in the case of heterogeneous proportions they link indicators of opposite kinds. Homogeneous logical proportions include analogical proportion and two other closely related proportions:

• reverse analogy: Rev(a, b, c, d) ((¬a ∧ b) ≡ (c ∧ ¬d)) ∧ ((a ∧ ¬b) ≡ (¬c ∧ d))
It Inv is the unique logical proportion (among the 120's!) which remains unchanged under any permutation of two terms among the four [START_REF] Prade | From analogical proportion to logical proportions[END_REF]. The four heterogeneous logical proportions have a quite different semantics. They express that there is an intruder among {a, b, c, d}, which is not a, which is not b, which is not c, and which is not d respectively [Prade and Richard, 2014b]. They are at the basis of an "oddness" measure, which may be used in classification, following the straightforward idea of classifying a new item in the class where it appears to be the least at odds [START_REF] Bounhas | Oddness/evennessbased classifiers for Boolean or numerical data[END_REF].

Besides, the equation a : b :: c : x where x is the unknown may have no solution (this is the case, e.g., for 1 : 0 :: 0 : x). In the Boolean case the solution exists only if a = b or a = c. When this solution exists, it is unique and given by x = c ≡ (a ≡ b) (that is also the solution, when it exists, of Rev(a, b, c, x) and of Par(a, b, c, x). This result was first noticed in [Klein, 1982] in an empirical approach based on semiotic observations, which made no distinction between a : b :: c : d, Rev (a, b, c, d), and Par(a, b, c, d) [START_REF] Prade | From analogical proportion to logical proportions[END_REF].

Let us now consider objects described by means of a set of Boolean features (binary attributes). In this setting, logical reasoning by analogy consists in identifying the analogical proportions that hold on a subset of attributes between four objects and to infer the value of the remaining attributes, or of the class attribute for the fourth object, knowing the value for the three others. This idea has been successfully used for building the solution of Raven Progressive Matrices IQ tests, without the help of any candidate solutions [Correa Beltran et al., 2016].

In terms of machine learning (see Chapter 11 in this volume and Chapter 12 in Volume 2), the objective is to learn the value u(x) of a function u for an object x. Let us consider classification: in this framework, u(x) is the label of a class chosen in a finite set of classes. A training set S composed of examples of objects a i , for which the supervision u(a i ) is known, is available:

S = {(a 1 , u(a 1 )), . . . , (a m , u(a m ))}
The idea is to find 3 objects a, b and c of S such that a : b :: c : x.3 It must be noticed that the object x to be classified is compared to a triple of objects (a, b, c), which differs from the classification based on the k nearest neighbors for which x is compared to its neighbors taken individually. Then, the value of u on x can be computed by solving the equation u(a) : u(b) :: u(c) : u(x).

This technique is based on the hypothesis that to the analogical relation between the object descriptors corresponds an analogical relation between the values of the supervision function u. This hypothesis has been verified with success for classification rule learning with objects described by binary and nominal attributes (noting that a nominal attribute can be replaced by a set of binary attributes) on classical databases [Bayoudh et al., 2007a].

An interesting feature of such analogical classifiers is that the size of the learning set can be drastically reduced without decreasing the sucess rate on a test set. This property can be explained in the following way. Call the analogical extension AE(S) of a set S of m vectors (binary, nominal or numerical) the multiset composed of the m 3 solutions to the equations a : b :: c : x, where a, b and c are elements of S. When the vectors are numerical and the arithmetic proportion is used, AE(S) has same mean and covariance matrix as S. Analogical classification with S as a learning set is indeed very similar in that case to a k-nearest neighbours method using AE(S), but requires m istead of m 3 learning patterns. The price to pay is in classification time of a new pattern, but it can be managed with preprocessing methods of S.

Classification based on analogical proportions has also been generalized to numerical features thanks to a multiple-valued extension of the logical definition of analogical proportion [Bounhas et al., 2017a].

Recent formal studies have shown that analogical classifiers always give exact predictions in the special cases where the classification process is governed by an affine Boolean function (which includes x-or functions) and only in this case, which does not prevent to get good results in other cases (as observed in practice), but which is still to be better understood [START_REF] Couceiro | Analogypreserving functions: A way to extend Boolean samples[END_REF]. This suggests that analogical proportions enforce a form of linearity, just as numerical proportions fit with linear interpolation.

Analogical Proportions Between Sequences

In order to obtain a general notion of analogical proportion and to apply it to various spaces, Yvon and Stroppa have proposed a definition that satisfies the symmetry and exchange postulates and that is helpful to solve analogical equations [START_REF] Stroppa And Yvon ; Stroppa | Analogical learning and formal proportions: Definitions and methodological issues[END_REF]. They take lessons from geometric proportions in R, where the rule of three applies:

u v = w x ⇔ u × x = v × w.
In order to analyse the second relation, it is natural to decompose the four numbers in prime factors. For example 6 10 = 21 35 can be written 2×3 2×5 = 7×3 7×5 . In other words, we can say that the numbers u = 6, v = 10, w = 21 and x = 35 are in analogical proportion because there exist four factors

f 1 = 2, f 2 = 7, f 3 = 3 and f 4 = 5 such that u = f 1 × f 3 , v = f 1 × f 4 , w = f 2 × f 3 , x = f 2 × f 4 .
Is it possible to transfer this cross factorization in another universe? Let Σ be the set of sequences on the alphabet Σ = {a, b, c, d} with the non commutative concatenation operation (explicitely denoted by "."). For instance, let us consider the numerical analogy 18 : 63 :: 30 : 105 and an analogy on sequences, here made of French words: déridés : ridons :: démarchés : marchons. They can be factorized in the following way:

18 = 2 × 3 × 2 × 1 × 3 63 = 1 × 3 × 1 × 7 × 3 30 = 2 × 5 × 2 × 1 × 3 105 = 1 × 5 × 1 × 7 × 3 déridés = dé . rid . é . ε . s ridons = ε . rid . ε . on . s démarchés = dé . march . é . ε . s marchons = ε . march . ε . on . s
It can be noted that, in both cases, each quadruple of factors of rank i read in a column is either ( f i , f i , g i , g i ) or ( f i , g i , f i , g i ). A factor may be the neutral element of the considered universe (1 for multiplication in R and ε for concatenation in Σ ).

This idea of factorizing in elementary analogical proportions has been used by Yvon and Stroppa for defining algorithms for checking proportions and for solving analogical equation between sequences, using systems with finite states. This idea was addressed in a different way in [START_REF] Miclet | Analogical dissimilarity: Definition, algorithms and two experiments in machine learning[END_REF] where an extension of the edit distance is used that defines an analogical dissimilarity between four sequences and leads to an approximate solving of analogical equations.

Another application of analogical equation solving on sequences is the generation of plausible patterns. In this framework, the study of [START_REF] Stroppa | Du quatrième de proportion comme principe inductif : une proposition et son application à l'apprentissage de la morphologie[END_REF] was about applications to phonetics and morphology. In [START_REF] Bayoudh | Learning a classifier with very few examples: Analogy-based and knowledge-based generation of new examples for character recognition[END_REF], it has been shown how to generate plausible training examples for the recognition of handwritten characters.

Interpolative Reasoning

Case-based reasoning relates two similar problems and transfers the solution of one of them to the other one. An analogical proportion states particular similarity and dissimilarity relations between f our terms. Thus, case-based reasoning and analogical reasoning are two forms of similarity-based reasoning. But they are not the only ones. In this last section of the chapter we present a brief overview of studies based on another similarity-based reasoning: the interpolative (and extrapolative) reasoning. Interpolation allows us, when the current situation is intermediate between known situations, to conclude in an intermediate way with respect to the conclusions of these situations. When the conclusion of only one situation, close to the current situation, is known, a solution can be extrapolated for the current situation, provided that some available information about the variations around this close situation can be exploited. Therefore, interpolation and extrapolation need variables with ordered referentials and some notions of similarity. These forms of reasoning, though they are important in commonsense reasoning, have got very little attention in AI outside the community working on fuzzy sets and approximate reasoning. First, some recalls about fuzzy sets and approximate reasoning are given. Then, interpolation and extrapolation in this framework are discussed. Finally, some studies on this subject that are not based on fuzzy sets are briefly presented.

Fuzzy Sets and Approximate Reasoning

In addition to the representation of uncertainty (see Chapters 3 and 4 in this volume) and preferences (see Chapter 7 in this volume), the semantics of fuzzy sets can be based on similarity. In fact, this corresponds to the first interpretation pointed out for fuzzy sets [START_REF] Bellman | Abstraction and pattern classification[END_REF]: the higher the membership degree of an element is, the closest to the core of the fuzzy set it is (the core of a fuzzy set being the set of elements with a membership degree equal to 1) For instance, a fuzzy set A with a triangular membership degree µ A such that a is the only value verifying µ A (a) = 1 represents the set of values more or less close to a (the closeness linearly decreases when the element goes away from a if µ A is triangular). More generally, a fuzzy rule of the form "if x is A then y is B" can be intuitively understood as "if x is close to a then y is close to b" when A and B are two fuzzy sets of respective cores {a} and {b}. This idea can be extended to rules with several conditions. Deduction based on these rules can be done thanks to the approximate reasoning method that is presented now.

The principle of approximate reasoning introduced in [Zadeh, 1979] (see [Bouchon-Meunier et al., 1999] for a detailed overview) is based on a mechanism of combination / projection of the representation of the available pieces of information. These pieces of information are represented by possibility distributions from which a new possibility distribution, representing the conclusion, can be deduced. So, let X and Y be two variables having their values respectively in ref-

erentials U and V . If it is known that "X is A " and that "if X is A then Y is B", represented respectively by π X = µ A and π (X,Y ) = µ A → µ B , it can be concluded that µ B (v) = π Y (v) = sup min(π X (u), π (X,Y ) (u, v))
where A, A (resp., B, B ) are the fuzzy subsets of U (resp., V ) that restrict the more or less possible values of X and Y , and → is a logical connector that defines here a fuzzy relation on U ×V modeling the relation between X and Y expressed by the "if . . . then . . . " rule linking them. The above expression is nothing but the computation of the marginal possibility distribution of Y from the joint distribution of (X,Y ) obtained by the conjunctive combination of available pieces of information. The pattern of reasoning corresponding to the schema, from "if X is A " and "if X is A then Y is B" it entails that "Y is B ", corresponds to the idea of "generalized modus ponens"4 [Zadeh, 1979]. According to the meaning given to the rule "if . . . then . . . ", different operators can be chosen for →: they are multivalued conjunctions or implications [START_REF] Dubois | What are fuzzy rules and how to use them[END_REF] depending on the interpretation of the rule as specifying that all the elements of the (fuzzy) Cartesian product A × B are values that are all possible for (X,Y ) or, on the contrary, that the elements of A × B are impossible (where B denotes the complement of B). This type of approximate reasoning has been applied to case-based reasoning by using fuzzy rules expressing that "the more two situations are similar from some viewpoint, the more it is guaranteed possible that they are according to other viewpoints" [START_REF] Hüllermeier | Model adaptation in possibilistic instance-based reasoning[END_REF] (see subsection 4.1.3 in Chapter 3 of this volume for a brief presentation of this kind of rules "with guaranteed possibility") and they can then be related to methods of the k-nearest neighbors type.

Graduality and Interpolation

The choice of a particular implication connective, the so-called Gödel implication (s → t = t if s ≥ t and s → t = 0 if s > t) or, simply its binary restriction called Rescher-Gaines implication (s → t = 1 if s ≥ t and s → t = 0 if s > t) allows us to give a gradual semantics [START_REF] Dubois | Gradual inference rules in approximate reasoning[END_REF] to the rule under the form "the more X is A, the more Y is B", which can be also read as "the closer X is to a the closer Y is to b". This is equivalent to a set of non fuzzy rules "if X ∈ A α then Y ∈ B α for α ∈ (0, 1] that express well the fact that the closer X is to a, i.e., in a cut A α = {u ∈ U|µ A (u) ≥ α} of high degree α, the more Y is in a cut of B of high degree (the more the cut is of high degree α, the closer to a the values in the cut). It can be shown that the approximate reasoning applied to a base of gradual rules5 offering an appropriate and sufficient coverage of U allows us to model linear or non linear interpolations [START_REF] Dubois | Gradual inference rules in approximate reasoning[END_REF]. The situation where the fuzzy subsets A i correspond to the fuzzy rule base "if X is A i then Y is B i " for i = 1, n does not constitute a coverage, even in an approximate way, of U has been also studied by several authors; see [START_REF] Perfilieva | Interpolation of fuzzy data: Analytical approach and overview[END_REF] for an overview of generalized interpolation methods between "scattered" rules.

The semantics in terms of similarity of a fuzzy set is also a starting point of [Ruspini, 1991] for defining a gradual consequence relation. The initial intuition is simple: the consequence relation p q between two propositional statements p and q in classical logic corresponds to an inclusion relation [p] ⊆ [q] between their respective sets of models. The inclusion can be weakened into an approximate inclusion in two very different ways (when [p] ⊆ [q]): either it is required only that all the preferred models of p are included in [q], and this is the starting point (from a semantic viewpoint) of nonmonotonic reasoning (see Chapters 2 and 3 of this volume), or it is required only that [p] is included in the set of models of q extended to the counter-models of q that are close enough to its models. This leads to two different types of weakened consequence relations, of which the properties partly differ [START_REF] Dubois | Similarity versus preference in fuzzy set-based logics[END_REF]]. According to this last view, a logical approach to interpolation has been proposed [START_REF] Dubois | A logical approach to interpolation based on similarity relations[END_REF]. Let us finally mention the formal framework of "extensional" fuzzy sets [Klawonn, 2000] (i.e., fuzzy sets that are unions of fuzzy "clusters" of elements with respect to a fuzzy relation of similarity) that allows to formally define a partionning process of data that can afterwards be used to build fuzzy rules adapted to existing data.

Similarity-Based Qualitative Reasoning

A more qualitative approach to similarity-based reasoning, that does not require the definition of membership functions, has been more recently proposed. It consists in interpreting terms that are not a priori vague, in a flexible way. For instance, having the possibility to interpret "married" as "married or living as husband and wife" allows us to solve inconsistencies in information merging problems [START_REF] Schockaert | Solving conflicts in information merging by a flexible interpretation of atomic propositions[END_REF]. In the same spirit, it is possible to enrich sets of categorization rules using geometrical-like properties in conceptual spaces in the sense of Gärdenfors [Gärdenfors, 2000]. The properties appearing in the conditions or conclusions of these rules are treated like abstract entities. By using as primitive the relation "to be between" for these entities, it is possible to obtain schemas of interpolative reasoning that can be characterized at the same time semantically and syntactically, as well as an extrapolative reasoning scheme, based on a "parallelism" relation between pairs of concepts, staying in both cases at a symbolic level that requires only the knowledge of relations between entities [START_REF] Schockaert | Interpolative and extrapolative reasoning in propositional theories using qualitative knowledge about conceptual spaces[END_REF].

There exist other forms of qualitative reasoning (see Chapter 5 in this volume). Let us also mention, in this perspective, an approach for reasoning on relative order of magnitude, based on the principles of combination and projection of approximate reasoning (recalled in Section 4.1 above), and using a representation of proximity and of negligibility in terms of fuzzy relations [Hadj Ali et al., 2003]).

Conclusion

Human judgement and reasoning often use comparisons and rely on similarities, but also on the perception of differences. It is also at work in decision making; see [Gilboa andSchmeidler, 1995, Dubois et al., 1997a] for similarity-based approaches, not reviewed here. As surveyed this chapter, different AI approaches have tried to give substance to this idea, in particular in case-based reasoning and in analogical reasoning. In these two types of reasoning two operations of primary importance emerge: similarity-based search (e.g., for case retrieval) and adaptation. Assessing the similarity is always a delicate issue and can be considered in different ways. Even if the starting intuitions seem to be similar, the different approaches detailed here can be distinguished according to the way situations are related. The study of adaptation is not less rich and shows the importance that must be given to domain knowledge in the reasoning process. This is also an opportunity to establish a link with some aspects of knowledge discovery and, more generally with learning, which are also related to reasoning issues.

Fig. 2

 2 Fig.2The CBR cycle.

  Symmetry of the relation "as": A : B :: C : D ⇔ C : D :: A : B Exchange of the means: A : B :: C : D ⇔ A : C :: B : D Furthermore, every expression of the form A : A :: B : B or A : B :: A : B is assumed to be a (trivial) analogical proportion. Besides, the two properties of symmetry and exchange, also satisfied by mathematical proportions, are at the origin of the term "analogical proportion". In particular, it has been noticed on the basis of the two properties introduced above, that the proportion A : B :: C : D can be rewritten on the form of 8 equivalent proportions (including itself). It can be shown that the 24 possibilities of permutation of 4 objects can be partitionned in 3 equivalence classes of 8 proportions each, with an example of each class below: A : B :: C : D A : B :: D : C A : C :: D : B

  reverses analogy into "b is to a as c is to d". Indeed Rev(a, b, c, d) = b : a :: c : d). • paralogy: Par(a, b, c, d) ((a ∧ b) ≡ (c ∧ d)) ∧ ((¬a ∧ ¬b) ≡ (¬c ∧ ¬d)). It expresses that what a and b have in common (positively or negatively), c and d have it also, and conversely. It can be shown that Par(a, b, c, d)) = c : b :: a : d, which provides an expression of analogical proportion in terms of similarity indicators. Switching the positive and the negative similarity indicators pertaining to the pair (c, d) in Par(a, b, c, d), we obtain the fourth homogeneous logical proportion called inverse paralogy: Inv(a, b, c, d) ((a ∧ b) ≡ (¬c ∧ ¬d)) ∧ ((¬a ∧ ¬b) ≡ (c ∧ d)). Inv(a, b, c, d) states that "what a and b have in common, c and d do not have it and conversely". It expresses a kind of "orthogonality" between the pairs (a, b) and (c, d).

It is noteworthy that this differs from analogical proportions (presented in Section 3) for which these two ways to read the four terms of an analogy are equivalent, according to the "exchange of the means" property.

These indicators are also the building blocks of the view of similarity proposed by Tversky[Tversky, 1977].

Or to find all the triples (a, b, c) realizing that and then to make a vote, as in the k-nearest neighbor method. Empirical studies suggest that if we restrict ourselves to triples where c is a k-nearest neighbor (a, b being generally quite far) this does not really harm the results[Bounhas et al., 2017a].

Rather then seeing a fuzzy set as a set of elements close to its core value, similarity measures between fuzzy sets themselves can be defined, and then it is possible to give some meaning to the analogical proportion of the form A : A :: B : B , but B obtained this way does not have, in general, a reason to be compatible with the result of the generalized modus ponens as defined above. However, some choice of resemblance relations and of operators allows us to reconcile these two viewpoints; see for example[START_REF] Bouchon-Meunier | A fuzzy approach to analogical reasoning[END_REF].

Gradual rules have been independently considered under the name of "topoi" in[Raccah, 1996], from a cognitive perspective.