Description Logics (DLs) supporting uncertainty are not as well studied and developed as their crisp counterparts, thereby limiting their practical use in real world domains. The Bayesian DL BEL and its extensions have been introduced to deal with uncertain knowledge without assuming (probabilistic) independence between axioms. In this paper we combine the classical DL ALC with Bayesian Networks to de ne a new DL known as BALC. BALC includes a solution to the consistency checking problem and changes to the tableaux algorithm that are not a part of BEL. Furthermore, BALC also supports probabilistic assertional information which was not studied for BEL. We present algorithms for four categories of reasoning problems for our logic; two versions of concept satis ability (referred to as total concept satis ability and partial concept satis ability respectively), knowledge base consistency, subsumption, and instance checking. We show that all reasoning problems in BALC are in the same complexity class as their classical variants, provided that the size of the Bayesian Network is included in the size of the knowledge base.
Description Logics (DLs) [1] supporting uncertainty are currently not as
mature and developed as their crisp conterparts. Moreover, many of the existing
approaches for handling uncertainty do not consider the meta-logical relations
between pieces of knowledge that is observed in contextual knowledge. The lack
of mature probabilistic reasoning services limits the application of DLs in many
real world domains, which often require reasoning about uncertain information.
As a simple example, when planning free time activities, the weather is often a
very real consideration. The kind of activities that are pleasant in poor weather
are often very di erent from summer activities. As such, building an ontology
that models activities will be quite di cult. However, considering the weather
as a context in which di erent pieces of knowledge hold simpli es this task. For
instance, the axiom
(Swimming v F un)Sunny
(
In a step towards reasoning with knowledge dependent on uncertain contexts, we study the Bayesian Description Logic BALC. BALC is a contextual Bayesian Description Logic based on the existing DL BE L and other Bayesian ontology languages [5, 6]. Unlike other families of probabilistic DLs (see e.g. [10] for a survey), Bayesian DLs do not directly encode the probabilities that concepts or roles are related, nor do they require independence assumptions between the different axioms in a knowledge base. Instead axioms and assertions are annotated with an optional context in which they are required to hold. The probability of these contexts holding is then represented using a Bayesian Network (BN). This gives Bayesian DLs the ability to perform conditional probabilistic reasoning. In terms of the underlying logic, our approach is similar to [12]. However, contrary to [12], we do not assume independence between the di erent axioms, but rather describe their joint probability distribution with the help of the contextual knowledge. 2
BALC Bayesian networks (BNs) are graphical models capable of representing the joint probability distribution of several discrete random variables in a compact manner. Given a random variable X, we denote as val(X) the set of values that X can take. For x 2 val(X), we denote as X = x the valuation of X taking the value x. This notation is extended to sets of variables in the obvious way. Given a set of random variables V , a world ! is a set of valuations containing exactly one valuation for every random variable X 2 V . A V -literal is an ordered pair of the form (Xi; x), where Xi 2 V and x 2 val(Xi). The name literal refers to them generalizing Boolean literals which are often denoted as x or :x for the random variable X. For simplicity, in this paper we will often use the notation X for (X; T ) and :X for (X; F ). A V -context is any set of V -literals. It is consistent if it contains at most one literal for each random variable. We will often call V -contexts primitive contexts.
De nition 1 (Bayesian Network). A Bayesian network is a pair B = (G; ) where G = (V; E) is a directed acyclic graph and is a set of conditional probability distributions for every variable X 2 V given its parents (X) on G: = fP (X = xj (X) = x0) j X 2 V g: BALC is a probabilistic extension of the classical DL ALC. The concept language for BALC is the same as for ALC, but axioms are considered to hold only in a given context. This is expressed by annotations given to these axioms, as formalized next.
De nition 2 (KB). Let V be a nite set of discrete random variables. A V -restricted general concept inclusion (V -GCI) is an expression of the form (C v D) where C and D are ALC concepts and is a V -context. A V -TBox is a nite set of V -GCIs. A V -restricted assertion (V -assertion) is an expression of the form C(x) or r(x; y) where C is an ALC concept, r is an ALC role name, x; y are individual names, and is a V -context. A V -ABox is a nite set of V -assertions. A BALC knowledge base (KB) over V is a triple K = (T ; A; B) where B is a BN over V , T is a V -TBox, and A is a V -ABox.
Note that this de nition does not prevent the encoding of classical statements. Axioms or assertions annotated with the empty set will hold in all contexts. We abbreviate (C v D); as (C v D) and C(x); as C(x). This means that every ALC KB is also a BALC KB. This fact will be useful in the following sections to provide lower bounds for the complexity of reasoning in BALC. When it is clear from the context, we will omit the V pre x and refer only to literals, contexts, GCIs, assertions, ABoxes, and TBoxes.
BALC uses a model-theoretic semantics. To formally de ne the notion of a model of a BALC KB, we rst introduce two di erent types of interpretations; V -interpretations and probabilistic interpretations. V -interpretations should be thought of as an interpretation linked to a speci c Bayesian world, while probabilistic interpretations take into account all worlds and their likelihood simultaneously.
De nition 3 (V -interpretation). A V -interpretation is a tuple of the form V = ( V ; V ; vV ) where V is a non-empty set called the domain, vV is a valuation function vV : V ! [X2V val(X) such that vV (X) 2 val(X), and V is an interpretation function that maps every concept name C to a set CV V and every role name r to a binary relation rV V V . The interpretation function vV is extended to complex ALC concepts as usual.
Given a valuation function vV , a Bayesian world !, and a context we denote vV = ! when vV assigns to each random variable the same value as it has in !; vV j= when for all (X; x) 2 we have that vV (X) = x; and ! j= there is ! = vV such that vV j= .
The V -interpretation V is a model of the GCI (C v D) , (V j= (C v D) ), i (i) vV 6j= , or (ii) CV DV . V is a model of the assertion C(x) (respectively r(x; y) ), denoted as V j= C(x) (respectively V j= r(x; y) ), i (i) vV 6j= , or (ii) xV 2 CV (respectively (xV ; yV ) 2 rV ). It is a model of the TBox T (ABox A) i it is a model of all the GCIs in T (assertions in A). It is a model of the knowledge base K i it is a model of both T and A.
V -interpretations focus on only a single world, but a KB has information about the uncertainty of being in one world or another. Probabilistic interpretations combine multiple V -interpretations and the probability distribution from the BN to give information about the uncertainty of some events. De nition 4 (Probabilistic interpretation). A probabilistic interpretation is a pair of the form P = (J ; PJ ), where J is a nite set of V -interpretations and PJ is a probability distribution over J such that PJ (V) > 0 for all V 2 J . The probabilistic interpretation P is a model of the GCI (C v D) , denoted as P j= (C v D) , i every V 2 J is a model of (C v D) . P is a model of the TBox T i every V 2 J is a model of T . P is a model of the assertion C(x) (respectively r(x; y) ), denoted as P j= C(x) (resp. P j= r(x; y) ), i every V 2 J is a model of C(x) (resp. r(x; y) ). P is a model of the ABox A i every V 2 J is a model of A.
The distribution PJ is consistent with the BN B if for every possible world ! of the variables in V it holds that
X V2J ;vV =!
PJ (V) = P (!): The probabilistic interpretation P is a model of the KB K = (T ; A; B) i it is a (probabilistic) model of both T and A, and is consistent with B. BALC allows for the notion of a complex context and a context language. Due to space limitations, we provide only the basic de nitions required for the presentation of the reasoning problems in BALC. For a thorough explanation, the interested reader can consult [4].
A complex context is a nite non-empty set of primitive contexts. Note that every primitive context can also be seen as a complex one by simply enclosing primitive context in an additional set; e.g., the primitive context corresponds to the complex context f g. Given a valuation function vV and a complex context = f 1; : : : ; ng we say that vV j= i vV satis es at least one i 2 . An immediate consequence of this de nition is that if vV j= then vV j= f g. Thus, in the following we assume that all contexts are in complex form unless explicitly stated otherwise. Finally we say that j= i for all vV j= then vV j= , or alternatively j= i for all Bayesian worlds ! such that ! j= then ! j= .
Given complex contexts = f 1; : : : ; ng and = f 1; : : : ; mg we de ne the operations _ ^ := := That is we de ne operations that ful ll the roles of propositional disjunction (_) and propositional conjunction (^), where disjunction has the property that either one of the two contexts holds and conjunction requires that both hold. Lemma 5. Given complex contexts
and , we have 1. ! j= 2. ! j= _ ^ i ! j= i ! j= or ! j= and ! j= , and
.
Two important special complex contexts are top (>) and bottom (?), which are de ned such that for all valuation functions vV , vV j= > and vV 6j=?. If there are n consistent primitive contexts these can be de ned as > := f 1; : : : ; ng and ?:= , where is any inconsistent context.
In the next section introduce and study the relevant decision and computation problems for our logic. 3
As a rst decision problem, we consider concept satis ability. Generalizing from the classical case, we say that a concept C is totally satis able if it is satis able in all the contexts of a knowledge base that have positive probability. De nition 6 (Total concept satis ability). A concept C is totally satis able with respect to a BALC KB K i there exists a probabilistic model P = (J ; PJ ) of K s.t. CV 6= ; for all V 2 J .
Notice that in the case that K is a classical ALC KB, then total concept satis ability corresponds precisely to concept satis ability.
When reasoning about BALC KBs it is useful to refer to the speci c TBox (or ABox) associated with a speci c Bayesian world !; i.e., the TBox (or ABox) containing only the axioms that hold in !. We call this reduced TBox (or ABox) a restriction to the world !, denoted as T! (or respectively A!). Formally, if K = (T ; A; B) is a BALC KB, and ! a world, the restriction of T and A to a world ! are de ned as
T! := f(C v D) j (C v D) 2 T ; ! j= A! := f j 2 A;
g 2 fC(x); r(x; y)g; ! j= g: One can think of total concept satis ability as requiring that a concept be classically satis able in each restricted knowledge base (T!, A!) where ! is a probabilistic world with positive probability.
Theorem 7. Given a BALC KB K, the concept C is not totally satis able in K i there exists a world ! such that P (!) > 0 and C is unsatis able in the ALC KB (T!; A!).
This theorem suggests a process for verifying total satis ability. In fact, it leads to a tight complexity bound for this problem.
Corollary 8. Total satis ability is ExpTime-complete.
Proof. The lower bound is a direct consequence from the fact that classical concept satis ability on a classical ALC KB is a special case of this problem, and is ExpTime-hard [13]. For the upper bound, an exponential time algorithm that solves total satis ability enumerates all (exponentially many) worlds, and for each such world ! it veri es that (i) P (!) > 0 (in polynomial space [9]) and that C is satis able in (T!; A!) (in exponential time [7]). tu u-rule if 1. (C1 u C2)(x) 2 A, and 2. either C1(x) or C2(x) is A-insertable then A0 := (A C1(x) ) C2(x) . t-rule if 1. (C1 t C2)(x) 2 A, and 2. both C1(x) and C2(x) are A-insertable then A0 := A C1(x) , A00 := A C2(x) . 91-rule if (9R:C)(x) 2 A, and there exists 2 such that (9R:C)(x) is A-insertable then A0 := A (9R:C)(x) 92-rule if (9R:C)(x) 2 A, there is no z such that both R(x; z) and C(z) are not
A-insertable, and x is not blocked then A0 := (A R(x; y) ) C(y) , where y is a new individual name and y > y0 for all individual names y0 2 A. 8-rule if 1. f(8R:C)(x) ; R(x; y) g A, and 2. C(y) ^ is A-insertable
then A0 := A C(y) ^ v-rule if 1. (C v D) 2 T ; E(x) 2 A, and 2. (:C t D)(x) ^ is A-insertable then A0 := A (:C t D)(x) ^ In the following, we provide a di erent algorithm that is also based on the idea of Theorem 7, but is more goal-directed. Before providing this algorithm, we must introduce some additional terminology. stricWteeduBsAeLCKC KtoBdwehneortee Cthies ncootntseaxtits thaabtle.dTeshcaritbiess!ajl=l woCKrlidsCthisatunlesaadtistoabrelein (T!; A!). Moreover, B is context that describes all worlds with probability greater than 0 in the BN; i.e., if ! j= B then P (!) > 0. Theorem 7 suggests that C is not totally satis able if there is a world that models both CK and B. This is formalized in the following theorem.
Theorem 9. The concept C is not totally satis able w.r.t. the KB K i is satis able.
C K ^ B We need to provide a method for computing the formulas CK and B. For the former, we present a variant of the glass-box approach for so-called axiom pinpointing [3, 8, 11], originally based on the ideas from [2]. The idea for this approach is to modify the standard tableaux algorithm for ALC, to keep track of the contexts in which the derived elements in the tableau hold. The modi ed tableaux rules are presented in Figure 1. Understanding these rules requires some additional notions that we present next.
An assertion C(x) is A-insertable in an ABox A i whenever there is a such that C(x) 2 A, then 6j= . In the expansion rules is used as shorthand for A C(x) := (A n fC(x) g) [ fC(x) _ g if C(x) 2 A and A [ fC(x) g otherwise; and A r(x; y) := (A n fr(x; y) g) [ fr(x; y) _ g if r(x; y) 2 A and A [ fr(x; y) g otherwise. The individual x is an ancestor of y if there is a chain of role assertions connecting x to y. The individual x blocks y i x is an ancestor of y and for every C(y) 2 A, it is the case that C(x) 2 A for some such that j= . An ABox contains a clash if it contains contradictory assertions. A rule application refers to applying one of the expansions rules to an ABox in order to generate a new ABox, and an ABox is fully expanded if none of the expansions rules can be applied to it.
Algorithm for nding CK: Given a BALC knowledge base K = (T ; A; B) and a concept C we start by asserting that there exists an instance of C by adding C(x)>, where x is a fresh individual name to A. We then apply the expansion rules in Figure 1 until all ABoxes are fully expanded. If at least one clash-free ABox is found, then return T =?.
If at least one clash is found in each completely expanded ABox then we know that there exists some valuation ! s.t. (T!; A!) is inconsistent. We now construct and return a context encoding these valuations. We do this by selecting a context representing a clash from each nal ABox and then combining these contexts. Suppose A1 : : : An are the completely expanded ABoxes then
CAi = _C(x) ;:C(x) 2Ai ( ^ ) is the context encoding all clashes for the i-th nal ABox. After constructing such a context for each nal ABox we combine them into the context CK = ^i=1 Ai n C : This construction algorithm is correct.
Theorem 10. The algorithm for nding C terminates and is sound and comK plete.
Finally, we have the following corollary that puts together all previously presented work to determine total concept satis ability. Once CK has been constructed we can determine whether K is totally concept unsatis able for C by iterating over all worlds ! and calculating P (!).
Corollary 11. C is not totally satis able in K i there is a world ! j= C such K that P (!) > 0.
As is usual for DLs we say that a BALC knowledge base is consistent if, and only if, it has a (probabilistic) model. We will often write P j= K when a probabilistic interpretation P is a model of K.
Recall that in our de nition of a V -interpretation we require that the domain V be non-empty. This leads us to the obvious consequence that a BALC knowledge base is only consistent if > is totally satis able.
Theorem 12. A BALC knowledge base K is consistent if, and only if, > is totally satis able in K.
This theorem shows that the BALC consistency problem can be reduced to an instance of the total concept satis ability problem. Leading to the following lemma.
Lemma 13 (Complexity of Consistency). Checking the consistency of a BALC KB is decidable in time O(2jjKjj). In fact, it is ExpTime-complete.
We now adapt the classical de nition of subsumption for BALC in order to take contexts into account. We do this by requiring that a concept subsumption hold only in the class of worlds that are relevant for a given context.
De nition 14 (Contextual Subsumption). Let K = (T ; A; B) be a BALC KB, C; D concepts, and a context. C is contextually subsumed by D in w.r.t. K, denoted as K j= (C v D) , if every probabilistic model of K is a probabilistic model of (C v D) .
In our setting, however, contexts are used as aids for expressing the uncertainty of di erent consequences (e.g., subsumptions) to hold. Hence, we introduce the notion of the probability of a subsumption.
De nition 15 (Probability of a Subsumption). Given the probabilistic model P = (J ; PJ ) of the KB K, and the concepts C; D, the probability of C v D is PP ((C v D) ) =
X V2J ;Vj=(CvD)
PK((C v D) ) = infPj=KPP ((C v D) ): That is, the probability of a subsumption in a speci c model is the sum of the probabilities of the worlds in which C is subsumed by D in context ; notice that this trivially includes all worlds where does not hold. In the case where K is inconsistent we de ne the probability of all subsumptions as 1 to ensure our de nition is consistent with general probability theory (recall that inf(;) = 1 in general).
Note that the relationship between the contextual subsumption problem and the probability of a subsumption is as one would expect. Namely we have that a KB entails a contextual subsumption i the probability of the subsumption in the KB is 1.
Theorem 16. Given a KB K, concepts C and D, and a context , it holds that:
K j= (C v D) i PK((C v D) ) = 1: This is convenient as it provides a method of reducing the contextual subsumption problem to calculating the probability of a subsumption. The following theorem provides a means of calculating this probability.
Theorem 17. For a consistent KB K = (T ; A; B), a contextual subsumption (C v D) , and the extended KB K0 = (T ; A [ fC(x) ; :D(x) g; B) we have PK((C v D) ) =
X P (!) + 1
P ( ): !j= K0 Furthermore, this approach runs in exponential time in the size of the input KB (assuming that the size of the BN; that is, the number of contexts, is included in the input).
Theorem 18. Given a knowledge base K we can calculate the probability of a contextual subsumption in time O(exp(jjKjj + jV j)). 5
Partial concept satis ability is a weaker form of satis ability in BALC that only requires the input concept to have a non-empty interpretation in some possible world. We formally de ne this notion next.
De nition 19 (Partial Concept Satis ability). The concept C is partially satis able with respect to the BALC KB K i there exists a probabilistic model P = (J ; PJ ) of K and a V -interpretation V 2 J , with PJ (V) > 0, and CV 6= ;. Clearly a concept cannot be even partially satis able if it is necessarily empty in all worlds. This yields the following theorem.
Theorem 20. A concept C is partially satis able with respect to a BALC KB K i K 6j= C v?.
We complete this analysis by using the fact that if a KB is s.t. PK((C v?)>) = 1 then there exist no model which has a V -interpretation where C is not empty. Theorem 21. C is not partially satis able in K i P ((C v?)>) = 1. Next, we de ne the probability of partial satis ability in a similar way to the probability of a subsumption. That is, we rst de ne the probability of partial satis ability for a concept C in a probabilistic interpretation and then use this to de ne it in the context of a knowledge base.
De nition 22 (Probability of Partial Satis ability). Given a concept C and a KB K, the probability of C being partially satis able in a probabilistic model P of K is
PP (C) :=
X We can reduce this problem to subsumption, in particular the probability of a subsumption.
Theorem 23. C is partially satis able in K with probability 1 PK((C v?)>).
Overall, this means that we can deal with this problem, within the same complexity bounds as in classical reasoning in ALC, as long as we are able to handle total concept satis ability, and the probability that it holds. Thus, we have already developed a method for solving it. We now turn our attention to instance checking, and the in uence of the ABox in reasoning.
We consider a probabilistic extension to the classical instance checking problem. In BALC we call this problem probabilistic instance checking and we de ne both a decision problem problem and probability calculation for it next. De nition 24 (Instance). Given an individual name a, a concept C, a primitive context , and a KB K, we say that a is an instance of C in for K, written as K j= C(x) , i for all probabilistic models P = (J ; PJ ) of K it holds that aV 2 CV for all V 2 J with vV j= .
Note that if the context associated with the instance check is > this de nition recalls the classical case. In this case it would be required that the named individual be a member of the concept in all cases (in all worlds with positive probability) which is exactly what would be veri ed in a classical KB which has only one context with probability 1. We next show how we go about providing a procedure that solves this problem.
Theorem 25. Given an individual name a, a concept C, a context , and a KB K = (T ; A; B), a is an instance of C in i PK0 ((D v C) ) = 1 where D is a new concept name not in T and K0 = (T ; A [ fD(a) g; B).
Since we have reduced instance checking to probabilistic subsumption we have the result that instance checking is in the same complexity class as probabilistic subsumption. This gives us the following lemma.
Lemma 26. Probabilistic instance checking in a knowledge base K is in the complexity class O(2jjKjj+jV j).
We next formalize the probability calculation for the instance checking problem. This is done in a very similar way to the probability of a subsumption. De nition 27 (probability of an instance). The probability of an instance in a probabilistic model P = (J ; PJ ) of a KB K is
PP (C(x) ) =
X V2J ;Vj=C(x)
PK(C(x) ) = inf PP (C(x) ):
Kj=P The probability of all instance checks for an inconsistent KB is always 1 to keep our de nitions consistent with probability theory.
Similar to the algorithm for solving the decision problem we now show that the probability calculation can be reduced to subsumption.
Theorem 28. Given the individual name a, concept C, primitive context , and KB K = (T ; A; B), a is an instance of C in with probability PK0 ((D v C) ) where D is a new concept name not in T and K0 = (T ; A [ fD(a) g; B). From this result we again see that calculating the probability of an instance can be reduced in constant time to probabilistic subsumption. Since we only add a single statement to the ABox of the knowledge base the input size does not change meaningfully post reduction.
Lemma 29. The probability of an instance in a KB K can be computed in time O(2jjKjj+jV j). 7
We have presented a new probabilistic extension of ALC based on the ideas of Bayesian ontology languages. In contrast to previous work that focused mainly on light-weight DLs, in our logic it is possible to express inconsistent knowledge, which requires the study of new reasoning problems. We developed a glass-box tableaux-based algorithm for nding out the context in which a given consequence holds. Using this information, we could also compute the probability of the consequence itself.
We showed, using the properties of the semantics of BALC that all the reasoning problems studied remain ExpTime-complete, just as the complexity of reasoning in classical ALC. Our results also hint at possible optimizations that can be exploited in an attempt to develop an e cient reasoner for our logic. In particular, we have shown that variations of the well-known tableau algorithm for ALC can be used. As future work, we plan to study these optimizations in detail, and analyse their applicability in practice.
Another interesting line of work would be to implement our ideas, and compare the resulting tool against other probabilistic DL reasoners. In particular, it would be interesting to compare against the tools from [14], which are also based on an extension of the tableaux algorithm, and use probabilistic semantics that are very similar to ours. Although a direct comparison would be unfair, given that the semantics from [14] are based on very strong independence assumptions, it should be possible to at least obtain a general idea of the behaviour of the two methods. 3. Baader, F., Pen~aloza, R.: Axiom pinpointing in general tableaux.
Journal of Logic and Computation 20(
Cape Town, South Africa (2018)
5. Ceylan, I_.I_., Pen~aloza, R.: The Bayesian description logic BEL. In: Demri, S.,
Kapur, D., Weidenbach, C. (eds.) Proceedings of the 7th International Joint
Conference on Automated Reasoning (IJCAR 2014). Lecture Notes in Computer Science,
vol. 8562, pp. 480{494. Springer (2014)
6. Ceylan, I_.I_., Pen~aloza, R.: The Bayesian ontology language BEL. Journal of
Automated Reasoning 58(
In: Mylopoulos, J., Reiter, R. (eds.) Proc. of the 12th Int. Joint Conf. on Arti cial Intelligence (IJCAI 1991). pp. 466{471. Morgan Kaufmann (1991) 14. Zese, R., Bellodi, E., Riguzzi, F., Cota, G., Lamma, E.: Tableau reasoning for description logics and its extension to probabilities. Ann. Math. Artif. Intell. 82(13), 101{130 (2018). https://doi.org/10.1007/s10472-016-9529-3