=Paper=
{{Paper
|id=Vol-477/paper-23
|storemode=property
|title=On Correspondences between Probabilistic First-Order and Description Logics
|pdfUrl=https://ceur-ws.org/Vol-477/paper_40.pdf
|volume=Vol-477
|dblpUrl=https://dblp.org/rec/conf/dlog/KlinovPS09
}}
==On Correspondences between Probabilistic First-Order and Description Logics==
https://ceur-ws.org/Vol-477/paper_40.pdf
On Correspondences between Probabilistic
First-Order and Description Logics
Pavel Klinov, Bijan Parsia, and Ulrike Sattler
School of Computer Science,
University of Manchester, UK
{pklinov,bparsia}@cs.man.ac.uk
Abstract This paper analyzes the probabilistic description logic P-
SHIQ by looking at it as a fragment of probabilistic first-order logic
with semantics based on possible worlds. We argue that this is an ap-
propriate way of investigating its properties and developing extensions.
We show how the previously made arguments about different types of
first-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 first-order case,
and the first-order logic, for which very few interesting decidable frag-
ments are currently known. The paper also presents a probabilistic logic
P-SHIQ+ which addresses some of the identified limitations of P-SHIQ.
1 Introduction and Preliminaries
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., [1]), the P-SH family
consists of purely logical extensions to the semantics and inference services.
These logics are also decidable, generally of the same worst case complexity as
the base logic, and can be implemented on top of existing DL reasoners [2].
However, there are several issues with the P-SH family both from an ex-
pressivity 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 first-
order 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 [3]). This analysis yields insight into
the semantics of P-SHIQ and into principled ways of extending it to address
troublesome limitations.
1.1 P-SHIQ
P-SHIQ [4] is a probabilistic generalization of the DL SHIQ. It has a number
of properties that make it an attractive formalism for managing uncertainty
in OWL ontologies. First, it is very expressive as it supports arbitrary SHIQ
concepts in probabilistic axioms. Second, any SHIQ ontology can be used as
a basis for a P-SHIQ ontology which facilitates transition from classical to
probabilistic ontological models [5]. Thirdly, its reasoning tasks are decidable.
Syntax of P-SHIQ The syntax of P-SHIQ is an extension of the syntax of
SHIQ with conditional constraints [6]. Conditional constraints are expressions
of the form (D|C)[l, u] where C and D are SHIQ concepts1 . Conditional con-
straints can be used for representing uncertainty in both terminological (TBox)
and assertional (ABox) knowledge. A probabilistic TBox (PTBox) is a 2-tuple
P T = (T , P) where T is a SHIQ TBox and P is a finite set of default2 condi-
tional constraints. Informally, a PTBox axiom (D|C)[l, u] means that “generally,
if a randomly chosen individual belongs to C, its probability of belonging to D
is between l and u”. A probabilistic ABox (PABox) is a finite set of strict condi-
tional constraints pertaining to a single probabilistic individual o. All constraints
in a PABox are of the restricted form (D|>)[l, u]. Informally, they mean that “o
is a member of D with probability between l and u” [4].
Semantics and Reasoning with P-SHIQ Although the semantics of P-
SHIQ is standardly given in terms of possible worlds [4], we present a slightly
different formulation based on a closely related notion of types [7]. This will
help to ensure uniform use of terminology in the later sections. Two preliminary
notions are needed:
Definition 1 (Closure, Concept Type). For an ontology O = (T , A), where
T is a TBox and A is an ABox, the concept closure of T , denoted as cl(T ), is
the smallest set of concepts such that:
– > is in cl(T ),
– For all C v D ∈ T , C and D are in cl(T ),
– If C ∈ cl(T ) then its subconcepts are in cl(T ),
– If C ∈ cl(T ) then ¬C
˙ (negation in the negation normal form) is in cl(T ).
A concept type Ct of an ontology O is a subset of cl(T ) such that for all C ∈ Ct,
C ∈ Ct iff ¬C
˙ ∈/ Ct. Given an interpretation (∆I , ·I ) |= T , a domain element
e ∈ ∆ is an instance of type Ct iff e ∈ C I for all C ∈ Ct.
I
1
Without loss of generality we will further assume that C, D are atomic concepts.
2
Default aspects of P-SHIQ are immaterial in the context of this paper.
d = {Ct|e is instance of Ct} is a well-defined function. The
The relation ctype(e)
set {Ct ⊆ cl(T )| Ci ∈Ct Ci is satisfiable w.r.t. T } is denoted T ypes(O).
Definition 2 (Type Consistency). A type Ct is said to be consistent with a
concept C (Ct a` C) if C ∈ Ct.
It is convenient to define probabilistic models using types. A probabilistic
interpretation
P P r is a function P r : T ypes(O → [0, 1]) such that
T ∈T ypes(O) P
P
r(T ) = 1. The probability of a concept C, denoted as P r(C), is
defined as T a`C P r(T ). P r(D|C) is used as an abbreviation for
P r(C u D)/P r(C) given P r(C) > 0. A probabilistic interpretation P r satis-
fies a conditional constraint (D|C)[l, u] (or P r is a model of (D|C)[l, u]) denoted
as P r |= (D|C)[l, u] iff P r(C) = 0 or P r(D|C) ∈ [l, u]. Finally, P r satisfies a set
of conditional constraints P iff it satisfies each of the constraints.
The following are the core reasoning problems of P-SHIQ [8]:
– Probabilistic Satisfiability (PSAT). PSAT is the problem of deciding whether
there exists a probabilistic interpretation that satisfies given PTBox.
– Tight Logical Entailment (TLogEnt). TLogEnt is the problem of computing
the tightest probability intervals for logical consequences.
1.2 First-Order Probabilistic Logic
FOPL2 is a probabilistic generalization of first-order logic aimed at capturing
belief statements (the subscript 2 stands for the Type 2 semantics [3]), like
“the probability that Tweety (a particular bird) flies is over 90%” [3]. It is very
expressive allowing to attach probabilities to arbitrary first-order formulas (both
closed and open). Its representational and computational properties have been
well investigated, and the results are applicable to its fragments.
Syntax of FOPL2 The syntax of FOPL2 is defined as follows [3]: assume a
first-order alphabet Φ of function and predicate names, and a countable set of
object variables X o . Object terms are formed by closing X o off under function
application as usual. The language also contains field terms, which range over
reals (with 0 and 1 being distinguished constants), and probability terms of the
form w(φ), where φ is a first-order formula. Field terms are closed off under
applications of functions ×, + on reals (e.g., t1 + t2 is a field term iff t1 , t2 are).
Then FOPL2 formulas are defined as follows:
– If P is an n-ary predicate name in Φ and t1 , . . . , tn are object terms, then
P (t1 , . . . , tn ) is an atomic formula.
– If t1 , t2 are field 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 ∈ X o , then φ ∧ ψ, φ ∨ ψ, ∀(x)φ, ∃(x)φ, ¬φ are
formulas. Standard relationships between logical connectives and quantifiers
are assumed to hold.
Finally, the denotation w(φ|ψ) ≤ t is the abbreviation of w(φ ∧ ψ) ≤ t × w(ψ).
Semantics of FOPL2 A probabilistic interpretation (Type 2 probability struc-
ture in [3]) M is a tuple (D, S, π, µ), where D is a domain, S is a set of states
(sometimes called possible worlds), π is a function S × Φ → ΦD (where ΦD is a
set of predicates and functions over D) which preserves arity, and µ is a prob-
ability distribution over S. Let v be valuation function that maps each object
variable to an element of D. Then M together with a state s and a valuation v
associates each object term t with an element of D ([t]M,s,v ∈ D) and each field
term t with a real number. (M, s, v) also associate formulas with truth values as
follows (we write (M, s, v) |= φ iff φ is true in M ):
Field terms of the form w(φ) are associated as follows: [w(φ)]M,v = µ{s ∈
S|(M, s, v) |= φ}.
– (M, s, v) |= P (x) if v(x) ∈ π(s, P ).
– (M, s, v) |= t1 < t2 if [t1 ]M,s,v < [t2 ]M,s,v .
– (M, s, v) |= ∀(x)φ if (M, s, v[x/d]) |= φ for all d ∈ D.
Other formulas, e.g. φ ∧ ψ, ¬ψ, t1 = t2 , etc. are defined as usual. It remains
to define the mapping for the field terms of the form w(φ): [w(φ)]M,v = µ{s0 ∈
S|(M, s0 , v) |= φ} (note that the association does not depend on a state here).
As usual, a FOPL2 formula is called satisfiable if there exists an interpretation
and a valuation in which the formula is true. It is called valid (denoted |= φ) iff
it is satisfied by all interpretations and valuations. More detailed exposition of
FOPL2 2 can be found in [3].
2 Correspondences between P-SHIQ and FOPL2
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 satisfiability of formulas so that P-SHIQ can be
viewed as a fragment of FOPL2 .
2.1 Syntactic Translation
We first define the injective function κ to be the mapping of P-ALCI formu-
las to FOPL2 . It is a superset of the standard translation of ALCI formulas
into the formulas of FOL [9] (in the Table 2.1 A, B stand for concept names,
R for role names, C, D for concept expressions, P for role names or inverses,
var ∈ {x, y}; var0 = x if var = y and y if var = x).
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).
Table 1. Translation of P-ALCI formulae into FOPL2
P-ALCI FOPL2
κ(A, var) A(var)
κ(¬C, var) ¬(κ(C, var))
κ(R, var, var0 ) R(var, var0 )
κ(R− , var, var0 ) R(var0 , var)
κ(C u D, var) κ(C, var) ∧ κ(D, var)
κ(C t D, var) κ(C, var) ∨ κ(D, var)
κ(∀P.C, var) ∀(var0 )(κ(P, var, var0 ) → κ(C, var0 ))
κ(∃P.C, var) ∃(var0 )(κ(P, var, var0 ) ∧ κ(C, var0 ))
κ(a : C) κ(C, x)[a/x]
κ((a, b) : P ) κ(P, x, y)[a/x, b/y]
κ(C v D, x) ∀(x)(κ(C, x) → κ(D, x))
κ((B|A)[l, u], x) l ≤ w(B(x)|A(x)) ≤ u
2.2 Satisfiability Preservation
Theorem 1. A P-SHIQ PTBox P T = (T , P) is satisfiable iff the correspond-
ing FOPL2 theory {κ(φ)|φ ∈ T ∪ P} is satisfiable.
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 |= T and P r |= P.
We will construct M = (D, S, π, µ) s.t. M |= κ(φ) for all φ ∈ T ∪ P. For
that we first observe that the existence of P r implies the existence of a SHIQ
interpretation: (∆I , ·I ) |= T [4]. Thus we can define D and π as follows: D = ∆I ;
π(t) = (κ−1 (t))I for all unary and binary predicates t. Note that π interprets all
predicate names independently of a state.
The key is to construct the set S and ensure the following property:
P r({Ct ∈ T ypes(O)|Ct a` C}) = µ({s ∈ S|(M, s, v) |= κ(C)}) (1)
for any concept C and some valuation v
Property (1) guarantees that P r(C) = µ(κ(C)) for all (C ∈ cl(T ) (hence
P r |= (D|C)[l, u] implies (M, v) |= l ≤ w(κ(D, x)|κ(C, x)) ≤ u for some v). It can
be achieved by defining a straightforward bijection between types and states us-
ing κ. For each type Ct = {C1 , . . . , Ck } we define a state
s = {κ(C1 , x), . . . , κ(Ck , x)}
d (we use s = κ(Ct) as a shorthand
V notation). It
is not hard to see that, if i Ci is satisfiable w.r.t. T then i κ(Ci , x) is satisfi-
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 iff φ ∈ s. We leave out the demon-
stration that Ct a` C implies κ(Ct) a` κ(C, x).
Finally, we define the probability function: µ(s) = P r(κ−1 (s)) for all s ∈ S.
It remains to show that M = (D, S, π, µ) satisfies 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 axiomP(B|A)[l, u]. It is translated into
Cta`BuA P (Ct)
the formula l ≤ w(κ(B, x)|κ(A, x)) ≤ u. Now P P (Ct) ∈ [l, u], therefore
P Cta`A
sa`κ(B,x)∧κ(A,x) µ(s)
P ∈ [l, u] (by definition of S and µ). In order to show that
sa`κ(A,x) µ(s)
this is equivalent to µ{s∈S:(M,s,v)|=B(x)∧A(x))}
µ{s∈S:(M,s,v)|=A(x)} ∈ [l, u] it suffices to prove that, if
there exists a state s0 ∈ 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) |= c(x). Take some s0 ∈ S. Then there
exists v : (M, s0 , v) |= c1 (a) ∧ · · · ∧ ck (a) ∧ κ(T ) where a is a fresh constant (this
follows from consistency of concept types). Since c = ci ∈ s0 for some i it follows
that (M, s0 , v[a/x]) |= c(x).
(⇐) can be shown completely analogously, so we skip the details.
2
2.3 Why the Translation Matters?
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 [4], it is
vulnerable to all arguments regarding the issues with the possible world seman-
tics of FOPL2 and its inappropriateness for handling statistics [10, 11, 3]. The
most serious issue is that generic probabilistic statements that are aimed at rep-
resenting statistics do not fulfill this role. The proper statistical interpretation of
a statement (D|C)[l, u] would be: “if a randomly chosen domain element belongs
to C, its probability of belonging to D is in [l, u]. However, in P-SHIQ semantics
it instead quantifies over randomly chosen named individuals. The difference is
illustrated on the following example:
Example 1 (Inadequate Handling of Statistics). Consider the PTBox: T = {A ≡
(= 1R.B), B ≡ (= 1R− .A)}; P = {(A|>)[0.5, 0, 5]}. The TBox component im-
plies a bijection between the interpretations of A and B so it seems that if the
probability that a random object is in A is 0.5 then the probability of being in
B should also be 0.5 (because there are as many instances of B in the domain
as there are of A). However, the result is [0, 1] because this relationship between
the interpretations is not captured in the possible world based semantics.
Secondly, the translation helps to understand the limitations of P-SHIQ,
namely, the inability to combine probabilistic knowledge about multiple individ-
uals in a single ABox, unnatural separation of classical and probabilistic indi-
viduals, inability to represent probabilistic relationships between roles, etc. The
common reason behind all those issues is that the set of states S is quite coarse-
grained 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 P-
SHIQ does not have such property (because SHIQ does not have finite 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 Possible extensions to P-SHIQ
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 briefly 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 first 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 P-
SHIQ all named individuals are split onto those for which there is some prob-
abilistic 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. {Big u Dense v Heavy, ball : Big, (ball : Dense)[0.9, 1]}
Intuitively the answer to the query ball : (Heavy)[?, ?] should be [0.9, 1]. How-
ever, due to the separation, the two balls are regarded as distinct individuals so
such entailment is not supported. There are, of course, workarounds, for exam-
ple, 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 prob-
abilistic 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 individ-
ual [4]. Thus it is not possible to assert a probabilistic role between individuals
for whom we store other probabilistic knowledge. Consider the example:
Example 3. {john : ¬T all[0.1, 0.2], pete : T all[0.9, 1],
(john, pete) : f riendOf [0.8, 1]}
In P-SHIQ either john or pete will have to be a classical individual so we will
not be able to use all the available probabilistic knowledge to answer the query
john : (T all u ∃f riendOf.¬T all)[?, ?] (the probability that John is tall but has
a short friend).
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+ .
3.1 Syntax of P-SHIQ+
Syntactically, P-SHIQ+ differs 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 definition is needed.
Definition 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 define the extended syntax of conditional constraints.
Definition 4 (Conditional Constraint). A conditional constraint in
P-SHIQ+ is an expression of the form: (ψ|φ)[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 proba-
bilistic ontology in P-SHIQ+ has a simpler structure than in P-SHIQ:
Definition 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 finite
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 different. Instead of implicitly
attributing statements of the form (C|>)[l, u] to a particular individual, it is
represented as (C(a)|>)[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.
3.2 Semantics of P-SHIQ+
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 specification 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 specification 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 specification of an ordered pair of domain elements which includes types
of both as well as relationships between them.
Definition 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 ∈ Ct and a : C ∈ O then
C ∈ Ct.
ctype is also extended: ctype(e) = Ct if additionally e = aI for all a ∈ Ct.
Definition 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 state-
ments. Then a role type Rt is a subset of R that satisfies the following condition:
if R ∈ Rt and R v S ∈ O or Inv(R) v Inv(S) ∈ O then S ∈ Rt.
Given an interpretation (∆I , ·I ) |= O, a pair of domain elements (e, f ) is an
instance of a role type Rt if (e, f ) ∈ RI for all R ∈ Rt.
Analogously to ctype, the function rtype(e, f ) = {Rt|(e, f ) is instance of Rt}.
Observe that it is also a well-defined, total function.
Definition 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 ∀R.C ∈ Ct1 and R ∈ Rt then C ∈ Ct2 .
– If ∀R.C ∈ Ct2 and Inv(R) ∈ Rt then C ∈ Ct1 .
– If ≤ 0R.C ∈ Ct1 and R ∈ Rt then ¬C
˙ ∈ Ct2 .
– If ≤ 0R.C ∈ Ct2 and Inv(R) ∈ Rt then ¬C
˙ ∈ Ct1 .
Definition 9 (Instantiation function). Given a model I = (∆I , ·I ) |= O
the function link(e, f ) on the set of pairs of domain elements is defined 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-defined function since ctype and rtype are well-
defined. 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 ∈ ∆I with link(e, f ) = L.
Now we can define the notion of consistency between a link and an entity.
Definition 10 (Consistency with an Entity). A link (Ct1 , Rt, Ct2 ) is con-
sistent with an entity φ w.r.t. the ontology O (denoted as L a` φ) if:
– If φ is a role R and R ∈ Rt,
– If φ is a concept C and C ∈ Ct1 ,
– If φ is a concept assertion C(e) and {e, C} ∈ Ct1 ,
– If φ is a role assertion R(e, f ) and (e ∈ Ct1 and R ∈ Rt and f ∈ Ct2 ) or
(f ∈ Ct1 and R ∈ Rt and e ∈ Ct2 ).
We now proceed to probabilistic models in P-SHIQ+ .
Definition 11 (Probabilistic Interpretation, Probability of an Entity).
A probabilistic interpretation P r of a probabilistic ontology P O = (O, P) is
Pprobability function on Links(O) (a mapping P r : Links(O) → [0, 1] s.t.
a
L∈Links(O) P r(L) = 1.
The
P probability of an entity φ denoted as P r(φ) is the
sum L∈Link(T ),La`φ PPr(L). Probability of the conjunction of two entities
P r(ψ ∧ φ) is the sum L∈Links(O),La`φ,La`ψ P r(L). Conditional probability
P r(ψ|φ) is an abbreviation of P Pr(ψ∧φ)
r(φ) .
As long as any fixed 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”).
Definition 12 (Probabilistic Satisfiability, Logical Entailment). A prob-
abilistic interpretation P r satisfies (or is a model of ) a P-SHIQ+ formula
(ψ|φ)[l, u] (denoted as P r |= φ) if P r(ψ|φ) ∈ [l, u]. P r satisfies a collection
of P-SHIQ+ formulas if it satisfies all of them. P r satisfies an ontology (O, P)
if P r |= P.
A P-SHIQ+ formula (ψ|φ)[l, u] is a logical consequence of a P-SHIQ+ on-
tology P O if it is satisfied 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 |= P O such that P r(φ) > 0.
Problems of deciding probabilistic satisfiability (PSAT) and computing tight
logical entailment (TLogEnt) are stated equivalently to P-SHIQ (see [4]).
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 on-
tology from the Example 2. Now both occurrences of ball denote the same
individual. The probability of Heavy(ball) is defined as: P r(Heavy(ball)) =
P
I|=Heavy(ball) P r(I). Consider the set of links that are consistent with ball. All
of them have Big in the first concept type and at least 90% also have Dense.
This means that at least 90% of them have Heavy in the first concept type (by
the definition 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 well-
formed P-SHIQ+ ontology. The answer to the query
(john : (T all u ∃f 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 |classmateOf )[0.60, 1].
3.3 Possible Further Extensions
P-SHIQ+ does address some important limitations of P-SHIQ but it is still
not a fully appropriate formalism for representing and reasoning with statisti-
cal knowledge. Its semantics is based on possible worlds (links) which results
in counterintuitive inference in some situations (see Example 1). No further ex-
tension 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 specific 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 [5]. If the issue happens to be critical then there might
several ways to rectify it. The two main alternatives are Bacchus’ Lp logic with
domain based semantics followed by applying belief functions to adjust subjective
beliefs basing on the general statistics [10, 11], and Halpern’s Type 3 semantics
which combines features of domain based and prossible world based models [3].
4 Conclusion
In this paper we presented a new look at the probabilistic description logic P-
SHIQ as a fragment of probabilistic first-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 first type of limitations and presented an
extended logic P-SHIQ+ which adds a few important capabilities to the exist-
ing arsenal. Namely, it enables full probabilistic role assertions, probabilistic role
hierarchies and eliminates the unnatural separation between classical and prob-
abilistic 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 [12].
References
[1] Koller, D., Levy, A.Y., Pfeffer, A.: P-CLASSIC: A tractable probabilistic descrip-
tion logic. In: Advances in Artificial Intelligence Conference. (1997) 390–397
[2] Klinov, P.: Pronto: A non-monotonic probabilistic description logic reasoner. In:
European Semantic Web Conference (ESWC 2008), Posters & Demos. (2008)
822–826
[3] Halpern, J.Y.: An analysis of first-order logics of probability. Artificial Intelligence
46 (1990) 311–350
[4] Lukasiewicz, T.: Expressive probabilistic description logics. Artificial Intelligence
172(6-7) (2008) 852–883
[5] Klinov, P., Parsia, B.: Probabilistic modeling and OWL: A user oriented intro-
duction into P-SHIQ(D). In: OWL: Experiences and Directions. (2008)
[6] Lukasiewicz, T.: Probabilistic logic programming with conditional constraints.
ACM Transactions on Computational Logic 2(3) (2001) 289–339
[7] Lutz, C., Sattler, U., Tendera, L.: The complexity of finite model reasoning in
description logics. Information and Computation 199(1–2) (2005) 132–171
[8] Lukasiewicz, T.: Probabilistic default reasoning with conditional constraints. An-
nals of Mathematics and Artificial Intelligence 34(1-3) (2002) 35–88
[9] Baader, F., Calvanese, D., McGuiness, D., Nardi, D., Patel-Schneider, P.F.: De-
scription Logic Handbook. Cambridge University Press (2003)
[10] Bacchus, F.: Lp, a logic for representing and reasoning with statistical knowledge.
Computational Intelligence 6 (1990) 209–231
[11] Bacchus, F.: Representing and reasoning with probabilistic knowledge. MIT Press
(1990)
[12] Klinov, P., Parsia, B.: On improving the scalability of checking satisfiability in
probabilistic description logics. Submitted to the Scalable Uncertainty Manage-
ment Conference (2009)