This paper analyzes the probabilistic description logic PSHIQ by looking at it as a fragment of probabilistic rst-order logic with semantics based on possible worlds. We argue that this is an appropriate way of investigating its properties and developing extensions. We show how the previously made arguments about di erent types of rst-order probabilistic semantics apply to P-SHIQ. This approach has advantages for the future of both P-SHIQ, which can further evolve by incorporating semantic theories developed for the full rst-order case, and the rst-order logic, for which very few interesting decidable fragments are currently known. The paper also presents a probabilistic logic P-SHIQ+ which addresses some of the identi ed limitations of P-SHIQ.
A common complaint about Description Logics (DLs), especially as the basis for ontology languages, is that they fail to support non-classical representations of uncertainty. While DLs typically can represent and reason with some forms of uncertainty (e.g., with existential or disjunctive information) in a variety of ways , until recently they have not handled probability.
One answer to this complaint is the P-SH family of logics which allow for the
incorporation of probabilistic formulae as an extension of the familiar and widely
used SH DLs. Unlike Bayesian extensions to DLs (e.g., [
However, there are several issues with the P-SH family both from an expressivity and from a theoretical point of view. First, it has not been fully clear whether it properly combines statistical and subjective probabilities. Second, probabilistic ABoxes have a number of strong and strange restrictions (including no probabilistic roles and only one probabilistic individual per ABox). Finally, the semantics of the P-SH family (in terms of possible worlds) is not particularly familiar in the DL setting.
It is standard to analyze DLs by considering them as fragments of
rstorder logic. In this paper, we apply this methodology to the analysis of the
P-SH family of probabilistic DLs by considering them as fragments of FOPL2
(FOL with possible world based semantics [
P-SHIQ
P-SHIQ [
Semantics and Reasoning with P-SHIQ Although the semantics of
PSHIQ is standardly given in terms of possible worlds [
It is convenient to de ne probabilistic models using types. A probabilistic interpretation P r is a function P r : T ypes(O ! [0; 1]) such that PT 2T ypes(O) P r(T ) = 1. The probability of a concept C, denoted as P r(C), is de ned as PT a`C P r(T ). P r(DjC) is used as an abbreviation for P r(C u D)=P r(C) given P r(C) > 0. A probabilistic interpretation P r satises a conditional constraint (DjC)[l; u] (or P r is a model of (DjC)[l; u]) denoted as P r j= (DjC)[l; u] i P r(C) = 0 or P r(DjC) 2 [l; u]. Finally, P r satis es a set of conditional constraints P i it satis es each of the constraints.
The following are the core reasoning problems of P-SHIQ [
FOPL2 is a probabilistic generalization of rst-order logic aimed at capturing
belief statements (the subscript 2 stands for the Type 2 semantics [
P (t1; : : : ; tn) is an atomic formula. { If t1; t2 are eld terms, then t1 t2, t1 t2, t1 < t2, t1 > t2, t1 = t2 are atomic formulas. Standard relationships between (in)equality relations are assumed to hold. { If ; are formulas and x 2 Xo, then ^ , _ , 8(x) , 9(x) , : are formulas. Standard relationships between logical connectives and quanti ers are assumed to hold.
Finally, the denotation w( j ) t is the abbreviation of w( ^ ) t w( ).
Semantics of FOPL2 A probabilistic interpretation (Type 2 probability
structure in [
Field terms of the form w( ) are associated as follows: [w( )]M;v = fs 2 Sj(M; s; v) j= g.
{ (M; s; v) j= P (x) if v(x) 2 (s; P ). { (M; s; v) j= t1 < t2 if [t1]M;s;v < [t2]M;s;v.
{ (M; s; v) j= 8(x) if (M; s; v[x=d]) j= for all d 2 D.
Other formulas, e.g. ^ , : , t1 = t2, etc. are de ned as usual. It remains to de ne the mapping for the eld terms of the form w( ): [w( )]M;v = fs0 2 Sj(M; s0; v) j= g (note that the association does not depend on a state here).
As usual, a FOPL2 formula is called satis able if there exists an interpretation
and a valuation in which the formula is true. It is called valid (denoted j= ) i
it is satis ed by all interpretations and valuations. More detailed exposition of
FOPL2 2 can be found in [
This section presents a translation between P-ALCI and the FOPL2. For the sake of brevity we will limit our attention to ALCI concepts as the translation can be extended to SHIQ concepts in a straightforward way (inverse roles are included because they will be important in the following section). We will show that the translation preserves satis ability of formulas so that P-SHIQ can be viewed as a fragment of FOPL2. 2.1
We rst de ne the injective function to be the mapping of P-ALCI
formulas to FOPL2. It is a superset of the standard translation of ALCI formulas
into the formulas of FOL [
This function transforms a P-ALCI ontology into the collection of FOPL2 theories. More precisely, a PTBox is transformed into a set of formulas while each PABox is translated into its own FOPL2 theory. This is because PABox axioms in P-SHIQ are treated as PTBox axioms (just labeled with the individual name) so they do not correspond to ground formulas in FOPL2. Interestingly, in our extension of P-SHIQ (see Section 3) they do (as they should).
Proof. The proof will proceed by construction, i.e. we will show that a satisfying probabilistic model in P-SHIQ can be transformed into a satisfying probabilistic interpretation in FOPL2 and vice versa.
()): Assume there exists P r : T ypes(O) ! [0; 1] s.t. P r j= T and P r j= P.
We will construct M = (D; S; ; ) s.t. M j= ( ) for all 2 T [ P. For
that we rst observe that the existence of P r implies the existence of a SHIQ
interpretation: ( I ; I ) j= T [
The key is to construct the set S and ensure the following property: P r(fCt 2 T ypes(O)jCt a` Cg) = (fs 2 Sj(M; s; v) j= (C)g) for any concept C and some valuation v (1)
Property (1) guarantees that P r(C) = ( (C)) for all (C 2 cl(T ) (hence P r j= (DjC)[l; u] implies (M; v) j= l w( (D; x)j (C; x)) u for some v). It can be achieved by de ning a straightforward bijection between types and states using . For each type Ct = fC1; : : : ; Ckg we de ne a state s = f (C1; x); : : : ; (Ck; x)g (we use s = (Ct) as a shorthand notation). It is not hard to see that, if di Ci is satis able w.r.t. T then Vi (Ci; x) is satis able w.r.t. (T ).
Similarly to P-SHIQ we use the notation s a` where is a translation of some ALCI concept expression into FOPL2 i 2 s. We leave out the demonstration that Ct a` C implies (Ct) a` (C; x).
Finally, we de ne the probability function: (s) = P r( 1(s)) for all s 2 S.
It remains to show that M = (D; S; ; ) satis es the corresponding formula in FOPL2 and some valuation v. For the sake of brevity we will only show this for probabilistic axioms. Consider a PTBox axiom (BjA)[l; u]. It is translated into the formula l w( (B; x)j (A; x)) u. Now PPCCtat`aB`AuAPP(C( Ct)t) 2 [l; u], therefore Psa` (B;x)^ (A;x) (s) 2 [l; u] (by de nition of S and ). In order to show that
Psa` (A;x) (s) this is equivalent to fs2S:(M;s;v)j=B(x)^A(x))g 2 [l; u] it su ces to prove that, if fs2S:(M;s;v)j=A(x)g there exists a state s0 2 S in M s.t. s0 a` c(x) (c is a unary predicate) then there exists a valuation v s.t. (M; s0; v) j= c(x). Take some s0 2 S. Then there exists v : (M; s0; v) j= c1(a) ^ ^ ck(a) ^ (T ) where a is a fresh constant (this follows from consistency of concept types). Since c = ci 2 s0 for some i it follows that (M; s0; v[a=x]) j= c(x).
(() can be shown completely analogously, so we skip the details. 2 2.3
This translation provides a new insight into both P-SHIQ and FOPL2 being valuable for the following reasons:
Firstly, while it has been claimed that P-SHIQ can represent and reason
about both statistical and subjective (i.e. degrees of belief) knowledge [
Secondly, the translation helps to understand the limitations of P-SHIQ, namely, the inability to combine probabilistic knowledge about multiple individuals in a single ABox, unnatural separation of classical and probabilistic individuals, inability to represent probabilistic relationships between roles, etc. The common reason behind all those issues is that the set of states S is quite coarsegrained and contains only information about concepts, but not roles or named individuals (constants). We will take it up in Section 3 in which extensions to P-SHIQ are proposed.
Finally, the translation is also valuable for the analysis of FOPL2. Since it is a highly undecidable logic it is natural to analyze its interesting decidable fragments and P-SHIQ is one of such fragments. It is known that all fragments of FOPL2 that have bounded model property are decidable. Interestingly PSHIQ does not have such property (because SHIQ does not have nite model property) but it is decidable which suggests that there might be other criteria for decidability. In particular, it is known that given the unrestricted use of variables it is undecidable even with a single unary predicate. 3
P-SHIQ has a number of limitations which are caused by two main reasons. First, it does not make use of all features that can be supported by the FOPL2 semantics. Second, as brie y explained in the previous section, possible world semantics is not the best ground for representing and reasoning with statistical knowledge. In this paper we attempt to address the rst type of limitations (the resulting logic will be called P-SHIQ+). The important issues, which will be addressed in P-SHIQ+, are the following:
Separation between classical and probabilistic individuals. In PSHIQ all named individuals are split onto those for which there is some probabilistic knowledge (i.e. PABox axioms) and those for which there is not. As a result, there is no straightforward way to combine classical and probabilistic reasoning for a single individual although that seems a very natural thing to do. For example, consider the following knowledge base: Example 2. fBig u Dense v Heavy; ball : Big; (ball : Dense)[0:9; 1]g Intuitively the answer to the query ball : (Heavy)[?; ?] should be [0:9; 1]. However, due to the separation, the two balls are regarded as distinct individuals so such entailment is not supported. There are, of course, workarounds, for example, it is possible to do some sort of \punning" between the two balls and obtain the desired result.
Isolated PABoxes. P-SHIQ does not allow for the representation of
probabilistic role assertions between probabilistic individuals. In other words, while
it is possible to state that (jim : P arent)[0:9; 0:95] it is not possible to state that
((jim; pete) : parentOf )[0:9; 0:95]. There is a way to represent probabilistic role
assertions in P-SHOIN but only between a classical and a probabilistic
individual [
No support of probabilistic role hierarchies. P-SHIQ only supports generic probabilistic relationships between concepts but not roles.
We next proceed to the syntax and semantics of P-SHIQ+. Syntactically, P-SHIQ+ di ers from P-SHIQ in two main aspects. Firstly, the notion of a conditional constraint is extended. Secondly, instead of a collection of independent PABoxes in P-SHIQ, a P-SHIQ+ ontology contains only a single probabilistic component, namely, a collection of conditional constraints. One preliminary de nition is needed.
De nition 3 (Entity). An entity in P-SHIQ+ is one of: role, concept, concept assertion, role assertion.
Intuitively, entities are the things that can appear in conditional constraints. Now we can de ne the extended syntax of conditional constraints. De nition 4 (Conditional Constraint). A conditional constraint in P-SHIQ+ is an expression of the form: ( j )[l; u] where ; are entities. Note that every conditional constraint in P-SHIQ is a well-formed conditional constraint in P-SHIQ+. No other probabilistic formulas are allowed. A probabilistic ontology in P-SHIQ+ has a simpler structure than in P-SHIQ: De nition 5 (Probabilistic Ontology). A probabilistic ontology in P-SHIQ+ is a tuple P O = (O; P) where O = (T ; A) is a SHIQ ontology3 and P is a nite collection of conditional constraints.
Any P-SHIQ ontology can be represented as a P-SHIQ+ ontology, however, the representation of PABox constraints is a bit di erent. Instead of implicitly attributing statements of the form (Cj>)[l; u] to a particular individual, it is represented as (C(a)j>)[l; u] and becomes an element of P. In other words, PABox constraints in P-SHIQ+ correspond to ground probabilistic formulas in FOPL2 while in P-SHIQ they do not. From an analysis of P-SHIQ alone, it may not be immediately clear that its drawbacks can be addressed. However, looking at the corresponding fragment of FOPL2 immediately reveals that none of the limitations is fundamental. FOPL2 does not require any separation between constants and neither does it prohibit attaching probabilities to binary predicates. In fact, what is necessary from the FOPL2 point of view is that the speci cation of the states provides enough 3 Role hierarchies are assumed to be a part of the TBox. information to determine if a particular formula is true at the given state (to be able to assign probabilities to weighted formulas). P-SHIQ speci cation only allows that for unary predicates and their combinations. We are going to extend it to binary predicates as well. It is worth noting that FOPL2 does not impose restrictions on the set of states, so one is free to extend it in an arbitrary way.
Recall from Section 1 that states in P-SHIQ are types, that is, subsets of the closure of relevant concepts. Unfortunately types do not provide enough information about relationships between domain objects. Our idea is to extend single type structures to two type structures, which we call links. Informally, a link is a speci cation of an ordered pair of domain elements which includes types of both as well as relationships between them.
De nition 6 (Extended Concept Type). Concept types in P-SHIQ+ are extensions of P-SHIQ concept types which may contain individual names. They have to satisfy one additional requirement, namely, if a 2 Ct and a : C 2 O then C 2 Ct. ctype is also extended: ctype(e) = Ct if additionally e = aI for all a 2 Ct. De nition 7 (Role type). Let R be the set of roles in an ontology O = (T ; A) (i.e. role names and their inverses) that can participate in probabilistic statements. Then a role type Rt is a subset of R that satis es the following condition: if R 2 Rt and R v S 2 O or Inv(R) v Inv(S) 2 O then S 2 Rt.
Given an interpretation ( I ; I ) j= O, a pair of domain elements (e; f ) is an instance of a role type Rt if (e; f ) 2 RI for all R 2 Rt.
Analogously to ctype, the function rtype(e; f ) = fRtj(e; f ) is instance of Rtg. Observe that it is also a well-de ned, total function.
De nition 8 (Link). A link L is a tuple (Ct1; Rt; Ct2) where Ct1; Ct2 are in T ypes(O) and Rt is a role type such that: { If 8R:C 2 Ct1 and R 2 Rt then C 2 Ct2. { If 8R:C 2 Ct2 and Inv(R) 2 Rt then C 2 Ct1. { If 0R:C 2 Ct1 and R 2 Rt then :_ C 2 Ct2.
{ If 0R:C 2 Ct2 and Inv(R) 2 Rt then :_C 2 Ct1.
De nition 9 (Instantiation function). Given a model I = ( I ; I ) j= O the function link(e; f ) on the set of pairs of domain elements is de ned as (ctype(e); rtype(e; f ); ctype(f )) where ctype is the concept type function and rtype is the role type function.
Observe that link is a well-de ned function since ctype and rtype are wellde ned. It is important to emphasize that links inherit the key property of types that any ordered pair of domain elements is an instance of one and only one link. We use Links(O) to denote the set of all links L such that there exists an interpretation I = ( I ; I ) of O and e; f 2 I with link(e; f ) = L.
Now we can de ne the notion of consistency between a link and an entity. De nition 10 (Consistency with an Entity). A link (Ct1; Rt; Ct2) is consistent with an entity w.r.t. the ontology O (denoted as L a` ) if: { If is a role R and R 2 Rt, { If is a concept C and C 2 Ct1, { If is a concept assertion C(e) and fe; Cg 2 Ct1, { If is a role assertion R(e; f ) and (e 2 Ct1 and R 2 Rt and f 2 Ct2) or (f 2 Ct1 and R 2 Rt and e 2 Ct2).
We now proceed to probabilistic models in P-SHIQ+.
De nition 11 (Probabilistic Interpretation, Probability of an Entity). A probabilistic interpretation P r of a probabilistic ontology P O = (O; P) is a probability function on Links(O) (a mapping P r : Links(O) ! [0; 1] s.t. PL2Links(O) P r(L) = 1.
The probability of an entity denoted as P r( ) is the sum PL2Link(T );La` P r(L). Probability of the conjunction of two entities P r( ^ ) is the sum PL2Links(O);La` ;La` P r(L). Conditional probability P r( j ) is an abbreviation of P r( ^ )
P r( ) .
As long as any xed ordered pair of domains elements is an instance of one and only one link, we can compute the probability of an entity as a sum of probabilities of all links which are consistent with it (intuitively, links are disjoint, that is, do not share elements, and exhaustive i.e., cover the space of all pairs). For example, the probability of a role is a total probability of all links in which the ordered pair of individuals is related via this role (informally this means \the probability that a randomly selected pair is related via the role"). De nition 12 (Probabilistic Satis ability, Logical Entailment). A probabilistic interpretation P r satis es (or is a model of ) a P-SHIQ+ formula ( j )[l; u] (denoted as P r j= ) if P r( j ) 2 [l; u]. P r satis es a collection of P-SHIQ+ formulas if it satis es all of them. P r satis es an ontology (O; P) if P r j= P.
A P-SHIQ+ formula ( j )[l; u] is a logical consequence of a P-SHIQ+ ontology P O if it is satis ed by all probabilistic models of P O. It is a tight logical consequence of P O if l (resp. u) is the minimum (resp. the maximum) over all P r j= P O such that P r( ) > 0.
Problems of deciding probabilistic satis ability (PSAT) and computing tight
logical entailment (TLogEnt) are stated equivalently to P-SHIQ (see [
One can verify that P-SHIQ+ is a fragment of FOPL2 by adapting the translation of P-SHIQ to FOPL2. All that has to be changed in the proof of Theorem 1 is the construction of states so that they correspond to links. Finally we present a few examples of the P-SHIQ+ advantages over P-SHIQ: Example 4 (Combining classical and probabilistic individuals). Consider the ontology from the Example 2. Now both occurrences of ball denote the same individual. The probability of Heavy(ball) is de ned as: P r(Heavy(ball)) = PIj=Heavy(ball) P r(I). Consider the set of links that are consistent with ball. All of them have Big in the rst concept type and at least 90% also have Dense. This means that at least 90% of them have Heavy in the rst concept type (by the de nition of types), therefore the result is [0:9:1] as it should be. Example 5 (Probabilistic role assertions). Ontology from the Example 3 is a wellformed P-SHIQ+ ontology. The answer to the query (john : (T all u 9f riendOf::T all)[?; ?] is [0:5; 0:9].
Example 6 (Probabilistic role hierarchies). It is possible to assert in P-SHIQ+ that at least 60% of classmates are friends: (f riendOf jclassmateOf )[0:60; 1]. 3.3
P-SHIQ+ does address some important limitations of P-SHIQ but it is still not a fully appropriate formalism for representing and reasoning with statistical knowledge. Its semantics is based on possible worlds (links) which results in counterintuitive inference in some situations (see Example 1). No further extension of the possible world semantics can solve this issue, so it is natural to investigate the possibilities of using domain probability distributions.
At the moment it is not entirely clear whether the improper handling of
statistics turns out to be critical in practical modeling or not. To be visible the
problem requires some speci c interaction between interpretations of concepts
and probabilistic axioms. However, designers of probabilistic ontologies must be
aware of it. We are planning to investigate this issue by extending the previously
created BRCA ontology [
Conclusion In this paper we presented a new look at the probabilistic description logic PSHIQ as a fragment of probabilistic rst-order logic. We gave a formal syntactic translation of P-SHIQ knowledges bases into FOPL2 theories and proved its faithfulness. This brought an extra insight into P-SHIQ, most importantly, into its limitations, both those that can be addressed by extending the existing possible world based semantics and those which cannot.
We then proceeded to address the rst type of limitations and presented an
extended logic P-SHIQ+ which adds a few important capabilities to the
existing arsenal. Namely, it enables full probabilistic role assertions, probabilistic role
hierarchies and eliminates the unnatural separation between classical and
probabilistic individuals. The logic is still decidable and even has the same worst case
complexity as P-SHIQ. Our next goal is to implement P-SHIQ+ by applying
techniques that proved useful for P-SHIQ [