Using the Chu Construction for generalizing formal concept analysis

Using the Chu Construction for generalizing formal concept analysis L. Antoni1, I.P. Cabrera2, S. Krajˇci1, O. Kr´ıdlo1, M. Ojeda-Aciego2 1University of Pavol Jozef ˇ Saf´arik, Koˇsice, Slovakia 2Universidad de M´alaga. Departamento Matem´atica Aplicada. Spain Abstract. The goal of this paper is to show a connection between FCA generalisations and the Chu construction on the category ChuCors, the category of formal contexts and Chu correspondences. All needed categorical properties like categorical product, tensor product and its bifunctor properties are presented and proved. Finally, the second order generalisation of FCA is represented by a category built up in terms of the Chu construction. Keywords: formal concept analysis, category theory, Chu construction 1 Introduction The importance of category theory as a foundational tool was discovered soon after its very introduction by Eilenberg and MacLane about seventy years ago. On the other hand, Formal Concept Analysis (FCA) has largely shown both its practical applications and its capability to be generalized to more abstract frameworks, and this is why it has become a very active research topic in the recent years; for instance, a framework for FCA has been recently introduced in [16] in which the sets of objects and attributes are no longer unstructured but have a hypergraph structure by means of certain ideas from mathematical morphology. On the other hand, for an application of the FCA formalism to other areas, in [8] the authors introduce a representation of algebraic domains in terms of FCA. The Chu construction [5] is a theoretical method that, from a symmetric monoidal closed (autonomous) category and a dualizing object, generates a *- autonomous category. This construction, or the closely related notion of Chu space, has been applied to represent quantum physical systems and their symmetries [1,2]. This paper continues with the study of the categorical foundations of formal concept analysis. Some authors noticed the property of being a cartesian closed category of certain concept structures that can be approximated [7, 17]; others have provided a categorical construction of certain extensions of FCA [9]; morphisms have received a categorical treatment in [14] as a means for the modelling of communication. There already exist some approaches [6] which consider the Chu construction in terms of FCA. In the current paper, we continue the previous study by the authors on the categorical foundation of FCA [10,12,13]. Specifically, the goal of this paper is to highlight the importance of the Chu construction in the research area of categorical description of the theory of FCA and its generalisations. The Chu construction plays here the role of some recipe for constructing a suitable category that covers the second order generalisation of FCA. The structure of this paper is the following: in Section 2 we recall the preliminary notions required both from category theory and formal concept analysis. Then, the various categorical properties of the input category which are required (like the existence of categorical and tensor product) are developed in detail in Sections 3 and 4. An application of the Chu construction is presented in Section 5 where it is also showed how to construct formal contexts of second order from the category of classical formal contexts and Chu correspondences (ChuCors). 2 Preliminaries In order to make the manuscript self-contained, the fundamental notions and its required properties are recalled in this section. Definition 1. Aformal context is any triple C=hB,A,Ri where Band Aare finite sets and R⊆B×Ais a binary relation. It is customary to say that Bis a set of objects,Ais a set of attributes and Rrepresents a relation between objects and attributes. On a given formal context (B, A, R), the derivation (or concept-forming) operators are a pair of mappings ↑: 2B→2Aand ↓: 2A→2Bsuch that if X⊆B, then ↑Xis the set of all attributes which are related to every object in Xand, similarly, if Y⊆A, then ↓Yis the set of all objects which are related to every attribute in Y. In order to simplify the description of subsequent computations, it is convenient to describe the concept forming operators in terms of characteristic functions, namely, considering the subsets as functions on the set of Boolean values. Specifically, given X⊆Band Y⊆A, we can consider mappings ↑X:A→ {0,1} and ↓Y:B→ {0,1} 1. ↑X(a) = ^ b∈B(b∈X)⇒((b, a)∈R)for any a∈A 2. ↓Y(b) = ^ a∈A(a∈Y)⇒((b, a)∈R)for any b∈B where the infimum is considered in the set of Boolean values and ⇒is the truthfunction of the implication of classical logic. Definition 2. Aformal concept is a pair of sets hX, Y i ∈ 2B×2Awhich is a fixpoint of the pair of concept-forming operators, namely, ↑X=Yand ↓Y=X. The object part Xis called the extent and the attribute part Yis called the intent. There are two main constructions relating two formal contexts: the bonds and the Chu correspondences. Their formal definitions are recalled below: Definition 3. Consider C1=hB1, A1, R1iand C2=hB2, A2, R2itwo formal contexts. A bond between C1and C2is any relation β∈2B1×A2such that its columns are extents of C1and its rows are intents of C2. All bonds between such contexts will be denoted by Bonds(C1,C2). The Chu correspondence between contexts can be seen as an alternative inter-contextual structure which, instead, links intents of C1and extents of C2. Namely, Definition 4. Consider C1=hB1, A1, R1iand C2=hB2, A2, R2itwo formal contexts. A Chu correspondence between C1and C2is any pair of multimappings ϕ=hϕL, ϕRisuch that –ϕL:B1→Ext(C2) –ϕR:A2→Int(C1) –↑2(ϕL(b1))(a2) = ↓1(ϕR(a2))(b1)for any (b1, a2)∈B1×A2 All Chu correspondences between such contexts will be denoted by Chu(C1,C2). The notions of bond and Chu correspondence are interchangeable; specifically, we will use the bond βϕassociated to a Chu correspondence ϕfrom C1 to C2defined for b1∈B1, a2∈A2as follows: βϕ(b1, a2) = ↑2(ϕL(b1))(a2) = ↓1(ϕR(a2))(b1) The set of all bonds (resp. Chu correspondences) between any two formal contexts endowed with set inclusion as ordering have a complete lattice structure. Moreover, both complete lattices are dually isomorphic. In order to formally define the composition of two Chu correspondences, we need to introduce the extension principle below: Definition 5. Given a mapping ϕ:X→2Ywe define its extended mapping ϕ+: 2X→2Ydefined by ϕ+(M) = Sx∈Mϕ(x), for all M∈2X. The set of formal contexts together with Chu correspondences as morphisms forms a category denoted by ChuCors. Specifically: –objects formal contexts –arrows Chu correspondences –identity arrow ι:C → C of context C=hB, A, Ri •ιL(o) = ↓↑({b}), for all b∈B •ιR(a) = ↑↓({a}), for all a∈A –composition ϕ2◦ϕ1:C1→ C3of arrows ϕ1:C1→ C2,ϕ2:C2→ C3(where Ci=hBi, Ai, Rii,i∈ {1,2,3}) •(ϕ2◦ϕ1)L:B1→2B3and (ϕ2◦ϕ1)R:A3→2A1 •(ϕ2◦ϕ1)L(b1) = ↓3↑3(ϕ2L+(ϕ1L(b1))) •(ϕ2◦ϕ1)R(a3) = ↑1↓1(ϕ1R+(ϕ2R(a3))) The category ChuCors is *-autonomous and equivalent to category of complete lattices and isotone Galois connection, more results on this category and its L-fuzzy extensions can be found in [10,12,13,15]. 3 Categorical product on ChuCors In this section, the category ChuCors is proved to contain all finite categorical products, that is, it is a Cartesian category. To begin with, it is convenient to recall the notion of categorical product. Definition 6. Let C1and C2be two objects in a category. By a product of C1 and C2we mean an object Pwith arrows πi:P → Cifor i∈ {1,2}satisfying the following condition: For any object Dand arrows δi:D → Cifor i∈ {1,2}, there exists a unique arrow γ:D → P such that γ◦πi=δifor all i∈ {1,2}. The construction will use the notion of disjoint union of two sets S1]S2 which can be formally described as ({1} × S1)∪({2} × S2) and, therefore, their elements will be denoted as ordered pairs (i, s) where i∈ {1,2}and s∈Si. Now, we can proceed with the construction: Definition 7. Consider C1=hB1, A1, R1iand C2=hB2, A2, R2itwo formal contexts. The product of such contexts is a new formal context C1× C2=hB1]B2, A1]A2, R1×2i where the relation R1×2is given by ((i, b),(j, a)) ∈R1×2if and only if (i=j)⇒(b, a)∈Ri for any (b, a)∈Bi×Ajand (i, j)∈ {1,2}×{1,2}. Lemma 1. The above defined contextual product fulfills the property of the categorical product on the category ChuCors. Proof. We define the projection arrows hπiL, πiRi ∈ Chu(C1×C2,Ci) for i∈ {1,2} as follows –πiL :B1]B2→Ext(Ci)⊆2Bi –πiR :Ai→Int(C1× C2)⊆2A1∪A2 –such that for any (k, x)∈B1]B2and ai∈Aithe following equality holds ↑i(πiL(k, x))(ai) = ↓1×2(πiR(ai))(k, x) The definition of the projections is given below πiL(k, x)(bi) = (↓i↑i(χx)(bi) for k=i ↓i↑i0(bi) for k6=ifor any (k, x)∈B1]B2and bi∈Bi πiR(ai)(k, y) = (↑i↓i(χai)(y) for k=i ↑k↓k0(y) for k6=ifor any (k, y)∈A1]A2and ai∈Ai. The proof that the definitions above actually provide a Chu correspondence is just a long, although straightforward, computation and it is omitted. Now, one has to show that to any formal context D=hE, F, Gi, where G⊆E×Fand any pair of arrows (δ1, δ2) with δi:D → Cifor all i∈ {1,2}, there exists a unique morphism γ:D → C1× C2such that the following diagram commutes: C1<π1C1× C2 π2>C2 D γ ∧ . . . . . . . . .δ2 > δ1 < We give just the definition of γas a pair of mappings γL:E→2B1]B2and γR:A1]A2→2F –γL(e)(k, x) = δkL(e)(x) for any e∈Eand (k, x)∈B1]B2. –γR(k, y)(f) = δkR(y)(f) for any f∈Fand (k, y)∈A1]A2. Checking the condition of categorical product is again straightforward but long and tedious and, hence, it is omitted. ut We have just proved that binary products exist, but a cartesian category requires the existence of all finite products. If we recall the well-known categorical theorem which states that if a category has a terminal object and binary product, then it has all finite products, we have just to prove the existence of a terminal object (namely, the nullary product) in order to prove ChuCors to be cartesian. Any formal context of the form hB, A, B ×Aiwhere the incidence relation is the full cartesian product of the sets of objects and attributes is (isomorphic to) the terminal object of ChuCors. Such formal context has just one formal concept hB, Ai; hence, from any other formal context there is just one Chu correspondence to hB, A, B ×Ai. 4 Tensor product and its bifunctor property Apart from the categorical product, another product-like construction can be given in the category ChuCors, for which the notion of transposed context C∗is needed. Given a formal context C=hB, A, Ri, its transposed context is C∗=hA, B, Rti, where Rt(a, b) holds iff R(b, a) holds. Now, if ϕ∈Chu(C1,C2), one can consider ϕ∗∈Chu(C∗ 2, C∗ 1) defined by ϕ∗ L=ϕRand ϕ∗ R=ϕL. Definition 8. The tensor product of formal contexts Ci=hBi, Ai, Riifor i∈ {1,2}is defined as the formal context C1C2=hB1×B2,Chu(C1,C∗ 2), Riwhere R((b1, b2), ϕ) = ↓2(ϕL(b1))(b2). Mori studied in [15] the properties of the tensor product above, and proved that ChuCors with is a symmetric and monoidal category. Those results were later extended to the L-fuzzy case in [10]. In both papers, the structure of the formal concepts of a product context was established as an ordered pair formed by a bond and a set of Chu correspondences. Lemma 2. Let Ci=hBi, Ai, Riifor i∈ {1,2}be two formal contexts, and let hβ, Xi ∈ Bonds(C1,C∗ 2)×2Chu(C1,C∗ 2)be an arbitrary formal concept of C1C2. Then β=Vψ∈Xβψand X={ψ∈Chu(C1,C∗ 2)|β≤βψ}. Proof. Let Xbe an arbitrary subset of Chu(C1,C∗ 2). Then, for all (b1, b2)∈ B1×B2, we have ↓C1C2(X)(b1, b2) = ^ ψ∈Chu(C1,C∗ 2)(ψ∈X)⇒ ↓2(ψL(b1))(b2) =^ ψ∈X ↓2(ψL(b1))(b2) = ^ ψ∈X βψ(b1, b2) Let βbe an arbitrary subset of B1×B2. Then, for all ψ∈Chu(C1,C∗ 2) ↑C1C2(β)(ψ) = ^ (b1,b2)∈B1×B2β(b1, b2)⇒ ↓2(ψL(b1))(b2) =^ (b1,b2)∈B1×B2β(b1, b2)⇒βψ(b1, b2) Hence ↑C1C2(β) = {ψ∈Chu(C1,C∗ 2)|β≤βψ} ut We now introduce the notion of product of one context with a Chu correspondence. Definition 9. Let Ci=hBi, Ai, Riifor i∈ {0,1,2}be formal contexts, and consider ϕ∈Chu(C1,C2). Then, the pair of mappings (C0ϕ)L:B0×B1→2B0×B2(C0ϕ)R: Chu(C0,C2)→2Chu(C0,C1) is defined as follows: –(C0ϕ)L(b, b1)(o, b2) = ↓C0C2↑C0C2(γb,b1 ϕ)(o, b2)where γb,b1 ϕ(o, b2) = (b=o)∧ϕL(b1)(b2)for any b, o ∈B0,bi∈Biwith i∈ {1,2} –(C0ϕ)R(ψ2)(ψ1) = ψ1≤(ψ2◦ϕ∗)for any ψi∈Chu(C0,Ci) As one could expect, the result is a Chu correspondence between the products of the contexts. Specifically, Lemma 3. Let Ci=hBi, Ai, Riibe formal contexts for i∈ {0,1,2}, and consider ϕ∈Chu(C1,C2). Then C0ϕ∈Chu(C0C1,C0C2). Proof. (C0ϕ)L(b, b1)∈Ext(C0C2) for any (b, b1)∈B0×B1follows directly from its definition. (C0ϕ)R(ψ)∈Int(C0C1) for any ψ∈Chu(C0,C1) follows from Lemma 2. Consider an arbitrary b∈B0,b1∈B1and ψ2∈Chu(C0,C∗ 2) ↑C0C2(C0ϕ)L(b, b1)(ψ2) =↑C0C2↓C0C2↑C0C2(γb,b1 ϕ)(ψ2) =↑C0C2(γb,b1 ϕ)(ψ2) =^ (o,b2)∈B0×B2γb,b1 ϕ(o, b2)⇒ ↓(ψ2R(b2))(o) =^ (o,b2)∈B0×B2(o=b)∧ϕL(b1)(b2)⇒ ↓(ψ2R(b2))(o) =^ o∈B0^ b2∈B2(o=b)⇒ϕL(b1)(b2)⇒ ↓(ψ2R(b2))(o) =^ o∈B0(o=b)⇒^ b2∈B2 (ϕL(b1)(b2)⇒ ↓(ψ2R(b2))(o)) =^ b2∈B2ϕL(b1)(b2)⇒ ↓(ψ2R(b2))(b) =^ b2∈B2ϕL(b1)(b2)⇒^ a∈A (ψ2R(b2)(a)⇒R(b, a)) =^ a∈A_ b2∈B2 (ϕL(b1)(b2)∧ψ2R(b2)(a)) ⇒R(b, a) =^ a∈Aψ2R+(ϕL(b1))(a)⇒R(b, a) =↓(ψ2R+(ϕL(b1))(b) = ↓↑↓(ψ2R+(ϕL(b1))(b) = ↓((ϕ◦ψ2)R(b1))(b) Note the use above of the extended mapping as given in Definition 5 in relation to the composition of Chu correspondences. On the other hand, we have ↓C0C1((C0ϕ)R(ψ2))(b, b1) =^ ψ1∈Chu(C0,C1) ((C0ϕ)R(ψ2)(ψ1)⇒ ↓(ψ1R(b1))(b)) =^ ψ1∈Chu(C0,C1) ((ψ1≥ϕ◦ψ2)⇒ ↓(ψ1R(b1))(b)) =^ ψ1∈Chu(C0,C1) ψ1≥ϕ◦ψ2 ↓(ψ1R(b1))(b) =↓((ϕ◦ψ2)R(b1))(b) Hence ↑C0C2((C0ϕ)L(b, b1))(ψ2) = ↓C0C1((C0ϕ)R(ψ2))(b, b1). So if ϕ∈Chu(C1,C2) then C0ϕ∈Chu(C0C1,C0C2). ut Given a fixed formal context C, the tensor product C(−) forms a mapping between objects of ChuCors assigning to any formal context Dthe formal context CD. Moreover to any arrow ϕ∈Chu(C1,C2) it assigns an arrow Cϕ∈Chu(C C1,CC2). We will show that this mapping preservers the unit arrows and the composition of Chu correspondences. Hence the mapping forms an endofunctor on ChuCors, that is, a covariant functor from the category ChuCors to itself. To begin with, let us recall the definition of functor between two categories: Definition 10 (See [4]). A covariant functor F: C →Dbetween categories C and Dis a mapping of objects to objects and arrows to arrows, in such a way that: –For any morphism f:A→B, one has F(f): F(A)→F(B) –F(g◦f) = F(g)◦F(f) –F(1A) = 1F(A). Lemma 4. Let C=hB, A, Ribe a formal context. C(−)is an endofunctor on ChuCors. Proof. Consider the unit morphism ιC1of a formal context C1=hB1, A1, R1i, and let us show that (CιC1) = ιCC1. In other words, C(−) respects unit arrows in ChuCors. ↑CC1(CιC1)(b, b1)(ψ) =^ (o,o1)∈B×B1(o=b)∧ιC1L(b1)(o1)⇒ ↓1(ψL(o))(o1) =^ o1∈B1↓1↑1(χb1)(o1)⇒ ↓1(ψL(b))(o1) =^ o1∈B1↓1↑1(χb1)(o1)⇒^ a1∈A1ψL(b)(a1)⇒R(o1, a1) =^ o1∈B1^ a1∈A1↓1↑1(χb1)(o1)⇒ψL(b)(a1)⇒R(o1, a1) =^ o1∈B1^ a1∈A1ψL(b)(a1)⇒↓1↑1(χb1)(o1)⇒R(o1, a1) =^ a1∈A1ψL(b)(a1)⇒^ o1∈B1↓1↑1(χb1)(o1)⇒R(o1, a1) =^ a1∈A1ψL(b)(a1)⇒ ↑1↓1↑1(χb1)(a1) =^ a1∈A1ψL(b)(a1)⇒R1(b1, a1) =↓1(ψL(b))(b1) and, on the other hand, we have ↑CC1(ιCC1(b, b1))(ψ) =↑CC1(χ(b,b1))(ψ) =^ (o,o1)∈B×B1χ(b,b1)(o, o1)⇒ ↓1(ψL(o))(o1) =↓1(ψL(b))(b1) As a result, we have obtained ↑CC1((CιC1)(b, b1))(ψ) =↑CC1(ιCC1(b, b1))(ψ) for any (b, b1)∈B×B1and any ψ∈Chu(C,C1); hence, ιCC1= (CιC1). We will show now that C(−) preserves the composition of arrows. Specifically, this means that for any two arrows ϕi∈Chu(Ci,Ci+1) for i∈ {1,2}it holds that C(ϕ1◦ϕ2)=(Cϕ1)◦(Cϕ2). ↑CC3C(ϕ1◦ϕ2)L(b, b1)(ψ3) =^ (o,b3)∈B×B3(o=b)∧(ϕ1◦ϕ2)L(b1)(b3)⇒ ↓(ψ3R(b3))(o) =^ b3∈B3(ϕ1◦ϕ2)L(b1)(b3)⇒ ↓(ψ3R(b3))(b) (by similar operations to those in the first part of the proof) =↓(ϕ1◦ϕ2◦ψ3)L(b1)(b) On the other hand, and writing Ffor C−in order to simplify the resulting expressions, we have ↑FC3((Fϕ1◦F ϕ2)L(b, b1))(ψ3) =↑FC3↓FC3↑FC3(Fϕ2)L+(F ϕ1)L(b, b1)(ψ3) =^ (o,b3)∈B×B3 _ (j,b2)∈B×B2(Fϕ1)L(b, b1)(j, b2)∧(F ϕ2)L(j, b2)(o, b3)⇒ ↓(ψ3R(b3))(o) =^ b3∈B3^ b2∈B2ϕ1L(b1)(b2)∧ϕ2L(b2)(b3)⇒ ↓(ψ3R(b3))(b) =^ b3∈B3_ b2∈B2ϕ1L(b1)(b2)∧ϕ2L(b2)(b3)⇒ ↓(ψ3R(b3))(b) =^ b3∈B3ϕ2L+(ϕ1L(b1))(b3)⇒ ↓(ψ3R(b3))(b) =^ b3∈B3(ϕ1◦ϕ2)L(b1)(b3)⇒ ↓(ψ3R(b3))(b)