We present DISPONTE, a semantics for probabilistic ontologies that is based on the distribution semantics for probabilistic logic programs. In DISPONTE each axiom of a probabilistic ontology is annotated with a probability. The probabilistic theory de nes thus a distribution over normal theories (called worlds) obtained by including an axiom in a world with a probability given by the annotation. The probability of a query is computed from this distribution with marginalization. We also present the system BUNDLE for reasoning over probabilistic OWL DL ontologies according to the DISPONTE semantics. BUNDLE is based on Pellet and uses its capability of returning explanations for a query. The explanations are encoded in a Binary Decision Diagram from which the probability of the query is computed.
Representing probabilistic knowledge and reasoning with it is fundamental in
order to realize the full vision of the Semantic Web, due to the ubiquity of
uncertainty in the real world and on the Web [
Similarly, in the eld of logic programming, there has been much work on
introducing uncertainty in the programs. Among the various proposals, the
distribution semantics [
In this paper we propose to apply this approach to ontology languages and, in particular, to the OWL DL fragment, that is based on the description logic SHOIN (D). However, the approach is applicable in principle to any description logic. We called the approach DISPONTE for \DIstribution Semantics for Probabilistic ONTologiEs" (Spanish for \get ready"). The idea is to annotate each axiom of a theory with a probability and assume that each axiom is independent of the others. A probabilistic theory de nes thus a distribution over normal theories (worlds) obtained by including an axiom in a world with a probability given by the annotation. The probability of a query is again computed from this distribution with marginalization.
We also present the system BUNDLE for \Binary decision diagrams for
Uncertain reasoNing on Description Logic thEories" that performs inference over
probabilistic OWL DL ontologies. BUNDLE uses the inference techniques
developed for probabilistic logic programs under the distribution semantics [
BUNDLE is based on the Pellet reasoner [
The paper is organized as follows. Section 2 describes the distribution semantics for logic programs while Section 3 presents DISPONTE. Section 4 illustrates BUNDLE and Section 5 discusses current limitations of DISPONTE and BUNDLE. Section 6 describes related works while Section 7 concludes the paper. 2
The probabilistic logic programming languages based on the distribution
semantics di er in the way they de ne the distribution over logic programs. Each
language allows probabilistic choices among atoms in clauses. Let us consider
ProbLog [
Let us call TF the set of atoms obtained by removing the probabilistic annotation from the probabilistic facts. Let us consider the case in which TC [ TF does not contain function symbols so that its Herbrand base is nite. Let us call ground(T ) the grounding of a normal program T . Since there are no function symbols, ground(TC [ TF ) is nite and so is the grounding ground(TF ) obtained by grounding the probabilistic atoms with constants from the Herbrand universe of TC [ TF . So each probabilistic fact Fi has a nite set of groundings.
A substitution is a set of couples V =c where V is a variable and c is a constant. A substitution j is applied to a logic atom F , indicated with F j , by replacing the variables in the substitution with constants. A substitution j is grounding for logic atom F if F j is ground. Suppose that a grounding is obtained with the substitution j : Fi j corresponds to a Boolean random variable Xij that is independent of the others.
Example 1. The following ProbLog program T encodes a very simple model of the development of an epidemic or pandemic:
C1 = epidemic : f lu(X); epid(X); cold: C2 = pandemic : f lu(X); n + epid(X); pand(X); cold: C3 = f lu(david): C4 = f lu(robert): F1 = 0:7 :: cold: F2 = 0:6 :: epid(X): F3 = 0:3 :: pand(X):
This program models the fact that if somebody has the u and the climate is cold there is the possibility that an epidemic or a pandemic arises. We are uncertain whether the climate is cold but we know for sure that David and Robert have the u. epid(X) and pand(X) can be considered as "probabilistic activators" of the e ects in the head given that the causes (f lu(X) and cold) are present. n + epid(X) means the negation of epid(X).
Fact F1 has only one grounding so there is a single Boolean variable X11. Fact F2 has two groundings, epid(david) and epid(robert) so there are two Boolean random variables X21 and X22. F3 also has two groundings so there are two Boolean random variables X31 and X32.
In order to present the distribution semantics, let us rst give some de nitions. An atomic choice is a selection of a value for a grounding of a probabilistic fact F and is represented by the triple (Fi; j ; k) where j is a substitution grounding Fi and k 2 f0; 1g. A set of atomic choices is consistent if (Fi; j ; k) 2 ; (Fi; j ; m) 2 ) k = m, i.e., only one truth value is selected for a ground fact. A composite choice is a consistent set of atomic choices. 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 (one atomic choice for every grounding of every probabilistic fact). A selection identi es a normal logic program w called a world in this way: w = TC [ fFi j j(Fi; j ; 1) 2 g. The probability of w is P (w ) = P ( ) = Q(Fi; j;1)2 pi Q(Fi; j;0)2 (1 pi). Since ground(TF ) is nite the set of worlds is nite: WT = fw1; : : : ; wmg and P (w) is a distribution over worlds: Pw2WT P (w) = 1. A world w is compatible with a composite choice if
We can de ne the conditional probability of a query Q given a world as P (Qjw) = 1 if w j= Q and 0 otherwise. This allows to de ne a joint distribution of the query and the worlds P (Q; w) by using the product rule of the theory of probability: P (Q; W ) = P (Qjw)P (w). The probability of Q can then be obtained from the joint distribution by the sum rule (marginalization over Q): P (Q) =
X P (Q; w) = w2WT
X P (Qjw)P (w) = w2WT
X w2WT :wj=Q
P (w) (1) In Example 1, T has 5 Boolean random variables and thus 32 worlds. The query epidemic is true in 5 of them and its probability is P (epidemic) = 0:588.
It is often unfeasible to nd all the worlds where the query is true so inference
algorithms nd instead explanations for the query [
Each explanation identi es a set of worlds, those that are compatible with it, and a set of explanations K identi es the set !K of worlds compatible with one of its explanations (!K = fw j 2 K; g). A set of explanations K is covering for a query Q if every world in which Q is true is in !K . For example, K = f 1; 2g is covering for the query epidemic.
The probability of a query can thus be computed from a covering set of explanations for the query by computing the probability of the Boolean formula B(Q) = _
^ 2K (Fi; j;1)2
Xij
^ (Fi; j;0)2 :Xij (2) For Example 1, the formula is B(epidemic) = X11 ^ X21 _ X11 ^ X22.
Explanations however, di erently from possible worlds, are not necessarily
mutually exclusive with respect to each other, so the probability of the query can
not be computed by a summation as in (1). In fact computing the probability
of a DNF formula of independent Boolean random variables is a #P-complete
problem [
X21 X22 X11 n3 1 n1 n2 0
A BDD performs a Shannon expansion of the Boolean formula f (X), so that if X is the variable associated to the root level of a BDD, the formula f (X) can be represented as f (X) = X ^ f X (X) _ :X ^ f :X (X) where f X (X) (f :X (X)) is the formula obtained by f (X) by setting X to 1 (0). Now the two disjuncts are mutually exclusive and the probability of f (X) can be computed as P (f (X)) = P (X)P (f X (X))+(1 P (X))P (f :X (X)) Figure 2 shows the function Prob that implements the dynamic programming algorithm for computing the probability of a formula encoded as a BDD.
Languages with non-binary choices such as Logic Programs with Annotated
Disjunctions can be handled by encoding the choices with binary variables [
DISPONTE assigns a semantics to probabilistic ontologies following the approach of the distribution semantics for probabilistic logic programs. It de nes a probability distribution over non-probabilistic ontologies called worlds. This probability distribution is extended to a joint distribution of the worlds and a query and the probability of the query is obtained by marginalization.
The probabilistic ontologies we consider associate to each axiom of the ontology a Boolean random variable that indicates whether the axiom is present in a world. A probabilistic ontology is thus a set of annotated axioms of the form pi :: Ai (3) or of unannotated axioms of the form Ai, for i = 1; : : : ; n, where pi is the probability with which axiom Ai is included in a world. Let us call OA the set fA1; : : : ; Ang and Xi the Boolean random variable associated to axiom Ai. Each Xi is independent of every Xj with i 6= j. The probability of each Xi of being true is pi. If the pi :: annotation is omitted for an axiom, we assume that the axiom is certain, i.e., that it has probability 1.
A world w is obtained by sampling a value for Xi for every axiom Ai of OA and by including Ai in w if Xi = 1. Since the random variables for the di erent axioms are independent, the probability P (w) of w is obtained as: P (w) = Y pi
Y (1
pj ) Ai2w
Aj2OAnw Given a query Q to O, we can de ne its conditional probability of being true given a world P (Qjw) in the following intuitive way: P (Qjw) = 1 if w j= Q and P (Qjw) = 0 if w 6j= Q.
The probability P (Q) can be obtained from the joint distribution of the query and the worlds by the sum rule:
P (Q) = X P (Q; w) = X P (Qjw)P (w) = w w
X P (w) w:wj=Q Similarly to the case of probabilistic logic programming, the probability of a query Q given a probabilistic ontology O can be computed by rst nding the explanations for Q in O. An explanation in this context is a subset of axioms of O that is su cient for entailing Q. Typically minimal explanations are sought for e ciency reasons. All the explanations for Q must be found, corresponding to all ways of proving Q. Let EQ be set of explanations and e be an explanation from EQ. The probability of Q can be obtained by computing the probability of the DNF formula
F (Q) = _
^ pi
e2EQ Ai2e
Example 2. This example is inspired by Examples 3.1, 4.1, 4.2 and 4.3 of [
SportsCar v Car u 9max speed: 245Km=h We also know that a Car is a subset of the class of vehicles HasF ourW heels with probability 0.9:
0:9 :: Car v HasF ourW heels Please note that this does not mean that a member of the class Car is a member of HasF ourW heels with probability 0.9, see Section 5. johns car is an instance of SportsCar with probability 0.8:
0:8 :: johns car : SportsCar We want to know what is the probability P (Q1) of axiom Q1 = johnsCar : HasF ourW heels being true. Q1 has a single explanation containing the axioms (4), (5) and (6). Since (4) is certain, P (Q1) is 0:8 0:9 = 0:72.
Example 3. Let us consider another example, inspired by the people+pets
ontology proposed in [
(9) (10) Then the query axiom Q2 = kevin : P etOwner has two explanations, one composed of the axioms (7) and (9) and the other composed of the axioms (8) and (10). Since (9) is certain, the probability of the rst explanation is 0.6. Similarly, the probability of the second explanation is again 0.6. If we associate the Boolean random variable X1 to (7) and X2 to (8), the query axiom is true if the formula X1 _ X2 is true. Thus, P (Q2) = P (X1 _ X2). Since X1 and X2 are independent, we get P (Q2) = 0:6 + 0:6 0:6 0:6 = 0:84: As you can see, the fact that kevin is an instance of both DogOwner and CatOwner increases the probability that he is an instance of P etOwner: if he were an instance of DogOwner only, its probability of being a P etOwner would be 0.6 and similarly if he were an instance of CatOwner only.
Now suppose that we known that P etOwner is a subclass of Ecologist with probability 0.7: 0:7 :: P etOwner v Ecologist (11) The query axiom Q3 = kevin : Ecologist has again two explanations, one composed of axioms (7), (9) and (11) and the other composed of the axioms (8), (10) and (11). Since (9) is certain, the probability of the rst explanation is 0:4 0:6 = 0:24. Similarly, the probability of the second explanation is 0:5 0:6 = 0:3. If we associate the Boolean random variable X3 to (11), Q3 is a consequence of the theory if X1 ^ X3 _ X2 ^ X3 is true. A BDD that can be built for this formula is the one shown in Figure 1 after replacing variable X21 with X1, variable X22 with X2 and variable X11 with X3.
The probability of node n3 computed by Prob is 0:7 1 + 0:3 0 = 0:7. The probability of node n2 is 0:6 0:7 + 0:4 0 = 0:42 and the probability of node n1 (and of Q3) is 0:6 0:7 + 0:4 0:42 = 0:588. 4
BUNDLE computes the probability of a query Q given a probabilistic ontology
O that follows the DISPONTE semantics. BUNDLE exploits an underlying
ontology reasoner that is able to return all explanations for a query. One of these
system is Pellet [
In order to assign probabilities to axioms, we exploit the possibility given by
OWL1.1 of declaring an annotation property for axioms. We thus annotate the
axioms with the XML tag bundle:probability whose value should be a real
number in [
BUNDLE takes as input two RDFXML les, one containing the ontology and one containing the annotations. For Example 3, the ontology le contains the following de nition of P etOwner: <owl:Class rdf:about="#PetOwner"> <rdfs:subClassOf>
<owl:Class rdf:about="#Ecologist" /> </rdfs:subClassOf> </owl:Class> The annotation le contains the annotation for the above axiom in the following form: <owl11:Axiom> <rdf:subject rdf:resource="#PetOwner"/> <rdf:predicate rdf:resource="&rdfs;subClassOf"/> <rdf:object rdf:resource="#Ecologist"/> <bundle:probability>0.6</bundle:probability> </owl11:Axiom> BUNDLE rst uses the annotation le for building a data structure P M ap that associates axioms with their probability. In order to do so, axioms are rst converted to strings. We use the Manchester syntax to obtain a string representation of an axiom.
Then BUNDLE uses the Explain function of Pellet to compute explanations for a query axiom. BUNDLE thus accepts all the forms of query axioms that are accepted by Pellet's Explain function, namely subclass, instance, property value, theory inconsistency and class unsatis ability.
Pellet returns the explanations for the query in the form of a set of sets of axioms. Then BUNDLE performs a double loop over the set of explanations and over the set of axioms in each explanation in which it builds a BDD representing the set of explanations. To manipulate BDDs we used the JavaBDD library1 that provides a Java interface to the major BDD libraries such as CUDD2.
Outside the outer loop, two data structures are initialized: V arAxAnn is an array that maintains the association between Boolean random variables (whose index is the array index) and axioms together with their probability, and BDD represents the set of explanations. BDD is initialized to the BDD representing the zero Boolean function. Then the outer loop is entered in which BDDE is initialized to the BDD representing the one Boolean function. In the inner loop the axioms of an explanation are considered one by one. Each axiom is rst looked up in P M ap to get its probability. If NULL is returned this means that this is a certain axiom and it does not need to be considered anymore. Then the axiom is searched for in V arAxAnn to see if it has already been assigned a random variable. If not, a cell is added to V arAxAnn to store the axiom with its probability. At this point we know the axiom's position i in V arAxAnn 1 http://javabdd.sourceforge.net/ 2 http://vlsi.colorado.edu/~fabio/CUDD/ and so the index of its Boolean variable Xi. We obtain a BDD representing Xi = 1 and we conjoin it with BDDE. At the end of the inner loop the BDD for the current explanation, BDDE, is disjoined with BDD. After the two cycles, function Prob of Figure 2 is called over BDD and its result is returned to the user.
BUNDLE has been implemented in Java and will be available for download from http://sites.unife.it/bundle. It has been successfully tested on various examples, including those of Section 3. 5
The probabilistic knowledge that can be expressed with the DISPONTE semantics is epistemic by nature, namely it represents degrees of belief in the axioms rather that statistical information. While this is reasonable for many axioms, for subclass and subproperty axioms one may want to express statistical information, for example with a probabilistic subclass axiom p :: A v B one may want to express the fact that a random individual of A has probability p of belonging to B. The DISPONTE semantics, instead, interpret the axioms as stating that A v B is true with probability p. The di erence is that, if two individuals i and j belong to class A, the probability that they both belong to B in the DISPONTE semantics is p while with a statistical interpretation is p p. Thus statistical information can be used to de ne a degree of partial overlap between classes. Extending DISPONTE to take account of this case is possible, it requires to de ne a probability distribution over models rather than over theories.
However, to reason with such knowledge, the inference engine must be modied in its inference procedure and cannot be used as a black box as in BUNDLE. In fact, BUNDLE assigns a single Boolean random variable to the axiom A v B, while with a statistical interpretation a di erent Boolean random variable must be assigned to each assertion that an individual of class A belongs to class B. We leave this extension for future work.
Another limitation of BUNDLE is the use of the OWL 1.1 Axiom construct to specify probabilities. This seems to restrict the kind of axioms on which probabilities can be placed, since the object of the RDF triple does not allow complex class expressions. However this limitation can be overcome by de ning a new class which is equivalent to the complex class expression and using the new class name in the RDF triple. In the future we plan to investigate the possibility of annotating the axioms directly in the ontology le.
As regards the complexity of reasoning on DISPONTE, it is equal to the complexity of the underlying description logic plus the #P complexity of computing the probability of a DNF formula of independent Boolean random variables, assuming the cost of keeping track of explanations during inference is negligible. Thus, the problem of inference in DISPONTE remains decidable if it was so in the underlying description logic.
Our work di ers from previous work in many respects. [
[
A di erent approach to the combination of description logic with probability
is taken by [
Similary to [
These works are based on Nilsson's probabilistic logic [
A probabilistic knowledge base K is a set of probabilistic formulas of the form p. A probabilistic interpretation P r satis es p i P r( ) p. P r satis es K, or P r is a model of K, i P r satis es all F 2 K. We say p is a tight logical consequence of K i p is the in mum of P r( ) subject to all models P r of K. Computing tight logical consequences from probabilistic knowledge bases can be done by solving a linear optimization problem.
Nilsson's probabilistic logic di ers from the distribution semantics: while a probabilistic knowledge base in Nilsson's logic may have multiple models that are probabilistic interpretations, a probabilistic program under the distribution semantics has a single model that de nes a single distribution over interpretations. Also, while in Nilsson's logic we want to compute the lowest p such that P r( ) p holds for all P r, in the distribution semantics we want to compute p such that P ( ) = p. Nilsson's logic complexity is lower than the #P complexity of the distribution semantics.
In fact Nilsson's logic allows weaker conclusions than the distribution semantics. For example, consider a probabilistic program composed of 0:4 :: a: and 0:5 :: b: and a probabilistic knowledge base composed of a 0:4 and b 0:5. The distribution semantics allows to say that P (a_b) = 0:7, while with Nilsson's logic the lowest p such that P r(a _ b) p holds is 0.5. This is due to the fact that in the distribution semantics the probabilistic atoms are considered independent, which allows to make stronger conclusions. However, note that this does not restrict expressiveness as you can specify with the distribution semantics any joint probability distribution over the atoms of the Herbrand base interpreted as Boolean random variables, possibly introducing new random facts if needed.
Alternative approaches to modeling imperfect and incomplete knowledge in
ontologies are based on fuzzy logic. A good survey of these approaches is
presented in [
We have presented the semantics DISPONTE for probabilistic ontologies that is inspired by the distribution semantics of probabilistic logic programming. We have also presented the system BUNDLE that is able to compute the probability of queries from an uncertain OWL DL ontology.
In the future, we plan to extend DISPONTE to take into account statistical terminological knowledge and improve the way in which the input to BUNDLE is speci ed.