A Language of Case Di erences

Abstract

This paper contributes to a line of research that consists in applying qualitative reasoning techniques to the formalization of the case-based inference, and in particular, to its adaptation phase. The importance of capturing case di erences has long been acknowledged in adaptation research, but research is still needed to properly represent and reason upon case di erences. Assuming that case di erences can be expressed as a set of feature di erences, we show that Category Theory can be used as a mathematical framework to design a qualitative language in which both case di erences, similarity paths and adaptation rules can be represented and reasoned upon symbolically.

Keywords

• case di erences qualitative modeling similarity path adaptation

Introduction

Qualitative modeling provides formalisms that focus on how people represent themselves and reason about dynamical systems. Qualitative representations partition continuous quantities, and turn them into entities that can be reasoned upon symbolically [ 8 ]. The case-based inference aims at nding a complete description of a target problem by transferring information from a set of past problem-solving episodes, called cases, that are indexed in memory. Adaptation is the part of this process that aims at modifying a retrieved case when it can not be reused as it is in the new situation. Previous work on applying qualitative modeling techniques to adaptation includes a qualitative representation of relationships between quantities (called variations in [ 3 ]), such that co-occurrences of variations (called co-variations in [ 4 ]) can be interpreted as qualitative proportionalities. These proportionalities have been shown in [ 4 ] to play a great role in di erent commonsense inferences, and in particular, it has been suggested that adaptation was essentially an \analogical jump" performed on such proportionalities.

In existing formalizations, adaptation is recognized as being part of the casebased reasoning cycle [ 1 ], but surprisingly, the adaptation step is not included in the case-based analogical inference [ 17 ]. A study of the literature shows the adaptation step is always performed after the analogical inference (i.e., retrieval, mapping, and transfer) has taken place, and only aims at modifying its result. Copyright © 2017 for this paper by its authors. Copying permitted for private and academic purpose. In Proceedings of the ICCBR 2017 Workshops. Trondheim, Norway Some adaptation methods such as critique-based adaptation [ 11 ], or conservative adaptation [ 14 ] are used to resolve inconsistencies in the reused source case, whereas others such as di erential adaptation [ 9 ], case-based adaptation [ 6 ] or adaptation by reformulation [ 15 ] modify the reused source case in order to t the requirements on the target case. One of the reasons why adaptation is left out of the case-base inference is that adaptation essentially consists in reasoning on the di erences that exist between two cases. While the importance of capturing case di erences has long been acknowleged in adaptation research (see for example [ 13 ], for a recent review), research is still needed to properly represent and reason on case di erences.

Establishing a di erence between two states is the result of a comparison process. Comparisons are qualitative judgements that play an important role in similarity assessment and in the analogical inference. According to [ 12 ], \ a comparison assembles two elements in order to come up with a third term that will tell their relationship ". Comparison involves three ideas: the source of the comparison, the target of the comparison (what the source is compared to), and their relationship. For example, one could compare a sheep (the source) to a goat (the target), on how they forage (their relationship): a sheep would graze, whereas goats are browsers. Comparisons are usually made with respect to a particular feature (or property), shared by the objects under comparison, and which can be measured, like the size, the weight, or the type of forage [ 21 ]. Some results even suggests that people use aggregated features inferred from the features of individual objects to compare collections of objects [ 20 ].

Assuming that case di erences can be expressed as a set of di erences in feature value, we show that Category Theory can be used as a mathematical framework to design a qualitative language in which both case di erences, but also \horizontal" connections of variations (similarity paths), and \vertical" connections (adaptation rules) can be represented and reasoned upon symbolically.

The paper is organized as follows. The next section provides some preliminary de nitions. Feature comparisons are modeled in Sec. 3 as labeled arrows, and formalized in Sec. 4 as morphisms of a category. Two constructions are made on such categories: products (Sec. 5), and paths (Sec.6). In Sec.7, comparisons are ordered by generality using a subsumption relation. Finally, Sec.8 concludes the paper. 2

Preliminaries

Category theory is the mathematical study of algebras of functions [ 2 ]. A category consists of a set of objects and a set of arrows. For each arrow f , there are given objects dompf q and codpf q called the domain and the codomain of f . We write f : A B to indicate that dompf q A and codpf q B. For two arrows f and g such that codpf q dompgq, there is a given arrow g f called the composite of f and g. For each object A, there is a given arrow 1A : A A called the identity arrow of A. Arrows satisfy the associativity law : h p g f q p h gq f for all f : A B, g : B C, and h : C D. Identity arrows verify f 1A 1B f f for all f : A B. An arrow f : A B is called an isomorphism if there is an arrow g : B A such that g f 1A and f g 1B. A groupoid is a category in which every arrow is an isomorphism. The category Rel is the category where objects are sets and arrows are binary relations. The identity arrow on a set A is the identity relation: 1A tp a; aq P A A | a P Au. Given f A B and g B C, the composition g f is de ned as: pa; cq P g f i Db P B | pa; bq P f and pb; cq P g. Categories are mathematical structures which underlying structure is a quiver, i.e., a directed graph where loops and multiple arrows between two vertices are allowed, on which the de nition of a category adds constraints on identity morphisms, associativity, and composition. A path in the graph of a category is a sequence c1 c2 : : : cn of arrows of C such that for all i, doqmp ci 1 codqp ci A path category (or free category) generated by a directed graph is the category where the objects are vertices, and arrows are paths between objects. A functor F : C D between two categories C and D is a mapping of objects to objects and arrows to arrows that preserves domain and codomains, identities, and composition: F pf : A Bq F pf q : F pAq F pBq, F p1Aq 1F pAq, and F pg f q F pgq F pf q. The product C D of two categories C and D is the category of pairs and arrows. Its objects have the form pC; Dq, for C P C and D P D, and its arrows have the form pf; gq : pC; Dq p C1; D1q for f : C D P C and g : C1 D1 P D. Compositions and units are de ned componentwise, i.e., pf 1; g1q p f; gq p f 1 f ; g1 gq, and 1C D p 1C; 1Dq. 3

Modeling Feature Di erences

We are interested in modeling the comparison between two values of a same feature. In the following, the term feature denotes either a binary variable (i.e., a variable which takes one of the two values 0 or 1), or a nominal variable (i.e., a variable which takes nominal values, like the color), or a quantity (i.e., a variable which take values on ordinal, interval, or ratio scales [ 18 ]). The term feature space denotes the set of values taken by a particular feature.

A straightforward way to represent a comparison from a source A to a target B is to trace an arrow from A to B and to label this arrow with a term that represents their relationship. For example, an arrow named g b can be used to represent the relationship in which the forage di ers from g(raze) to b(rowse) from source to target (Fig. 1). The distinction between the source and the target A g b

B of a comparison makes the process by essence directional. It can be noted that this remains true even if the underlying relation is symmetrical. To illustrate this, consider the symmetrical binary relation brother, which relates two people when they are brothers. For two brothers A and B, both brotherpA; Bq and brotherpB; Aq hold (by symmetry), but A brother B and B brother A represent two di erent comparisons.

When the source and the target of the comparison are values of a same feature space, the comparison relation is transitive: if A can be compared with B and B with C, then A can be compared with C [ 5 ]. Besides, the relation is invertible, by which we mean that it is not possible to compare an object A to an object B without also being able to \reverse the viewpoint" and compare B with A with another relationship (possibly the same). For example, if a sheep A can be compared to a goat B with the relationship g b (g stands for graze, and b for browse), then an inverse relationship b g can be used to compare B to A. It can be noted that feature value comparisons constitute a special case among similarity relationships. In the general case, similarity relationships are neither transitive nor invertible. For example, if Ted went to the same school as John and John went to the same school as Mary, it does not entail that Ted went to the same school as Mary. Comparisons may also not be invertible in simili (\a tree is like a man") or metaphors (\love is a battle eld"): we might say \a man is like a tree", meaning that a man has roots, but not \a tree is like a man" [ 21 ]. 4

Formalization

Feature spaces can be formalized as categories, which we will call feature categories. The objects are the values of the feature space, and arrows represent comparisons between these values. Category Theory seems to be a natural setting to represent such comparisons, since arrows (also called morphisms) are the main \building blocks" of categories as mathematical structures. The categorical notion of composition of arrows corresponds to the transitivity of the comparison relation. Besides, each object of a category must be related to itself by an identity arrow. So representing a feature space as a category requires to distinguish identity arrows from di erence arrows. Identity arrows, like d d or , have the same object as origin and destination, and express commonalities. Di erence arrows, like d m of , have di erent origin and destination objects, and express di erences. As all arrows are invertible in a feature category, the obtained category is a groupoid.

For example, the category Bin (Fig. 2) represents the quantity space of Boolean values, by taking as objects the two Boolean values 1 (True) and 0 (False), and as arrows the possible comparisons between these values. Feature categories may also represent quantity spaces. For example, consider the category C , in which objects are elements of N, and there are three arrows , , and ¡ . The arrow is the identity arrow that links every integer x P N to itself. The arrow (resp., ¡ ) links two integers x and y whenever x y (resp., x ¡ y). Every arrow is invertible since y ¡ x holds whenever x y. The category Area (Fig. 3) represents location areas of apartments. Its objects are the three nominal values d(owntown), m(idtown), and u(uptown), and its arrows the nine possible comparisons between them. Feature categories are interpreted on a set (like a set of patients, of cooking recipes, etc.). Let X denote such a set. The semantics of a feature category C on a set X is given by a functor :I : C Rel, called the interpretation functor, which maps each object of the category C to a subset of X , and arrows to subsequent binary relations. The functor :I generalizes the notion of binary variation. The de nition of a binary variation as proposed in [ 3 ] corresponds to the indicator function of :I , when it is restricted to a given arrow of C.

If there exists a eld function ' : X C, which maps each element of X to an object of C, the interpretation functor :I can be de ned to map each object a of C to its inverse image by ' in X , i.e., to the set of elements of X which take the value a for the property ':

aI t x P X | 'pxq pa bqI aI bI

X au X for an object a of C For example, let X be a set of patients, and ' : X C be a eld function that associates to each element of X an object of the category C , representing the age of the patient. The interpretation functor :I : C Rel maps each age value n P N to the set of patients having that age, and maps each comparison to the corresponding binary relation. The binary relation qp I is the set of pairs pa; bq of patients such that b is (strictly) older than a. Likewise, let X be a set of apartments, and ' : X Area be a eld function that associates to each element of X an object of the category Area. The interpretation functor :I : Area Rel maps each nominal value to the set of apartments having the corresponding location area, and maps each comparison to the corresponding binary relation. The binary relationq p m d I is the set of pairs pa; bq of apartments such that a is located in midtown and b is located in downtown. 5

Representing Di erences on Multiple Features

The product C1 C2 : : : Cn of n comparison categories C1, C2,. . . ,Cn has as objects the n-tuples pa1; a2; : : : ; anq where ai is an object of Ci, and as arrows the n-tuples pa1 b1; a2 b2; : : : ; an bnq, where ai bi is an arrow of Ci. For example, p m d q, is an arrow in the product Area C , and could be used to represent the comparison between an apartment located in midtown and an apartment located in downtown, both having the same price.

The interpretation functor :I is extended to products in such a way that an element x P X is in the interpretation of the product if it is common to all interpretations of Ci's: pa1; a2; : : : ; anqI for n objects ai of Ci pa1 b1; a2 b2; : : : ; an bnqI biqI for n arrows ai

bi of Ci £ i £ i aiI pai 6 6.1

Similarity

Analogy as Shared Di erences

Two pairs are analogous when the same comparison can be made between them. When comparisons represent relations, this idea is consistent with the idea of analogy as a transfer of a relational structure, as outlined by Structure-mapping Theory [ 10 ]. For example, in the Andromeda galaxy, the X12 planets resolve around the X12 star, which can be represented as comparisons of the form \A:X12 planet resolve around X12 star". An analogy can be made between the Andromeda galaxy and the solar system, by mapping these comparisons with comparisons such as \A:solar system planet resolve around sun". But the idea of analogy as shared comparisons can be generalized to the comparisons made to establish feature di erences, that do not represent relations. For example, a same comparison g b can be made from a sheep to a goat and from a cow to a moose: cow graze, whereas moose browse. As a result, a cow is to a sheep what a moose is to a goat.

The same idea can be applied to logical proportions, which can be seen as shared comparisons. For two propositional variables x and y, there are four indicators: I1px; yq x ^ y, I2px; yq x ^ y, I3px; yq x ^ y, and I4px; yq x^ y, and each logical proportion is de ned by two distinct equivalences between these indicators [ 19 ]. For example, two pairs px; yq and pz; tq are in analogical proportion if I2px; yq I2pz; tq and I3px; yq I3pz; tq, i.e., if x ^ y z ^ t and x ^ y z ^ t (here, denotes the logical equivalence). Let Cx, Cy, Cz, and Ct be the feature categories constructed as in Fig. 4. The category Cx contains the x x x x x

x x x x x two objects x and x for the propositional variable x. The interpretation functor :I is de ned using the valuation function v, which is a function from the set of propositional variables to t0; 1u, seen as the class of all subsets of a one-element set (0 is the empty set and 1 is the one-element set): pa aI bqI vpaq P t0; 1u aI bI t 0; 1u t 0; 1u for an object a of Cx for an arrow a b of Cx The arrow px x; y yq of the product Cx Cy is interpreted as the binary relation px x; y yqI vpx ^ yq vpx ^ yq. Two pairs px; yq and pz; tq are in analogical proportion if the interpretation of the two arrows px x; y yq and pz z; t tq are the same, i.e., if px x; y yqI p z z; t tqI . Likewise, two pairs px; yq and pz; tq would be in paralogy if the interpretation of the arrows px x; y yq and pz z; t tq are the same. 6.2

Similarity Paths

Let C be a feature category. A similarity path of C is a combination of arrows of C. For example, d d d m is a similarity path in the category Area. The free category F pCq generated by C is the category that has the paths of C as arrows. This de nition can be extended to the product C1 C2 : : : Cn of n comparison categories C1, C2,. . . ,Cn. A path in is an arrow of the free category F p q generated by . For example, ( d d q, p d m q, is a path in the free category generated by the product Area C .

The interpretation of a similarity path on the set X is given by the interpretation functor :I which by de nition of functors, preserves composition: p c q d I pq d I pq c I . Here, the composition operation on the arrows of the category Rel is the usual composition of binary relations. This de nition can also be extended to the product C1 C2 : : : Cn of n feature categories C1, C2,. . . ,Cn: for two sets of arrows ci; di P Ci, pp c1 ; : : : ;q cpn d1 ; : : : ;qqdn

I p d1 ; : : : ;q dn I p c1 ; : : : ;q cn I For example, for an apartment srce P X located in downtown, and an apartment tgt P X located in midtown, the pair psrce; tgtq is in the interpretation of the similarity path p d d q; p d m q; if there is an apartment pb such that srce p d d q; I pb p d m q; I tgt, that is, such that the location of pb is downtown and its price is strictly greater than the price of srce, and equal to the price of tgt. This de nition is consistent with the notion of similarity path, which is de ned in [ 16 ] as a sequence of relations srce pb0 r1 pb1 r2 pb2 : : : pbq 1 rq pbq tgt such that the pbi's are problems and ri's are binary relations between problems. 7 7.1

Ordering Di erences

A Subsumption Relation

A subsumption operator enables to order comparisons by generality. Let C1 and C2 be two feature categories. For an arrow c1 of C1, and an arrow c2 of C2, we write c1 c2 to represent that whenever an A can be compared to B using the comparison c1 , then A can be compared to B using comparison c2 . For example, in Area C , the subsumption relation d m represents the fact that any apartment located in downtown is more expensive than any apartment located in midtown. The subsumption operator can also relate the arrows of two product categories C C1 C2 : : : Ck and D D1 D2 : : : D`. For example, if C C Area represents comparisons between the number of rooms and the location of apartments, and D C represents comparisons in price, then p q ; m d represents the fact that for a same number of rooms, an apartment located in downtown is more expensive than an apartment located in midtown.

Subsumption relations c1 c2 are interpreted as set inclusions in X X :

This de nition extends naturally to product categories:

p c1 ; : : : ;q ck p d1 ; : : : ;q d` if p c1 ; : : : ;q ck I p d1 ; : : : ;q d` I A subsumption relation corresponds to the notion of co-variation, that is dened in [ 4 ] as a functional dependency between variations, and may be used to represent adaptation rules. 7.2

Analogical Jump

An analogical "jump" consists in making the hypothesis that a subsumption relation on comparisons holds for a given pair of objects. From a logical point of view, an analogical jump is de ned in [ 7 ] as the following hypothetical rule of inference: if P pxq

P pyq and Qpxq, then we can infer Qpyq

For example, Bob's car and John's car share the property P of being a 1982 Mustang GLX V6 hatchbacks, and Bob's car has the property Q of having a price of 3500 $. The inference is that the price of John's car should also be around 3500 $. This schema can be rephrased using comparisons: from x P

y, infer x Q y In this schema, P and Q are two comparisons representing respectively that an element shares the property P with another element, and that it shares the property Q. This inference consists in making the hypothesis that the subsumption relation P Q on comparisons holds for the pair px; yq. Such inference can also be made when the comparisons represent di erences. For example, if

C C Area represents comparisons between the number of rooms and the location of apartments, and D C represents comparisons in price, then the subsumption relation p q ; m d can be applied to a pair px; yq of apartments to infer that an apartment y located in downtown is more expensive than an apartment x with the same number of rooms, but located in midtown. 8

Conclusion

Category Theory seems to be a natural setting to represent the feature comparisons made when establishing case di erences. We showed that it can be used to and to design a qualitative language in which both case di erences, similarity paths and adaptation rules can be represented and reasoned upon symbolically. We believe that such results open the way to new qualitative formalizations of the case-based inference, that would be able to integrate both retrieval and adaptation in a same analogical process.

References

1. Aamodt , A. , Plaza , E. : Case-based Reasoning: Foundational Issues, Methodological Variations, and System Approaches . AI Commun . 7 , 39 { 59 ( 1994 )

2. Adowey , S. : Category Theory . Oxford University Press ( 2010 )

3. Badra , F. : Representing and Learning Variations . In: Int. Conf. Tools Artif. Intell . pp. 950 { 957 . IEEE, Vietri sul Mare ( 2015 )

4. Badra , F. : Reasoning with Co-variations . In: AIMSA. Varna, Bulgaria ( 2016 )

5. Brown , R., Porter , T. : Category Theory: an abstract setting for analogy and comparison . In: What is Categ. Theory? Adv. Stud. Math. Log. , pp. 257 |- 274 . Polimetrica ( 2006 )

6. Craw , S. , Wiratunga , N. , Rowe , R.C. : Learning adaptation knowledge to improve case-based reasoning . Artif. Intell . 170 ( 16 - 17 ), 1175 {1192 (nov 2006 )

7. Davis , T.R. , Russell , S.J.: A Logical Approach to Reasoning by Analogy . In: IJCAI Int. Jt. Conf. Artif. Intell . ( 1987 )

8. Forbus , K.D.: Qualitative modeling . Wiley Interdiscip. Rev. Cogn. Sci. 2 ( 4 ), 374 { 391 ( 2011 )

9. Fuchs , B. , Lieber , J. , Mille , A. , Napoli , A. : Di erential adaptation: An operational approach to adaptation for solving numerical problems with CBR . KnowledgeBased Syst . 68 , 103 {114 (apr 2014 )

10. Gentner , D. : Structure-Mapping : A Theoretical Framework for Analogy . Cogn. Sci. 7 ( 2 ), 155 { 170 ( 1983 )

11. Hammond , K.J.: CHEF: A Model of Case-based Planning . In: AAAI Proc . pp. 267 { 271 ( 1986 )

12. Hoquet , T. : La liaison comme comparaison : sciences de rapports et logique de la relation . Asterion ( 2014 ), http://asterion.revues. org/2515

13. Jalali , V. , Leake , D. , Forouzandehmehr , N.: Ensemble of Adaptations for Classi - cation: Learning Adaptation Rules for Categorical Features , pp. 186 { 202 . Springer International Publishing, Cham ( 2016 )

14. Lieber , J.: Application of the Revision Theory to Adaptation in Case-Based Reasoning: The Conservative Adaptation . In: ICCBR Proc . ( 2007 )

15. Lieber , J. , Napoli , A. : Correct and Complete Retrieval for Case-Based ProblemSolving . In: ECAI. pp. 68 { 72 ( 1998 )

16. Melis , E. , Lieber , J. , Napoli , A. : Reformulation in case-based reasoning , pp. 172 { 183 . Springer Berlin Heidelberg, Berlin, Heidelberg ( 1998 )

17. Ontan~on, S. , Plaza , E.: On Knowledge Transfer in Case-Based Inference . In: D azAgudo, B. , Watson , I. (eds.) ICCBR Proc . pp. 312 { 326 . Springer-Verlag Berlin Heidelberg ( 2012 )

18. Paritosh , P.K. : Back of the Envelope Reasoning for Robust Quantitative Problem Solving Field of Computer Science . Tech. rep. , Electrical Engineering and Computer Science Department, Northwestern University ( 2007 )

19. Prade , H., Richard, G.: From analogical proportion to logical proportions: A survey . Stud. Comput. Intell . 548 , 217 { 244 ( 2014 )

20. Scontras , G. , Gra , P. , Goodman , N.D. : Comparing pluralities . Cognition 123 ( 1 ), 190 { 197 ( 2012 )

21. Tversky , A. : Features of Similarity . In: Readings Cogn. Sci. A Perspect. from Psychol . Artif. Intell., pp. 290 { 302 . Elsevier Inc. (oct 2013 )