Epistemic and Statistical Probabilistic Ontologies Fabrizio Riguzzi, Elena Bellodi, Evelina Lamma, and Riccardo Zese ENDIF – University of Ferrara, Via Saragat 1, I-44122, Ferrara, Italy {fabrizio.riguzzi,elena.bellodi,evelina.lamma}@unife.it riccardo.zese@student.unife.it Abstract. We present DISPONTE, a semantics for probabilistic on- tologies that is based on the distribution semantics for probabilistic logic programs. In DISPONTE the axioms of a probabilistic ontology can be annotated with an epistemic or a statistical probability. The epistemic probability represents a degree of confidence in the axiom, while the statistical probability considers the populations to which the axiom is applied. 1 Introduction Uncertainty has been recognized as an important feature for the Semantic Web [36, 24]. In order to be able to represent and reason with probabilistic knowledge, various authors have advocated the use of probabilistic ontologies, see e.g. [26], and many proposals have been put forward for allowing ontology languages, and OWL in particular, to represent uncertainty [30, 10, 22, 23]. The integration of probability into logic has been much studied lately, with many different proposals. In the field of logic programming, the distribution semantics [33] has emerged as one of the most effective approaches [33, 28, 8]. In [3] we applied this approach to ontological languages and, in particular, to the OWL DL fragment, that is based on the description logic SHOIN (D). We called the approach DISPONTE for “DIstribution Semantics for Probabilis- tic ONTologiEs” (Spanish for “get ready”). The idea is to annotate axioms of a theory with a probability and assume that each axiom is independent of the oth- ers. In this paper we extend DISPONTE by considering two types of probabilistic annotations, an epistemic type, that represents a degree of belief in the axiom as a whole as in [3], and a new statistical type, that considers the populations to which the axiom is applied. Statistical probabilities allow to represent partial concept overlapping and knowledge on random individuals of populations. The two types of probability can be used separately or jointly in the same OWL DL knowledge base. The probability of a query is computed from a covering set of explanations by solving the disjoint sum problem. The paper is organized as follows. Section 2 introduces Description Logics. Section 3 presents DISPONTE and explains the principles on which it is based, while Section 4 illustrates approaches for performing reasoning. Section 5 de- scribes related work and, finally, Section 6 concludes the paper. 2 Description Logics Description Logics (DLs) are knowledge representation formalisms that possess nice computational properties such as decidability and/or low complexity, see [1, 2] for excellent introductions. DLs are particularly useful for representing ontologies and have been adopted as the basis of the Semantic Web. For example, the OWL DL sublanguage of OWL is based on the SHOIN (D) DL. While DLs can be translated into predicate logic, they are usually represented using a syntax based on concepts and roles. A concept corresponds to a set of individuals of the domain while a role corresponds to a set of couples of individuals of the domain. In order to illustrate DLs, we now describe SHOIN following [24]. Let A, R and I be sets of atomic concepts, roles and individuals, respectively. A role is either an atomic role R ∈ R or the inverse R− of an atomic role R ∈ R. We use R− to denote the set of all inverses of roles in R. An RBox R consists of a finite set of transitivity axioms T rans(R), where R ∈ R, and role inclusion axioms R v S, where R, S ∈ R ∪ R− . Concepts are defined by induction as follows. Each A ∈ A is a concept, ⊥ and > are concepts, and if a ∈ I, then {a} is a concept. If C, C1 and C2 are concepts and R ∈ R ∪ R− , then (C1 u C2 ), (C1 t C2 ), and ¬C are concepts, as well as ∃R.C, ∀R.C, n ≥ R and n ≤ R for an integer n ≥ 0. A TBox T is a finite set of concept inclusion axioms C v D, where C and D are concepts. We use C ≡ D to abbreviate C v D and D v C. An ABox A is a finite set of concept membership axioms a : C, role membership axioms (a, b) : R, equality axioms a = b, and inequality axioms a 6= b, where C is a concept, R ∈ R and a, b ∈ I. A knowledge base K = (T , R, A) consists of a TBox T , an RBox R and an ABox A. SHOIN is decidable iff there are no number restrictions on non-simple roles. A role is non-simple iff it is transitive or it has transitive subroles. A knowledge base K is usually assigned a semantics in terms of set-theoretic interpretations and models of the form I = (∆I , ·I ). The semantics of DLs can be given equivalently by transforming a DL knowledge base into a predicate logic theory and then using the model-theoretic semantics of the resulting theory. A translation of SHOIN into First Order Logic with Counting Quantifiers is given in the following as an extension of the one given in [34]. The translation uses two functions πx and πy that map concept expressions to logical formulas, where πx is given by πx (A) = A(x) πx (¬C) = ¬πx (C) πx ({a}) = (x = a) πx (C u D) = πx (C) ∧ πx (D) πx (C t D) = πx (C) ∧ πx (D) πx (∃R.C) = ∃y.R(x, y) ∧ πy (C) πx (∃R− .C) = ∃y.R(y, x) ∧ πy (C) πx (∀R.C) = ∀y.R(x, y) → πy (C) πx (∀R− .C) = ∀y.R(y, x) → πy (C) πx (≥ nR) = ∃≥n y.R(x, y) πx (≥ nR− ) = ∃≥n y.R(y, x) πx (≤ nR) = ∃≤n y.R(x, y) πx (≤ nR− ) = ∃≤n y.R(y, x) and πy is obtained from πx by replacing x with y and vice-versa. Table 1 shows the translation of each axiom of SHOIN knowledge bases. Axiom Translation CvD ∀x.πx (C) → πx (D) RvS ∀x, y.R(x, y) → S(x, y) T rans(R) ∀x, y, z.R(x, z) ∧ R(z, y) → S(x, y) a:C C(a) (a, b) : R R(a, b) a=b a=b a 6= b a 6= b Table 1. Translation of SHOIN axioms into predicate logic. SHOIN (D) adds to SHOIN datatype roles, i.e., roles that map an individ- ual to an element of a datatype such as integers, floats, etc. Then new concept definitions, involving datatype roles, are added, that mirror those involving roles introduced above. We also assume that we have predicates over the datatypes. A query over a knowledge base is usually an axiom for which we want to test the entailment from the knowledge base. The entailment test may be reduced to checking the satisfiability of a concept in the knowledge base, i.e., the non- emptiness of the concept. For example, the entailment of the axiom C v D may be tested by checking the satisfiability of the concept C u ¬D. 3 The DISPONTE Semantics for Probabilistic Ontologies A probabilistic knowledge base is a set of certain axioms, that take the form of DL axioms, of epistemic probabilistic axioms of the form p ::e E (1) where p is a real number in [0, 1] and E is a TBox, RBox or ABox axiom, and of statistical probabilistic axioms of the form p ::s E (2) where p is a real number in [0, 1] and E is a TBox or RBox axiom. In axioms of the form (1), the notation ::e introduces probability p as an epistemic probability, i.e., as the degree of our belief in axiom E, while in ax- ioms of the form (2) the notation ::s interprets p as a statistical probability, i.e., as information regarding random individuals from certain populations. For example, an epistemic probabilistic concept inclusion axiom of the form p ::e C v D (3) represents the fact that we believe in the truth of C v D with probability p. A statistical probabilistic concept inclusion axiom of the form p ::s C v D (4) instead means that a random individual of class C has probability p of belonging to D, thus representing the statistical information that a fraction p of the indi- viduals of C belong to D. In this way, the overlap between C and D is quantified by the statistical probability p. The difference between the two axioms is that, if two individuals belong to class C, the probability that they both belong to D according to (3) is p, since p represents the truth of the formula as a whole, while according to (4) is p·p, since each individual has probability p of belonging to class D and the two events are independent. Therefore, statistical probability regards the knowledge we have about population of a given domain. In order to give a semantics to such probabilistic knowledge bases, we consider their translation into predicate logic. The idea of DISPONTE is to associate independent Boolean random variables to (instantiations of) the formulas in predicate logic that are obtained from the translation of the axioms. By assigning values to every random variable we obtain a world, the set of predicate logic formulas whose random variable is assigned to 1. To clarify what we mean by instantiations, we assume a fixed interpretation domain ∆I that is non-empty and possibly infinite. Given a predicate logic formula F and a domain ∆I , we define a substitution θ as a set of couples x/i where x is a variable universally quantified in the outermost quantifier in F and i ∈ ∆I . The application of θ to F , indicated by F θ, is called an instantiation of F and is obtained by replacing x with i in F and by removing x from the external quantification for every couple x/i in θ. By instantiating the universally qualified variables we are able to separately represent each individual to which the axiom is applied. To obtain a world w of a probabilistic knowledge base T , we translate every axiom into a predicate logic formula and we replace each individual a appearing in the knowledge base K with aI . Every formula obtained from an axiom without a probability annotation is included in w. For each axiom of the form (1), we decide whether or not to include it in w. For each axiom of the form (2), we generate all the substitutions for the variables of the equivalent predicate logic formula indicated in Table 2. There may be an infinite number of instantiations. For each instantiated formula we decide whether or not to include it in w. In this way we obtain Axiom Variables to be instantiated p ::s C v D x p ::s R v S x, y p ::s T rans(R) x, y, z Table 2. Axiom variables to be instantiated. a predicate logic theory which can be assigned a model-theoretic semantics. A query is entailed by a world if it is true in every model of the world. To formally define the semantics we follow the approach of [28]. An atomic choice in this context is a triple (Fi , θj , k) where Fi is the formula obtained by translating the ith axiom, θj is a substitution and k ∈ {0, 1}. k indicates whether (Fi , θj , k) is chosen to be included in a world (k = 1) or not (k = 0). If Fi is obtained from an unannotated axiom, then θj = ∅ and k = 1. If Fi is obtained from an axiom of the form (1), then θj = ∅. If Fi is obtained from an axiom of the form (2), then θj instantiates the variables indicated in Table 2. Note that, differently from [28], substitutions do not ground formulas but this is not a core requirement of [28]. A composite choice κ is a consistent set of atomic choices, i.e., (Fi , θj , k) ∈ κ, (Fi , θj , m) ∈ κ ⇒ k = m (only oneQdecision for each Q formula). The probability of composite choice κ is P (κ) = (Fi ,θj ,1)∈κ pi (Fi ,θj ,0)∈κ (1 − pi ). A selec- tion σ is a total composite choice, i.e., it contains an atomic choice (Fi , θj , k) for every instantiation Fi θj of every formula of the theory. Since the domain may be infinite, selections may, too. Let us indicate with ST the set of all selections. A selection σ identifies a theory wσ called a world in this way: wσ = {Fi θj |(Fi , θj , 1) ∈ σ}. Let us indicate with WT the set of all worlds. A composite choice κ identifies a set of worlds ωκ = {wσ |σ ∈ ST , σ ⊇ κ}.SWe define the set of worlds identified by a set of composite choices K as ωK = κ∈K ωκ . A composite choice κ is an explanation for a query Q if Q is entailed by every world of ωκ . A set of composite choices K is covering with respect to Q if every world wσ in which Q is entailed is such that wσ ∈ ωK . Two composite choices κ1 and κ2 are incompatible if their union is inconsistent. A set K of composite choices is mutually incompatible if for all κ1 ∈ K, κ2 ∈ K, κ1 6= κ2 ⇒ κ1 and κ2 are incompatible. We define the P probability of a mutually incompatible set of composite choices K as P (K) = κ∈K P (κ). Two sets of composite choices K1 and K2 are equivalent if ωK1 = ωK2 , i.e., if they identify the same set of worlds. Kolmogorov defined probability functions (or measures) as real-valued func- tions over an algebra Ω of subsets of a set W called the sample space. The set Ω is an algebra of W iff (1) W ∈ Ω, (2) Ω is closed under complementa- tion, i.e., ω ∈ Ω → (W \ ω) ∈ Ω and (3) Ω is closed under finite union, i.e., ω1 ∈ Ω, ω2 ∈ Ω → (ω1 ∪ ω2 ) ∈ Ω. The elements of Ω are called measurable sets. Not every subset of W need be present in Ω. Given a sample space W and an algebra Ω of subsets of W, a probability measure is a function µ : Ω → R that satisfies the following axioms: (1) µ(ω) ≥ 0 for all ω ∈ Ω, (2) µ(W) = 1, (3) ω1 ∩ ω2 = ∅ → µ(ω1 ∪ ω2 ) = µ(ω1 ) + µ(ω2 ) for all ω1 ∈ Ω, ω2 ∈ Ω. If F θ is an instantiated formula and κ is a composite choice such that κ ∩ {(F, θ, 0), (F, θ, 1)} = ∅, the split of κ on F θ is the set of composite choices SF θ,κ = {κ ∪ {(F, θ, 0)}, κ ∪ {(F, θ, 1)}}. It is easy to see that κ and SF θ,κ identify the same set of possible worlds, i.e., that ωκ = ωSF θ,κ . Following [28], we can prove the following results. Theorem 1 (Existence of a mutually incompatible set of composite choices). Given a finite set K of finite composite choices, there exists a finite set K 0 of mutually incompatible finite composite choices such that ωK = ωK 0 . Proof. Given a finite set of finite composite choices K, there are two possibilities to form a new set K 0 of composite choices so that K and K 0 describe the same set of possible worlds: 1. removing dominated elements: if κ1 , κ2 ∈ K and κ1 ⊂ κ2 , let K 0 = K \ {κ2 }. 2. splitting elements: if κ1 , κ2 ∈ K and κ1 ∪ κ2 is consistent (and neither is a superset of the other), there is an (F, θ, k) ∈ κ1 \ κ2 . We replace κ2 by the split of κ2 on F θ. Let K 0 = K \ {κ2 } ∪ SF θ,κ2 . In both cases ωK = ωK 0 . If we repeat this two operations until neither is ap- plicable we obtain a splitting algorithm (see Figure 1) that terminates because K is a finite set of finite composite choices. The resulting set K 0 is mutually incompatible and is equivalent to the original set. tu Fig. 1. Splitting Algorithm. 1: procedure split(K) 2: Input: set of composite choices K 3: Output: mutually incompatible set of composite choices equivalent to K 4: loop 5: if ∃κ1 , κ2 ∈ K and κ1 ⊂ κ2 then 6: K := K \ {κ2 } 7: else 8: if ∃κ1 , κ2 ∈ K, such that κ1 ∪ κ2 is inconsistent then 9: choose (F, θ, k) ∈ κ1 \ κ2 10: K := K \ {κ2 } ∪ SF θ,κ2 11: else 12: exit and return K 13: end if 14: end if 15: end loop 16: end procedure Theorem 2 (Equivalence of the probability of two equivalent mutually incompatible finite set of finite composite choices). If K1 and K2 are both mutually incompatible finite sets of finite composite choices such that they are equivalent then P (K1 ) = P (K2 ). Proof. The theorem is the same as Lemma A.8 in [29]. We report here the proof for the sake of clarity. Consider the set D of all instantiated formulas F θ that appear in an atomic choice in either K1 and K2 . This set is finite. Each composite choice in K1 and K2 has atomic choices for a subset of D. For both K1 and K2 , we repeatedly replace each composite choice κ of K1 and K2 with its split K 0 on an Fi θj from D that does not appear in κ. This procedure does not change the total probability as the probabilities of (Fi , θj , 0) and (Fi , θj , 1) sum to 1. At the end of this procedure the two sets of composite choices will be iden- tical. In fact, any difference can be extended into a possible world belonging to ωK1 but not to ωK2 or vice versa. t u We can thus define a unique probability measure µ : ΩT → [0, 1] where ΩT is defined as the set of sets of worlds identified by finite sets of finite composite choices: ΩT = {ωK |K is a finite set of finite composite choices}. It is easy to see that ΩT is an algebra over WT . Then µ is defined by µ(ωK ) = P (K 0 ) where K 0 is a finite mutually incompat- ible set of finite composite choices equivalent to K. hWT , ΩT , µi is a probability space according to Kolmogorov’s definition. The probability of a query Q is given by P (Q) = µ({w|w ∈ WT ∧ w |= Q}). If Q has a finite set K of finite explanations such that K is covering then {w|w ∈ WT ∧ w |= Q} = ωK ∈ ΩT and P (Q) is well-defined. Example 1. Let us consider the following ontology, inspired by the people+pets ontology proposed in [27]: ∃hasAnimal.P et v P etOwner (kevin, f luf f y) : hasAnimal (kevin, tom) : hasAnimal 0.4 ::e fluffy : Cat 0.3 ::e tom : Cat 0.6 ::e Cat v P et The predicate logic formulas (without external quantifiers) equivalent to the probabilistic axioms are F1 = Cat(fluffy) F2 = Cat(tom) F3 = Cat(x) → P et(x) A covering set of explanations for the query axiom Q = kevin : P etOwner is K = {κ1 , κ2 } where κ1 = {(F1 , ∅, 1), (F3 , ∅, 1)} and κ2 = {(F2 , ∅, 1), (F3 , ∅, 1)}. An equivalent mutually exclusive set K 0 of explanations can be obtained by applying the splitting algorithm. In this case K 0 = {κ01 , κ02 } where κ01 = {(F1 , ∅, 1), (F3 , ∅, 1), (F2 , ∅, 0)} and κ02 = {(F2 , ∅, 1), (F3 , ∅, 1)}. So P (Q) = 0.4 · 0.6 · 0.7 + 0.3 · 0.6 = 0.348. Example 2. If the axiom 0.6 ::e Cat v P et in Example 1 is replaced by 0.6 ::s Cat v P et then the query would have the explanations K = {κ1 , κ2 } where κ1 = {(F1 , ∅, 1), (F3 , {x/fluffy}, 1)} and κ2 = {(F2 , ∅, 1), (F3 , {x/tom}, 1)}. An equivalent mutually exclusive set K 0 of explanations obtained by applying the splitting algorithm is K 0 = {κ01 , κ02 , κ03 } with κ01 = {(F1 , ∅, 1), (F3 , {x/fluffy}, 1), (F2 , ∅, 0)}, κ02 = {(F1 , ∅, 1), (F3 , {x/fluffy}, 1), (F2 , ∅, 1), (F3 , {x/tom}, 0)} and κ03 = {(F2 , ∅, 1), (F3 , {x/tom}, 1)}. So P (Q) = 0.4 · 0.6 · 0.7 + 0.4 · 0.6 · 0.3 · 0.4 + 0.3 · 0.6 = 0.3768. Example 3. Let us consider a slightly different ontology: 0.5 ::s ∃hasAnimal.P et v P etOwner (kevin, fluffy) : hasAnimal (kevin, tom) : hasAnimal fluffy : Cat tom : Cat 0.6 ::s Cat v P et The predicate logic formulas without external quantifiers equivalent to the prob- abilistic axioms are F1 = ∃y.hasAnimal(x, y) ∧ P et(y) → P etOwner(x) F2 = Cat(x) → P et(x) A covering set of explanations for the query axiom Q = kevin : P etOwner is K = {κ1 , κ2 } where κ1 = {(F1 , {x/kevin}, 1), (F2 , {x/fluffy}, 1)} and κ2 = {(F1 , {x/kevin}, 1), (F2 , {x/tom}, 1)}. An equivalent mutually exclusive set K 0 of explanations obtained by apply- ing the splitting algorithm is K 0 = {κ01 , κ02 } where κ01 = {(F1 , {x/kevin}, 1), (F2 , {x/fluffy}, 1), (F2 , {x/tom}, 0)} and κ02 = {(F1 , {x/kevin}, 1), (F2 , {x/tom}, 1)}. So P (Q) = 0.5 · 0.6 · 0.4 + 0.5 · 0.6 = 0.42. Example 4. Let us consider the ontology: 0.7 ::s Schoolchild v European 0.4 ::s Schoolchild v OnlyChild 0.6 ::s European v GoodInM ath 0.5 ::s OnlyChild v GoodInM ath The predicate logic formulas without the external quantifiers equivalent to the probabilistic axioms are: F1 = Schoolchild(x) → European(x) F2 = Schoolchild(x) → OnlyChild(x) F3 = European(x) → GoodInM ath(x) F4 = OnlyChild(x) → GoodInM ath(x) A covering set of explanations for the query axiom Q = Schoolchild v GoodInM ath is K = {κ1 , κ2 } where κ1 = {(F1 , {x/i}, 1), (F3 , {x/i}, 1)} and κ2 = {(F2 , {x/i}, 1), (F4 , {x/i}, 1)}, where i is an anonymous member of ∆I . After splitting we get K 0 = {κ01 , κ02 , κ03 } where κ01 = {(F1 , {x/i}, 1), (F3 , {x/i}, 1)}, κ02 = {(F1 , {x/i}, 0), (F2 , {x/i}, 1), (F4 , {x/i}, 1)} and κ03 = {(F1 , {x/i}, 1), (F3 , {x/i}, 0), (F2 , {x/i}, 1), (F4 , {x/i}, 1)}. So P (Q) = 0.7 · 0.6 + 0.3 · 0.4 · 0.5 + 0.7 · 0.4 · 0.4 · 0.5 = 0.536. 4 Reasoning under the DISPONTE semantics The BUNDLE algorithm presented in [3] computes the probability of queries from a probabilistic ontology that follows the DISPONTE semantics with only epistemic probabilities. BUNDLE uses an underlying DL reasoner that is able to return explanations for queries such as Pellet [35]. The explain function of Pellet is used for this purpose [15, 17, 12, 16]. BUNDLE makes the explanations mutually incompatible by using Binary Decision Diagrams (BDD)[4] because this approach has been demonstrated to be faster than using the splitting al- gorithm [18, 31]. BDDs are used to compute the probability using the dynamic programming algorithm of [8]. In order to also deal with statistical probabilities, Pellet needs to be modified so that it records, besides the axioms that have been used to answer the query, also the individuals to which they are applied. We are currently working on modifying the tableau expansion rules of Pellet so that the individuals on which they operate are recorded together with the axioms. The first results on this activity are reported in [32], which presents a performance evaluation of inference over the real probabilistic ontology for breast cancer risk assesment both for BUNDLE and PRONTO. 5 Related Work [13] proposed an extension of the description logic ALC that is able to ex- press statistical information on the terminological knowledge such as partial concept overlapping. Similarly, [20] presented a probabilistic description logic based on Bayesian networks that deals with statistical terminological knowledge. [13, 20] do not allow probabilistic assertional knowledge about concept and role instances. [14] allows assertional knowledge about concept and role instances together with statistical terminological knowledge and combines the resulting probability distributions using cross-entropy minimization but does not allow epistemic statements. [9] proposed a probabilistic extension of OWL that admits a translation into Bayesian networks. The semanticsP that is proposed assigns a probability distri- bution P (i) over individuals, P i.e. i P (i) = 1, and assigns a probability to a class C as P (C) = i∈C P (i), while we assign a probability measure to sets of worlds. PR-OWL [6, 5] is an upper ontology that provides a framework for building probabilistic ontologies. It allows to use the first-order probabilistic logic MEBN [21] for representing uncertainty in ontologies. The use of a full fledged first-order probabilistic logic distinguishes this work from ours, where we tried to provide a minimal extension to description logics. A different approach to the combination of description logic with probability is taken by [10, 22, 23] where the authors use probabilistic lexicographic entail- ment from probabilistic default reasoning. The logics proposed in these papers allow both terminological probabilistic knowledge as well as assertional proba- bilistic knowledge about instances of concepts and roles. PRONTO [19] is one of the systems that allows to perform inference in this semantics. These works are based on Nilsson’s probabilistic logic [25], where a probabilistic interpretation P r defines a probability distribution over the set of interpretations Int. The probability of a logical formula F according to P r, denoted P r(F ), is the sum of all P r(I) such that I ∈ Int and I |= F . A probabilistic knowledge base K is a set of probabilistic formulas of the form F ≥ p. A probabilistic interpretation P r satisfies F ≥ p iff P r(F ) ≥ p. P r satisfies K, or P r is a model of K, iff P r satisfies all F ≥ p ∈ K. P r(F ) ≥ p is a tight logical consequence of K iff p is the infimum of P r(F ) subject to all models P r of K. Nilsson’s probabilistic logic differs from the distribution semantics: while the first computes the lowest p such that P r(F ) ≥ p holds for all P r, the latter computes p such that P (F ) = p. Thus Nilsson’s logic allows weaker conclusions: consider a probabilistic ontology composed of the axioms 0.4 ::e a : C. and 0.5 ::e b : C. and a probabilistic knowledge base composed of C(a) ≥ 0.4 and C(b) ≥ 0.5. The distribution semantics allows to say that P (a : C ∨ b : C) = 0.7, while with Nilsson’s logic the lowest p such that P r(C(a)∨C(b)) ≥ p holds is 0.5. This is due to the fact that in the distribution semantics the probabilistic axioms are considered as independent, which allows to make stronger conclusions. Other approaches, such as [7, 11], combine a liteweight ontology language, DL-Lite and Datalog+/- respectively, with graphical models, Bayesian networks and Markov networks respectively. In both cases, an ontology is composed of a set of annotated axioms and a graphical model and the annotations are sets of assignments of random variables from the graphical model. The semantics is assigned by considering the possible worlds of the graphical model and by stating that an axiom holds in a possible world if the assignments in its annotation hold. The probability of a conclusion is then the sum of the probabilities of the possible worlds where the conclusion holds. Our approach provides a tighter integration of probability in ontologies as we do not rely on an additional graphical model. In summary, we allow to extend Description Logics languages with more complete treatment of probabilistic knowledge that includes subjective and sta- tistical statement. 6 Conclusions We extended the DISPONTE semantics by allowing the representation of statis- tical information on concepts and populations. In this way both epistemic and partial overlap information can be expressed in a seamless way. References 1. Baader, F., Calvanese, D., McGuinness, D.L., Nardi, D., Patel-Schneider, P.F. (eds.): The Description Logic Handbook: Theory, Implementation, and Applica- tions. Cambridge University Press (2003) 2. Baader, F., Horrocks, I., Sattler, U.: Description logics. In: Handbook of knowledge representation, chap. 3, pp. 135–179. Elsevier (2008) 3. Bellodi, E., Lamma, E., Riguzzi, F., Albani, S.: A distribution semantics for prob- abilistic ontologies. In: International Workshop on Uncertainty Reasoning for the Semantic Web. No. 778 in CEUR Workshop Proceedings, Sun SITE Central Eu- rope (2011) 4. Bryant, R.E.: Graph-based algorithms for boolean function manipulation. IEEE Trans. on Comput. 35(8), 677–691 (1986) 5. Carvalho, R.N., Laskey, K.B., Costa, P.C.G.: PR-OWL 2.0 - bridging the gap to OWL semantics. In: International Workshop on Uncertainty Reasoning for the Semantic Web (2010) 6. Costa, P.C.G., Laskey, K.B., Laskey, K.J.: PR-OWL: A Bayesian ontology language for the semantic web. In: International Workshop on Uncertainty Reasoning for the Semantic Web. LNCS, vol. 5327, pp. 88–107. Springer (2008) 7. d’Amato, C., Fanizzi, N., Lukasiewicz, T.: Tractable reasoning with Bayesian de- scription logics. In: International Conference on Scalable Uncertainty Management. LNCS, vol. 5291, pp. 146–159. Springer (2008) 8. De Raedt, L., Kimmig, A., Toivonen, H.: ProbLog: A probabilistic Prolog and its application in link discovery. In: International Joint Conference on Artificial Intelligence. pp. 2462–2467 (2007) 9. Ding, Z., Peng, Y.: A probabilistic extension to ontology language OWL. In: Hawaii International Conference On System Sciences. IEEE (2004) 10. Giugno, R., Lukasiewicz, T.: P-SHOQ(D): A probabilistic extension of SHOQ(D) for probabilistic ontologies in the semantic web. In: European Conference on Logics in Artificial Intelligence. LNCS, vol. 2424, pp. 86–97. Springer (2002) 11. Gottlob, G., Lukasiewicz, T., Simari, G.I.: Conjunctive query answering in proba- bilistic Datalog+/- ontologies. In: International Conference on Web Reasoning and Rule Systems. LNCS, vol. 6902, pp. 77–92. Springer (2011) 12. Halaschek-Wiener, C., Kalyanpur, A., Parsia, B.: Extending tableau tracing for ABox updates. Tech. rep., University of Maryland (2006) 13. Heinsohn, J.: Probabilistic description logics. In: Conference on Uncertainty in Artificial Intelligence. pp. 311–318. Morgan Kaufmann (1994) 14. Jaeger, M.: Probabilistic reasoning in terminological logics. In: International Con- ference on Principles of Knowledge Representation and Reasoning. pp. 305–316 (1994) 15. Kalyanpur, A., Parsia, B., Cuenca-Grau, B., Sirin, E.: Tableaux tracing in SHOIN. Tech. Rep. 2005-66, University of Maryland (2005) 16. Kalyanpur, A., Parsia, B., Horridge, M., Sirin, E.: Finding all justifications of OWL DL entailments. In: International Semantic Web Conference. LNCS, vol. 4825, pp. 267–280. Springer (2007) 17. Kalyanpur, A., Parsia, B., Sirin, E., Hendler, J.A.: Debugging unsatisfiable classes in OWL ontologies. J. Web Sem. 3(4), 268–293 (2005) 18. Kimmig, A., Demoen, B., Raedt, L.D., Costa, V.S., Rocha, R.: On the implemen- tation of the probabilistic logic programming language problog. Theor. Prac. Log. Prog. 11(2-3), 235–262 (2011) 19. Klinov, P.: Pronto: A non-monotonic probabilistic description logic reasoner. In: European Semantic Web Conference. LNCS, vol. 5021, pp. 822–826. Springer (2008) 20. Koller, D., Levy, A.Y., Pfeffer, A.: P-CLASSIC: A tractable probablistic description logic. In: National Conference on Artificial Intelligence. pp. 390–397 (1997) 21. Laskey, K.B., Costa, P.C.G.: Of starships and Klingons: Bayesian logic for the 23rd century. In: Conference in Uncertainty in Artificial Intelligence. pp. 346–353. AUAI Press (2005) 22. Lukasiewicz, T.: Probabilistic default reasoning with conditional constraints. Ann. Math. Artif. Int. 34(1-3), 35–88 (2002) 23. Lukasiewicz, T.: Expressive probabilistic description logics. Artif. Int. 172(6-7), 852–883 (2008) 24. Lukasiewicz, T., Straccia, U.: Managing uncertainty and vagueness in description logics for the semantic web. J. Web Sem. 6(4), 291–308 (2008) 25. Nilsson, N.J.: Probabilistic logic. Artif. Intell. 28(1), 71–87 (1986) 26. Obrst, L., McCandless, D., Stoutenburg, S., Fox, K., Nichols, D., Prausa, M., Sward, R.: Evolving use of distributed semantics to achieve net-centricity. In: AAAI Fall Symposium (2007) 27. Patel-Schneider, P, F., Horrocks, I., Bechhofer, S.: Tutorial on OWL (2003) 28. Poole, D.: Abducing through negation as failure: stable models within the inde- pendent choice logic. J. Log. Program. 44(1-3), 5–35 (2000) 29. Poole, D.: Probabilistic horn abduction and Bayesian networks. Artif. Intell. 64(1) (1993) 30. Predoiu, L., Stuckenschmidt, H.: Probabilistic extensions of semantic web lan- guages - a survey. In: The Semantic Web for Knowledge and Data Management: Technologies and Practices. Idea Group Inc (2008) 31. Riguzzi, F.: Extended semantics and inference for the Independent Choice Logic. Log. J. IGPL 17(6), 589–629 (2009) 32. Riguzzi, F., Lamma, E., Bellodi, E., Zese, R.: Semantics and inference for proba- bilistic ontologies. In: Popularize Artificial Intelligence Workshop. pp. 41–46. No. 860 in CEUR Workshop Proceedings, Sun SITE Central Europe (2012) 33. Sato, T.: A statistical learning method for logic programs with distribution seman- tics. In: International Conference on Logic Programming. pp. 715–729. MIT Press (1995) 34. Sattler, U., Calvanese, D., Molitor, R.: Relationships with other formalisms. In: Description Logic Handbook. pp. 137–177 (2003) 35. Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. J. Web Sem. 5(2), 51–53 (2007) 36. URW3-XG: Uncertainty reasoning for the World Wide Web, final report (2005)