A probabilistic formal context is a triadic context whose third dimension 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 coincide, 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.
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 [
Firstly, for axiomatizing rules from formal contexts possibly containing wrong
incidences or having missing incidences the notion of a partial implication (also called
association rule) and confidence has been defined by Luxenburger in [12].
Furthermore, 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 [
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
experiment that has been repeated several times, since some effects could not be observed
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. [
The document is structured as follows. In Section 2 some basic notions for probabilistic 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 following 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
A probability measure P on a countable set W is a mapping P : 2W → [
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
define the derivations in world w as operators ·Iw : 2G → 2M and ·Iw : 2M → 2G where AIw := { m ∈ M | ∀g ∈ A : (g, m, w) ∈ I }
BIw := { g ∈ G | ∀m ∈ B : (g, m, w) ∈ I } for object sets A ⊆ G and attribute sets B ⊆ M, i.e., AIw is the set of all common attributes of all objects in A in the world w, and BIw is the set of all objects that have all attributes in B in w. 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 | XIw ⊆ YIw }.
Furthermore, we define the following properties for implications X → Y:
It is readily verified that P(X → Y) = P{ w ∈ Wε | XIw ⊆ YIw } = ∑{ P{ w } | w ∈ Wε and XIw ⊆ YIw }. 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
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 [
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×. 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:
Proof. It is readily verified that the following equivalences hold:
P(X → Y) = 1 ⇔ ∀w ∈ W : XIw ⊆ YIw ⇔ XI× = ]
w∈W ⇔ K× |= X → Y.
XIw × { w } ⊆ ] w∈W
YIw × { w } = YI× The second statement can be proven analogously.
Recall the notion of a pseudo-intent [
BK := { P → PI× I× | P ∈ PsInt(K×) }.
ε base for the almost certain implications of K, in particular this holds for the following implication set:
BK,1 := BK ∪ { P → PIε× 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:
2. X1 ⊆ X2 and Y1 ⊇ Y2 imply P(X1 → Y1) ≤ P(X2 → Y2). 3. X0 ⊆ X1 ⊆ . . . ⊆ Xn implies P(X0 → Xn) ≤ Vin=1 P(Xi−1 → Xi). Proof.
1. If Y ⊆ X, then XIw ⊆ YIw 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. 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
P(X0 → Xn−1) ≤ ^in=−11 P(Xi−1 → Xi).
Of course, it also holds that X0 ⊆ Xn−1 ⊆ Xn, and it follows by induction hypothesis and the previous inequality that
P(X0 → Xn) ≤ P(X0 → Xn−1) ∧ P(Xn−1 → Xn) ≤ ^n i=1 P(Xi−1 → Xi).
tu Lemma 8. Let K = (G, M, W, I, P) be a probabilistic formal context. Then for all implications X → Y the following equalities are valid:
P(X → Y) = P(XI× I× → YI× I× ) = P(XIε× Iε× → YIε× Iε× ).
Proof. Let X → Y be an implication. Then for all worlds w ∈ W it holds that g ∈ XIw ⇔ ∀m ∈ X : (g, m, w) ∈ I ⇔ ∀m ∈ X : ((g, w), m) ∈ I× ⇔ (g, w) ∈ XI× , and we conclude that XIw = π1(XI× ∩ (G × { w })). Furthermore, we then infer XIw = XI× I× Iw , and thus the following equations hold:
P(X → Y) = P{ w ∈ W | XIw ⊆ YIw }
= P{ w ∈ W | XI× I× Iw ⊆ YI× I× Iw } = P(XI× I× → YI× I× ).
it may be concluded that P(X → Y) = P(XIε× Iε× → YIε× Iε× ).
In particular, for all possible worlds w ∈ Wε it holds that g ∈ XIw ⇔ (g, w) ∈ XIε× , and thus XIw = π1(XIε× ∩ (G × { w })) and XIw = XIε× Iε× Iw are satisfied. Consequently, Lemma 9. Let K be a probabilistic formal context. Then the following statements hold:
follows from B ∪ { XI× I× → YI× I× }.
Proof. Of course, the implication X → XI× I× holds in K×, i.e., certainly holds in K by Lemma 5, and hence follows from B. Thus, the implication X → YI× I× is entailed by B ∪ { XI× I× → YI× I× }, and because of Y ⊆ YI× I× the claim follows.
The second statement follows analogously.
Lemma 10. Let K be a probabilistic formal context. Then the following statements hold: tu tu
YIε× Iε× Proof. First note that (XIε× Iε× ∪ YIε× Iε× )Iε× Iε× = (X ∪ Y)Iε× Iε× . As YIε× Iε× is a subset of (XIε× Iε× ∪ YIε× Iε× )Iε× Iε× , the implication (X ∪ Y)Iε× Iε× → YIε× Iε× certainly holds in K, cf. Statement 1 in Lemma 7.
Furthermore, we have that XIw ⊆ YIw if, and only if, XIw ⊆ XIw ∩ YIw = (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(XIε× Iε× → YIε× Iε× ) = P(X → Y) = P(X → X ∪ Y) = P(XIε× Iε× → (X ∪ Y)Iε× Iε× ). Obviously, { XIε× Iε× → (X ∪ Y)Iε× Iε× , (X ∪ Y)Iε× Iε× → YIε× Iε× } entails XIε× Iε× → YIε× Iε×. tu Lemma 11. Let K be a probabilistic formal context, and X, Y be intents of Kε× such that
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. tu 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 XIε× Iε× → YIε× Iε× have the same probability. Lemma 9 states that X → Y follows from BK,1 ∪ { XIε× Iε× According to Lemma 10, the implication XIε× Iε× → YIε× Iε× follows from { XIε× Iε× → → YIε× Iε× }. (X ∪ Y)Iε× Iε× , (X ∪ Y)Iε× Iε× → YIε× Iε× }. Furthermore, it holds that
P(XIε× Iε× → (X ∪ Y)Iε× Iε× ) = P(XIε× Iε× → YIε× Iε× ) = P(X → Y) ≥ p, starting at XIε× Iε× and ending at (X ∪ Y)Iε× Iε× , i.e., and the second implication (X ∪ Y)Iε× Iε× → YIε× Iε× certainly holds, i.e., follows from BK,1. Finally, Lemma 11 states that there is a chain of neighboring intents of K× ε
XIε× Iε× = X0Iε× Iε× ≺ X1Iε× Iε× ≺ X2Iε× Iε× ≺ . . . ≺ XnIε× Iε× = (X ∪ Y)Iε× Iε× , such that all implications XiI−ε×1Iε× → XiIε× Iε× have a probability ≥ p, and are thus contained in BK,p. Hence, BK,p entails the implication X → Y.
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→ 2 , { w2 } 7→ 21 }) whose 1 incidence relation I is defined as follows: 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, 12 = { ∅ → { m2 }, { m2 } → { m1, m2 } }.
However, the set B := { ∅ → { m1, m2 } } is also a probabilistic implicational base for K and 21 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 context that has this implication set as an implicational base, or directly compute all pseudoclosures 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 / XI , cf. [12]. In general, there is no correspondence 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: Then we have that P({ m2 } → { m1 }) = 12 and conf({ m2 } → { m1 }) = 31 , i.e., the confidence is smaller than the probability.
The Description Logic EL⊥ and Probabilistic Interpretations
This section gives a brief overview on the light-weight description logic EL⊥ [
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 interpretations: An interpretation is a tuple I = (ΔI , ·I ) that consists of a set ΔI , called domain, and an extension function ·I : NC ∪ NR → 2ΔI ∪ 2ΔI ×ΔI 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 }.
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.
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.
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.
any world.
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
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.
a threshold. A probabilistic base of GCIs for I and p is a TBox B that satisfies the following conditions:
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 } rI× := { ((d, w), (e, w)) | (d, e) ∈ rIw } (A ∈ NC), (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 [
(∃ 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.
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 .
the probability of the GCI d X v d Y in I, i.e., it hol→ds tYhaitnPth(eXin→ducYed)c=ontPex(tdKXI,Mv edquYal)s.
Proof. The following equivalences are satisfied for all Z ⊆ M and worlds w ∈ W: d ∈ ZIw ⇔ ∀C ∈ Z : (d, C, w) ∈ I ⇔ ∀C ∈ Z : d ∈ CIw ⇔ d ∈ (l Z)Iw . Now consider two subsets X, Y ⊆ M, then it holds that
P(X → Y) = P{ w ∈ W | XIw ⊆ YIw }
= P{ w ∈ W | (l X)Iw ⊆ (l Y)Iw } = P(l X v l Y).
Analogously to [
I
For an implication set B over a set M of EL⊥-concept descriptions we define its induced TBox by d B := { d X v d Y | X → Y ∈ B }. tu tu
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 )ε× = K × . Then according to Distel in [5, Theorem 5.12] it follows that
Iε the TBox d B0 is a base of GCIs for Iε×, i.e., a base for the almost certain GCIs of I. Consequently, d B is complete for the almost certain GCIs of I. tu
probabilistic implicational base for KI and p that contains an almost certain implicational base for KI , then d B is a probabilistic base of GCIs for I and p.
Proof. Consider a GCI d X v d Y ∈ d B. Then Lemma 17 yields that the implication X → Y and the GCI d X v d Y have the same probability. Since B is a probabilistic implicational base for KI and p, we conclude that P(d X v d Y) ≥ p is satisfied.
Assume that C v D is an arbitrary GCI with probability ≥ p. We have to show that d B entails C v D. Let J be an arbitrary model of d B. Consider an implication X → Y ∈ B, then d X v d Y ∈ d B holds, and hence it follows that (d X)J ⊆ (d Y)J . Consequently, the implication X → Y holds in the induced context KJ ,M . (We here mean the non-probabilistic formal context that is induced by
I
a non-probabilistic interpretation, cf. [
Furthermore, since all model-based most-specific concept descriptions of Iε× are
expressible in terms of M , we have that E ≡ d πM (E) holds for all mmscs E of Iε×,
cf. [
P(C v D) = P(CIε×Iε× v DIε×Iε× ) = P(l πM (CIε×Iε× ) v
I l πM (DIε×Iε× ))
I = P(πM (CIε×Iε× ) → πM (DIε×Iε× )).
I I Consequently, B entails the implication πM (CIε×Iε× ) → πM (DIε×Iε× ), hence it holds
I I in KJ ,MI , and furthermore the GCI CIε×Iε× v DIε×Iε× holds in J . As J is an arbitrary interpretation, d B entails CIε×Iε× v DIε×Iε× .
Corollary 18 yields that d B is complete for the almost certain GCIs of I. In particular, the GCI C v CIε×Iε× almost certainly holds in I, and hence follows from d B. We conclude that d B |= C v DIε×Iε× . Of course, the GCI DIε×Iε× v D holds in all interpretations. Finally, we conclude that d B entails C v D. tu
d BKI ,p is a probabilistic base of GCIs for I and p where BKI ,p is defined as in Theorem 12. 6
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 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
particular, [
The author thanks Sebastian Rudolph for proof reading and a fruitful discussion, and the anonymous reviewers for their constructive comments.