Epistemic and Statistical Probabilistic Ontologies

Abstract

We present DISPONTE, a semantics for probabilistic ontologies 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 con dence in the axiom, while the statistical probability considers the populations to which the axiom is applied.

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 di erent proposals. In the eld of logic programming, the distribution semantics [ 33 ] has emerged as one of the most e ective 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 Probabilistic 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 others. 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 describes related work and, nally, Section 6 concludes the paper.

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 2 R or the inverse R of an atomic role R 2 R. We use R to denote the set of all inverses of roles in R. An RBox R consists of a nite set of transitivity axioms T rans(R), where R 2 R, and role inclusion axioms R v S, where R; S 2 R [ R .

Concepts are de ned by induction as follows. Each A 2 A is a concept, ? and > are concepts, and if a 2 I, then fag is a concept. If C, C1 and C2 are concepts and R 2 R [ R , then (C1 u C2), (C1 t C2), and :C are concepts, as well as 9R:C, 8R:C, n R and n R for an integer n 0.

A TBox T is a nite 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 nite 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 2 R and a; b 2 I. A knowledge base K = (T ; R; A) consists of a TBox T , an RBox R and an ABox A.

SHOIN is decidable i there are no number restrictions on non-simple roles. A role is non-simple i 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 Quanti ers 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(fag) = (x = a) x(C u D) = x(C) ^ x(D) x(C t D) = x(C) ^ x(D) x(9R:C) = 9y:R(x; y) ^ y(C) x(9R :C) = 9y:R(y; x) ^ y(C)

x(8R:C) = 8y:R(x; y) ! y(C) x(8R :C) = 8y:R(y; x) ! y(C)

x( nR) = 9 ny:R(x; y) x( nR ) = 9 ny:R(y; x)

x( nR) = 9 ny:R(x; y) x( nR ) = 9 ny: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 C v D 8x: x(C) ! x(D)

R v S 8x; y:R(x; y) ! S(x; y) T rans(R) 8x; 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

SHOIN (D) adds to SHOIN datatype roles, i.e., roles that map an individual to an element of a datatype such as integers, oats, etc. Then new concept de nitions, 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 satis ability of a concept in the knowledge base, i.e., the nonemptiness of the concept. For example, the entailment of the axiom C v D may be tested by checking the satis ability 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 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 ::e E p ::s E (1) (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 axioms 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 individuals of C belong to D. In this way, the overlap between C and D is quanti ed by the statistical probability p. The di erence 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 xed interpretation domain I that is non-empty and possibly in nite. Given a predicate logic formula F and a domain I , we de ne a substitution as a set of couples x=i where x is a variable universally quanti ed in the outermost quanti er in F and i 2 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 quanti cation for every couple x=i in . By instantiating the universally quali ed 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 in nite number of instantiations. For each instantiated formula we decide whether or not to include it in w. In this way we obtain

Axiom p ::s C v D p ::s R v S p ::s T rans(R)

Variables to be instantiated x x; y x; y; z 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 de ne 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 2 f0; 1g. 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, di erently 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) 2 ; (Fi; j ; m) 2 ) k = m (only one decision for each formula). The probability of composite choice is P ( ) = Q(Fi; j;1)2 pi Q(Fi; j;0)2 (1 pi). A selection 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 in nite, selections may, too. Let us indicate with ST the set of all selections. A selection identi es a theory w called a world in this way: w = fFi j j(Fi; j ; 1) 2 g. Let us indicate with WT the set of all worlds. A composite choice identi es a set of worlds ! = fw j 2 ST ; g. We de ne the set of worlds identi ed by a set of composite choices K as !K = S 2K ! .

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 2 !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 2 K; 2 2 K; 1 6= 2 ) 1 and 2 are incompatible. We de ne the probability of a mutually incompatible set of composite choices K as P (K) = P 2K 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 de ned probability functions (or measures) as real-valued functions over an algebra of subsets of a set W called the sample space. The set is an algebra of W i (1) W 2 , (2) is closed under complementation, i.e., ! 2 ! (W n !) 2 and (3) is closed under nite union, i.e., !1 2 ; !2 2 ! (!1 [ !2) 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 satis es the following axioms: (1) (!) 0 for all ! 2 , (2) (W) = 1, (3) !1 \ !2 = ; ! (!1 [ !2) = (!1) + (!2) for all !1 2 ; !2 2 .

If F is an instantiated formula and is a composite choice such that \ f(F; ; 0); (F; ; 1)g = ;, the split of on F is the set of composite choices SF ; = f [ f(F; ; 0)g; [ f(F; ; 1)gg. 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 nite set K of nite composite choices, there exists a nite set K0 of mutually incompatible nite composite choices such that !K = !K0 . Proof. Given a nite set of nite composite choices K, there are two possibilities to form a new set K0 of composite choices so that K and K0 describe the same set of possible worlds: 1. removing dominated elements: if 1; 2 2 K and 1 2, let K0 =

K n f 2g. 2. splitting elements: if 1; 2 2 K and 1 [ 2 is consistent (and neither is a superset of the other), there is an (F; ; k) 2 1 n 2. We replace 2 by the split of 2 on F . Let K0 = K n f 2g [ SF ; 2 .

In both cases !K = !K0 . If we repeat this two operations until neither is applicable we obtain a splitting algorithm (see Figure 1) that terminates because K is a nite set of nite composite choices. The resulting set K0 is mutually incompatible and is equivalent to the original set. tu Theorem 2 (Equivalence of the probability of two equivalent mutually incompatible nite set of nite composite choices). If K1 and K2 are both mutually incompatible nite sets of nite 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 nite. 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 K0 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 identical. In fact, any di erence can be extended into a possible world belonging to !K1 but not to !K2 or vice versa. tu We can thus de ne a unique probability measure : T ! [0; 1] where T is de ned as the set of sets of worlds identi ed by nite sets of nite composite choices: T = f!K jK is a nite set of nite composite choicesg. It is easy to see that T is an algebra over WT .

Then is de ned by (!K ) = P (K0) where K0 is a nite mutually incompatible set of nite composite choices equivalent to K. hWT ; T ; i is a probability space according to Kolmogorov's de nition.

The probability of a query Q is given by P (Q) = (fwjw 2 WT ^ w j= Qg). If Q has a nite set K of nite explanations such that K is covering then fwjw 2 WT ^ w j= Qg = !K 2 T and P (Q) is well-de ned.

Example 1. Let us consider the following ontology, inspired by the people+pets ontology proposed in [ 27 ]: 9hasAnimal:P et v P etOwner (kevin; f luf f y) : hasAnimal (kevin; tom) : hasAnimal 0:4 ::e u y : Cat 0:3 ::e tom : Cat 0:6 ::e Cat v P et The predicate logic formulas (without external quanti ers) equivalent to the probabilistic axioms are

F1 = Cat( u y ) F2 = Cat(tom)

F3 = Cat(x) ! P et(x) A covering set of explanations for the query axiom Q = kevin : P etOwner is K = f 1; 2g where 1 = f(F1; ;; 1); (F3; ;; 1)g and 2 = f(F2; ;; 1); (F3; ;; 1)g.

An equivalent mutually exclusive set K0 of explanations can be obtained by applying the splitting algorithm. In this case K0 = f 01; 02g where 01 = f(F1; ;; 1); (F3; ;; 1); (F2; ;; 0)g and 02 = f(F2; ;; 1); (F3; ;; 1)g. 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 = f 1; 2g where 1 = f(F1; ;; 1); (F3; fx= u yg; 1)g and 2 = f(F2; ;; 1); (F3; fx=tomg; 1)g. An equivalent mutually exclusive set K0 of explanations obtained by applying the splitting algorithm is K0 = f 01; 02; 03g with 01 = f(F1; ;; 1); (F3; fx= u yg; 1); (F2; ;; 0)g, 02 = f(F1; ;; 1); (F3; fx= u yg; 1); (F2; ;; 1); (F3; fx=tomg; 0)g and 03 = f(F2; ;; 1); (F3; fx=tomg; 1)g. 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 di erent ontology: 0:5 ::s 9hasAnimal:P et v P etOwner (kevin; u y) : hasAnimal (kevin; tom) : hasAnimal

u y : Cat tom : Cat 0:6 ::s Cat v P et The predicate logic formulas without external quanti ers equivalent to the probabilistic axioms are

F1 = 9y: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 = f 1; 2g where 1 = f(F1; fx=keving; 1); (F2; fx= u yg; 1)g and 2 = f(F1; fx=keving; 1); (F2; fx=tomg; 1)g.

An equivalent mutually exclusive set K0 of explanations obtained by applying the splitting algorithm is K0 = f 01; 02g where 01 = f(F1; fx=keving; 1); (F2; fx= u yg; 1); (F2; fx=tomg; 0)g and 02 = f(F1; fx=keving; 1); (F2; fx=tomg; 1)g. 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 quanti ers 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 = f 1; 2g where 1 = f(F1; fx=ig; 1); (F3; fx=ig; 1)g and 2 = f(F2; fx=ig; 1); (F4; fx=ig; 1)g, where i is an anonymous member of I . After splitting we get K0 = f 01; 02; 03g where 01 = f(F1; fx=ig; 1); (F3; fx=ig; 1)g, 02 = f(F1; fx=ig; 0); (F2; fx=ig; 1); (F4; fx=ig; 1)g and 03 = f(F1; fx=ig; 1); (F3; fx=ig; 0); (F2; fx=ig; 1); (F4; fx=ig; 1)g. 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 algorithm [ 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 modi ed 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 rst 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 express 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 semantics that is proposed assigns a probability distribution P (i) over individuals, i.e. Pi P (i) = 1, and assigns a probability to a class C as P (C) = Pi2C 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 rst-order probabilistic logic MEBN [ 21 ] for representing uncertainty in ontologies. The use of a full edged rst-order probabilistic logic distinguishes this work from ours, where we tried to provide a minimal extension to description logics.

A di erent approach to the combination of description logic with probability is taken by [ 10, 22, 23 ] where the authors use probabilistic lexicographic entailment from probabilistic default reasoning. The logics proposed in these papers allow both terminological probabilistic knowledge as well as assertional probabilistic 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 de nes 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 2 Int and I j= F . A probabilistic knowledge base K is a set of probabilistic formulas of the form F p. A probabilistic interpretation P r satis es F p i P r(F ) p. P r satis es K, or P r is a model of K, i P r satis es all F p 2 K. P r(F ) p is a tight logical consequence of K i p is the in mum of P r(F ) subject to all models P r of K.

Nilsson's probabilistic logic di ers from the distribution semantics: while the rst 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 statistical statement.

Conclusions

We extended the DISPONTE semantics by allowing the representation of statistical 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 Applications . 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 probabilistic ontologies . In: International Workshop on Uncertainty Reasoning for the Semantic Web. No. 778 in CEUR Workshop Proceedings, Sun SITE Central Europe ( 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 description 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 Arti cial 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 Arti cial Intelligence. LNCS , vol. 2424 , pp. 86 { 97 . Springer ( 2002 )

11. Gottlob , G. , Lukasiewicz , T. , Simari , G.I. : Conjunctive query answering in probabilistic 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 Arti cial Intelligence . pp. 311 { 318 . Morgan Kaufmann ( 1994 )

14. Jaeger , M. : Probabilistic reasoning in terminological logics . In: International Conference 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 justi cations 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 unsatis able 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 implementation 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. , Pfe er , A.: P-CLASSIC : A tractable probablistic description logic . In: National Conference on Arti cial 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 Arti cial 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 independent 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 languages - 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 probabilistic ontologies . In: Popularize Arti cial 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 semantics . 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, nal report ( 2005 )