Analogy Between Concepts (Extended Abstract)

1 Introduction

Analogical reasoning has raised the interest of psychologists and computer scientists for a long time; see, e.g., [Dedre Gentner and Kokinov, 2001; Prade and Richard, 2014]. We focus here on analogical proportions which are statements of the form "x is to y as z is to t", expressing an analogical parallel between pairs (x, y) and (z, t). A statement such as "Carlsen is to chess as Mozart is to music" introduces Carlsen as a precocious virtuoso of chess, a quality that Mozart is well known to have concerning music. It relates two types of items, here people and activities. It is an example of what we call relational proportions which are statements of the form "object A has the same relationship with attribute a as object B with attribute b". This can be viewed as a special case of analogical proportions. In case where x, y, z, t are items which can be represented in terms of the same set of features, a formal definition has been proposed for analogical proportions in the setting of Boolean logic and then extended using multiple-valued logic for handling numerical features [Miclet and Prade, 2009; Prade and Richard, 2013; Dubois et al., 2016], by stating that "x differs from y as z differs from t and y differs from x as t differs from z". The nature of Relational Proportions (RP for short) suggests to handle them in the setting of formal concept analysis. This leads us to the question of defining analogical proportions between formal concepts. For more details and proofs, the reader is referred to [Barbot et al., 2019].

∗This paper is an extended abstract of [Barbot et al., 2019] published in Artificial Intelligence.

†Contact Author

2 Analogical Proportions: Basics

Analogical proportions [Dorolle, 1949; Hesse, 1959] are usually characterized by three axioms. They acknowledge the interchangeability of pairs (x, y) and (z, t) in the proportion "x is to y as z is to t", and enforce the idea that y and z can be interchanged if the proportion is valid, just as in the equality of two numerical ratios where means can be exchanged.

Definition 1 (Axioms of Analogical Proportion). An analogical proportion (AP) on a set X is a quaternary relation on X, i.e., a subset of X4 . An element of this subset, written (x : y :: z : t), which reads "x is to y as z is to t", must obey the following axioms (studied in [Lepage, 2003]):

1. Reflexivity of 'as': (x : y :: x : y)
2. Symmetry of 'as': (x : y :: z : t) ⇔ (z : t :: x : y)
3. Exchange of means: (x : y :: z : t) ⇔ (x : z :: y : t)

Then, thanks to (2) and (3), it can be easily seen that (x : y :: z : t) ⇔ (t : y :: z : x) should also hold (exchange of the extremes). According to the first two axioms, four other formulations are equivalent to the canonical form (x : y :: z : t). Finally, the eight equivalent forms of an analogical proportion are: (x : y :: z : t), (z : t :: x : y), (y : x :: t : z), (t : z :: y : x), (z : x :: t : y), (t : y :: z : x), (x : z :: y : t) and (y : t :: x : z). A fourth (optional) axiom, called determinism, insists on the uniqueness of the solution t = y of the equation in t: (x : y :: x : t).

With respect to this axiomatic definition of AP, Stroppa and Yvon [2006] have given another definition, based on the notion of factorization when the set of objects is a commutative semigroup. From these previous works, Miclet et al. [Miclet et al., 2014] have derived the following definitions in the lattice framework.

Definition 2. A 4-tuple (x, y, z, t) of a lattice (L, ∨, ∧,≤)4 is a Factorial Analogical Proportion (FAP) (x : y :: z : t) iff

x = (x ∧ y) ∨ (x ∧ z) x = (x ∨ y) ∧ (x ∨ z) y = (x ∧ y) ∨ (y ∧ t) y = (x ∨ y) ∧ (y ∨ t) z = (z ∧ t) ∨ (x ∧ z) z = (z ∨ t) ∧ (x ∨ z) t = (z ∧ t) ∨ (y ∧ t) t = (z ∨ t) ∧ (y ∨ t)

Definition 3. A 4-tuple (x, y, z, t) of (L, ∨, ∧, ≤)4 is a Weak Analogical Proportion (WAP) when x∧t = y ∧z and x∨t = y ∨ z. It is denoted x : y WAP :: z : t.

In the case of a distributive lattice (e.g., a Boolean lattice), this alternative definition is equivalent to the FAP. But, in general, a FAP is a WAP and the converse is false, which explains the use of adjective "weak" [Miclet et al., 2014].

Example 1. Let Σ be a finite set associated with the Boolean lattice (2Σ, ∪, ∩, ¬,⊆). When saying that "x is to y as z is to t" where x, y, z, t ⊆ Σ, we express that x differs from y in the same way as z differs from t. For example, if x = {a, b, e} and y = {b, c, e}, we see that to transform x into y, we have to remove a and add c. Now, if z = {a, d, e}, we can construct t with the same operations, to get t = {c, d, e}. More formally, with this view, we should have x \ y = z \ t and y \ x = t \ z (with x \ y = x ∩ ¬y). This is equivalent to x ∩ t = y ∩ z and x ∪ t = y ∪ z. This relation linking x, y, z, t is clearly symmetrical, and satisfies the exchange of the means. Hence it is a correct definition of the AP in the Boolean setting [Miclet and Prade, 2009].

We give here a simple example of FAP in a lattice.

Proposition 1. Let y and z be two elements of a lattice, the proportion y : y ∨ z :: y ∧ z : z is a FAP. We call it a Canonical Analogical Proportion (CAP).

3 Analogical Proportions in FCA

In order to derive more specifically the AP notion in a Formal Concept Analysis (FCA) framework, we first recall some basic elements of FCA, before studying the relations between several kinds of AP and their characterization in FCA.

FCA starts with a binary relation R defined between a set O of objects and a set A of attributes (or properties). The tuple (O,A,R) is called a formal context. The notation (o, a) ∈ R or oRa means that object o has attribute a. We denote o↑ = {a ∈ A | (o, a) ∈ R} the attribute set of object o and a↓ = {o ∈ O | (o, a) ∈ R} the object set having attribute a. Similarly, for any subset o of objects, o↑ is defined as {a ∈ A | a↓ ⊇ o}. Then a formal concept is defined as a pair (o, a), such that a↓ = o and o↑ = a. One calls o the extension of the concept and a its intension.

The set of all formal concepts is equipped with a partial order (denoted ≤) defined as: (o1, a1) ≤ (o2, a2) iff o1 ⊆ o2 (or, equivalently, a2 ⊆ a1). Then it is structured as a lattice, called the concept lattice of R.

Example 2. The concept lattice of context R displayed in Figure 1 is shown in Figure 2.

Since a concept x is associated to a set of objects ox and a set of attributes ax, the objective of this section is to relate the AP definitions with these sets, and to study the links between APs in a concept lattice and APs on object or attribute sets.

Proposition 3. Let x, y, z and t be 4 concepts, if (ax : ay :: az : at or ox : oy :: oz : ot) then x : y WAP :: z : t.

Comments. The converse is false. Let us consider the formal context R in Fig. 2. We have x : y WAP :: z : t due to Proposition 2. However, the Boolean APs ax : ay :: az : at and ox : oy :: oz : ot are both false. The WAP between concepts is less restrictive than the AP between sets of attributes: in a WAP, objects are allowed to possess attributes which are not shared by any other object concerned in the WAP. In this lattice, x, y, z and t are in WAP, but ax : ay :: az : at and ox : oy :: oz : ot are both false. Besides, x′ , y′ , z′ and t′ are in WAP and ox′ : oy′ :: oz′ : ot′ is true, but ax′ : ay′ :: az′ : at′ and the FAP x′ : y′ :: z′ : t′ are both false.

We give now a proposition which leads us to a corollary in which is defined yet another analogical proportion between formal concepts, the strongest of all.

Proposition 4. Let x, y, z and t be 4 concepts, if (ax ∪ at = ay ∪az and ox ∪ot = oy ∪oz) then the FAP x : y :: z : t holds.

Corollary 1. Let x, y, z and t be 4 concepts, the following 2 conjunctions are equivalent:

This characterizes a particular case of FAP between concepts that we call a Strong Analogical Proportion (SAP). It is denoted x : y SAP :: z : t.

Comments. From Corollary 1, ax : ay :: az : at and ox : oy :: oz : ot imply the FAP x : y :: z : t. However, the reciprocal is false. Let us consider the concept lattice displayed in Figure 2: we have the FAP y : ⊤ :: ⊥ : z (which is a CAP), but oy ∪ oz ̸= o⊤ ∪ o⊥ and ay ∪ az ̸= a⊤ ∪ a⊥.

4 Formal Concepts and Relational Proportion

4.1 From a RP to Concepts in AP

We study here if we can deduce from a relational proportion "A is the B of a", or "A is to a as B is to b", formal concepts in WAP and an analogical complex from this knowledge.

As an example, we have found in a web magazine the following proportion "Massimiliano Alajmo is the Mozart of Italian cooking". The background knowledge allowing to understand this relational proportion is the following: music and Italian cooking are disciplines practiced by humans, such disciplines can be practiced with different levels of ability, Mozart is a musician and Mozart is a genius in music discipline. Since the quality "to be a genius" is not possessed by everybody, there must exist many "ordinary gifted" musicians. Then, the background knowledge can be expressed by the formal context on the left side of Figure 3. where o1 stands for Mozart, o2 for one of "ordinary gifted" musicians, a1 is the attribute "practices music", a2 "is a genius" and a3 "has an ordinary ability".

Now, when the new data "Alajmo is the Mozart of Italian cooking" is introduced, the knowledge extends as follows: Alajmo practices Italian cooking, and he has something in common with Mozart that is not Italian cooking. The relational proportion is a reduced form of "Alajmo is to Italian cooking as Mozart is to music". Since Mozart has only the other attribute "Genius", Alajmo must have it. Moreover, since cooking is a discipline practiced by humans, there must exist some ordinary gifted Italian cook. At last, we must introduce the notion of non-genius in our universe. If we do not, we implicitly suppose that everybody is a genius for some activity. The knowledge is now expressed by the formal context on the right side of Figure 3 where o3 stands for Alajmo, o4 an ordinary gifted Italian cook and a4 Italian cooking. This context is called the analogical context. Considering the associated concept lattice, the closest analogical proportion to "Alajmo is the Mozart of Italian cooking" is ({o3}, {a2, a4}) : ({o4}, {a3, a4}) WAP :: ({o1}, {a1, a2}) : ({o2}, {a1, a3}) which translates into "Mozart is to some ordinary musician as Alajmo is to some ordinary cook".

More formally, from the relational proportion "o1 is the o2 of a", we can derive an analogical context as above. It is composed of objects o1 and o2, described by four attributes: a is possessed by o1 and not by o2, ˜a is possessed by o2 and not by o1, b is possessed both by o1 and o2 and ˜b is some attribute not possessed by o1 nor o2. Secondly we complete the context with two objects o3 and o4 that are the complements of o2 and o1 with respect to the four attributes. The result is the analogical context where a1 = b, a2 = a, a3 = ˜a and a4 = ˜b.

4.2 Analogical Complex

In the previous subsection, it turns out that the analogical context is an interesting pattern, from which we can construct relational proportions. A more general definition of this pattern, named analogical complex, has been given in [Miclet and Nicolas, 2015]. We present it here through an example.

Let us consider the context in Fig. 4, called SmallZoo, extracted from the Zoo data base [Lichman, 2013]. The context of Fig. 5 is a subcontext of SmallZoo with special characteristics described in Fig. 6. Any subcontext with such characteristics is called 'analogical complex'. In the left part of Fig. 6, a '×' between a subset of objects (say, o1) and a subset of attributes (say, a4) means that every object of o1 is in relation with every attribute of a4, and a 'blank' between a subset of objects (say, o1) and a subset of attributes (say, a1) means that no object of o1 is in relation with no attribute of a1. In practice, the right table is sufficient to define an analogical complex, since the left one is the same for all of them. Thus, an analogical complex is defined by the 8 sets o1, ..., o4, a1, ..., a4, and it is said to be complete when none of these sets are empty. From the analogical complex structure, we derive a formal definition of a relational proportion.

Definition 4. Let (o1,4, a1,4) be a complete analogical complex in a formal context, the following sets are said to be in the formal relational proportion (RP) (o1 is to a3 as o2 is to a2), and we write (o1 � a3 �� o2 � a2).

Comments. The reduced form of the RP would be (o1 is the o2 of a3). Besides, from the same complex, we can extract the RPs (o1 � a4 �� o3 � a1 ), (o2 � a4 �� o4 � a1 ) and (o3 � a3 �� o4 � a2 ). Since the operator �� is commutative, it gives a total of 8, but permuting the extremes and the means in a RP may lead to awkward phrasings.

Example 3. The complex described in Fig. 6 implies all attributes but a6 (predator) and objects o1 and o2 (chicken and crow), o5 (fruitbat), o8 (penguin) and o7 (mink). From this context, the RP in reduced form "a fruitbat is the mink of airborne animals" can be derived for instance, meaning that fruitbat and mink have hair, are toothed and produce milk, but that the mink is aquatic at the contrary of the fruitbat. Of course, the interest of such phrases has to be taken in context: the SmallZoo data base is supposed to be the only knowledge.

4.3 WAP and Analogical Complex

We explore now the links between WAP between concepts and complete analogical complex, and then the formal RPs.

First, we are interested in defining non degenerated WAPs, called complete and bi-complete, forbidding inclusion between two of its concepts. It is a key notion for building WAP between concepts with a sound cognitive interpretation.

Definition 5. Let us consider (x : y WAP :: z : t), this WAP is complete through attributes when (ax ∩ ay) \ a∩, (ax ∩ az) \ a∩, (ay ∩ at) \ a∩ and (az ∩ at) \ a∩ are nonempty where a∩ = ax ∩ ay ∩ az ∩ at. A WAP complete through objects is similarly defined using subsets of objects.

A WAP is bi-complete when

• if it is complete through attributes and ((x ∨ y) : (x ∨ z) WAP :: (y ∨ t) : (z ∨ t)) is complete through objects.
• or if it is complete through objects and ((x ∧ y) : (x ∧ z) WAP :: (y ∧ t) : (z ∧ t)) is complete through attributes.

In order to derive RPs from an AP between concepts, we consider a complete WAP through attributes (a similar reasoning can be done from a complete WAP through objects) and introduce a process to extract an analogical complex.

Due to the completeness, sets a1 = (az ∩ at) \ a∩, a2 = (ay∩at)\a∩, a3 = (ax∩az)\a∩ and a4 = (ax∩ay)\a∩ are nonempty. We also define o1 = ˜ ox the set of objects proper to x (that appear in ox but not in the objects of y, z and t) and similarly o2 = ˜ oy, o3 = ˜ oz and o4 = ˜ ot .

By construction, every o ∈ o1 is in relation with every a ∈ a3 ∪ a4. It is also the case between o2 and a2 ∪ a4, o3 and a1 ∪ a3, o4 and a1 ∪ a2. For all the other combinations, for instance o1 and a1, for any o ∈ o1, there exists a ∈ a1 such that o /∈ a↓ . However, these properties do not guarantee that the subcontext (o1,4, a1,4) is an analogical schema, even if it is a closed schema: it can exist an object o ∈ oi in relation with an attribute a ∈ aj, where (i, j) ∈ {(1, 1), (1, 2), (2, 1), (2, 3), (3, 2), (3, 4), (4, 3), (4, 4)}. In such a case, either a or o is removed and this postprocessing permits to obtain an analogical schema. But this schema is not necessarily a complex, since the associated subcontext may be not maximal. Then a second postprocessing maximises the schema into complex, adding new attributes and/or objects chosen among those which do not appear in ax ∪ . . . ∪ at nor ox ∪ . . . ∪ ot.

This method may lead to several complexes, according to the choices in both postprocessings. This set of complexes is a sub-lattice of the lattice of complexes and in case of a bicomplete WAP as input, one of the output lattices is entirely made of complete analogical complexes [Barbot et al., 2019].

Example 4. In SmallZoo, x = ({o1, o2, o4}, {a1, a2, a4}), y = ({o5}, {a0, a3, a4, a7}), z = ({o4, o8}, {a1, a2, a5}), t = ({o7, o9}, {a0, a3, a5, a6}) are concepts in complete WAP through attributes. At the beginning, o1 = {o1, o2}, o2 = {o5}, o3 = {o8}, o4 = {o7, o9}, a1 = {a5}, a2 = {a0, a3}, a3 = {a1, a2}, a4 = {a4}. Due to the relation between o9 and a2, the first postprocessing applied on the subcontext shown in Fig. 7 can remove (either o9 or) a2. After removing a2, the table in Fig. 8 is an analogical schema and we can check that it is maximal in SmallZoo. Note that if we had chosen to remove o9, the postprocessings would have produced the analogical complex detailed in Fig. 5.

For example, from the complete analogical complex described above, we can derive the following RP: "the chicken and the crow are to the feathers as the fruitbat is to the hair, the milk and the teeth". It makes sense when considering that all these animals share the attribute "airborne".

5 Conclusion

We have shown how relational proportions can be identified in a formal context. Relational proportions offer a basis for concise forms of explanations. Indeed, if B has some wellknown features, the proportion "object A is to attribute a as object B is to attribute b" provides an argument for stating that "object A is the B of a", when A possesses these well-known features also, as in "Carlsen is the Mozart of chess". It is worth pointing out that two cognitive capabilities, namely conceptual categorization and analogical reasoning can be handled together in the setting of formal concept analysis. This short presentation has left aside the algorithmic side (based on the identification of formal complexes), which is discussed in the long version of [Barbot et al., 2019].

Acknowledgements

The authors acknowledge a partial support of ANR-11LABX-0040-CIMI (project ISIPA).