Probabilistic Implicational Bases in FCA and Probabilistic Bases of GCIs in EL⊥ Francesco Kriegel Institute for Theoretical Computer Science, TU Dresden, Germany francesco.kriegel@tu-dresden.de http://lat.inf.tu-dresden.de/˜francesco Abstract. A probabilistic formal context is a triadic context whose third dimen- sion is a set of worlds equipped with a probability measure. After a formal definition of this notion, this document introduces probability of implications, and provides a construction for a base of implications whose probability satisfy a given lower threshold. A comparison between confidence and probability of implications is drawn, which yields the fact that both measures do not coin- cide, and cannot be compared. Furthermore, the results are extended towards the light-weight description logic EL⊥ with probabilistic interpretations, and a method for computing a base of general concept inclusions whose probability fulfill a certain lower bound is proposed. Keywords: Formal Concept Analysis, Description Logics, Probabilistic Formal Context, Probabilistic Interpretation, Implication, General Concept Inclusion 1 Introduction Most data-sets from real-world applications contain errors and noise. Hence, for mining them special techniques are necessary in order to circumvent the expression of the errors. This document focuses on rule mining, especially we attempt to extract rules that are approximately valid in data-sets, or families of data-sets, respectively. There are at least two measures for the approximate soundness of rules, namely confidence and probability. While confidence expresses the number of counterexamples in a single data-set, probability expresses somehow the number of data-sets in a data-set family that do not contain any counterexample. More specifically, we consider implications in the formal concept analysis setting [7], and general concept inclusions (GCIs) in the description logics setting [1] (in the light-weight description logic EL⊥ ). Firstly, for axiomatizing rules from formal contexts possibly containing wrong in- cidences or having missing incidences the notion of a partial implication (also called association rule) and confidence has been defined by Luxenburger in [12]. Further- more, Luxenburger introduced a method for the computation of a base of all partial implications holding in a formal context whose confidence is above a certain threshold. In [2] Borchmann has extended the results to the description logic EL⊥ by adjusting the notion of confidence to GCIs, and also gave a method for the construction of a base of confident GCIs for an interpretation. Secondly, another perspective is a family of data-sets representing different views of the same domain, e.g., knowledge of different persons, or observations of an exper- iment that has been repeated several times, since some effects could not be observed c paper author(s), 2015. Published in Sadok Ben Yahia, Jan Konecny (Eds.): CLA 2015, pp. 193–204, ISBN 978–2–9544948–0–7, Blaise Pascal University, LIMOS laboratory, Clermont-Ferrand, 2015. Copying permitted only for private and academic purposes. 194 Francesco Kriegel in every case. In the field of formal concept analysis, Vityaev, Demin, and Ponomaryov, have introduced in probabilistic extensions of formal contexts and their formal concepts and implications, and furthermore gave some methods for their computation, cf. [4]. In [9] the author has shown some methods for the computation of a base of GCIs in probabilistic description logics where concept and role constructors are available to express probability directly in the concept descriptions. Here, we want to use another approach, and do not allow for probabilistic constructors, but define the notion of a probability of general concept inclusions in the light-weight description logic EL⊥ . Furthermore, we provide a method for the computation of a base of GCIs satisfying a certain lower threshold for the probability. More specifically, we use the description logic EL⊥ with probabilistic interpretations that have been introduced by Lutz and Schröder in [11]. Beforehand, we only consider conjunctions in the language of formal concept analysis, and define the notion of a probabilistic formal context in a more general form than in [4], and provide a technique for the computation of base of implications satisfying a given lower probability threshold. The document is structured as follows. In Section 2 some basic notions for probabilis- tic extensions of formal concept analysis are defined. Then, in Section 3 a method for the computation of a base for all implications satisfying a given lower probability threshold in a probabilistic formal context is developed, and its correctness is proven. The fol- lowing sections extend the results to the description logic EL⊥ . In particular, Section 4 introduces the basic notions for EL⊥ , and defines probabilistic interpretations. Section 5 shows a technique for the construction of a base of GCIs holding in a probabilistic interpretation and fulfilling a lower probability threshold. Furthermore, a comparison of the notions of confidence and probability is drawn at the end of Section 3. 2 Probabilistic Formal Concept Analysis A probability measure P on a countable set W is a mapping P: 2W → [0, 1] such that P(∅) = 0 and P(W ) = 1 hold, and P is σ-additive, i.e., S for all pairwise disjoint countable families (Un )n∈N with Un ⊆ W it holds that P( n∈N Un ) = ∑n∈N P(Un ). A world w ∈ W is possible if P{ w } > 0 holds, and impossible otherwise. The set of all possible worlds is denoted by Wε , and the set of all impossible worlds is denoted by W0. Obviously, Wε ] W0 is a partition of W. Definition 1 (Probabilistic Formal Context). A probabilistic formal context K is a tuple (G, M, W, I, P) that consists of a set G of objects, a set M of attributes, a countable set W of worlds, an incidence relation I ⊆ G × M × W, and a probability measure P on W. For a triple (g, m, w) ∈ I we say that object g has attribute m in world w. Furthermore, we define the derivations in world w as operators · Iw : 2G → 2M and · Iw : 2M → 2G where A Iw := { m ∈ M | ∀g ∈ A : (g, m, w) ∈ I } B Iw := { g ∈ G | ∀m ∈ B : (g, m, w) ∈ I } for object sets A ⊆ G and attribute sets B ⊆ M, i.e., A Iw is the set of all common attributes of all objects in A in the world w, and B Iw is the set of all objects that have all attributes in B in w. Probabilistic Implicational Bases and Probabilistic Bases of GCIs 195 Definition 2 (Implication, Probability). Let K = (G, M, W, I, P) be a probabilistic formal context. For attribute sets X, Y ⊆ M we call X → Y an implication over M, and its probability in K is defined as the measure of the set of worlds it holds in, i.e., P(X → Y) := P{ w ∈ W | X Iw ⊆ Y Iw }. Furthermore, we define the following properties for implications X → Y: 1. X → Y holds in world w of K if X Iw ⊆ Y Iw is satisfied. 2. X → Y certainly holds in K if it holds in all worlds of K. 3. X → Y almost certainly holds in K if it holds in all possible worlds of K. 4. X → Y possibly holds in K if it holds in a possible world of K. 5. X → Y is impossible in K if it does not hold in any possible world of K. 6. X → Y is refuted by K if does not hold in any world of K. It is readily verified that P(X → Y) = P{ w ∈ Wε | X Iw ⊆ Y Iw } = ∑{ P{ w } | w ∈ Wε and X Iw ⊆ Y Iw }. An implication X → Y almost certainly holds if P(X → Y) = 1, possibly holds if P(X → Y) > 0, and is impossible if P(X → Y) = 0. If X → Y certainly holds, then it is almost certain, and if X → Y is refuted, then it is impossible. 3 Probabilistic Implicational Bases At first we introduce the notion of a probabilistic implicational base. Then we will develop and prove a construction for such bases w.r.t. probabilistic formal contexts. If the underlying context is finite, then the base is computable. The reader should be aware of the standard notions of formal concept analysis in [7]. Recall that an implication follows from an implication set if, and only if, it can be syntactically deduced using the so-called Armstrong rules as follows: 1. From X ⊇ Y infer X → Y. 2. From X → Y and Y → Z infer X → Z. 3. From X1 → Y1 and X2 → Y2 infer X1 ∪ X2 → Y1 ∪ Y2. Definition 3 (Probabilistic Implicational Base). Let K = (G, M, W, I, P) be a proba- bilistic formal context, and p ∈ [0, 1] a threshold. A probabilistic implicational base for K and p is an implication set B over M that satisfies the following properties: 1. B is sound for K and p, i.e., P(X → Y) ≥ p holds for all implications X → Y ∈ B, and 2. B is complete for K and p, i.e., if P(X → Y) ≥ p, then X → Y follows from B. A probabilistic implicational base is irredundant if none of its implications follows from the others, and is minimal if it has minimal cardinality among all bases for K and p. It is readily verified that the above definition is a straight-forward generalization of implicational bases as defined in [7, Definition 37], in particular formal contexts coincide with probabilistic formal contexts having only one possible world, and implications holding in the formal context coincide with implications having probability 1. We now define a transformation from probabilistic formal contexts to formal contexts. It allows to decide whether an implication (almost) certainly holds, and furthermore it can be utilized to construct an implicational base for the (almost) certain implications. Definition 4 (Scaling). Let K be a probabilistic formal context. The certain scaling of K is the formal context K× := (G × W, M, I × ) where ((g, w), m) ∈ I × iff (g, m, w) ∈ I, and the almost certain scaling of K is the subcontext K× × ε := (G × Wε , M, Iε ) of K . × 196 Francesco Kriegel Lemma 5. Let K = (G, M, W, I, P) be a probabilistic formal context, and let X → Y be a formal implication. Then the following statements are satisfied: 1. X → Y certainly holds in K if, and only if, X → Y holds in K× . 2. X → Y almost certainly holds in K if, and only if, X → Y holds in K× ε . Proof. It is readily verified that the following equivalences hold: P(X → Y) = 1 ⇔ ∀w ∈ W : X Iw ⊆ Y Iw × ] ] × ⇔ XI = w∈W X Iw × { w } ⊆ w∈W Y Iw × { w } = Y I ⇔ K× |= X → Y. The second statement can be proven analogously. t u Recall the notion of a pseudo-intent [6–8]: An attribute set P ⊆ M of a formal context (G, M, I ) is a pseudo-intent if P 6= P II , and Q II ⊆ P holds for all pseudo-intents Q ( P. Furthermore, it is well-known that the canonical implicational base of a formal context (G, M, I ) consists of all implications P → P II where P is a pseudo-intent, cf. [6–8]. Consequently, the next corollary is an immediate consequence of Lemma 5. Corollary 6. Let K be a probabilistic formal context. Then the following statements hold: 1. An implicational base for K× is an implicational base for the certain implications of K, in particular this holds for the following implication set: × × BK := { P → P I I | P ∈ PsInt(K× ) }. 2. An implicational base for K× ε w.r.t. the background knowledge BK is an implicational base for the almost certain implications of K, in particular this holds for the following implication set: × × BK,1 := BK ∪ { P → P Iε Iε | P ∈ PsInt(K× ε , BK ) }. Lemma 7. Let K = (G, M, W, I, P) be a probabilistic formal context. Then the following statements are satisfied: 1. Y ⊆ X implies that X → Y certainly holds in K. 2. X1 ⊆ X2 and Y1 ⊇ Y2 imply P(X1 → Y1 ) ≤ PV (X2 → Y2 ). 3. X0 ⊆ X1 ⊆ . . . ⊆ Xn implies P(X0 → Xn ) ≤ in=1 P(Xi−1 → Xi ). Proof. 1. If Y ⊆ X, then X Iw ⊆ Y Iw follows for all worlds w ∈ W. 2. Assume X1 ⊆ X2 and Y2 ⊆ Y1. Then X1Iw ⊇ X2Iw and Y2Iw ⊇ Y1Iw follow for all worlds w ∈ W. Consider a world w ∈ W where X1Iw ⊆ Y1Iw . Of course, we may conclude that X2Iw ⊆ Y2Iw . As a consequence we get P(X1 → Y1 ) ≤ P(X2 → Y2 ). 3. We prove the third claim by induction on n. For n = 0 there is nothing to show, and the case n = 1 is trivial. Hence, consider n = 2 for the induction base, and let X0 ⊆ X1 ⊆ X2. Then we have that X0Iw ⊇ X1Iw ⊇ X2Iw is satisfied in all worlds w ∈ W. Now consider a world w ∈ W where X0Iw ⊆ X2Iw is true. Probabilistic Implicational Bases and Probabilistic Bases of GCIs 197 Of course, it then follows that X0Iw ⊆ X1Iw ⊆ X2Iw . Consequently, we conclude P(X0 → X2 ) ≤ P(X0 → X1 ) and P(X0 → X2 ) ≤ P(X1 → X2 ). For the induction step let n > 2. The induction hypothesis yields that ^n−1 P(X0 → Xn−1 ) ≤ P(Xi−1 → Xi ). i=1 Of course, it also holds that X0 ⊆ Xn−1 ⊆ Xn , and it follows by induction hypothesis and the previous inequality that ^n P(X0 → Xn ) ≤ P(X0 → Xn−1 ) ∧ P(Xn−1 → Xn ) ≤ P(Xi−1 → Xi ). t u i=1 Lemma 8. Let K = (G, M, W, I, P) be a probabilistic formal context. Then for all implica- tions X → Y the following equalities are valid: × × × × × × × × P(X → Y) = P(X I I → Y I I ) = P(X Iε Iε → Y Iε Iε ). Proof. Let X → Y be an implication. Then for all worlds w ∈ W it holds that × g ∈ X Iw ⇔ ∀m ∈ X : (g, m, w) ∈ I ⇔ ∀m ∈ X : ((g, w), m) ∈ I × ⇔ (g, w) ∈ X I , × and we conclude that X Iw = π1 (X I ∩ (G × { w })). Furthermore, we then infer × × X Iw = X I I Iw , and thus the following equations hold: P(X → Y) = P{ w ∈ W | X Iw ⊆ Y Iw } × × × × × × × × = P{ w ∈ W | X I I Iw ⊆ Y I I Iw } = P(X I I → Y I I ). × In particular, for all possible worlds w ∈ Wε it holds that g ∈ X Iw ⇔ (g, w) ∈ X Iε , and × × × thus X Iw = π1 (X Iε ∩ (G × { w })) and X Iw = X Iε Iε Iw are satisfied. Consequently, × × × × it may be concluded that P(X → Y) = P(X Iε Iε → Y Iε Iε ). t u Lemma 9. Let K be a probabilistic formal context. Then the following statements hold: 1. If B is an implicational base for the certain implications of K, then the implication X → Y × × × × follows from B ∪ { X I I → Y I I }. 2. If B is an implicational base for the almost certain implications of K, then the implication × × × × X → Y follows from B ∪ { X Iε Iε → Y Iε Iε }. × × Proof. Of course, the implication X → X I I holds in K× , i.e., certainly holds in K × × by Lemma 5, and hence follows from B. Thus, the implication X → Y I I is entailed × × × × × × by B ∪ { X I I → Y I I }, and because of Y ⊆ Y I I the claim follows. The second statement follows analogously. t u Lemma 10. Let K be a probabilistic formal context. Then the following statements hold: × × × × × × × × 1. P(X Iε Iε → Y Iε Iε ) = P(X Iε Iε → (X ∪ Y) Iε Iε ), × × × × 2. (X ∪ Y) Iε Iε → Y Iε Iε certainly holds in K, and 198 Francesco Kriegel × × × × × × × × × × × × 3. X Iε Iε → Y Iε Iε is entailed by { X Iε Iε → (X ∪ Y) Iε Iε , (X ∪ Y) Iε Iε → Y Iε Iε }. × × (X ∪ Y) Iε Iε p × × × × X Iε Iε p Y Iε Iε × × × × × × × × × × Proof. First note that (X Iε Iε ∪ Y Iε Iε ) Iε Iε = (X ∪ Y) Iε Iε . As Y Iε Iε is a subset of × × × × × × × × × × (X Iε Iε ∪ Y Iε Iε ) Iε Iε , the implication (X ∪ Y) Iε Iε → Y Iε Iε certainly holds in K, cf. Statement 1 in Lemma 7. Furthermore, we have that X Iw ⊆ Y Iw if, and only if, X Iw ⊆ X Iw ∩ Y Iw = (X ∪ Y) Iw . Hence, the implication X → Y has the same probability as X → X ∪ Y. Consequently, we may conclude by means of Lemma 7 that × × × × × × × × P(X Iε Iε → Y Iε Iε ) = P(X → Y) = P(X → X ∪ Y) = P(X Iε Iε → (X ∪ Y) Iε Iε ). × × × × × × × × × × × × Obviously, { X Iε Iε → (X ∪ Y) Iε Iε , (X ∪ Y) Iε Iε → Y Iε Iε } entails X Iε Iε → Y Iε Iε . t u Lemma 11. Let K be a probabilistic formal context, and X, Y be intents of K× ε such that X ⊆ Y and P(X → Y) ≥ p. Then the following statements are true: 1. There is a chain of neighboring intents X = X0 ≺ X1 ≺ X2 ≺ . . . ≺ Xn = Y in K× ε , 2. P(Xi−1 → Xi ) ≥ p for all i ∈ { 1, . . . , n }, and 3. X → Y is entailed by { Xi−1 → Xi | i ∈ { 1, . . . , n } }. Proof. The existence of a chain X = X0 ≺ X1 ≺ X2 ≺ . . . ≺ Xn−1 ≺ Xn = Y of neighboring intents between X and Y in K× ε follows from X ⊆ Y. From Statement 3 in Lemma 7 it follows that all implications Xi−1 → Xi have a probability of at least p in K. It is trivial that they entail X → Y. t u Theorem 12 (Probabilistic Implicational Base). Let K be a probabilistic formal context, and p ∈ [0, 1) a probability threshold. Then the following implication set is a probabilistic implicational base for K and p: BK,p := BK,1 ∪ { X → Y | X, Y ∈ Int(K× ε ) and X ≺ Y and P(X → Y) ≥ p }. Proof. All implications in BK,1 hold almost certainly in K, and thus have probability 1. By construction, all other implications X → Y in the second subset have a probability ≥ p. Hence, Statement 1 in Definition 3 is satisfied. Now consider an implication X → Y over M such that P(X → Y) ≥ p. We have to prove Statement 2 of Definition 3, i.e., that X → Y is entailed by BK,p . × × × × Lemma 8 yields that both implications X → Y and X Iε Iε → Y Iε Iε have the same × × × × probability. Lemma 9 states that X → Y follows from BK,1 ∪ { X Iε Iε → Y Iε Iε }. × × × × × × According to Lemma 10, the implication X Iε Iε → Y Iε Iε follows from { X Iε Iε → × × × × × × (X ∪ Y) Iε Iε , (X ∪ Y) Iε Iε → Y Iε Iε }. Furthermore, it holds that × × × × × × × × P(X Iε Iε → (X ∪ Y) Iε Iε ) = P(X Iε Iε → Y Iε Iε ) = P(X → Y) ≥ p, Probabilistic Implicational Bases and Probabilistic Bases of GCIs 199 × × × × and the second implication (X ∪ Y) Iε Iε → Y Iε Iε certainly holds, i.e., follows from BK,1. Finally, Lemma 11 states that there is a chain of neighboring intents of K× ε × × × × starting at X Iε Iε and ending at (X ∪ Y) Iε Iε , i.e., × × I× I× I× I× I× I× I× I× × × X Iε Iε = X0ε ε ≺ X1ε ε ≺ X2ε ε ≺ . . . ≺ Xnε ε = (X ∪ Y) Iε Iε , I× I× I× I× such that all implications Xi−1 → Xi ε ε ε ε have a probability ≥ p, and are thus con- tained in BK,p . Hence, BK,p entails the implication X → Y. t u Corollary 13. Let K be a probabilistic formal context. Then the following set is an implica- tional base for the possible implications of K: BK,ε := BK,1 ∪ { X → Y | X, Y ∈ Int(K× ε ) and X ≺ Y and P(X → Y) > 0 }. However, it is not possible to show irredundancy or minimality for the base of probabilistic implications given above in Theorem 12. Consider the probabilistic formal context K = ({ g1, g2 }, { m1, m2 }, { w1, w2 }, I, { { w1 } 7→ 12 , { w2 } 7→ 12 }) whose incidence relation I is defined as follows: w1 m1 m2 w2 m1 m2 (G × W, { m2 }) g1 × × g1 × × g2 × g2 × × ({ (g1, w1 ), (g1, w2 ), (g2, w2 ) }, { m1, m2 }) The only pseudo-intent of K× is ∅, and the concept lattice of K× is shown above. Hence, we have the following probabilistic implicational base for p = 12 : BK, 1 = { ∅ → { m2 }, { m2 } → { m1, m2 } }. 2 However, the set B := { ∅ → { m1, m2 } } is also a probabilistic implicational base for K and 12 with less elements. In order to compute a minimal base for the implications holding in a probabilistic formal context with a probability ≥ p, one can for example determine the above given probabilistic base, and minimize it by means of constructing the Duquenne-Guigues base of it. This either requires the transformation of the implication set into a formal con- text that has this implication set as an implicational base, or directly compute all pseudo- closures of the closure operator induced by the (probabilistic) implicational base. Recall that the confidence of an implication X → Y in a formal context (G, M, I ) is defined as conf (X → Y) := (X ∪ Y) I / X I , cf. [12]. In general, there is no corre- spondence between the probability of an implication in K and its confidence in K× or K× ε . To prove this we will provide two counterexamples. As first counterexample we consider the context K above. It is readily verified that P({ m2 } → { m1 }) = 21 and conf ({ m2 } → { m1 }) = 34 , i.e., the confidence is greater than the probability. Furthermore, consider the following modification of K as second counterexample: w1 m1 m2 w2 m1 m2 g1 × × g1 × g2 g2 × Then we have that P({ m2 } → { m1 }) = 12 and conf ({ m2 } → { m1 }) = 31 , i.e., the confidence is smaller than the probability. 200 Francesco Kriegel 4 The Description Logic EL⊥ and Probabilistic Interpretations This section gives a brief overview on the light-weight description logic EL⊥ [1]. First, assume that ( NC , NR ) is a signature, i.e., NC is a set of concept names, and NR is a set of role names, respectively. Then EL⊥ -concept descriptions C over ( NC , NR ) may be constructed according to the following inductive rule (where A ∈ NC and r ∈ NR ): C ::= ⊥ | > | A | C u C | ∃ r. C. We shall denote the set of all EL⊥ -concept descriptions over ( NC , NR ) by EL⊥ ( NC , NR ). Second, the semantics of EL⊥ -concept descriptions is defined by means of interpre- tations: An interpretation is a tuple I = (∆I , ·I ) that consists of a set ∆I , called domain, I I I and an extension function ·I : NC ∪ NR → 2∆ ∪ 2∆ ×∆ that maps concept names A ∈ NC to subsets AI ⊆ ∆I and role names r ∈ NR to binary relations rI ⊆ ∆I × ∆I . The extension function is extended to all EL⊥ -concept descriptions as follows: ⊥I := ∅, >I := ∆I , (C u D)I := CI ∩ DI , (∃ r. C)I := { d ∈ ∆I | ∃e ∈ ∆I : (d, e) ∈ rI and e ∈ CI }. A general concept inclusion (GCI) in EL⊥ is of the form C v D where C and D are EL⊥ - concept descriptions. It holds in an interpretation I if CI ⊆ DI is satisfied, and we then also write I |= C v D, and say that I is a model of C v D. Furthermore, C is subsumed by D if C v D holds in all interpretations, and we shall denote this by C v D, too. A TBox is a set of GCIs, and a model of a TBox is a model of all its GCIs. A TBox T entails a GCI C v D, denoted by T |= C v D, if every model of T is a model of C v D. To introduce probability into the description logic EL⊥ , we now present the notion of a probabilistic interpretation from [11]. It is simply a family of interpretations over the same domain and the same signature, indexed by a set of worlds that is equipped with a probability measure. Definition 14 (Probabilistic Interpretation, [11]). Let ( NC , NR ) be a signature. A prob- abilistic interpretation I is a tuple (∆I , (·Iw )w∈W , W, P) consisting of a set ∆I , called domain, a countable set W of worlds, a probability measure P on W, and an extension function ·Iw for each world w ∈ W, i.e., (∆I , ·Iw ) is an interpretation for each w ∈ W. For a general concept inclusion C v D its probability in I is defined as follows: P(C v D) := P{ w ∈ W | CIw ⊆ DIw }. Furthermore, for a GCI C v D we define the following properties (as for probabilistic formal contexts): 1. C v D holds in world w if CIw ⊆ DIw . 2. C v D certainly holds in I if it holds in all worlds. 3. C v D almost certainly holds in I if it holds in all possible worlds. 4. C v D possibly holds in I if it holds in a possible world. 5. C v D is impossible in I if it does not hold in any possible world. 6. C v D is refuted by I if it does not hold in any world. Probabilistic Implicational Bases and Probabilistic Bases of GCIs 201 It is readily verified that P(C v D) = P{ w ∈ Wε | CIw ⊆ DIw } = ∑{ P{ w } | w ∈ Wε and CIw ⊆ DIw } for all general concept inclusions C v D. 5 Probabilistic Bases of GCIs In the following we construct from a probabilistic interpretation I a base of GCIs that entails all GCIs with a probability greater than a given threshold p w.r.t. I . Definition 15 (Probabilistic Base). Let I be a probabilistic interpretation, and p ∈ [0, 1] a threshold. A probabilistic base of GCIs for I and p is a TBox B that satisfies the following conditions: 1. B is sound for I and p, i.e., P(C v D) ≥ p for all GCIs C v D ∈ B, and 2. B is complete for I and p, i.e., if P(C v D) ≥ p, then B |= C v D. A probabilistic base B is irredundant if none of its GCIs follows from the others, and is minimal if it has minimal cardinality among all probabilistic bases for I and p. For a probabilistic interpretation I we define its certain scaling as the disjoint union × of all interpretations Iw with w ∈ W, i.e., as the interpretation I × := (∆I × W, ·I ) whose extension mapping is given as follows: × AI := { (d, w) | d ∈ AIw } ( A ∈ NC ), I× : Iw r = { ((d, w), (e, w)) | (d, e) ∈ r } (r ∈ NR ). Furthermore, the almost certain scaling Iε× of I is the disjoint union of all interpretations Iw where w ∈ Wε is a possible world. Analogously to Lemma 5, a GCI C v D certainly holds in I iff it holds in I × , and almost certainly holds in I iff it holds in Iε× . In [5] the so-called model-based most-specific concept descriptions (mmscs) have been defined w.r.t. greatest fixpoint semantics as follows: Let J be an interpretation, and X ⊆ ∆J . Then a concept description C is a mmsc of X in J , if X ⊆ CJ is satisfied, and C v D for all concept descriptions D with X ⊆ DJ . It is easy to see that all mmscs of X are unique up to equivalence, and hence we denote the mmsc of X in J by XJ . Please note that there is also a role-depth bounded variant w.r.t. descriptive semantics given in [3]. Lemma 16. Let I be a probabilistic interpretation. Then the following statements hold: × 1. CIw × { w } = CI ∩ (∆I × { w }) for all concept descriptions C and worlds w ∈ W. × 2. CIw × { w } = CIε ∩ (∆I × { w }) for all concept descriptions C and possible worlds w ∈ Wε . × × × × × × × × 3. P(C v D) = P(CI I v DI I ) = P(CIε Iε v DIε Iε ) for all GCIs C v D. Proof. 1. We prove the claim by structural induction on C. By definition, the statement holds for ⊥, >, and all concept names A ∈ NC . Consider a conjunction C u D, then (C u D)Iw × { w } = (CIw ∩ DIw ) × { w } = CIw × { w } ∩ DIw × { w } I.H. I × × =C ∩ DI ∩ (∆I × { w }) × = (C u D)I ∩ (∆I × { w }). 202 Francesco Kriegel For an existential restriction ∃ r. C the following equalities hold: (∃ r. C)Iw × { w } = { d ∈ ∆I | ∃e ∈ ∆I : (d, e) ∈ rIw and e ∈ CIw } × { w } × = { (d, w) | ∃(e, w) : ((d, w), (e, w)) ∈ rI and (e, w) ∈ CIw × { w } } I.H. × × = { (d, w) | ∃(e, w) : ((d, w), (e, w)) ∈ rI and (e, w) ∈ CI } × = (∃ r. C)I ∩ (∆I × { w }). 2. analogously. 3. Using the first statement we may conclude that the following equalities hold: P(C v D) = P{ w ∈ W | CIw × { w } ⊆ DIw × { w } } × × = P{ w ∈ W | CI ∩ (∆I × { w }) ⊆ DI ∩ (∆I × { w }) } × × × × × × = P{ w ∈ W | CI I I ∩ (∆I × { w }) ⊆ DI I I ∩ (∆I × { w }) } × × × × = P{ w ∈ W | CI I Iw × { w } ⊆ DI I Iw × { w } } × × × × = P(CI I v DI I ). The second equality follows analogously. t u For a probabilistic interpretation I = (∆I , ·I , W, P) and a set M of EL⊥ -concept descriptions we define their induced context as the probabilistic formal context KI ,M := (∆I , M, W, I, P) where (d, C, w) ∈ I iff d ∈ CIw . Lemma 17. Let I be a probabilistic interpretation, M a set of EL⊥ -concept descriptions, and X, Y ⊆ M. Then the probability d ofdthe implication X → Y in the induced contextdKI ,M equals d the probability of the GCI X v Y in I , i.e., it holds that P(X → Y) = P( X v Y). Proof. The following equivalences are satisfied for all Z ⊆ M and worlds w ∈ W: l d ∈ Z Iw ⇔ ∀C ∈ Z : (d, C, w) ∈ I ⇔ ∀C ∈ Z : d ∈ CIw ⇔ d ∈ ( Z)Iw . Now consider two subsets X, Y ⊆ M, then it holds that P(X → Y) = P{ w ∈ W | X Iw ⊆ Y Iw } l l l l = P{ w ∈ W | ( X)Iw ⊆ ( Y)Iw } = P( X v Y). t u Analogously to [5], the context KI is defined as KI ,MI with the following attributes: × MI := { ⊥ } ∪ NC ∪ { ∃ r. XIε | ∅ 6= X ⊆ ∆I × Wε }. ⊥ For an implication d set Bdover adset M of EL -concept descriptions we define its induced TBox by B := { X v Y | X → Y ∈ B }. Probabilistic Implicational Bases and Probabilistic Bases of GCIs 203 d Corollary 18. If B contains an almost certain implicational base for KI , then B is complete for the almost certain GCIs of I . Proof. We know that a GCI almost certainly holds in I if, and only if, it holds in Iε× . Let B0 ⊆ B be an almost certain implicational base for KI , i.e., an implicational base for (KI )× = KIε× . Then according to Distel in [5, Theorem 5.12] it follows that d ε the TBox B 0 d is a base of GCIs for Iε× , i.e., a base for the almost certain GCIs of I . Consequently, B is complete for the almost certain GCIs of I . t u Theorem 19. Let I be a probabilistic interpretation, and p ∈ [0, 1] a threshold. If B is a probabilistic implicational d base for KI and p that contains an almost certain implicational base for KI , then B is a probabilistic base of GCIs for I and p. d d d Proof. Consider a GCId X vd Y ∈ B. Then Lemma 17 yields that the implication X → Y and the GCI X v Y have the same probability. d Since d B is a probabilistic implicational base for KI and p, we conclude that P( X v Y) ≥ p is satisfied. Assume d that C v D is an arbitrary GCI with probabilityd≥ p. We have to show that B entails C v D. LetdJ be an d arbitrary d model of B. Consider an impli- cation X → Y ∈ B, then X v Y ∈ B holds, and hence it follows that d J d J ( X) ⊆ ( Y) . Consequently, the implication X → Y holds in the induced con- text KJ ,MI . (We here mean the non-probabilistic formal context that is induced by a non-probabilistic interpretation, cf. [2, 3, 5].) Furthermore, since all model-based most-specific d concept descriptions of Iε× are expressible in terms of MI , we have that E ≡ π MI (E) holds for all mmscs E of Iε× , cf. [2, 3, 5]. Hence, we may conclude that × × × × P(C v D) = P(CIε Iε v DIε Iε ) l × × l × × = P( π MI (CIε Iε ) v π MI (DIε Iε )) × × × × = P(π MI (CIε Iε ) → π MI (DIε Iε )). × × × × Consequently, B entails the implication π MI (CIε Iε ) → π MI (DIε Iε ), hence it holds × × × × in KJ ,MI , and furthermore the GCI CIε Iε v DIε Iε holds in J . As J is an arbitrary d × × × × Iε Iε v DIε Iε . interpretation, B entails C d Corollary 18 yields that B is complete for the almost certain GCIs of I . In par- × × d ticular, the GCI C v CIε Iε almost certainly holds in I , and hence follows from B. d × × × × We conclude that B |= C v DIε Iε . Ofdcourse, the GCI DIε Iε v D holds in all interpretations. Finally, we conclude that B entails C v D. t u Corollary d 20. Let I be a probabilistic interpretation, and p ∈ [0, 1] a threshold. Then BKI ,p is a probabilistic base of GCIs for I and p where BKI ,p is defined as in Theorem 12. 6 Conclusion We have introduced the notion of a probabilistic formal context as a triadic context whose third dimension is a set of worlds equipped with a probability measure. Then 204 Francesco Kriegel the probability of implications in such probabilistic formal contexts was defined, and a construction of a base of implications whose probability exceeds a given threshold has been proposed, and its correctness has been verified. Furthermore, the results have been applied to the light-weight description logic EL⊥ with probabilistic interpretations, and so we formulated a method for the computation of a base of general concept inclusions whose probability satisfies a given lower threshold. For finite input data-sets all of the provided constructions are computable. In partic- ular, [3, 5] provide methods for the computation of model-based most-specific concept descriptions, and the algorithms in [6, 10] can be utilized to compute concept lattices and canonical implicational bases (or bases of GCIs, respectively). The author thanks Sebastian Rudolph for proof reading and a fruitful discussion, and the anonymous reviewers for their constructive comments. References [1] Franz Baader et al., eds. The Description Logic Handbook: Theory, Implementation, and Applications. New York, NY, USA: Cambridge University Press, 2003. [2] Daniel Borchmann. “Learning Terminological Knowledge with High Confidence from Erroneous Data”. PhD thesis. TU Dresden, Germany, 2014. [3] Daniel Borchmann, Felix Distel, and Francesco Kriegel. Axiomatization of General Concept Inclusions from Finite Interpretations. LTCS-Report 15-13. Chair for Automata Theory, Institute for Theoretical Computer Science, TU Dresden, Germany, 2015. [4] Alexander V. Demin, Denis K. Ponomaryov, and Evgenii Vityaev. “Probabilistic Concepts in Formal Contexts”. In: Perspectives of Systems Informatics - 8th International Andrei Ershov Memorial Conference, PSI 2011, Novosibirsk, Russia, June 27-July 1, 2011, Revised Selected Papers. Ed. by Edmund M. Clarke, Irina Virbitskaite, and Andrei Voronkov. Vol. 7162. Lecture Notes in Computer Science. Springer, 2011, pp. 394–410. [5] Felix Distel. “Learning Description Logic Knowledge Bases from Data using Methods from Formal Concept Analysis”. PhD thesis. TU Dresden, Germany, 2011. [6] Bernhard Ganter. “Two Basic Algorithms in Concept Analysis”. In: Formal Concept Analysis, 8th International Conference, ICFCA 2010, Agadir, Morocco, March 15-18, 2010. Proceedings. Ed. by Léonard Kwuida and Baris Sertkaya. Vol. 5986. Lecture Notes in Computer Science. Springer, 2010, pp. 312–340. [7] Bernhard Ganter and Rudolf Wille. Formal Concept Analysis - Mathematical Foundations. Springer, 1999. [8] Jean-Luc Guigues and Vincent Duquenne. “Famille minimale d’implications informatives résultant d’un tableau de données binaires”. In: Mathématiques et Sciences Humaines 95 (1986), pp. 5–18. [9] Francesco Kriegel. “Axiomatization of General Concept Inclusions in Probabilistic Descrip- tion Logics”. In: Proceedings of the 38th German Conference on Artificial Intelligence, KI 2015, Dresden, Germany, September 21-25, 2015. Vol. 9324. Lecture Notes in Artificial Intelligence. Springer Verlag, 2015. [10] Francesco Kriegel. NextClosures – Parallel Exploration of Constrained Closure Operators. LTCS- Report 15-01. Chair for Automata Theory, Institute for Theoretical Computer Science, TU Dresden, Germany, 2015. [11] Carsten Lutz and Lutz Schröder. “Probabilistic Description Logics for Subjective Uncer- tainty”. In: Principles of Knowledge Representation and Reasoning: Proceedings of the Twelfth International Conference, KR 2010, Toronto, Ontario, Canada, May 9-13, 2010. Ed. by Fangzhen Lin, Ulrike Sattler, and Miroslaw Truszczynski. AAAI Press, 2010. [12] Michael Luxenburger. “Implikationen, Abhängigkeiten und Galois Abbildungen”. PhD thesis. TH Darmstadt, Germany, 1993.