We present BUNDLE, a reasoner able to perform reasoning on probabilistic knowledge bases according to the semantics DISPONTE. 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. BUNDLE exploits an underlying OWL DL reasoner, which is Pellet, that is able to return explanations for a query. However, it can work well with any reasoner able to return explanations for a query. The explanations are encoded in a Binary Decision Diagram from which the probability of the query is computed.
Uncertainty has been recognized as an important feature for the Semantic Web [13].
In order to be able to represent and reason with probabilistic knowledge, various
authors have advocated the use of probabilistic ontologies and many proposals have been
put forward for allowing ontology languages, and OWL in particular, to represent
uncertainty [
In this paper we apply this approach to ontological languages and, in particular, to the OWL DL fragment, that is based on the description logic S HOIN (D). However, the approach is applicable in principle to any description logic. We called the approach DISPONTE for “DIstribution Semantics for Probabilistic ONTologiEs”. The idea is to annotate axioms of a theory with a probability and assume that each axiom is independent of the others. As in Probabilistic Logic Programming, the probability of a query is computed from a covering set of explanations by solving a disjoint sum problem.
We also present the algorithm BUNDLE - for “Binary decision diagrams for Uncertain reasoNing on Description Logic thEories” - that performs inference over probabilistic ontologies.
The paper is organized as follows. Section 2 illustrates Description Logics. Section
3 presents DISPONTE. Section 4 describes BUNDLE and presents the results of the
experimental comparison between the probabilistic reasoners BUNDLE and PRONTO
[
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. A RBox R consists of a finite 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 defined 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 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. A 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 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.
The semantics of DLs can be given in a set-theoretic way or by transforming a DL knowledge base into a predicate logic theory and then using the model-theoretic semantics of the resulting theory.
S HOIN (D) adds to S HOIN datatype roles, i.e., roles that map an individual to an element of a datatype such as integers, floats, etc.
A query over a knowledge base is usually an axiom for which we want to test the entailment from the knowledge base. 3
The DISPONTE Semantics for Probabilistic Ontologies A probabilistic knowledge base is a set of certainly true axioms, that take the form of DL axioms, of epistemic probabilistic axioms of the form p ::e E 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 where p is a real number in [0; 1] and E is a TBox or RBox axiom. In epistemic probabilistic axioms, p is interpreted as the degree of our belief in axiom E, while in statistical probabilistic axioms, p is interpreted as information regarding random individuals from certain populations. For example, an epistemic probabilistic concept inclusion axiom of the form p ::e C v D 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 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 quantified. 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 the epistemic axiom is p, while according to the statistical axiom is p p.
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 formula in predicate logic that is obtained from the translation of the axiom. An instantiation is a substitution for a logical formula F , consisting of pairs x=a, where x is a variable universally quantified by the outermost quantifier and a is an individual.
We now formally define the semantics in the following. 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. A set of atomic choices is consistent if (Fi; j ; k) 2 and (Fi; j ; m) 2 implies k = m. A composite choice is a set of atomic choices and its probability is P ( ) = Q(Fi; j;1)2 pi Q(Fi; j;0)2 (1 pi). A selection is a total composite choice, i.e., an atomic choice for every instantiation of formulas of the theory. A selection identifies a theory w called a world in this way: w = fFi j j(Fi; j ; 1) 2 g. A composite choice identifies a set of worlds ! = fw j 2 ST ; g, where ST is the set of all selections. A composite choice is an explanation for a query Q if Q is entailed by every world of ! . We define the set of worlds identified by a set of composite choices K as !K = S 2K ! . 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.
Now we can define a unique probability measure : ! [0; 1], where = f!K jK is a finite set of finite composite choicesg. is defined by (!K ) = P 2K0 P ( ) where K0 is a finite mutually incompatible set of finite composite choices such that !K = !K0 .
Example 1. Let us consider the following simple ontology, inspired by the
people+pets ontology proposed in [
u y : Cat tom : Cat 0:6 ::e Cat v P et The predicate logic formula (without external quantifiers) equivalent to the only probabilistic axiom above is: F1 = Cat(x) ! P et(x). A covering set of explanations for the query axiom Q = kevin : P etOwner is K = f 1g with 1 = f(F1; ;; 1)g. In fact, there is only one probabilistic axiom and its presence is necessary to entail the query. This is also a mutually exclusive set of explanations since it contains a single composite choice so P (Q) = 0:6.
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; fx= u y g; 1)g and 2 = f(F1; fx=tomg; 1)g. The set K0 = f 01; 02g, where
01 = f(F1; fx= u y g; 1)g and 02 = f(F1; fx= u y g; 0); (F1; fx=tomg; 1)g, is such
that !K = !K0 and K0 is mutually incompatible, so P (Q) = 0:6 + 0:6 0:4 = 0:84.
K’ can be found by applying the splitting algorithm of [
The BUNDLE algorithm computes the probability of queries from a probabilistic
ontology that follows the DISPONTE semantics. BUNDLE needs an underlying DL
reasoner, such as Pellet [12], that is able to return explanations for queries. BUNDLE
builds a Binary Decision Diagram (BDD) from the set of explanations. The BDD is
then used to compute the probability using the dynamic programming algorithm of [
If the knowledge base contains only epistemic probabilistic axioms, Pellet can be used directly as the underlying ontology reasoner. If the knowledge base contains also statistical probabilistic axioms, 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. Each tableau expansion rule used by Pellet returns a set of uninstantiated axioms. Therefore we have modified Pellet’s expansion rules in order to return a set of couples (axiom; substitution) instead of simple axioms.
In order to evaluate the performances of BUNDLE, we followed the methodology
of [
(W omanU nderAbsoluteBRCRiskjW oman)[0; 0:123]
Tests have been defined by randomly sampling a subset of conditional constraints from the probabilistic part and adding these constraints to the classical part to form a random ontology. We varied the number of constraints from 9 to 15, and, for each number, we repeatedly sampled ontologies and tested them for consistency. We stopped sampling when we obtained 100 consistent ontologies for each number of constraints. The ontologies have then been translated into DISPONTE by replacing the constraint (DjC)[l; u] with the axiom l ::s C v D. For each ontology we performed the query a : C, where a is a new individual for which a number of class assertions are added to the ontology: a was randomly assigned to each class appearing in the sampled conditional constraints with probability 0.6. Class C of the query was randomly selected among those representing women under increased and lifetime risk.
We then applied both BUNDLE and PRONTO to each generated test and we
measured the execution time and the memory used. Figure 1(a) shows the average execution
time as a function of the number of axioms and, similarly, Figure 1(b) shows the
average amount of memory used. These graphs show that BUNDLE is faster and uses less
memory than PRONTO. The comparison is not meant to be interpreted in terms of a
superiority of BUNDLE, since the two systems treat ontologies with different semantics,
rather, it should provide a qualitative evaluation of the complexity of the DISPONTE
semantics with respect to the one of [
15 x 105 )s10 m ( e m iT 5 11. Sato, T.: A statistical learning method for logic programs with distribution semantics. In:
International Conference on Logic Programming. pp. 715–729. MIT Press (1995) 12. Sirin, E., Parsia, B., Cuenca-Grau, B., Kalyanpur, A., Katz, Y.: Pellet: A practical OWL-DL reasoner. Journal of Web Semantics 5(2), 51–53 (2007) 13. URW3-XG: Uncertainty reasoning for the World Wide Web, final report (2005)