Categorization and analogical reasoning are two important cognitive processes, for which there exist formal counterparts (at least they may be regarded as such): namely, formal concept analysis on the one hand, and analogical proportions (modeled in propositional logic) on the other hand. This is a rst attempt aiming at relating these two settings. The paper presents an algorithm that takes advantage of the lattice structure of the set of formal concepts for searching for analogical proportions that may hold in a formal context. Moreover, properties linking analogical proportions and formal concepts are laid bare.
Categorization and analogical reasoning play important roles in cognitive processes. They both heavily rely on the ideas of similarity and dissimilarity. Items belonging to the same category should be similar, while they are dissimilar with respect to items belonging to other categories. Analogical proportions, which are statements of the form `a is to b as c is to d', express the similarity of the relations linking a and b with the relations linking c and d (note that however a and b may be somewhat dissimilar (as well as c and d). In a Boolean setting, where items are described in terms of binary attributes, similarity amounts to the identity of properties, while dissimilarity refers to the presence of properties for an item which are absent in the other considered item.
Among formal approaches aiming at categorizing items, Formal Concept
Analysis (FCA) provides a way for characterizing concepts both extensionally in
terms of the objects that they cover and intensionally in terms of the properties
that these objects share. FCA is known as a lattice-theoretic framework devised
for knowledge extraction from Boolean data tables called formal contexts that
relate objects and properties. Introduced under this name by Wille [
Besides, there has been a renewal of interest for analogical proportions in the
last decade, rstly in relation with computational linguistic concerns. Set-based,
algebraic and logical models have been proposed [
The paper is organized as follows. We rst provide a short background on analogical proportions in Section 2. Then in Section 3, after a brief reminder of basic de nitions in FCA, we present an e cient algorithm able to discover analogical proportions in a formal context by using the lattice of formal concepts. In Section 4, we further investigate the theoretical relations between FCA and analogical proportions, by showing how formal concepts are involved in analogical proportions, before indicating lines for further research and concluding. 2
An analogical proportion `a is to b as c is to d', usually denoted a : b :: c : d,
expresses that the way a and b di er is the same as the way c and ddi er [
and D, all subsets of some set X. The dissimilarity between A and B is evaluated
by A \ B and by A \ B, where A denotes the complement of A in X, while the
similarity corresponds to A \ B and A \ B. Viewing an analogical proportion as
expressing that the di erences between A and B and between C and D are the
same, we get the following de nition [
immediate logical counterpart when a, b, c, and d now denote Boolean variables: ((a ^ :b) (c ^ :d)) ^ ((:a ^ b) (:c ^ d)) This formula is true for the 6 truth value assignments of a; b; c; d appearing in Table 1, and is false for the 24 6 = 10 remaining possible assignments.
It can be checked that the above de nitions of an analogical proportion
satis es the following characteristic postulates [
(or items) a; b; c; d are described by sets of binary properties belonging to a set P rop. Then, each item can be viewed as a subset of P rop, made of the attributes that hold true on this item3. Then, we can apply De nition 1, namely a \ b = c \ d and a \ b = c \ d. Another way of seeing this analogical proportion is given by the equivalent de nition: De nition 2 Four objects (a; b; c; d) de ned by binary properties are in analogical proportion i the truth-values of each property on these objects make a 4-tuple of binary values corresponding to one of the six 4-tuples displayed in Table 1. Analogical dissimilarity We now introduce the concept of analogical dissimilarity (AD) between four objects de ned by binary attributes. It is simply the sum on all the attributes of the analogical dissimilarity per attribute. The latter is de ned according to the following table: a b c d
AD = 0 1 1 0 1 0 2 1 1 2 0 1 0 1 1 0
Searching for analogical proportions in formal concepts This section is devoted to the following problem: given a formal context with n objects and d properties (or attributes), is it possible to discover 4-tuples of objects in analogical proportion, without running an O(n4 d) algorithm? We give in this section an heuristic algorithm which uses the lattice of formal concepts, and has shown experimentally its e ciency for discovering analogical proportions. We start with a brief reminder on FCA. 3For an object x, this subset is called R"(x) in Formal Concept Analysis, see Sect. 3.1. 3.1
FCA starts with a binary relation R, called formal context, de ned between a set Obj of objects and a set P rop of Boolean properties. The notation (x; y) 2 R means that object x has property y. R"(x) = fy 2 P ropj(x; y) 2 Rg is the set of properties of object x. Similarly, R#(y) = fx 2 Objj(x; y) 2 Rg is the set of objects having property y.
Given a set Y of properties, one can de ne the set of objects [
This is the set of objects sharing all properties in Y (and having maybe some others). Then a formal concept is de ned as a pair made of its extension X and its intension Y such that
R#(Y ) = X and R"(X) = Y; where (X; Y ) Obj P rop, and R"(X) is similarly de ned as fy 2 P ropjR#(y) Xg. It can be also shown that formal concepts are maximal pairs (X; Y ) (in the sense of inclusion) such that X Y R.
Moreover, the set of all formal concepts is equipped with a partial order (denoted ) de ned as: (X1; Y1) (X2; Y2) i X1 X2 (or, equivalently, Y2 Y1), and forms a complete lattice, called the concept lattice of R.
Let us consider an example where R is a relation that de nes links
between eight objects Obj = f1; 2; 3; 4; 5; 6; 7; 8g and nine properties P rop =
fa; b; c; d; e; f; g; h; ig. There is a \ " in the cell corresponding to an object x
and to a property y if the object x has property y, in other words the \ "s
describe the relation R (or context). An empty cell corresponds to the fact that
(x; y) 62 R, i.e., it is known that object x has not property y. The relation R
in the example is given in Figure 1. There are 5 formal concepts. For instance,
consider X = fa; b; c; d; eg. Then R" (X) = f7; 8g ; likewise if Y = f7; 8g. Then
R# (Y ) = fa; b; c; d; eg.
The basic idea of our algorithm is to start from some 4-tuple of objects, to
observe the attributes that contribute to make AD non-zero for this 4-tuple,
and to replace one of the four objects by another object. Then we iterate the
process. Two important features have been added to avoid a random walk in the
space of the 4-tuples.
1. The replacement of one object by another is done according to the
observation of the lattice of concepts. The idea is to try to decrease the value of
AD. This point will be explained in the next section.
2. All 4-tuples of objects that are created are stored in a list, ordered by
increasing value of AD. The next 4-tuple to be chosen is the rst in the list.
This algorithm can therefore be seen as an optimization procedure, more
precisely as a best- rst version of the GRAPHSEARCH algorithm ([
Let us come now to the heart of the algorithm, namely the replacement of one object by another. Can we nd some information in the lattice that leads us to choose both an object in the 4-tuple and another object to replace it ? Remember that we are looking for a replacement that makes the AD decrease.
Now, let us consider the following situation, taken from BASE lm (see Figure 2). Suppose that we are studying the 4-tuple of objects (3; 4; 9; 12), with AD = 1. Attribute c is the only one to contribute in the AD of this 4-tuple. Actually, c has the values (1; 1; 0; 1) on the 4-tuple (3; 4; 9; 12). We notice now that there are two interesting concepts in the lattice with respect to c, the rst one being (fb; c; h; g; ag ; f3g) and the second being (fb; h; g; ag ; f2; 3g), which are directly connected. What can we deduce from this pair of connected concepts ? { Attribute c has value 1 on object 3. { Attribute c has value 0 on object 2. { Attribute c is the only attribute to switch from 1 to 0 to transform concept (fb; c; h; g; ag ; f3g) into concept (fb; h; g; ag ; f2; 3g).
We can conclude from this evidence that replacing object 3 by object 2 will decrease by 1 the value of AD, since c will take values (0; 1; 0; 1) on the 4-tuple (2; 4; 9; 12), and therefore that (2; 4; 9; 12) is an analogical proportion.
Unfortunately this argument does not lead to a greedy algorithm, since there no insurance, given a 4-tuple, that there exists a couple of concepts having the three above properties. Most of the time, actually, there is more than one attribute switching to 1 between two connected concepts, and only one insuring the decreasing of AD.
Let us take another example from the same data base. The 4-tuple (5; 4; 9; 12) has a AD of 4, because of the attributes d, f , g and h. Two interesting connected concepts are (fc; f; d; e; i; ag ; f12g) and (fc; d; e; ag ; f7; 12g), since f switching from 1 to 0 will decrease the AD (see the table below). But replacing 12 by 7 in the 4-tuple (5; 4; 9; 12) will switch not only f but also the attribute i, and we don't know what will happen when switching i: it may decrease as well as increase the AD. Actually, in this case, it increases the AD. Hence, the 4-tuple (5; 4; 9; 7) has the same AD of 4.
Heuristic h-Doap. Let a couple of connected concepts be (A [ B; Z) and (B; Z [ Y ), A and B being subsets of attributes and Y and Z being subsets of objects such that A \ B = ; and Y \ Z = ;. If there is a 4-tuple with one of its four objects in Z and if there is an attribute in B that decreases the AD of this 4-tuple when switching from 1 to 0, then create a new 4-tuple by replacing the object in Z by an object in Y . Next section shows how this heuristic can be used to discover 4-tuples of objects with null AD in a formal context, i.e. analogical proportions of objects. 3.4
Discovering one analogical proportion. We explain in this section the algorithm used to discover one analogical proportion in a formal context. We call it `Discover One Analogical Proportion', in short Doap. As already stated, it is a simple version of Graphsearch, where the nodes to be explored are 4-tuples of objects. We denote Start the 4-tuple of objects chosen to begin, Open the current set of 4-tuples to be processed and Closed the set of 4-tuples already processed.
The choice of Start is either done randomly or by selecting objects which appear in small subsets of objects in the lattice. We also require that the explored 4-tuples are composed of four di erent objects, since we do not want to converge towards 4-tuples trivially in proportion, such as (1; 3; 1; 3) or even (2; 2; 2; 2).
The algorithm stops either by discovering an analogical proportion, or in failure. One has to notice that its failure does not insure that there is no analogical proportion, since there is no guarantee given by the heuristic. We have never met this failure case, but our experiments are very limited, as explained in section 3.5. Discovering several analogical proportions. To discover more analogical proportions, the simplest manner is to imbed algorithm Doap in a procedure that discards the rst two objects of a discovered analogical 4-tuple from the formal context before re-running the algorithm. Since the transitivity holds for analogical proportions on objects (u : v :: w : x and w : x :: y : z implies u : v :: y : z), we are loosing no information on analogical 4-tuples. However, we are not insured to nd all proportions in that manner, due to the fact that algorithm Doap may not nd an existing proportion. 3.5
The size of Close when the algorithm Doap stops is a precise indication of its practical time complexity. Notice that a random algorithm, running on n objects (without any construction of a formal lattice), in which there are q 4-tuples in analogical proportion would in average try ((n4)=8 q) 4-tuples before discovering a proportion. In the previous formula, the number \8" comes from the fact that, when there is one analogical proportion in a formal context, then there are in fact exactly 8 through suitable permutations. This property stems directly from the postulates an analogical proportion (see section 2).
We have used two di erent formal contexts to run the algorithm Doap. The
rst one is described in [
leech 1
bream 2
frog 3
dog 4
spike-weed 5
reed 6
bean 7
maize 8
x 9
y 10
z 11
t 12
Fig. 2. BASElm: A formal context from Belohlavek [
The lattice constructed on this formal context (with the In-Close free
software [
To appreciate these results, we have compared with a random search, replacing line 13 of the Doap algorithm by picking a random 4-tuple. The detailed results are given in Figure 4. The average size of the Closed list is 253 and its median size is 174.
We also have tried to \symmetrize" the role of 0 and 1 in this formal context by adding the reverse attributes (indeed the Table 1 de ning analogical proportions is left unchanged when exchanging 0 and 1). It leads to 12 objects and 18 4 We actually had a good surprise: Doap found a third proportion, namely (2; 4; 9; 12). Fig. 4. Results of 630 runs of random Doap on BASElm. The Y axis is graduated from 0 up to 2000. attributes instead of 9. The size of the lattice of concepts is now 94. The algorithm Doap with the same parameters examines in average 93 4-tuples before nding an analogical proportion. The median value is 31. The symmetrization does not seem to be a good idea in this case. The random Doap algorithm has failed to give complete results on these data, due to over ows in the Close list.
The second experiment has been run on the Lenses data base, from UCI ML
Repository [
A rst conclusion is that our heuristic algorithm seems to perform well. In the second context the basic search space has a size over 40.000 and we examine only 77 4-tuples in average. The construction of the lattice of concepts takes in practice much more time than the discovery of analogical proportions, which seems to suggest that it is a relevant space for looking for analogical proportions. 4
Analogical proportions between formal concepts We have seen that discovering analogical proportions in a formal context bene ts from the knowledge of the associated lattice of formal concepts. Then it raises the question of understanding how formal concepts are involved in analogical proportions. Clearly, four objects in the same formal concept form an analogical proportion { in a trivial way { w.r.t. the subset of attributes involved in the formal concept. Partial answers to the question, when two formal concepts are involved in the proportion, are given in this section. 4.1
We are interested in this section in examining the properties of the smallest context with an analogical proportion between objects. Obviously, this context will have exactly four objects. If we want to have, only one time, each of the possible analogical proportions between attributes, we need six of them (see table 1) and we obtain BASE 0 (see Figure 5).
u v w x u v w x w x a u c d v x b v b d
We can construct now the concept lattice of BASE 0, but it is interesting to get rid of attributes f (which will not be present in any context) and e (present in every context). We call BASE 1 the reduced context, shown at Figure 5.
Its lattice is displayed in Figure 5. Note that there is a perfect symmetry between attributes and objects. The third line of the lattice expresses that u : v :: w : x, but also in subsets terms that fc; dg : fb; dg :: fa; cg : fa; bg. The second line expresses that a : b :: c : d and that fw; xg : fv; xg :: fu; wg : fu; vg. This is not surprising: as explained in section 2, we can see an object as the set of properties that hold true for it.
Firstly, let us remark that the two following propositions are equivalent. This is immediate from section 2, in which these two equivalent de nitions of analogical proportion have been presented. 1. x1, x2, x3 and x4 are four objects, in analogical proportion in this order. 2. R"(x1), R"(x2), R"(x3) and R"(x4) are four subsets of properties in analogical proportion in this order.
Property 1 Let x1, x2, x3 and x4 be four objects in analogical proportion in this order. Let (X1; Y1) be the5 concept with the smallest set X1 of objects in which x1 is present. Let us de ne (X2; Y2), (X3; Y3) and (X4; Y4) in the same way. Then the four sets of attributes Y1, Y2, Y3 and Y4 are in analogical proportion, in this order.
Proof. Since x1 2 X1, all the attributes in Y1 take value 1 on x1. Since X1 is the smallest set of objects including x1, there is no attribute outside Y1 having 5 If they were two, x1 would be present in the intersection of the two. value 1 on x1. Hence, Y1 is exactly R"(x1), the extension of x1, i.e. the subset of attributes that take value 1 on x1. This is also true for x2, x3 and x4. We have to prove now that x1 : x2 :: x3 : x4 implies R"(x1) : R"(x2) :: R"(x3) : R"(x4). It is immediate from the remark above.
For example, in BASE 0, we know that 1 : 8 :: 11 : 12. We have X1 = f1; 2; 3; 11g, Y1 = fa; b; gg, X2 = f6; 8; 12g, Y2 = fa; c; d; f g, X3 = f11g, Y3 = fa; b; e; g; ig and X4 = f12g, Y4 = fa; c; d; e; f; ig. The proportion Y1:Y2::Y3:Y4 holds, since: fa; b; gg:fa; c; d; f g::fa; b; e; g; ig:fa; c; d; e; f; ig.
Property 2 Let (X1; Y1), (X2; Y2), (X3; Y3) and (X4; Y4) be four concepts of a lattice of concepts, such that the four sets of attributes Y1, Y2, Y3 and Y4 are in analogical proportion, in this order. Let Xb1 be the subset of X1 composed of all objects that are in X1 but cannot be found in any subset of X1 belonging to a concept. We de ne in the same manner Xb2, Xb3 and Xb4. The following property holds true: 8x1 2 Xb1; x2 2 Xb2; x3 2 Xb3; x4 2 Xb4 : x1 x2 :: x3 : x4.
Proof. It is the reciprocal of Property 1: Y1 is the extension of all objects in Xb1, and we take x1 in Xb1. We derive the conclusion from the remark above. Property 3 Let x1, x2, x3 and x4 be four objects, in analogical proportion in this order.
Let A1111 = fyjy 2 R"(x1); y 2 R"(x2); y 2 R"(x3); y 2 R"(x4))g Let A1100 = f j
y y 2 R"(x1); y 2 R"(x2); y 62 R"(x3); y 62 R"(x4))g Let A0011 = fyjy 62 R"(x1); y 62 R"(x2); y 2 R"(x3); y 2 R"(x4))g Let A1010 = f j
y y 2 R"(x1); y 62 R"(x2); y 2 R"(x3); y 62 R"(x4))g Let A0101 = fyjy 62 R"(x1); y 2 R"(x2); y 62 R"(x3); y 2 R"(x4))g Then (fx1; x2g; A1111 [ A1100) is included into a formal concept. (fx3; x4g; A1111 [ A0011) is included into a formal concept. (fx1; x3g; A1111 [ A1010) is included into a formal concept.
(fx2; x4g; A1111 [ A0101) is included into a formal concept.
The result follows from the de nition of the subsets of attributes considered and their clear relation with the de nition of analogical proportions. The fact that we only have an inclusion in the above property should not come as a surprise. Indeed, when describing objects, attributes that are nor not relevant w.r.t. the analogical proportion may be present. 5
Lines for further research and concluding remarks
Beyond the already introduced set function, R#(Y ) = fx 2 ObjjR"(x) Y g,
which is at the core of FCA,and which leads to the de nition of formal concepts,
it has been noticed [
Y g = \y62Y R#(y). This is the set of objects { R# (Y ) = R#(Y ) = \y2Y R#(y). This is the set of objects sharing all properties in Y . { R#r(Y ) = fx 2 ObjjR"(x) [ Y 6= Objg = [y62Y R#(y). This is the set of objects that are missing at least one property outside Y .
It has been recently pointed out [
When comparing the features underlying FCA and analogical proportions,
one can notice that the same 4 \indicators" are involved from the beginning: a\b,
a \ b, a \ b, and a \ b. Indeed R# (Y ) is based on the condition R"(x) \ Y 6= ;,
R#N (Y ) on the condition R"(x)\Y = ;, R# (Y ) on the condition R"(x)\Y = ;,
and R#r(Y ) on the condition R"(x) \ Y 6= ;. Moreover, with these 4 indicators,
one can de ne other so-called logical proportions [
Finally, the experiments with Doap have obviously to be scaled on larger formal contexts, in order to estimate its practical complexity more accurately. Some more thought has also to be given about the choice of the Start 4-tuples, especially to take advantage of the addition of the reverse attributes. An interesting point would be to be able to choose the Start in order to insure that every analogical proportion can be discovered. We also believe that the speed of Doap can be increased, since there are still a lot of parameters to tune, for example breaking ties in the head of the Close list in a non random fashion.
An interesting question is whether or not the construction of the lattice must precede the heuristic search. It would certainly be of great interest to construct only the parts that are required by the running od the Doap algorithm. This would lead to merge the two parts of the method, rather than computing the whole lattice (a very costly operation) before its exploration.
More generally, it would be clearly of interest to have an algorithm also able
to nd out the analogical proportions that hold in some sub-context (since as
already said, irrelevant attributes may hide interesting analogical proportions),
rather than in the initial formal context. This will open a machine learning point
of view [
We would like to thank the anonymous reviewers for their careful reading of this article and their interesting suggestions.