We apply recent results on the construction of suitable orderings for the existence of right adjoint to the analysis of the following problem: given a preference ordering on the set of attributes of a given context, we seek an induced preference among the objects which is compatible with the information provided by the context. ? Partially supported by Spanish Ministry of Science and FEDER funds through projects TIN2011-28084 and TIN12-39353-C04-01. ?? Partially supported by ESF Fund CZ.1.07/2.3.00/30.0041.
The mathematical study of preferences started almost one century ago with the works of Frisch, who was the rst to write down in 1926 a mathematical model about preference relations. On the other hand, the study of adjoints was initiated in the mid of past century, with works by Ore in 1944 (in the framework of lattices and Galois connections) and Kan in 1958 (in the framework of category theory and adjunctions). The most recent of the three theories considered in this work is that of Formal Concept Analysis (FCA), which was initiated in the early 1980s by Ganter and Wille, as a kind of applied lattice theory.
Nowadays FCA has become an important research topic in which a, still growing, pure mathematical machinery has expanded to cover a big range of applications. A number of results are published yearly on very diverse topics such as data mining, semantic web, chemistry, biology or even linguistics.
The rst basic notion of FCA is that of a formal context, which can be seen as a triple consisting of an initial set of formal objects B, a set of formal attributes A, and an incidence relation I B A indicating which object has which attribute. Every context induces a lattice of formal concepts, which are pairs of subsets of objects and attributes, respectively called extent and intent, where the extent of a concept contains all the objects shared by the attributes from its intent and vice versa.
Given a preference ordering among the attributes of a context, our contribution in this work focuses on obtaining an induced ordering on the set of objects which, in some sense, is compatible with the context.
After browsing the literature, we have found just a few papers dealing simultaneously with FCA and preferences, but their focus and scope are substantially di erent to ours. For instance, Obiedkov [11] considered some types of preference grounded on preference logics, proposed their interpretation in terms of formal concept analysis, and provided inference systems for them, studying as well their relation to implications. Later, in [12], he presented a context-based semantics for parameterized ceteris paribus preferences over subsets of attributes (preferences which are only required to hold when the alternatives being compared agree on a speci ed subset of attributes).
Other approaches to preference handling are related to the development of recommender systems. For instance, [8] proposes a novel recommendation model based on the synergistic use of knowledge from a repository which includes the users behavior and items properties. The candidate recommendation set is constructed by using FCA and extended inference rules.
Finally, another set of references deal with extensions of FCA, either to the
fuzzy or multi-adjoint case, or to the rough case. For instance, in [
Glodeanu has recently proposed in [6] a new method for modelling users'
preferences on attributes that contain more than one trait. The modelling of
preferences is done within the framework of Formal Fuzzy Concept Analysis,
speci cally using hedges to decrease the size of the resulting concept lattice as
presented in [
An alternative generalization which, among other features, allows for specifying preferences in an easy way, is that of multi-adjoint FCA [9,10]. The main idea underlying this approach is to allow to use several adjoint pairs in the de nition of the fuzzy concept-forming operators. Should one be interested in certain subset(s) of attributes (or objects), the only required setting is to declare a speci c adjoint pair to be used in the computation with values within each subset of preferred items.
The combination of the two last approaches, namely, fuzzy FCA with hedges and the multi-adjoint approach have been recently studied in [7], providing new means to decrease the size of the resulting concept lattices.
This work can be seen as a position paper towards the combination of recent results on the existence of right adjoint for a mapping f : hX; X i ! Y from a partially ordered set X to an unstructured set Y , with Formal Concept Analysis, and with the generation of preference orderings.
The structure of this work is the following: in Section 2, the preliminary results related to attribute preferences and the characterization of existence of right adjoint to a mapping from a poset to an unstructured codomain are presented; then, in Section 3 the two approaches above are merged together in order to produce a method to induce an ordering among the objects in terms of a given preference ordering on attributes and a formal context. 2 2.1
We recall the de nition of a (total) preference ordering and describe an induced ordering on the corresponding powerset.
In the general approach to preferences, a preference relation on a nonempty set A is said to be a binary relation A A which is re exive (8a 2 A; a a) and total (8a; b 2 A; (a b) _ (b a)).
In this paper, we will consider a simpler notion, in which a preference relation is modeled by a total ordering. Formally, by a total preference relation we understand any total ordering of the set A, i.e., a binary relation A A such that is total, re exive, antisymmetric (8a; b 2 A; a b and b a implies a = b), and transitive (8a; b; c 2 A; a b and b c implies a c).
Any total preference relation on a set A induces a total ordering on the powerset 2A in a natural way.
De nition 1. Let hA; i be a nonempty set with a total preference relation. A subset X is said to be lectically smaller than a subset Y , denoted X <lec Y , if max (X r Y ) [ (Y r X) 2 Y: If X <lec Y or X = Y we will write X lec Y .
It is not di cult to show that the set 2A with the lectic order forms a totally ordered set. 2.2
We assume basic knowledge of the properties and constructions related to partially ordered sets.
As we are including the necessary de nitions for the development of the construction of adjunctions, we state below the notion of adjunction we will be working with.
De nition 2. Let A = hA; Ai and B = hB; Bi be posets, f : A ! B and g : B ! A be two mappings. The pair (f; g) is said to be an adjunction between A and B, denoted by (f; g) : A B, whenever for all a 2 A and b 2 B we have f (a)
B b The mapping f is called left adjoint and g is called right adjoint.
Given a mapping from a poset hA; Ai to an unstructured set B, the necessary and su cient conditions for f to have a right adjoint were given in [5]; the idea was to build it gradually, in terms of the canonical decomposition of f : A ! B through Af , the quotient set3 of A wrt the kernel relation f , de ned as a f b if and only if f (a) = f (b):
A Af f '
B
i f (A) where mapping is the canonical projection onto the quotient set Af , de ned by (a) = [a]f , ' is the canonical isomorphism of the quotient and the image, de ned by '([a]f ) = f (a), and i is the inclusion of the image into the codomain.
The obtained characterization is recalled in the theorem below.
Theorem 1. Given a poset A = hA; Ai and a mapping f : A ! B, let f be the kernel relation. Then, there exists a poset structure on B, say B = hB; Bi, and a mapping g : B ! A such that (f; g) : A B if and only if 1. There exists max([a]f ) for all a 2 A. 2. For all a1; a2 2 A, a1 A a2 implies max([a1]f ) A max([a2]f ).
If the conditions hold, a suitable ordering on the image of f (that can also be extended to B) can be de ned as follows: b1 B b2 if and only if there exist a1 2 f 1(b1); a2 2 f 1(b2)
such that max([a1]f ) A max([a2]f ):
It is worth to notice that the theorem above can be easily adapted to characterize existence of Galois connections.
Given the results introduced in the previous section, here we will merge them so that, given a preference relation on the set of attributes A, an induced ordering is obtained on the set of objects B.
In order to simplify the presentation and minimize technicalities, we will consider a crisp context C = (B; A; I) and a total preference ordering on the set of attributes, say hA; i. 3 The equivalence class of a under the kernel relation f will be denoted as [a]f .
The general idea can be depicted as the diagram below hA; i
g h2A; leci f
B o 2B each of the three stages is explained as follows: 1. To begin with, the preference on attributes allows for generating4 the corresponding lectic order on h2A; leci. 2. On this lattice, the usual concept-forming operator f can be de ned, see [4], from h2A; leci to the (unstructured) powerset of objects of B. Namely, given A 2 2A we de ne
f (A) = fb 2 B j (b; a) 2 I for all a 2 Ag: Now, under suitable conditions as stated in [5], there exists an ordering on 2B such that a right adjoint for f exists. 3. Finally, this ordering is projected down to B to obtain an induced ordering among all the objects.
Summarizing, given a preference ordering of the set of attributes hA; i and a context, an induced ordering on the set of objects B is obtained, which is compatible with the context.
It is worth to note that, by considering the inclusion ordering on 2A, the inclusion ordering on 2B and the (other) standard concept-forming operator forms a Galois connection, hence the inverse inclusion ordering leads to an adjunction. This means that the proposed approach, in a certain sense, generalizes the standard concept-forming approach.
To begin with, Theorem 1 characterizes when an ordering can be induced in the codomain B so that a right adjoint to a given mapping f : hA; Ai ! B exists. It is not di cult to nd examples in which that situation does not hold. Example 1. Consider the context C = (fo1; o2; o3g; fa1; a2g; I), where the incidence relation I is de ned as in the left of Figure 1. In addition, consider that attribute a1 is more preferred than a2 (which we denote a1 a2).
For this context it is clear that Property 2 of Theorem 1 does not hold in general. Speci cally, if we consider (singleton) sets A1 = fa1g and A2 = fa2g, then we have A2 lec A1 but, clearly, max[A2]f 6 lec max[A1]f , i.e. A020 6 lec A010, since A020 = fa1; a2g, whereas A010 = fa1g.5 4 Hence the g, but notice that this is just a notation, not an actual mapping from A to 2A. 5 See Section 3.1.
Example 2. Consider an alternative incidence relation de ned as in the right of Figure 1. Again, consider that attribute a1 is more preferred than a2.
For this alternative context, the previous problem does not arise, since A020 = fa2g and A010 = fa1g. Therefore, an ordering on 2B can be given which, when projected on the set of objects B, leads to o1 o2 o3.
The obtained result is compatible with the information given by the incidence relation, in that o3 has more preferred attributes than o2 and so on. Anyway, the existence of situations in which it is not possible to induce an ordering on B leads to the more general problem of studying conditions on the context which guarantee its existence.
To begin with, property 1 automatically holds in our approach; the details are given below. 3.1
Property 1, i.e. max([A]f ) exists for all A, always holds in this framework due to the particular de nition of f as the standard concept-forming operator.
In e ect, given A 2 2A, the equivalence class [A]f consists of sets of attributes whose image coincides with that of A, this is independent from the particular ordering chosen in 2A.
We know that, under the inclusion ordering, the closure of A, denoted A00, is the maximum of [A]f : i.e. Ai A00 for all Ai 2 [A]f . Furthermore, as the inclusion ordering implies lectic ordering we have that Ai lec A00 for all Ai 2 [A]f , which states that A00 is also the maximum of [A]f in the chain h2A; leci. 3.2
As shown in the previous examples, property 2 does not always hold.
A rst naive step would be simply checking Property 2 in all the pairs of subsets A1 lec A2. Fortunately, not all of them have to be checked since the lectic ordering contains the inclusion ordering and, for this ordering the property holds (this is just a consequence of the fact that the usual concept-forming operators form a Galois connection), but there are other possibilities to be taken into account, which are pairs of sets of attributes satisfying A1 lec A2 but A1 6 A2.
Speci cally, in order to study the complexity of checking property 2 (by brute force) we have rstly to solve the following
Problem: Given an ordered set A = fa1; : : : ; ang with n elements, we want to count the pairs of subsets A1 and A2 such that A1 is lectically less than A2 wrt the ordering given by the subscripts of the elements in A, but is NOT included in it. because those are the cases in which the property is not known to hold and, hence, are called problematic pairs.
For the computation, we will interpret a subset as a chain [d1; : : : ; dn] of n digits, indicating membership or not to the subset.
The key idea for counting the number of problematic pairs is related to two important places in the chain, for which we introduce a special notation: 1. Digit d` represents the rst attribute a` which is in A2 but not in A1 (the ` should recall the rst `ectic discrepancy). 2. Digit di represents the rst attribute ai which is in A1 but not in A2, that is, the rst discrepancy wrt the i nclusion ordering.
It is obvious that, in any given pair of subsets, d` is more preferred, i.e. occurs before, than di.
Now, we can state that every attribute more preferred than ai, except a`, either belongs to both sets or does not belong to any of them; so in every such position only two possibilities arise (either two 1s or two 0s), this means that a factor 2 is associated to any such digit. In addition, there is no restriction for attributes less preferred than ai, that is, in every such position four possibilities can occur, and this means that a factor 4 is associated to any such digit.
In order to see the general pattern of possible cases, let us consider a set with four attributes, so n = 4. There are three possible positions for di, namely, second, third and fourth, which are handled separately. i-discrepancy in 4th digit In this case, d` can be in any of the three rst places, and the remaining two positions should have coincident values. Then, there are 3 22 possibilities. i-discrepancy in 3th digit Now, there are only two possible positions for d`, and the remaining one should have coincident values (so two possibilities). In the last digit there is no restriction (4 possibilities). All in all, there are 2 21 4 cases. i-discrepancy in 2nd digit Then d` should be the rst one. There are two digits with no restriction, so 42 cases.
Summarizing, we have 3 22 40 + 3 21 41 + 1 20 42 possibilities.
The previous example shows a clear pattern by which the number of problematic cases for n attributes is given by the following expression (n 1) 2n 2 40 + (n 2) 2n 3 41 +
+ 2 21 4n 3 + 1 20 4n 2 n 1 or, in compressed form as X(n k=1
k)2n+k 3.
This sum can be expressed in closed form as follows n 1 X(n k=1
n 1 k)2n+k 3 = 2n 3 X(n
k)2k
cient conditions on the context We have just seen that checking Property 2 by brute force on every problematic pair has exponential complexity on the size of the set of attributes, therefore we introduce in this section some possible ways to establish su cient conditions on the context so that the proposed approach can be applied to de ne an induced ordering on the set of objects.
To begin with, the following result states a partial su cient condition. Proposition 1. Consider a context such that the following conditions hold for all pair of attributes satisfying b a (a is more preferred than b): 1. There exists an object in which b holds but a does not. 2. Whenever b implies6 a less preferred attribute, say c, then a implies c as well.
Then property 2 holds for all the singleton sets of attributes.
Proof. Consider ak aj , and the singletons Ak = fakg and Aj = faj g. It is clear that Ak lec Aj , therefore we have to show that A0k0 lec A0j0.
By contradiction, assume that A0k0 6 lec A00. This means that the most prej ferred discrepant attribute between both closures, say ad, is in A0k0 and not in A0j0, i.e. ad 2 A0k0 r A00.
j
We will reason by cases, according to the relative position of ak and ad wrt the preference ordering. 6 As the usual implication of attributes. { It cannot occur that attribute ad is more preferred than ak, since in that case ad should hold in every object satisfying ak, since ad 2 A0k0rA0j0, contradicting the rst hypothesis. { Furthermore, it cannot be the case that ad ak either. We have once again that ad (now less preferred than ak) holds in very object satisfying ak. Now, the second hypothesis states that ad is also implied by aj and, that is ad 2 A00 j which contradicts that ad 2 A0k0 r A00.
j { Finally, the case ad = ak means that aj is not a discrepant attribute; now, as it is the case that aj 2 A0j0, it should happen that aj 2 A0k0 and, hence, ak should imply aj , violating hypothesis 1. tu
Obviously, this proposition alone does not imply the ful llment of property 2, but gives a clue of a general su cient condition, albeit too strong, which is stated below: Proposition 2. Consider a context with a preference ordering such that, for all subset of attributes A, satisfying the following properties: 1. There exists an object failing to satisfy the most preferred attribute in A, but satisfying all the other attributes. 2. Whenever A implies an attribute, say ad, then any other subset of attributes, more preferred in the lectic order, implies ad as well.
Then property 2 holds.
It is worth to introduce some comments on the conditions used in the previous proposition.
To begin with, the rst condition makes sense: as we wish to establish an ordering on the objects, according to a prescribed order of preference among the attributes and information in the context, the not-so-trivial cases are precisely those containing objects failing to satisfy most preferred attributes, but satisfying several less preferred ones. Otherwise, the user should not need any formal tool to choose according to his/her preferences.
Speci cally, consider a context containing lines as in Figure 2, again assuming a1 more preferred than a2 more preferred than a3. In such a case, it might not be clear whether to choose car 1 because it satis es the most preferred attribute (being cheap, but without safety measures like ABS or airbag, and without the comfort of an air-conditioned system) or car 2, which is not cheap but includes safety and comfort measures.
The second hypothesis is reasonable as well, since it somehow implies the coherence of the preference ordering between attributes. It is worth to remark that it is not just a technical requirement which can be avoided by considering contexts without any implied attributes because in practical situations it can make sense to admit certain implications. For instance, back to the previous example of cars and its attributes, it might be convenient consider simultaneously the attributes Automatic Climate Control (ACC) and Air Conditioned (A/C) since, although ACC always implies A/C, it could be the case that a user would be satis ed just with a basic A/C system.
In this paper, we have sketched a method for inducing an ordering in the set of objects from a preference ordering in the set of attributes which is based on the machinery of FCA and recent results concerning the existence of right adjoints to a given mapping. Some su cient conditions have been given in order to guarantee that the proposed framework can be applied to a given context.
The problem has been stated in its simplest version, with a speci cation of preferences as a total ordering, and considering a crisp context. We have just started to scratch the surface of the problem and, to be honest, there is much more work to be done than contributed results to the topic presented in this paper.
We enumerate below a number of possible alternatives to be developed in the short and mid term: 1. Obtain weaker su cient conditions for property 2 to hold and, if possible, characterize those contexts for which property 2 automatically holds. For this characterisation it seems crucial to obtain information about the greatest discrepant attribute of two given closed sets of attributes. 2. Consider general preference relations (re exive and total) or even other approaches to the notion of preference, see [3]. 3. Consider preference relations which allow to assign weights to each attribute, so that the comparison between objects satisfying di erent sets of attributes can be made more in consonance with the user. 4. The previous item naturally leads to the consideration of one-sided concept lattices, in which it is possible to specify that objects satisfy attributes only to a certain degree.
. . . 3. P. Fishburn. Preference structures and their numerical representations. Theoretical
Computer Science, 217:359{383, 1999. 4. B. Ganter and R. Wille. Formal Concept Analysis: Mathematical Foundation.
Springer Verlag, 1999. 5. F. Garc a-Pardo, I. Cabrera, P. Cordero, M. Ojeda-Aciego, and F. Rodr guez. On the de nition of suitable orderings to generate adjunctions over an unstructured codomain. Information Sciences, 286:173{187, 2014. 6. C. V. Glodeanu. Exploring users' preferences in a fuzzy setting. Electronic Notes in Theoretical Computer Science, 303:37{57, 2014. Proceedings of the Workshop on Algebra, Coalgebra and Topology (WACT 2013). 7. J. Konecny, J. Medina, and M. Ojeda-Aciego. Multi-adjoint concept lattices with heterogeneous conjunctors and hedges. Annals of Mathematics and Arti cial Intelligence, 2014. Accepted. http://dx.doi.org/10.1007/s10472-014-9405-y. 8. X. Li and T. Murata. A knowledge-based recommendation model utilizing formal concept analysis and association. In 2nd Intl Conf on Computer and Automation Engineering (ICCAE), pages 221{226, 2010. 9. J. Medina and M. Ojeda-Aciego. Multi-adjoint t-concept lattices. Information
Sciences, 180(5):712{725, 2010. 10. J. Medina, M. Ojeda-Aciego, and J. Ruiz-Calvin~o. Formal concept analysis via multi-adjoint concept lattices. Fuzzy Sets and Systems, 160(2):130{144, 2009. 11. S. Obiedkov. Modeling preferences over attribute sets in formal concept analysis.
In F. Domenach, D. Ignatov, and J. Poelmans, editors, Formal Concept Analysis, volume 7278 of Lecture Notes in Computer Science, pages 227{243. Springer Berlin Heidelberg, 2012. 12. S. Obiedkov. Modeling ceteris paribus preferences in formal concept analysis. In P. Cellier, F. Distel, and B. Ganter, editors, Formal Concept Analysis, volume 7880 of Lecture Notes in Computer Science, pages 188{202. Springer Berlin Heidelberg, 2013.