Extending Attribute Exploration by Means of Boolean Derivatives

Extending Attribute Exploration by Means of Boolean Derivatives J. Antonio Alonso-Jim´enez1, Gonzalo A. Aranda-Corral1, Joaqu´ın Borrego-D´ıaz1, and M. Magdalena Fern´andez-Lebr´on2, M. Jos´e Hidalgo-Doblado1 1Departamento de Ciencias de la Computaci´on e Inteligencia Artificial 2Departamento de Matem´atica Aplicada I E.T.S. Ingenier´ıa Inform´atica, Universidad de Sevilla, Avda. Reina Mercedes s.n. 41012-Sevilla, Spain Abstract. We present a translation of problems of Formal Context Analysis into ideals problems in F2[x] through the Boolean derivatives. The Boolean derivatives are introduced as a kind of operators on propositional formulas which provide a complete calculus. They are useful to refine stem basis as well as for extending attribute exploration. 1 Introduction Attribute exploration (cf. [3]) is a family of interactive procedures for Knowledge Acquisition (KA) in Formal Concept Analysis (FCA), whose goal is to build a knowledge base of the attributes we are working with. The procedures used in FCA have nice computer implementations, existing even generalizations for the management of the background information. Sometimes attribute exploration is hard or tedious to apply. Thus, it may advisable to use automated tools. Many Computer Algebra Systems (CAS) provide tools for working with discrete data, for example, Gr¨obner basis. Since it is possible to translate entailment problems into ideal problems in finite fields, Gr¨obner basis is a powerful tool for reasoning in propositional logic [8, 9, 2]. Our aim is to extend the framework of attribute exploration through the introduction of Boolean derivatives and the assistance of a CAS. The CAS that we will use CoCoA (http://cocoa.dima.unige.it/), very well suited for our pourposes because of its easy management of Gr¨obner basis and related tools. The paper is organized as follows. The next section reviews the relationship between propositional logic and the ring F2[x], as well as the basics of FCA. In the third section the Boolean derivatives are introduced, as well as a complete polynomial calculus based on them. An algebraic characterization of sensitivity for implications in FCA is given in forth section. In fifth and sixth sections new versions of attribute exploration are introduced, and in section 7 an application to graph theory is given. We conclude with some remarks about future work. 2 Background We assume that the reader is familiar with propositional logic and polynomial algebra on positive characteristics. We setup a propositional language PV = c Radim Belohlavek, Sergei O. Kuznetsov (Eds.): CLA 2008, pp. 121–132, ISBN 978–80–244–2111–7, Palack´y University, Olomouc, 2008. {p1, . . . , pn},PForm will denote the set of propositional formulas, and var(F) denotes the set of variables of the propositional formula F. The ring in which we are working is F2[x] (where x=x1, . . . , xn). A key ideal is I2:= (x1+x2 1, . . . , xn+x2 n). To clarify our proposition, let fix an identification pi7→ xi(or p7→ xp) between PV and the set of indeterminates. Given α= (α1, . . . αn)∈Nn, let us define |α|:= max{α1, . . . , αn}, and sg(α) := (δ1, . . . , δn), where δiis 0 if αi= 0 and 1 otherwise. The degree of a(x)∈ F2[x], is deg∞(a(x)) :=max{|α|:xαis a monomial of a}, and degi(a(x)) is the degree w.r.t. xi. If deg∞(a(x)) ≤1, a(x) is called a polynomial formula. Three maps represent the relationship between propositional logic and F2[x]: –Φ:F2[x]→F2[x] is defined by Φ(X α∈I xα) := X α∈I xsg(α). –The map P:PForm →F2[x] is defined by the following equations •P(⊥) = 0, P(pi) = xi, P(¬F) = 1 + P(F) •P(F1∧F2) = P(F1)·P(F2) and P(F1∨F2) = P(F1)+P(F2)+P(F1)P(F2) •P(F1→F2) = 1 + P(F1) + P(F1)P(F2), and •P(F1↔F2) = 1 + P(F1) + P(F2) –Θ:F2[x]→PForm is defined by •Θ(0) = ⊥, Θ(1) = >,Θ(xi) = pi, •Θ(a·b) = Θ(a)∧Θ(b), and Θ(a+b) = ¬(Θ(a)↔Θ(b)). We have that Θ(P(F)) ≡Fand P(Θ(a)) = a. Since we shall frequently be applying Φ◦P, we define the polynomial projection as π:= Φ◦P. Regarding valuations and polynomials, the key fact is that, if v:PV → {0,1} is a valutation with v(pi) = δi, then for every F∈PForm, v(F) = P(F)(δ1, . . . δn) The behaviour of the ideals of F2[x] is well known: If A⊆(F2)n, then V(I(A)) = A, and for every I∈Ideals(F2[x]), I(V(I)) = I+I2. Therefore F≡F0if and only if P(F) = P(F0) (mod I2) which is also equivalent to Φ◦P(F) = Φ◦P(F0). The following theorem states the main relationship between propositional logic and F2[x]: Theorem 1. The following conditions are equivalent: (1) {F1, . . . , Fm} |=G. (2) 1 + P(G)∈(1 + P(F1), . . . , 1 + P(Fn)) + I2. (3) NF(1 + P(G),GB [(1 + P(F1), . . . , 1 + P(Fm))+I2]) = 0. (where GB denotes Gr¨obner basis) and NF denotes normal form. In the rest of this section we succintly present some elements of FCA we use, although we assume that the reader knows the basic principles of this theory (the fundamental reference is [3]). We represent a formal context as M= (O, A, I), which consists of two sets, O(the objects) and A(the attributes) and a relation I⊆O×A. Finite contexts can be represented by a 1-0-table (representing Ias a Boolean function on O×A). The main goal in FCA is the computation of the concept lattice associated to the context. 122 Jos´e Antonio Alonso-Jim´enez, Gonzalo A. Aranda-Corral, Joaqu´ın BorregoD´ıaz, M. Magdalena Fern´andez-Lebr´on, M. Jos´e Hidalgo-Doblado Basic logical expressions in FCA are implication between attributes, that is, pair of sets of attributes written as Y1→Y2. Truth with respect to M= (O, A, I) is defined as follows. A subset T⊆Arespects Y1→Y2if Y16⊆ Tor Y2⊆T. We say that Y1→Y2holds in M(M|=Y1→Y2) if for all o∈O, the set {o}0 respects Y1→Y2. In that case we say that Y1→Y2is an implication of M. From a propositional logic viewpoint, Y1→Y2is the formula VY1→VY2, so it is equivalent to a set of Horn clauses (implications with a singleton as right-hand side). On the other hand, the definition of truth can be extended: Given Y⊆A, define ¬Y:= Y→ ⊥, and it holds in the context if for all o∈O,Y6⊆ {o}0. Given a formula written with {→,⊥},M|=Fcan be defined in the natural way. Since this set of connectives is functionally complete, truth definition can be extended to PForm. Definition 1. Let Lbe a set of implications and Lan implication of M. •Lfollows from L(L |=L) if each subset of Arespecting Lalso respects L. • L is closed if every implication following from Lis already in L. • L is complete if every implication of the context follows from L. • L is non-redundant if for each L∈ L,L\{L} 6|=L. • L is a stem basis for Mif it is complete and non-redundant. For every context we can obtain a stem basis from the pseudo-intents: Theorem 2. [7] The set L={Y→Y00 :Yis a pseudointent}is a stem basis. Actually one can choose Y→Y00 \Yinstead of Y→Y0, so we will assume, by default, that for every implication Y1→Y2belonging to a stem basis Y1 and Y2are disjoint. Such a basis for the example of figure 5 (left) is L={∅ → N, {N, A} → {Mo},{N, Le} → {Mo}}. The called Amstrong rules facilitates implicational reasoning: R1 : X→XR2 : X→Y X∪Z→YR3 : X→Y, Y ∪Z→W X∪Z→W It has that A set of implications Lis closed if and only if the set is closed by Amstrong rules [1]. A consequence of Amstrong result is that, if `Adenotes the proof notion associated to Amstrong rules, stem basis are `A-complete, that is: Theorem 3. Let Lbe a stem basis for M, and Lan implication. Then M|=L if and only if L `AL The computing of stem basis may be expensive if the set of objects is large. Even it is possible we do not have the complete context M, or it has a potentially infinite set of objects. Attribute exploration is an interactive procedure designed to obtain a stem basis starting with a set Hof good examples generating the subcontext MH:= (H, A, I ∩(H×A)) One expects that a stem basis associated to MHis also a stem basis for the complete context. To guarantee it, we proceed as follows. Assume that L= Extending Attribute Exploration by Means of Boolean Derivatives 123 1. Compute pseudo-intent: Find Xa pseudo-intent for MH. 2. Soundness of the new implication: Ask to the user X? →X00 (the operators 0are w.r.t. the subcontext). The user must react: –Confirming the suggested implication (adding it to L), or –giving o(a counterexample) such that {o}0does not respect the implication. This is added to H, and the implication is discarded. Fig. 1. Attribute exploration {L1, . . . , Lk}is a partial set of implications accepted as true, built from pseudointents of MH1. Attribute exploration consists in a loop of the two steps shown in fig. 1, and it stops when no new pseudointent is found (see [4] for variants). 3 Boolean derivatives and non-clausal theorem proving We introduce an operator on propositional formulas as a translation of the usual derivation on F2[x]. In this section we review its basic properties (from [2]). Recall that a derivation on a ring Ris a map d:R→Rverifying that d(a+b) = d(a) + d(b) and d(a·b) = d(a)·b+a·d(b) Definition 2. A map ∂:PForm →PF orm is a Boolean derivation if there exists a derivation don the ring F2[x]such that ∂=Θ◦d◦π If the derivation on F2[x] is d=∂ ∂xp, we denote ∂as ∂ ∂p . It has that: ∂ ∂pF≡ ¬(F{p/¬p} ↔ F) Thus, the value of ∂ ∂p Fwith respect to a valuation does not depend on p. Therefore, we can apply valuations on PV \{p}to this formula. Definition 3. The independence rule (or ∂-rule) on polynomial formulas is ∂x(a1, a2) : a1, a2 1 + Φ(1 + a1·a2)(1 + a1·∂ ∂x a2+a2·∂ ∂x a1+∂ ∂x a1·∂ ∂x a2) In order to simplify the notation, if ai=bi+xp·ci,with degxp(bi) = degxp(ci) = 0 (i= 1,2),. Then we can rewrite the values as: ∂xp(a1, a2) : b1+xp·c1, b2+xp·c2 Φ[1 + (1 + b1·b2)[1 + (b1+c1)(b2+c2)]] The rule is symmetric and generalizes resolution of non-tautological polynomial clauses (see lemma 1). For formulas the rule is translated as ∂p(F1, F2) := Θ(∂xp(π(F1), π(F2))). 1Pseudointents are generated in lexicographic order. This way previously computed pseudointents are preserved by augmentations of H. See th. 27 in [3]. 124 Jos´e Antonio Alonso-Jim´enez, Gonzalo A. Aranda-Corral, Joaqu´ın BorregoD´ıaz, M. Magdalena Fern´andez-Lebr´on, M. Jos´e Hidalgo-Doblado It naturally induces a concept of proof, `∂. A `∂-refutation is a proof of ⊥. In [2] the soundness and the refutational completeness of `partial has been proved Theorem 4. [2] Let v:P V \{p}→{0,1}. The following conditions are equivalent: 1. v|=∂p(F1, F2). 2. There exists an extension of vto P V is a model of {F1, F2}. For example, ∂x1(x1(1 + x2), x1(1 + x2)) = 1 + x2. So the valuation vs.t. v(¬p2) = 1 is the only one that we can extend to a model of p1∧ ¬p2. When ∂p(π(F1), π(F2)) = 1, every partial valuation is extendable to a model of {F1, F2}. Theorem 5. [2] If Γis inconsistent then Γ`∂⊥. Let be ∂p[Γ] defined as ∂p[Γ] := {∂p(F, G) : F, G ∈Γ}. Given Q={q1, . . . , qk} ⊆ PV the operator ∂Q:= ∂q1◦···◦∂qkis well defined modulo logical equivalence (by corollary 4, for every p, q ∈PV ,∂p◦∂q[Γ]≡ ∂q◦∂p[Γ]). A consequence of corollary 4 and theorem 5 is that entailment can be located on variables of the goal; Corollary 1. Γ|=F⇐⇒ ∂P V \var(F)[Γ]|=F We can define an explicit equivalent expression for ∂pwhen it is applied to implications. To simplify, suppose that the right-side of implications is a singleton. Lemma 1. Let Ci≡VYi 1→VYi 2be a implications (i= 1,2,Yi 1∩Yj 2=∅), and Γbe a set of implications. Let ∂c p(C1, C2)be the symmetric operator ∂c p(C1, C2) :=            {C1, C2}p /∈var(C1)∪var(C2) {C2}p∈Y1 1, p /∈var(C2) {VY1 1→V(Y1 2\{p}), C2}p∈Y1 2, p /∈var(C2) {>} p∈(Y1 1∩Y2 1)∪(Y1 2∩Y2 2) {Resolventp(C1, C2)}p∈Y1 1∩Y2 2 If ∂c p[Γ] := S{∂c p(C1, C2) : C1, C2∈Γ}, then ∂c Q[Γ]≡∂Q[Γ](Q⊆PV ). 4 Algebraic characterization of sensitive implications We shall provide an algebraic treatment for implications on a fixed M= (O, A, I). It is well know that every set X⊆(F2)nis an algebraic set; that is, there exists aX∈F2[x] such that V(aX) = X. If |A|=n,Mis identified with a subset X(M) of (F2)n(each object identified with the 1-0 expresion of its intent). Let aM∈F2[x] denote a polynomial formula such that V(aM) = X(M). Since IV (aM) = (aM) + I2,the coordinate ring of Mis F2[x]/I(X(M)) ∼ =(F2[x]/(aM))/I2 One might also use an ideal JXsuch that V(JX) = X, if it is better to work with them (for example using CoCoA’s command IdealsofPoints). Thus we can assume that I2⊆JM. We choose aMonly to simplify the proofs. Also, each o∈Odefines a valuation vodefined by: vo(pi) = 1 iff oIpi. Extending Attribute Exploration by Means of Boolean Derivatives 125 Proposition 1. Let F∈PForm and let Lbe a stem basis. The following conditions are equivalent: (1) M|=F. (2) 1 + π(F)∈(aM) + I2. Moreover, if Fis an implication, they are also equivalent to (3) {P(L) : L∈ L}∪{1 + π(F)} `∂0. (4) ∂c P V \var(F)[L]|=F Proof (1) ⇐⇒ (2): If M|=F, then V(aM)⊆V(1 + π(F)). Thus, IV (1 + π(F)) ⊆ IV (aM) hence 1 + π(F)∈(aM) + I2. The converse is similar. If Fis an implication and M|=F, then L |=F. Therefore L∪{¬F}is inconsistent so by completeness, L∪{¬F} `∂⊥hence we have (3). The converse is true by soundness. (4) is equivalent to L |=Fby lemma 1. We now deal with the problem of redundant arguments in implications. In the worst case, the recognizing of redundancy requires a complete exploration of intents. An argument is redundant if it is not sensitive: Definition 4. A formula Fis sensitive in pw.r.t. a formal context Mif M6|= F{p/¬p} ↔ F. We say that Fis sensitive w.r.t. M(or simply sensitive, if M is fixed) if Fis sensitive in all its variables. Thus, Fis not sensitive in piff M|=¬∂ ∂p F. In this case, there exists Gwith var(G) =var(F)\{p}such that M|=F↔G(e.g. F{p/⊥}). Sensitive implications (also called proper implications) have several advantages over implications obtained from pseudo-intents (see [10]). In attribute exploration, sensitivity analysis is justified: it is possible that implications are based on a nonrepresentative set of examples, and thus they can be refined, basically giving witnesses of the role of the arguments in the implication, or making them more precise, removing redundant arguments: Lemma 2. Let L=Y1→Y2be an implication. If M|=Land Lis not sensitive in p∈Y1, then M|=Y1\{p} → Y2. If p∈Y2, then M|=¬Y1. By default, sensitivity analysis for implications will be always restricted to attributes in the left-hand side. Proposition 2. Let p∈var(F). The following conditions are equivalent: (1) Fis sensitive in pw.r.t. M. (2) ∂ ∂xpπ(F)6= 0 in the coordinate ring of M. Proof. (1) =⇒(2): Assume vo6|=F↔F{p/¬p}for some o∈O. Then vo|=∂ ∂p F, so V(aM)6⊆ V(π(∂ ∂p F)) = V(∂ ∂xpπ(F)),hence ∂ ∂xpπ(F)/∈(aM) + I2. (2) =⇒(1): If ∂ ∂xpπ(F)/∈(aM) + I2, then O=V(aM)6⊆ V(π(∂ ∂p F)). Therefore there exists o∈Osuch that vo|=∂ ∂p F. Thus Fis sensitive in p. 126 Jos´e Antonio Alonso-Jim´enez, Gonzalo A. Aranda-Corral, Joaqu´ın BorregoD´ıaz, M. Magdalena Fern´andez-Lebr´on, M. Jos´e Hidalgo-Doblado (3) Sensitivity test: If the implication has not been discarded, test whether the implication is sensitive in all its arguments w. r. t. the actual set H(using lemma 2 if necessary). If it is not sensitive in some of them, the user must to react: –Adding a new example oto H, witness of the sensitivity (that is, he/she thinks that it is sensitive), or –eliminating the attribute of the implication (it accepts it is not sensitive), changing the accepted implication by the refined one. Fig. 2. Sensitivity test to add to algorithm of fig. 1 One can recursively apply the above criteria (w.r.t. an order on PV ) to obtain sensitive implications. If Lis a stem basis and L0is the refinement obtained, since Amstrong’s rule R2 states Y1\{Y} → Y2|=Y1→Y2, one has that L0|=L. Thus L0is also a complete set of implications. The set L0has an advantage over other sets of proper implications (e.g. [10]) that it directly works on Duquenne-Guigues basis so it does not need an specific algorithm to build it. 5 Variants of attribute exploration We shall propose new steps for attribute exploration. All of them are investigated with the translation into polynomials in mind. Although in the exposition we do not explicitely use polynomials -the results and their proofs are more readable in logical formin practice they will be useful. The attribute exploration can be extended by adding a sensitivity test w.r.t H(shown in fig. 2). Note that addition of a new object follows the formula aH∪{(δ1,...,δn)}=Φ(aH·(1 + Πn i=1(xi+δi+ 1))) For the running example, the implication N∧A→Mo is obtained and considered as sound. In this case, aM=x1x2x4+x1x2+x1x3+x1x4+x1+ 1. A Gr¨obner basis for aM+I2is {x2 4+x4, x2 3+x3, x4 2+x2, x3x4+x3, x2x4+x2+x3+x4, x2x3+x2, x1+ 1} It verifies (with CoCoA) that ∂ ∂x1π(N∧A→Mo) = x2(1 + x3)∈(aM) + I2 We think that is not really sensitive in N(every live being needs water), so we accept A→Mo, which is now sensitive. Reasoning similarly with the other one, it obtains {N, A →Mo, L →Mo}, a stem basis of sensitive implications. Sensitivity test can be also added when background knowledge exists. In this case, we deal with hard problems as consistency checking or entailment. It starts with Hand a background knowledge Γfor MH, that is, MH|=Γ. Or, in algebraic terms, V(aH)⊆V({1 + π(F) : F∈Γ}).The step to add is in given figure 3. Condition (∗) means 1 + ∂ ∂xp π(L)/∈({1 + π(F) : F∈Γ}) + I2 Extending Attribute Exploration by Means of Boolean Derivatives 127 (3) Sensitivity test: Test whether the implication is sensitive in all its arguments with the actual set Hand the background knowledge Γ, that is, whether for each attribute pin the antecedent of L Γ6|=L↔L{p/¬p}(∗) If it is not sensitive in some of them, the user must to react: – Giving o∈O, a witness of the sensitivity (which is added to H), that is vo|={∂ ∂p L} ∪ Γ(∗∗) – or else removing the attribute of the implication (he/she accepts it is not sensitive). Fig. 3. Sensitivity test with background knowledge Regarding to the existence of an object for (∗∗), if the user does not know one, but believes that it really exists, a model search program may be used to give an anonymous object. Test (∗∗) can be fairly translated into algebraic terms. 6 Attribute exploration with new attributes Now we propose how to extend the context by adding new attributes. Formally, one starts with M0, a subcontext with partial set of attributes, M0= (H, A0, I ∩(H×A0)),with A0(A Assume that, at some stage, full extents for a set H0of objects are introduced, with the aim of expanding the new attributes to initial objects of M0(see fig. 5). The user only knows -about the new attributesa background knowledge Γ, relating old and new attributes. Since it seems not advisable to add many arguments at once (to facilitate the answers of tests), Γwill be relatively small. It is important to observe that ∆=L ∪ Γ, where Lis the partial set of implications, may be inconsistent with ontological commitments implicitely or unconsciously accepted for the old attributes; that is, it may be false for M0, whenever the extents of Hwere expanded to the full attribute set. Thus one needs an expandability test for objects of H(to simplify assume that the new attributes are {pk+1, . . . , pn}): For each o≡(δ1, . . . , δk)of H, is there (δk+1, . . . δn)∈ {0,1}n−ksuch that {pj:δj= 1 ∧j∈ {1, . . . , n}} respects ∆? Theorem 6. Let Mbe an expansion of M0to the complete attribute set, with the same set of objects. If Γis a stem basis (respectively a background knowledge) for M, then ∂c {pk+1,...,pn}[Γ]is a complete set of implications (respectively ∂{pk+1,...,pn}[Γ]is a background knowledge) for M0. Proof. Assume that Γis a stem basis. Let Lbe an implication in the language A\ {pk+1, . . . , pn}. If M|=L, then Γ|=L. By corollary 1, ∂p[Γ]|=Lso by lemma 1, ∂c p[Γ]|=Lholds. If Γis a background knowledge, the result is a straightforward consequence of corollary 1. 128 Jos´e Antonio Alonso-Jim´enez, Gonzalo A. Aranda-Corral, Joaqu´ın BorregoD´ıaz, M. Magdalena Fern´andez-Lebr´on, M. Jos´e Hidalgo-Doblado (3) Expansion test: If implication has not been discarded, test whether the set of implications plus background knowledge is extendable to H. – If it is extendable, the user shall proceed: •Confirming the suggested implication, or •giving o∈Osuch that {o}0does not respect the implication. This is added to H0, and the implication is discarded. – Else, it must revise the background knowledge, or to discard the implication Fig. 4. Aditional step for exploration with new attributes Need water Aquatic Mobility Legs Cat 1 0 1 1 Leech 1 1 1 0 Frog 1 1 1 1 Maize 1 0 0 0 Fish 1 1 1 0 Need water Aquatic Mobility Legs Land Cat 1 0 1 1 ? Leech 1 1 1 0 ? Frog 1 1 1 1 ? Maize 1 0 0 0 ? Fish 1 1 1 0 0 Dog 1 0 1 1 1 Bean 1 0 0 0 1 Fig. 5. Extension of the context on live beings with new attributes Corollary 2. Let ∆⊆P Form. The following conditions are equivalent: (1) Every extension of objects of Hcan be expanded to the full attribute set, consistently with ∆. (2) {1 + π(F) : F∈∂{pk+1,...,pn}[∆]} ⊆ (aH) + I2 Assume now that it has previously certified that ∆is expandable to objects of H, and let Lbe a new implication. If ∆∪{L}can be consistently extended to H, but the user thinks that it is not true, in a first stage the user is required to give a counterexample for Lby completing the extention of some object of H(in this way it bounds the set of new examples), or, if he/she does not know which, a new example. Summarizing, the new step is shown in figure 4. For example, suppose that we decide to add a new attribute, to live in land (La). Some complete extensions are given (figure 5). We only know as background knowledge that aquatic live beings do not live in land, and we consider the implication every live being with legs and mobility lives in land, that is ∆={A→ ¬La, Le ∧Mo →La} In this case, π[∆] = {1 + xAxLa,1 + xLexMo +xLexMoxLa}. The set Hcan not be consistently expanded to a model of ∆, because ∂{xLa}[π[∆]] = {1 + xA+xAxLexM,1}and xA+xAxLexM/∈(aH) + I2. 6.1 A final remark: defining the new attributes We now see how to extend the above procedure for learning the new attribute. We suppose we have a stem basis consistent with old information; and, in a second stage, we wish to find a definition of the new attribute w.r.t the old ones Extending Attribute Exploration by Means of Boolean Derivatives 129