We present Bayesian Description Logics (BDLs): an extension of Description Logics (DLs) with contextual probabilities encoded in a Bayesian network (BN). Classical DL reasoning tasks are extended to consider also the contextual and probabilistic information in BDLs. A complexity analysis of these problems shows that, for propositionally closed DLs, this extension comes without cost, while for tractable DLs the complexity is a ected by the cost of reasoning in the BN.
Description logic (DL) ontologies are usually composed of axioms that restrict the class of possible interpretations. As these are hard restrictions, DL ontologies can only encode absolute, immutable knowledge. For some application domains, however, knowledge depends on the situation (or context) in which it is considered. For example, the notion of a luxury hotel in a small rural center will be di erent from the one in a large cosmopolis. When building an ontology for hotels, it makes sense to contextualize the axioms according to location, and possibly other factors like season, type of weather, etc. Since these contexts refer to notions that are external to the domain of interest, it is not always desirable, or even possible, to encode them directly into the classical DL axioms.
To handle contextual knowledge, we label every axiom with the context in which it holds. For example, hLuxuryHotel v 9hasFeature:MeetingRoom : cityi states that in the context of a city, every luxury hotel has a meeting room. This axiom imposes no restriction in case the context is not a city: it might still hold, or not, depending on other factors.
Labeling the axioms in an ontology allows us to give a more detailed description of the knowledge domain. Reasoning in these cases can be used to infer knowledge that is guaranteed to hold in any given context. While the knowledge within this context is precise, there might be a level of uncertainty regarding the current context. To model this uncertainty, we attach a probability to each of the possible contexts. Since we cannot assume that the contexts are (probabilistically) independent, we need to describe the joint probability distribution ? Supported by DFG within the Research Training Group \RoSI" (GRK 1907). ?? Partially supported by DFG within the Cluster of Excellence `cfAED'. x :x y 0:7 z x y x :y :x y :x :y z over the space of all contexts. Thus, we consider knowledge bases that are composed of an ontology labeled with contextual information, together with a joint probability distribution over the space of contexts.
To represent the probabilistic component of the knowledge base, we use
Bayesian networks (BNs) [
In previous work we have studied the Bayesian extension of the DL EL [5{7]. Here, we extend those ideas to arbitrary DLs and (monotonic) reasoning tasks. 2
We now introduce Bayesian DLs. These logics extend classical DLs to handle
uncertainty, expressed through a Bayesian network [
Intuitively, G = (V; E) encodes a series of conditional independence assumptions between the random variables. More precisely, every variable x 2 V is conditionally independent of its non-descendants given its parents. Thus, every BN B de nes a unique joint probability distribution (JPD) over V given by PB(V ) = Y PB(x j (x)):
x2V A very simple BN is shown in Figure 1. Every node of the graph has an associated conditional probability distribution table. For the node x, the probability distribution is not conditional, since x has no parents in B0, and for z the table describes the conditional probability of z given its two parents x and y. From this network we can derive e.g. P (x; :y; z) = P (z j x; :y) P (:y j x) P (x) = 0. 3 In their general form, BNs allow for arbitrary discrete random variables. We restrict w.l.o.g. to Boolean variables for ease of presentation.
We abstract from the speci c DL used, and consider an arbitrary ontology language L that de nes possibly in nite classes (i) A of well-formed axioms ; (ii) C of consequences; and (iii) O of ontologies such that every element of O is a nite subset of A, and if O 2 O, then every subset of O is also an ontology in O. The semantics of this language is given by a class I of interpretations and an entailment relation j= I (A [ C) that expresses which interpretations satisfy which axioms and consequences. We say that an interpretation I is a model of the ontology O, denoted by I j= O if I j= for all 2 O.4 Finally, we say that O entails the consequence c, denoted by O j= c if every model of O satis es c. Notice that the entailment relation is monotonic; i.e., if O j= c and O O0 2 O, then O0 j= c. Any DL with acyclic TBoxes, or with general ontologies is an ontology language of this kind; consequences in these languages are e.g. concept unsatis ability, concept subsumption, or ontology inconsistency.
For the rest of this paper, we consider L to be an arbitrary but xed ontology language, with axioms A, ontologies O, consequences C, and interpretations I. As an example scenario we use subsumption in EL with general TBoxes. In the Bayesian ontology language BL, ontologies are generalized by annotating every axiom with a context, which is de ned as a set of literals belonging to a BN. De nition 1 (KB). Let V be a nite set of Boolean variables. A V -literal is either x or :x, where x 2 V ; a V -context is a consistent set of V -literals.
A V -axiom is of the form h : i where 2 A and is a V -context. A V -ontology is a nite set O of V -axioms, such that f j h : i 2 Og 2 O. A V -consequence is a pair hc : i, where c 2 C and is a V -context.
A BL knowledge base (KB) over V is a pair K = (B; O) where B is a BN over V and O is a V -ontology.5 Intuitively, a V -axiom is only guaranteed to hold when the context is satis ed. The semantics of this logic is de ned by extending interpretations to evaluate the random variables from the BN.
De nition 2 (interpretation). Given a nite set of Boolean variables V , a V -interpretation is a pair I = (I; VI) where I 2 I and VI : V ! f0; 1g is a valuation of the variables in V .
If there is no danger of ambiguity we will usually omit the pre x V . The valuation VI is extended to contexts by de ning VI(:x) = 1 VI(x) for all x 2 V , and VI( ) = min VI(`);
`2 where VI(;) := 1 for every context . The V -interpretation I = (I; VI) is a model of the V -axiom h : i or the V -consequence hc : i, denoted as I j= h : i (respectively I j= hc : i), i VI( ) = 0 or I j= (resp., I j= c). It is a model of the V -ontology O i it is a model of all the V -axioms in O. The ontology O entails hc : i if every model of O is a model of hc : i. The idea is that the 4 We use the in x notation for the relation j=. 5 Unless stated otherwise we assume that K is over V in the rest of the paper. restriction is only required to hold whenever the context is satis ed. Thus, any interpretation that violates the context trivially satis es the whole V -axiom. Example 3. Let V0 = fx; y; zg, and consider the BEL V0-ontology
O0 := f hA v C : fx; ygi ; hA v B : f:xgi ; hB v C : f:xgi g: The interpretation I0 = (I0; V0) where V0(fx; :y; zg) = 1, and I0 = (fdg; I0 ) with AI0 = fdg, and BI0 = CI0 = ; is a model of O0, but not of hA v B : fxgi. BL generalizes L: an ontology from L is a special case of a BL V -ontology, where all V -axioms are associated with the empty context; i.e., are of the form h : ;i. Since every valuation satis es the empty context ;, a V -interpretation I = (I; VI) satis es the V -axiom h : ;i i I j= , and analogously for consequences hc : i. For brevity, we use O j= c to denote that O entails hc : ;i. For a valuation W of the variables in V , we de ne the V -ontology containing the V -axioms that must be satis ed in any V -interpretation I = (I; VI) with VI = W.
De nition 4 (restriction). Let K = (B; O) be a KB. The restriction of O to a valuation W of the variables in V is the V -ontology
OW := fh : ;i j h : i 2 O; W( ) = 1g: So far, our semantics have focused on the evaluation of the Boolean variables and the interpretation of concepts, ignoring the probabilistic information provided by the BN. To handle these probabilities, we introduce multiple-world semantics next. Intuitively, a V -interpretation describes a possible world; by assigning a probabilistic distribution over these interpretations, we describe the required probabilities, which should be consistent with the BN.
De nition 5 (probabilistic model). A probabilistic interpretation is a pair P = (I; PI), where I is a set of V -interpretations and PI is a probability distribution over I such that PI(I) > 0 only for nitely many interpretations I 2 I. It is a model of the V -ontology O (resp., of the V -consequence hc : i) if every I 2 I is a model of O (resp., of hc : i). P is consistent with the BN B if for every valuation W of the variables in V it holds that
X PI(I) = PB(W):
I2I; VI=W The probabilistic interpretation P is a model of the KB (B; O) i it is a (probabilistic) model of O and consistent with B.
As consequence of this semantics, probabilistic models preserve the probability distribution of B for subsets of literals; i.e., contexts. The proof follows from the fact that a context describes a partial valuation. Hence, the probability of a context is the sum of the probabilities of all valuations that extend . Formally, let K = (B; O) be a KB, and a context. For every model P of K it holds that
X PI(I) = PB(VI):
I2I; VI( )=1 It is sometimes useful to consider a special kind of probabilistic interpretations, which we call pithy. These interpretations contain at most one V -interpretation for each valuation of the variables in V . Each of these V -interpretations provides the essential information associated to the corresponding valuation. De nition 6 (pithy). The probabilistic interpretation P = (I; PI) is called pithy if for every valuation W of the variables in V there exists at most one V -interpretation I = (I; VI) 2 I such that VI = W.
We now study the main reasoning problems in BL, and their complexity. 3
Reasoning in BL We have shown how to represent probabilistic knowledge using a BL KB. We now focus on reasoning with this knowledge. Recall that in the classical case an ontology O entails a consequence c i every model of O is also a model of c. We generalize this notion to consider contexts and the probabilities from the BN. De nition 7 (entailment). Let hc : i be a V -consequence and K a BL KB. K entails hc : i, denoted as K j= hc : i, if every probabilistic model of K is a model of hc : i. For a probabilistic interpretation P = (I; PI), the probability of hc : i is PP (hc : i) := PI2I;Ij=hc: i PI(I). The probability of hc : i w.r.t. K is PK(hc : i) := inf PP (hc : i):
Pj=K We say that c is a positive entailment in if PK(hc : i) > 0, and a p-entailment in , p 2 (0; 1] if PK(hc : i) p. 1-entailments are also called almost-sure. Clearly, if K j= hc : i, then PK(hc : i) = 1. The converse may not hold since the entailment relation might be violated in V -interpretations of probability zero. Example 8. Consider the KB K0 = (B0; O0), where B0 is the BN depicted in Figure 1 and O0 the ontology from Example 3. Then, PK0 (hA v C : ;i) = 1 and PK0 (hC v B : fx; ygi) = 0. Moreover, for any two concepts E; F , it holds that PK0 (hE v F : fx; :ygi) = 1 since hE v F : fx; :ygi can only be violated in V -interpretations with probability 0. But, in general, K0 6j= hE v F : fx; :ygi. 3.1
Probabilistic Entailments We consider rst the problem of computing the probability of an entailment, or deciding the properties of this probability. As an intermediate step, we show that it is possible w.l.o.g. to restrict reasoning to pithy models.
Lemma 9. Let K be a KB. If P is a probabilistic model of K, then there exists a pithy model Q of K such that for every consequence hc : i it holds that PQ(hc : i) PP (hc : i).
Proof (Sketch). Let W be a valuation and I; I0 2 I two V -interpretations such that VI = VI0 = W. Construct a new interpretation J as the disjoint union of I and I0. The probabilistic interpretation (H; PH) with H = (I [ fJg) n fI; I0g and PH(H) := (PI(H) H 6= J
PI(I) + PI(I0) H = J is a model of K. Moreover, J j= h : i i both I j= h : i and I0 j= h : i. tu As we show next, the probability of a consequence can be computed by reasoning over the restrictions OW of the V -ontolgy O.
Theorem 10. Let K = (B; O) be a KB and hc : i a consequence.
PK(hc : i) = 1
PB( ) +
PB(W):
X WOW(j)==c1 Proof. For every valuation W construct the V -interpretation IW as follows. If OW j= c, then IW is any model (I; W) of OW ; otherwise, IW is any model (I; W) of OW that does not satisfy hc : i, which must exist by de nition. The probabilistic interpretation PK = (I; PI) with I = fIW j W a valuation of V g and PI(IW ) = PB(W) for all W is a model of K and
PPK (hc : i) =
PI(IW ) =
PI(IW ) +
PI(IW )
X
IWj=hc: i Thus, PK(hc : i) 1 PB( ) + POWj=c;W( )=1 PB(W). Suppose now that the inequality is strict, then there exists a probabilistic model P = (J; PJ) of K such that PP (hc : i) < PPK (h : i). By Lemma 9, we can assume w.l.o.g. that P is pithy, and hence for every valuation W with PB(W) > 0 there exists exactly one JW 2 J with VJW = W. We thus have
X JWj=hc: i;W( )=1
PJ(JW ) <
X IWj=hc: i;W( )=1
PI(IW ):
Since PI(IW ) = PJ(JW ) for all W, there exists a valuation W0 with IW0 j= hc : i
but JW0 6j= hc : i. Since JW0 is a model of OW0 it follows that OW0 6j= c. By
construction, then we have that IW0 6j= hc : i, which is a contradiction. tu
Based on this theorem, we can compute the probability of an entailment as
described in Algorithm 1. The algorithm simply veri es for all possible valuations
W, whether OW entails c. Clearly, the for loop is executed 2jV j times; once for
each valuation of the variables in V . Each of these executions needs to compute
Algorithm 1 Probability of an entailment
Input: KB K = (B; O), consequence hc : i
Output: PK(hc : i)
1: P 0; Q 0
2: for all valuations W do
3: if W( ) = 0 then
4: Q Q + PB(W)
5: else if OW j= c then
6: P P + PB(W)
7: return 1 Q + P
the probability PB(W) and, possibly, decide whether OW j= c. The former can be
done in polynomial time on the size of B, using the standard chain rule [
Theorem 11. Deciding p-entailment in BL is in PSpace|.
As a lower bound, unsurprisingly, p-entailment is at least as hard as deciding
entailment in L, and deciding probabilities from the BN. Since this latter problem
is hard for the class PP [
Theorem 12. Deciding p-entailment is both PP-hard and |-hard. From these two theorems it follows that if the complexity of deciding entailments in L is at least PSpace, then p-entailment in BL is in the same complexity class. This means that any DL at least as expressive as ALC (without a TBox), can be extended with our probabilistic semantics, without a ecting the complexity of reasoning. For tractable DLs like the EL and DL-Lite families, the complexity increases to PP. If we restrict only in deciding positive or almost-sure entailments, then these bounds can be lowered.
Theorem 13. The complexity of deciding positive entailment is between NP
and NP|; deciding almost-sure entailments is between coNP and coNP|.
Proof. To decide positive entailment, we can simply guess a valuation W and
check in polynomial time with a |-oracle that (i) PB(W) > 0 and (ii) either
W( ) = 0 or OW j= c. The correctness of this algorithm is given by Theorem 10.
Thus the problem is in NP|. To show hardness, we recall that deciding, given
a BN B and a variable x 2 V , whether PB(x) > 0 is NP-hard [
Algorithm 1 shows that the probabilistic and the logical components of the KB can be decoupled while reasoning. This is an encouraging result as it means that one can apply the optimized methods developed for BN inference and for DL reasoning directly in BL without mayor modi cations. 3.2
Contextual Entailments We now turn our attention to deciding whether a consequence follows from all models of the KB in a classical sense; that is, whether K j= hc : i holds. This problem is intractable already for the sublogic of BEL that allows only the conjunction constructor, even if restricted to the empty context. Theorem 14. Let K be a BEL KB and C; D two concepts. Deciding whether K j= hC v D : ;i is coNP-hard.
Proof. We present a reduction from validity of DNF formulas, which is known
to be coNP-hard [
Lemma 15. Let K = (B; O) be a KB. Then K j= hc : i i for every valuation W with W( ) = 1, it holds that OW j= c.
It thus su ces to identify all valuations that de ne V -ontologies entailing the
consequence. To do this, we will take advantage of techniques developed in the
area of axiom-pinpointing [
Notice that a consequence depends only on the V -ontology and not on the BN. For that reason, for the rest of this section we focus only on this part of the KB.
We can see every context as the conjunctive clause := V`2 `. In this view, the V -ontology O is a set of labeled axioms over the distributive lattice B of all Boolean formulas over the variables V modulo equivalence. Each formula in this lattice de nes a sub-ontology O containing all axioms h : i 2 O with j= .
Using the terminology from [
Theorem 16. Let be a boundary for c w.r.t. O in B. Then, for any context we have that K j= hc : i i j= .
Several methods have been developed for computing boundaries, either through
a black-box approach that makes several calls to an external reasoner [
Corollary 17. Contextual entailment in BL can be decided in ExpTime|. Clearly, a boundary for c provides more information than necessary for deciding whether the axiom holds in a given context . It encodes all contexts that entail the desired axiom. We can use this knowledge to deduce the most likely context. 3.3
Most Likely Context The problem of nding the most likely context for a consequence can be seen as the dual of computing the probability of this consequence. Intuitively, we are interested in nding the most likely explanation for an event; assuming that a consequence holds, we are interested in nding an explanation for it, in the form of a context, that has the maximal probability of occurring.
De nition 18 (most likely context). Given a KB K = (B; O) and c 2 C, the context is called a most likely context for c w.r.t. K if (i) K j= hc : i, and (ii) for every context 0, if K j= hc : 0i, then PB( 0) PB( ).
Notice that we are not interested in maximizing PK(hc : i) but rather PB( ). Indeed, these two problems can be seen as dual, since PK(hc : i) depends inversely, but not exclusively, on PB( ) (see Theorem 10).
Algorithm 2 computes the set of all most likely contexts for c w.r.t. K, together with their probability. It maintains a value p of the highest known probAlgorithm 2 Compute all most likely contexts
[ f g ability for a context, and a set with all the contexts that have probability p. The algorithm rst computes a boundary for the consequence, which is used to test, for every context whether K j= hc : i. In that case, it compares PB( ) with p. If the former is larger, then the highest probability is updated to this value, and the set is restarted to contain only . If they are the same, then is added to the set of most likely contexts. The number of contexts is exponential on B, and for each of them we have to test propositional entailment, which is also exponential on B. The most expensive step is to compute the boundary, whose complexity depends on the complexity of reasoning.
Theorem 19. Algorithm 2 computes all most likely contexts for c w.r.t. K in exponential time, with a | oracle.
In general, it is not possible to lower this exponential upper bound, since a simple consequence may have exponentially many most likely contexts. However, Algorithm 2 can be adapted to compute one most likely context in a more e cient way. The main idea is to order the calls in the for loop by decreasing probability. Once a context with j= has been found, it is guaranteed to be a most likely context and the algorithm may stop. This approach would still require exponential time in the worst case, even with a | oracle, since it requires the computation of the boundary. 4
The amount of work on handling uncertain knowledge with description logics
is too vast to cover in detail here. Many probabilistic description logics have
been de ned, which di er not only in their syntax but also in their use of the
probabilities and their application. These logics were recently surveyed in [
One of the rst attempts for combining BNs and DLs was P-Classic [
Perhaps the closest to our approach are the Bayesian extension of DL-Lite [
We have introduced probabilistic extensions of DLs. Our basic assumption is that we have certain knowledge, which depends on an uncertain situation, or context. In practical terms, this means that every axiom is associated to a context with the intended meaning that, if the context holds, then the axiom must be true. Uncertainty is represented through a BN that encodes the probability distribution of the contexts. The advantage of using Bayesian networks relies in their capacity of describing conditional independence assumptions compactly.
We have studied the complexity of reasoning in this probabilistic logic. We have shown that for expressive DLs, the complexity of reasoning is not a ected by the introduction of the contextual and probabilistic components. For tractable DLs the complexity of reasoning increases, which was expected since handling BNs is intractable in general. Moreover, we have shown that reasoning can be decoupled between the probabilistic and the logical components.
There are several directions for future work. One of them is to tighten the
complexity bounds for inexpressive DLs, in particular for the DL-Lite family, as
was done for EL [