Reasoning by analogy is an important component of common sense reasoning whose formalization has undergone recent improvements with the logical and algebraic study of the analogical proportion. The starting point of this study considers analogical proportions on a formal context. We introduce analogical complexes, a companion of formal concepts formed by using analogy between four subsets of objects in place of the initial binary relation. They represent subsets of objects and attributes that share a maximal analogical relation. We show that the set of all complexes can be structured in an analogical complex lattice and give explicit formulae for the computation of their infimum and supremum.
Analogical reasoning [4] plays an important role in human reasoning. It enables us to draw plausible conclusions by exploiting parallels between situations, and as such has been studied in AI for a long time, e.g., [5, 9] under various approaches [3]. A key pattern which is associated with the idea of analogical reasoning is the notion of analogical proportion (AP), i. e. a statement between two pairs (A, B) and (C, D) of the form ‘A is to B as C is to D’ where all elements A, B, C, D are in a same category .
However, it is only in the last decade that researchers working in computational linguistics have started to study these proportions in a formal way [6, 17, 19]. More recently, analogical proportions have been shown as being of particular interest for classification tasks [10] or for solving IQ tests [2]. Moreover, in the last five years, there has been a number of works, e.g., [11, 15] studying the propositional logic modeling of analogical proportions.
In all previous cases, the ability to work on the set of all possible analogical proportions is required, either for checking missing objects or attributes or for making informed recommendations or more generally ensuring the completeness and efficiency of reasoning. In practice the analysis of objects composed of binary attributes, such as those studied by Formal Concept Analysis, is an important and easy context where AP are used. The question is whether it is possible to obtain a good representation of the space of all AP by applying the principles of FCA. A heuristic algorithm to discover such proportions by inspecting a lattice of formal concepts has been proposed in [14]. Moreover, a definition of an analogical proportion between formal concepts has been given in [13], as a particular case of proportions between elements of a lattice, studied also in [18].
In this paper, we are interested in a slightly different task involving a more integrated view of concept categorization and analogy: looking for the structure of the space of all AP. Our goal is to build an extension of formal concepts considering the presence of analogical proportions as the funding relation instead of the initial binary relation between objects and attributes. We call this extension analogical complexes, which isolate subcontexts in formal contexts with a certain structure reflecting the existence of a maximal analogical proportion between subsets of objects and subsets of attributes. 2
Definition 1 (Analogical proportion [7, 12]). An analogical proportion (AP) on a set X is a quaternary relation on X, i.e. a subset of X4 whose elements (x, y, z, t), written x : y :: z : t , which reads ’x is to y as z is to t’, must obey the following two axioms: 1. Symmetry of ’as’: x : y :: z : t ⇔ z : t :: x : y 2. Exchange of means: x : y :: z : t ⇔ x : z :: y : t In case of formal contexts, objects are described by boolean attributes. An AP (x, y, z, t) between four Boolean variables exists if the following formula is true: (x ∧ ¬y) ⇔ (z ∧ ¬t) and (y ∧ ¬x) ⇔ (t ∧ ¬z)
Basically, the formula expresses that the dissimilarity observed between x
and y is the same as the dissimilarity between z and t. An equivalent formula is
x 6= y ⇔ (x = z ∧ y = t) and x = y ⇔ z = t
It has 6 models of Boolean 4-tuples among the 16 possible ones. Note that this
includes the trivial cases where x = y = z = t. Since we are only interested in
this paper in non trivial analogical proportions, we further require that x 6= t
and y 6= z. This reduces the number of possible Boolean 4-tuples in AP to four
and it leads to the notion of analogical schema that we will use for the definition
of analogical complexes.
Definition 2 (Analogical schema). The binary matrix AS = 01 10 01 10 is
1 1 0 0
called an analogical schema. We write AS(i, j) if the value at row i and column
j of matrix AS is 1 (e.g. AS(
The analogical schema may be seen as a formal context on four objects o1, o2, o3, o4 that are in the non-trivial AP: o1 : o2 :: o3 : o4. The figure 1 shows the associated concept lattice. In this lattice, A ∧ D = B ∧ C and A ∨ D = B ∨ C. The figure also give names for each column and row profiles that we call object and attribute types: for instance the first column as type 1 and the second row as type b. 4 AB { } {a} A 3 AC { } {b} B 2 BD { } {c} C 1 CD { } {d} D
1 2 3 4 a ×× b × × c × × d ××
We use in this paper the zoo dataset proposed by R. Forsyth [8] for illustration purpose. We call smallzoo the formal context extracted from this database corresponding to attributes 2 to 9 and to the objects corresponding to the two largest classes 1 and 2. Moreover, this context has been clarified and we have chosen arbitrarily one object for each of the 10 different types of objects with different attribute profiles. The corresponding table is given below. smallzoo 2 3 4 5 6 7 8 9 18 hair feathers eggs milk airborne aquatic predator toothed type 1 aardvark 1 0 0 1 0 0 1 1 1 12 chicken 0 1 1 0 1 0 0 0 2 17 crow 0 1 1 0 1 0 1 0 2 20 dolphin 0 0 0 1 0 1 1 1 1 22 duck 0 1 1 0 1 1 0 0 2 28 fruitbat 1 0 0 1 1 0 0 1 1 42 kiwi 0 1 1 0 0 0 1 0 2 49 mink 1 0 0 1 0 1 1 1 1 59 penguin 0 1 1 0 0 1 1 0 2 64 platypus 1 0 1 1 0 1 1 0 1
The formal concept lattice is provided in figure 2, as computed by FCA
Extension [16]. It contains 31 elements. The central elements (at least two objects
and two attributes) are listed below:
c(
The 4-tuple (chicken : fruitbat :: penguin : mink) is an analogical proportion that finds a support using attributes (aquatic, hair, feathers, airborne). Each attribute reflects one of the four possible types of Boolean analogy. For instance, hair is false for chicken and penguin and true for fruitbat and mink whereas feathers is true for chicken and penguin and false for fruitbat and mink. The observed analogy can be explained thanks to this typology: the dissimilarity between chicken and fruitbat based on the opposition feather/hair is the same as the dissimilarity between penguin and mink and there are two other opposite attributes, airborne and aquatic, that explain the similarity within each ’is to’ relation. Note that the analogical schema if fully symmetric and thus one could also in principle write AP between attributes: hair:feathers::aquatic: airborne. 3
3.1
A formal concept on a context (X, Y, I) is a maximal subcontext for which relation I is valid. We define analogical complexes in the same way: they are maximal subcontexts for which the 4-tuples are in AP. This requires to split objects and attributes in four classes.
Definition 3 (Analogical complex). Given a formal context (X, Y, I), a set of objects O ⊆ X, O = O1 ∪ O2 ∪ O3 ∪ O4, a set of attributes A ⊆ Y , A = A1 ∪ A2 ∪ A3 ∪ A4, and a binary relation I, the subcontext (O, A) forms an analogical complex (O1,4, A1,4) iff 1. The binary relation is compatible with the analogical schema AS: ∀o ∈ Oi, i = 1..4, ∀a ∈ Aj , j = 1..4, I(o, a) ⇔ AS(i, j). 2. The context is maximal with respect to the first property (⊕ denotes the exclusive or and \ the set-theoretic difference): ∀o ∈ X\O, ∃j ∈ [1, 4], ∃a ∈ Aj , I(o, a) ⊕ AS(i, j). ∀a ∈ Y \A, ∃i ∈ [1, 4], ∃o ∈ Oi, I(o, a) ⊕ AS(i, j).
The first property states that the value of an attribute for an object in a complex is a function of object type and attribute type (integer from 1 to 4) given by the analogical schema. The second property states that adding an object (resp. an attribute) to the complex would discard the first property for at least one attribute (resp. object) value. Note that the ways analogical schema or analogical complex are defined are completely symmetric. Thus the role of objects and attributes may be interchanged in all properties on analogical complexes. Example 2. We extract two subcontexts from smallzoo, highlighting analogical schemas by sorting rows and columns.
These subcontexts are maximal in the sense that it is not possible to add an object or an attribute without breaking the analogical proportion. They are associated to the following analogical complexes:
({12}, {28}, {59}, {49}), ({7, 8}, {2, 5, 9}, {3, 4}, {6}) ({12, 17, 28}, {12, 17, 28}, {20, 49, 59, 64}, {20, 49, 59, 64}), ({7}, ∅, ∅, {6}) The first example provides a strong analogical relation between four animals in the context smallzoo since it uses all attributes and all the types of analogy. Attribute clusters correspond to aquatic predators, toothed animals with hair and milk, birds (feathers and eggs) and flying animals (airborne). The second example shows some of the sets in analogical complexes can be empty. In such a case some sets may be duplicated. Among all complexes, those that exhibit all types of analogy are particularly meaningful: we call them complete complexes. 3.2
Definition 4. A complex C = (O1,4, A1,4) is complete if none of its eight sets are empty.
By construction, if CA = (O1,4, A1,4) is a complete analogical complex and if A = Si=1,4 Ai, the following formula holds: ∀(o1, o2, o3, o4) ∈ O1,4, ∀(a1, a2, a3, a4) ∈ A1,4 (o1↑ ∩ o4↑) ∩ A = (o2↑ ∩ o3↑) ∩ A = ∅ and o1↑ ∪ o4↑ = o2↑ ∩ o3↑ = A
The next proposition shows that CAC exhibits strong discrimination and similarity properties among pairs of objects and attributes. The similarity condition alone would lead to the concatenation of independent (non overlapping) formal concepts. The discrimination condition tempers this tendency by requiring the simultaneous presence of opposite pairs.
Proposition 1. Let us define on a formal context F C = (X, Y, I) the relations: discrimination(oi, oj , ak, al) = I(oi, ak) ∧ I(oj , al) ∧ ¬I(oi, al) ∧ ¬I(oj , ak).
similarity(oi, oj , ak, al) = I(oi, ak) ∧ I(oj , ak) ∧ I(oi, al) ∧ I(oj , al).
A complete analogical complex (O1,4, A1,4) in F C corresponds to a maximal subcontext such that: 1. object pair discrimination (resp. similarity): ∀(oi, oj ) ∈ Oi × Oj , i 6= j, ∃(ak, al) ∈ Ak × Al such that discrimination(oi, oj , ak, al) (resp. similarity(oi, oj , ak, al)); 2. attribute pair discrimination (res. similarity): ∀(ak, al) ∈ Ak × Al, k 6= l, ∃(oi, oj ) ∈ Oi × Oj such that discrimination(oi, oj , ak, al) (resp. similarity(oi, oj , ak, al)).
Proof. Since objects and attribute have a completely symmetrical role, it is sufficient to prove the proposition for object pairs. It proceeds easily by enumerating the possible type pairs with different elements. If objects have type 1 and 2 or 3 and 4, attributes allowing object pair discrimination have type b and c and attributes allowing object pair similarity have type a and d. If objects have type 1 and 3 or 2 and 4, attributes allowing object pair discrimination have type a and d and attributes allowing object pair similarity have type b and c. If objects have type 1 and 4 and if t1 ∈ T1 = {a, b} and t2 ∈ T2 = {c, d}, attributes allowing object pair discrimination have type t1 and t2 and attributes allowing object pair similarity have different types both in T1 or both in T2. If objects have type 2 and 3 and if t1 ∈ T1 = {a, c} and t2 ∈ T2 = {b, d}, attributes allowing object pair discrimination have type t1 and t2 and attributes allowing object pair similarity have different types both in T1 or both in T2. tu
In case of incomplete complexes, some of these properties are no more relevant and a degenerate behaviour may appear: some of the sets may be identical. This fact allows to establish a new proposition on complete complexes: Proposition 2. In a complete analogical complex, side-by-side intersections of sets are empty.
Proof. This property holds since when the intersection of two object (resp. attribute) sets in an analogical complex AC is not empty, then AC contains at least two empty attribute (resp. object) sets. This fact is a consequence of property 1.
Indeed, if an object belongs to two different types, their profiles must be the same. The discrimination property ensures that the profile of two different object types differ by at least two different attribute with different types (e.g. if the object has type 1 and 3, attributes of type b and c should have different values). Thus it cannot exists attributes of the discriminant type (e.g. attributes of type b and c in the previous case) and the corresponding sets are empty. This completes the proof.
The converse of the proposition is not true: if all side-by-side intersections of sets differ, the complex is not necessary complete. For instance, consider the following context: Definition 5 (Partial Order on analogical complexes). Given two analogical complexes C1 = (O11,4, A11,4) and C2 = (O12,4, A21,4), the partial order ≤ is defined by
1 C ≤ C 2 iff
O1 i ⊆ Oi2 for i = 1, 4 and
Ai2 ⊆ Ai1 for i = 1, 4 .
C1 is called a sub-complex of C2 and C2 is called a super-complex of C1
As for formal concepts, the set of all complexes has a lattice structure. Let us first define a derivation operator on analogical quadruplets: Definition 6 (Derivation on set quadruplets).
Let O = O1 ∪ O2 ∪ O3 ∪ O4 be a set of objects partitioned in four subsets, and A be a set of attributes. For all i and j ∈ [1, 4], one defines Oi0j = {a ∈ A | ∀o ∈ Oi I(o, a) ⇔ AS(i, j)}
Let A = A1 ∪ A2 ∪ A3 ∪ A4 be a set of attributes partitioned in four subsets, and O be a set of objects. For all i and j ∈ [1, 4], one defines A0ij = {o ∈ O | ∀a ∈ Ai I(o, a) ⇔ AS(i, j)}
Finally, we define the derivation on quadruplets as follows:
4 4 4 4 O10,4 = ( \ Oj01, \ Oj02, \ Oj03, \ Oj04) j=1 j=1 j=1
j=1 4 4 4 4 A01,4 = ( \ A0j1, \ A0j2, \ A0j3, \ A0j4) Example 3. Consider O = ({12}, {28}, {59}, {49}). One has: O101 = {a ∈ A | ¬I(12, a)} = {2, 5, 7, 8, 9};
O201 = {a ∈ A | ¬I(28, a)} = {3, 4, 7, 8}; O301 = {a ∈ A | I(59, a)} = {3, 4, 7, 8};
O401 = {a ∈ A | I(49, a)} = {2, 4, 5, 7, 8} Then O10 = Tj4=1 Oj01 = {7, 8} Finally, O0 = ({7, 8}, {2, 5, 9}, {3, 4}, {6}).
We exhibit a basic theorem for these complexes that naturally extends the basic theorem on concepts: Proposition 3. Given two analogical complexes C1 = (O11,4, A11,4) and C2 = (O12,4, A21,4), – The join of C1 and C2 is defined by C1 ∧ C2 = (O1,4, A1,4) where
∀i ∈ [1, 4] Oi = Oi(C1) ∩ Oi(C2) A1,4 =
A1(C1)∪A1(C2), A2(C1)∪A2(C2), A3(C1)∪A3(C2), A4(C1)∪A4(C2) 00 – The meet of C1 and C2 is defined by C1 ∨ C2 = (O1,4, A1,4) where
O1,4 =
O1(C1)∪O1(C2), O2(C1)∪O2(C2), O3(C1)∪O3(C2), O4(C1)∪O4(C2) 00 Proof. The meet and the join are dual and one only needs to prove the proposition for the join. The ordering by set inclusion requires the set of objects Oi of C1 ∧ C2 to be included in Oi(C1) ∩ Oi(C2) and its set of attributes Aj to be included in Aj (C1) ∪ Aj C2). Taking exactly the intersection of objects thus ensures the set of objects to be maximal. The corresponding maximal sets of attributes may be inferred using the derivation operator ’ we have just defined. Another way to generate these sets is to apply the derivation operator twice on the union of sets of attributes.
Example 4. The complex lattice of smallzoo has 24 elements, including 18 complete complexes. It is sketched in figure 3.
In this lattice, for example, the join of the analogical complex numbered 9 and 12, which are as follows
9 = ({12}, {28}, {59, 64}, {20, 49}), ({7}, {9}, {4}, {6}) 12 = ({12, 17}, {28}, {59}, {49, 64}), ({7}, {2, 5}, {3}, {6}) is number 15, namely:
15 = ({12}, {28}, {59}, {49}), ({7, 8}, {2, 5, 9}, {3, 4}, {6})
The resulting object sets are for each type the intersection of the two joined
object sets. The resulting attribute sets contain for each type the union of the
two joined attribute sets and may contain other elements with a correct profile
on all objects. For instance, A1(9 ∧ 12) = {7, 8} is made of the union of A1(
The meet of the analogical complexes numbered 9 and 12 is number 19, namely 19 = ({12, 17, 28}, {12, 17, 28}, {20, 49, 59, 64}, {20, 49, 59, 64}), ({7}, ∅, ∅, {6}) 5
We have introduced a new conceptual object called analogical complex that uses a complex relation, analogical proportion, to compare objects with respect to their attribute values. Although this relation works on set quadruplets instead of simple sets like in formal concepts, we have shown that it is possible to keep the main properties of concepts, that is, maximality and comparison at the level of object or attribute pairs. The set of all complexes are structured within a lattice that contains two types of elements. The most meaningful ones only contain non empty sets and are a strong support for doing analogical inference. An interesting extension of this work would be to develop this inference process for analogical data mining in a way close to rule generation in FCA.
The degenerate case where some of the sets are empty is more frequent than in FCA where their presence is limited to the top or bottom of the lattice. The presence of a single empty set may reflect the lack of some object or attribute and is thus a possible new research direction for completing a knowledge base or an ontology. Particularly, analogy in a Boolean framework introduces a form of negation through the search of dissimilarities (discrimination) between objects.
We have written an implementation the search for complete analogical complexes, using the Answer Set Programming framework [1]. The properties of definition 3 are translated straightforwardly in logical constraints and the search of all complexes is achieved by an ASP solver looking for all solutions. The description of the ASP program would be beyond the scope of this paper but it can be seen as a relatively simple exercise of extension of the search for formal concepts by adding a few logical constraints. It is likely that most of the existing tools of FCA could be adapted the same way for analogical complex analysis. This would allow to include both categorization and analogy within common data mining environments. 1 3, 4, 6, 7 ∅ 3, 4, 6, 7 ∅ 2, 5, 8, 9 22 2, 5, 8, 9 17 13 1 6 20, 59 7 28 2 22 8 15 12 7, 8 28 2, 5, 9 59 3, 4 49 6 16
10 9 12 7 28 9 59, 64 4 20, 49 6
19 12, 17, 28 7 12, 17, 28 ∅ 20, 49, 59, 64 ∅ 20, 49, 59, 64 6 14 11 18 7 6
4 1 3, 4, 7 28 6 59 8 22 2, 5, 9 5
2