=Paper=
{{Paper
|id=None
|storemode=property
|title=Relationships Between Probabilistic Description and First-Order Logics
|pdfUrl=https://ceur-ws.org/Vol-613/paper9.pdf
|volume=Vol-613
|dblpUrl=https://dblp.org/rec/conf/cade/KlinovP10
}}
==Relationships Between Probabilistic Description and First-Order Logics==
https://ceur-ws.org/Vol-613/paper9.pdf
Relationships between Probabilistic Description and
First-Order Logics
Pavel Klinov and Bijan Parsia
School of Computer Science
University of Manchester, United Kingdom
{pklinov|bparsia}@cs.man.ac.uk
Abstract This paper analyzes the probabilistic description logic P-SHIQ as a
fragment of first-order probabilistic logic (FOPL). P-SHIQ was suggested as
a language that is capable of representing and reasoning about different kinds
of uncertainty in ontologies, namely generic probabilistic relationships between
concepts and probabilistic facts about individuals. However, some semantic prop-
erties of P-SHIQ have been unclear which raised concerns regarding whether it
could be used for representing probabilistic ontologies. In this paper we provide
an insight into its semantics by translating P-SHIQ into FOPL with a specific
semantics based on possible worlds. From that reduction, we show that some
of the restrictions of P-SHIQ are fundamental and sketch alternative semantic
foundations for a probabilistic description logic.
1 Introduction and Motivation
One common complaint about description logic (DL) based ontology languages, such as
the Web Ontology Language (OWL), is they fail to support non-classical uncertainty, in
particular, 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 [1] [2]. Unlike Bayesian extensions to DLs and OWL, the P-SH
family consists of proper extensions to the syntax and semantics of the underlying logic
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.
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 how it actually
combines statistical and subjective probabilities. Second, probabilistic ABoxes have a
number of strong restrictions (including no support of roles assertions between proba-
bilistic individuals and only one probabilistic individual per ABox).
Often, insight into a DL (and associated extensions and reasoning techniques) has
followed by considering its standard first-order translation, that is, in considering it as
a fragment of first order-logics. In this paper, we attempt to apply this methodology to
the P-SH family by considering them as fragments of a first-order logic extended with
various forms of probability (FOPL). We show that we can understand P-SH logics as
fragments of FOPL and explain its limitations on the basis of the known properties of
FOPL with semantics based on possible worlds. Finally, we sketch another fragment of
FOPL which has different semantics and allows lifting of the P-SH restrictions.
2
2 Preliminaries
P-SHIQ We consider a particular representative of the P-SH family, named P-
SHIQ, whose syntactic constructs include those of SHIQ together with conditional
constraints. Constraints are expressions of the form (D|C)[l, u] where D, C are SHIQ
concept expressions (called conclusion and evidence respectively) and [l, u] ⊆ [0, 1].
A probabilistic TBox (PTBox) is a 2-tuple P T = (O, P) where O is a classical
DL ontology and P is a finite set of conditional constraints. Informally, a PTBox axiom
(D|C)[l, u] means that “if a randomly chosen individual belongs to C, its probability
of belonging to D is in [l, u]”. A probabilistic ABox (PABox) is a finite set of condi-
tional constraints pertaining to a single probabilistic individual o. Set of all probabilistic
individuals is denoted as IP . A probabilistic ontology P O = (O, P, (Po )o∈IP ) is a
combination of one PTBox and a set of PABoxes, one for each probabilistic individual.
The semantics of P-SHIQ is standardly explained in terms of the notion of a pos-
sible world which is defined with respect to a set of basic concepts Φ [2]. A possible
world I is a set of DL concepts from Φ such that {a : C|C ∈ I} ∪ {a : ¬C|C ∈ / I}
is satisfiable for a fresh individual a (in other words, possible worlds correspond to re-
alizable concept types). The set of all possible worlds with respect to Φ is denoted as
IΦ . A world I satisfies a concept C denoted as I |= C if C ∈ I. Satisfiability of basic
concepts is inductively extended to concept expressions as usual.
A world I is said to be a model of a DL axiom η denoted as I |= η if η ∪ {a : C|C ∈
I} ∪ {a : ¬C|C ∈ / I} is satisfiable for a fresh individual a. A world I is a model of a
classical DL knowledge base O denoted as I |= O if it is a model of all axioms of O.
Existence of such world is equivalent to the standard satisfiability in DL [2].
A probabilistic interpretation P r is a discrete probability distribution over IΦ . P r
is said to satisfy a DL knowledge base O denoted as P r |= KB iff ∀I ∈ IΦ , P r(I) >
0P⇒ I |= KB. The probability of a concept C, denoted as P r(C), is defined as
I|=C P r(I). P r(D|C) is used as an abbreviation for P r(C ⊓ D)/P r(C) given
P r(C) > 0. A probabilistic interpretation P r satisfies a conditional constraint
(D|C)[l, u], denoted as P r |= (D|C)[l, u], iff P r(C) = 0 or P r(D|C) ∈ [l, u]. P r
satisfies a set of conditional constraints F iff it satisfies each of the constraints. A PT-
Box P T = (O, P) is called satisfiable iff there exists an interpretation that satisfies
O ∪ P. Logical entailment is defined in a standard way [2]1 .
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 se-
mantics [3]), like “the probability that Tweety (a particular bird) flies is over 90%”. It
is very expressive allowing to attach probabilities to arbitrary first-order formulas. Its
representational and computational properties have been thoroughly investigated, and
the results of these investigations are applicable to its fragments.
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
1
P-SHIQ, as it is presented in [2], is a non-monotonic formalism. However, we consider only
its monotonic basis in this paper. Our position is that it must be clarified first, before proceeding
to non-monotonic machinery, such as lexicographic entailment, built on its top.
3
terms are formed by closing X o off under function application as usual. In addition, the
language 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 (the denotation
w(φ|ψ) ≤ t is the abbreviation of w(φ ∧ ψ) ≤ t × w(ψ)). 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.
– If φ, ψ are formulas and x ∈ X o , then φ∧ψ, φ∨ψ, ∀(x)φ, ∃(x)φ, ¬φ are formulas.
Standard relationships between logical connectives and quantifiers are assumed.
A probabilistic interpretation (Type 2 probability structure in [3]) M is a tuple
(D, S, π, µ), where D is a domain, S is a set of states, π is a function S × Φ → ΦD
(where ΦD is a set of predicates and functions over D) which preserves arity, and µ is
a probability distribution over S. M together with a state s and a valuation v associates
each object term o with an element of D ([o](M,s,v) ∈ D) and each field term f with a
real number. (M, s, v) associates formulas with truth values (we write (M, s, v) |= φ if
φ is true in (M, s, v)) as follows:
– (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 probability terms of the form w(φ): [w(φ)](M,s,v) = µ{s′ ∈
S|(M, s′ , v) |= φ}. As usual, a FOPL2 formula is called satisfiable if there exists a
tuple (M, s, v) in which the formula is true.
Note that, although FOPL2 does not impose any restrictions on the set S (i.e. it can
be any set over which a probability distribution can be defined). However, it is natural to
associate states with possible interpretations of symbols in Φ over D (see [4]). Then the
model structure can be simplified to (D, S, µ) since the interpretations are implicitly
encoded in the states.
3 Mapping between P-SHIQ and FOPL2
This section presents a mapping between P-SHIQ and FOPL2 . For brevity we will
limit our attention to ALC concepts (calling the resulting logic P-ALC) as the trans-
lation can be easily extended to more expressive DLs. We will show that it preserves
entailments so that P-SHIQ can be viewed as a fragment of FOPL2 .
Basic Translation We define the injective function κ to be the mapping of syntactic
constructs of P-ALC to FOPL2 2 . It is a superset of the standard translation of ALC into
4
Table 1. Translation of P-ALC formulae into FOPL2
P-ALC FOPL2
κ(A, var) A(var)
κ(¬C, var) ¬(κ(C, var))
κ(R, var, var′ ) R(var, var′ )
κ(C ⊓ D, var) κ(C, var) ∧ κ(D, var)
κ(C ⊔ D, var) κ(C, var) ∨ κ(D, var)
κ(∀R.C, var) ∀(var′ )(R(var, var′ ) → κ(C, var′ ))
κ(∃R.C, var) ∃(var′ )(R(var, var′ ) ∧ κ(C, var′ ))
κ(a : C) κ(C, x)[a/x]
κ((a, b) : R) R[a/x, b/y]
κ(C ⊑ D, x) ∀(x)(κ(C, x) → κ(D, x))
κ((B|A)[l, u], x) l ≤ w(B(r)|A(r)) ≤ u
FOL [5] (in the Table 3 A, B stand for concept names, R for a role name, C, D for
concepts, r for a fresh constant, var ∈ {x, y}; var′ = x if var = y and y if var = x).
This function transforms a P-ALC PTBox into a FOPL2 theory. The most important
thing is that it translates generic PTBox constraints into ground probabilistic formulas
for a fresh constant r. The implications of this will be discussed in Section 4.
Faithfulness We next show that this translation is faithful by establishing correspon-
dence between models in P-ALC and FOPL2 . Observe, that in contrast to [6], here we
consider the natural choice of states in Type 2 model structure in which they correspond
to first-order models of the knowledge base.
Theorem 1. Let P T = (O, P) be a PTBox in P-ALC and F = {κ(φ)|φ ∈ O ∪ P} be
the corresponding FOPL2 theory. Then for every P-ALC model P r of P T there exists
a corresponding Type 2 structure M = (D, S, µ) such that 1) M |= κ(φ) for all φ ∈ O
and 2) M |= l ≤ w(B(r)|A(r)) ≤ u for all conditional constraints (B|A)[l, u] in P,
and vice versa, where κ is defined according to Table 1.
Proof. We prove only (⇒). Let P r : IΦ → [0, 1] be a model of P T . P r satisfies
classical ontology O so there exists a classical model I = (∆I , ·I ) of O. We first
extend ∆I to ensure that all possible worlds are realizable over it (one possibility is
to take the disjoint union of all realizations)3 . Then we construct a Type 2 structure
(D, S, µ) as follows: let D = ∆I and S be the set of all interpretations of predicate
names (translations of concept and roles names) and r over ∆I that satisfy classical
formulas in F . S must be non-empty: let sI be such that sI (P ) = κ−1 (P )I for all
predicate names and sI (r) is an arbitrary domain element. Since r is a fresh constant
and κ encompasses a standard and faithful translation from ALC to FOL, sI is a model
of all classical formulas in F and therefore 1) holds.
2
For a possible world I = {Ci } we use the notation κ(I) to denote the set {κ(Ci )}
3
This is only possible if the DL does not allow for nominals.
5
The rest is to define a probability distribution µ that satisfies probabilistic formulas
in F . Recall that P r is probability distribution over the set of (possible worlds). We
define a function σ which maps each world I = {Ci } to a set of states σ(I) ⊆ S as
follows: σ(I) = {s|s |= κ(I)(r)} . Then let µ(σ(I)) = P r(I) for all possible worlds.
It is not hard to see that µ is a probability distribution as it mimics the probability distri-
bution P r. Finally, (D, S, µ) satisfies all formulas of the kind l ≤ w(B(r)|A(r)) ≤ u
in F because µ(B(r) ∧ A(r)) = PPr(B ⊓ A), µ(A(r)) = PPr(A)) (by construction, e.g.,
µ(A(r)) = µ({s|s |= A(r)}) = Cti |=A µ{σ(Cti )} = Cti |=A P r(Cti ) = P r(A))
and P r |= (B|A)[l, u] and therefore 2) holds. ⊓
⊔
Theorem 1 implies that the translation preserves satisfiability and entailments.
Translation of PABoxes One particularly odd restriction of P-SHIQ is that PABoxes
cannot be combined into a single set of formulas. This is so because PABox constraints
are modeled as generic constraints and the information about the individual is present
only on a meta-level (as a label of the PABox). Therefore, to extend our translation
to PABoxes we either have to translate them into a corresponding disjoint set of la-
beled FOPL2 theories or make special arrangements to faithfully translate them into a
combined FOPL2 theory. We opt for the latter because it will let us get rid of any meta-
logical aspects and help analyze a P-SHIQ ontology as a standard FOPL2 theory.
Since PABoxes in P-SHIQ are isolated from each other, the translation should
preserve that isolation. The most obvious way to prevent any interaction between sets
of formulas in a single logical theory is to make their signatures disjoint. However,
the translation should not only respect disjointness of PABoxes but also preserve their
interaction with PTBox and the classical part of the ontology (see Example 1).
Example 1. Consider the following PTBox: P = {(F lyingObject|Bird)[0.9, 1],
(F lyingObject|¬Bird)[0, 0.5]} and two PABoxes: PT weety = {(Bird|⊤)[1, 1]},
PSam = {(¬Bird|⊤)[1, 1]}. Obviously, if these sets of axioms are translated and com-
bined into a single FOPL2 theory then it will contain a conflicting pair of formulas
{w(Bird(r)) ≥ 0.9, w(Bird(r)) ≤ 0.5} ⊆ F . This inconsistency can be avoided by
introducing fresh first-order predicates for every PABox: {w(BirdT weety (r)) ≥ 0.9,
w(BirdSam (r)) ≤ 0.5}. However, this would break any connection between PTBox
and PABox axioms, for example, prevent the following entailments:
{w(F lyingObjectT weety (r)) ≥ 0.9, w(F lyingObjectSam (r)) ≤ 0.5}.
One can faithfully extend the translation to PABoxes by introducing fresh concept
names to relativize each TBox and PTBox axiom for every probabilistic individual to
avoid inconsistencies. The transformation will consist of the following steps4 :
– Firstly, we transform a P-ALC ontology P O = (O, P, (Po )) into a set of PTBoxes
{(O, P ∪ Po )} ∪ {(O, P)}. Informally, we create a copy PTBox for every prob-
abilistic individual (P To ) and make them isolated from each other. Now, instead
of one PTBox and a set of PABoxes we have just a set of PTBoxes. This step
preserves probabilistic entailments in the following sense: P O |= (B|A)[l, u] iff
(O, P) |= (B|A)[l, u] and P O |= (B|A)[l, u] for o iff P To |= (B|A)[l, u].
4
Full example is available at http://www.cs.man.ac.uk/˜klinovp/research/pshiq/example.pdf.
6
– Secondly, we transform every PTBox P To into P To′ by renaming every concept
name C into Co in all TBox axioms and conditional constraints. It is easy to
see that P To |= C ⊑ D iff P To′ |= Co ⊑ Do and P To |= (B|A)[l, u] iff
P To′ |= (Bo |Ao )[l, u]. Intuitively, we have created a fresh copy of each PTBox
to guard against possible conflicts between PABox constraints for different proba-
bilistic individuals. Signatures of P To′ are pairwise disjoint and denoted as Σo .
– Next, we union all P To′ with disjoint signatures S (including the original P T =
(O, P)) into a single unified PTBox P TU = o∈Ip P To ∪ P T with signature
S
ΣU = o∈Ip Σo ∪ Σ.
– Finally we can apply the previously presented faithful translation to P TU and ob-
tain a single FOPL2 theory which corresponds to the original P-ALC ontology.
A necessary condition for faithfulness of this transformation is that the original iso-
lation of PABoxes is preserved by creating fresh copies of PTBoxes. In particular, this
means that the unified PTBox cannot entail any subsumption relation between concept
expressions Co1 and Co2 defined over disjoint signatures except of the case when one
of them is either ⊤ or ⊥. If this is false, for example, if P TU |= Co1 ⊑ Co2 then
the following PABox constraints represented as (Co1 |⊤)[1, 1] and (Co2 |⊤)[0, 0] will
be mutually inconsistent in P TU (but they were consistent in the original P-ALC be-
cause they belonged to different PABoxes isolated from each other). This condition is
formalized in the following lemma (whose proof is omitted for brevity):
Lemma 1. Let O1 and O2 be copies of a satisfiable ALC ontology O with disjoint
signatures Σ1 and Σ2 , and OU be the union of O1 and O2 . Then for any concept
expressions C1 , C2 over Σ1 and Σ2 respectively such that O1 2 C1 ⊑ ⊥ and O1 2
⊤ ⊑ C2 , OU 2 C1 ⊑ C2 .
Now we can obtain the main result:
Theorem 2. Let P O = (O, P, (Po )) be a P-ALC ontology and F be a FOPL2 theory
obtained by combining PABoxes and translating the resulting PTBox into FOPL. Then
for every P-ALC model P ro of P To = (O, P ∪ Po ) for every probabilistic individual
o there exists a corresponding Type 2 structure M = (D, S, µ) such that:
1. M |= κ(φ) for all φ ∈ O,
2. M |= l ≤ w(B(r)|A(r)) ≤ u for all conditional constraints (B|A)[l, u] in P,
3. M |= l ≤ w(Bo (r)|Ao (r)) ≤ u for all conditional constraints (B|A)[l, u] in Po ,
and vice versa, where κ is defined according to Table 1.
Proof. Due to Theorem 1 it suffices to show that the steps 1-3 of the transformation
preserve probabilistic models. This can be done by establishing a correspondence be-
tween possible worlds of each P To and P TU . Since there are no subsumptions between
concept expressions over signatures of different PTBoxes (see Lemma 1), each possi-
ble world Io in P To corresponds to a finite set of possible worlds of P TU defined as:
σ(Io ) = {IU |Cio ∈ IU iff Ci ∈ Io } (each Cio is a new concept name for Ci intro-
duced on step 2). Then, a probability distribution over all possible worlds in P TU can
be defined as P rU (IU ) = P ro (Io )/|σ(Io )|. It follows that for any concept C over Σo ,
7
P ro (C) is equal to P rU (Co ) where Co is the correspondingly renamed concept. There-
fore, P rU |= (Bo |Ao )[l, u] if P ro |= (B|A)[l, u]. The
Preverse direction can be proved
along the same lines (i.e., P ro (Io ) can be defined as IU ∈σ(Io ) P rU (IU )).
4 Discussion
The main conclusion following from the presented translation is that P-SHIQ all PT-
Box statements express degrees of belief (i.e. subjective probabilities) about a single,
yet unnamed, individual. This is not an easily expected outcome because the variable-
free syntax of P-SHIQ may give a misleading impression that PTBox constraints cor-
respond to universally quantified formulas of some sort. The fact that probabilistic indi-
viduals are not translated to corresponding constants in FOPL2 (in contrast to classical
individuals) is also not a trivial outcome. Both these features of P-SHIQ have im-
portant implications, but before moving to them, let us consider another, perhaps more
naturally looking translation and explain why it is not faithful.
It may well appear that conditional constraints in P-SHIQ should be interpreted as
implicitly universally quantified formulas analogously to probabilistic logic program-
ming. That way, (B|A)[l, u] corresponds to ∀x(l ≤ w(B(x)|A(x)) ≤ u). However,
the standard behavior of the universal quantifier is incompatible with the P-SHIQ se-
mantics in which classical and probabilistic individuals are separated. For example, the
PTBox ({a : ¬A}, {(A|⊤)[1, 1]}) is satisfiable although the corresponding FOPL the-
ory {¬A(a), ∀x(w(A(x)) = 1)} is not.
There is a possibility to interpret conditional constraints in P-SHIQ as closed quan-
tified formulas, but this requires a non-standard quantifier which makes the variable act
as a random designator. This idea dates back to Cheeseman who originally proposed to
use formulas of the form ∀x.pr[B(x)|A(x)][l, u] to capture statistical knowledge [7].
In fact, the fresh constant r used in our translation plays the role of such non-standard
quantifier. However, as pointed out by several authors (see especially [3] [8] [9]), such
formulas cannot serve as representations of statistical assertions because their interpre-
tations are not based on proportions of domain elements5 .
Unfortunately, using Type 2 semantics to interpret different kinds of probabili-
ties complicates not only the representation of statistics but also the combination of
statistical assertions with probabilistic statements about specific individuals (degrees
of belief). In particular, this requires modeling of PABox constraints in P-SHIQ as
generic PTBox statements with information about individuals presenting only on a
meta-level. This is the reason why PABox statements do not correspond to ground
probabilistic formulas in FOPL2 . If they did, then there would be no connection be-
tween a “statistical” statement (F lyingObject|Bird)[0.9, 1] (represented in FOPL2 as
(0.9 ≤ f lyingobject(r)|bird(r)) ≤ 1) and a belief statement (tweety : Bird)[1, 1]
(represented as 1 ≤ w(bird(tweety) ≤ 1) since beliefs about r cannot affect beliefs
about tweety. Therefore (tweety : Bird)[1, 1] is effectively modeled as (Bird|⊤)[1, 1]
5
We must mention that P-SHIQ could, in principle, be translated to FOPL with domain-based
semantics by employing a known translation between domain-based probability and possible-
world-based probability (see [10] for details). However, this will solve no issues with P-SHIQ
as it will still behave as FOPL2 with single probabilistic individual.
8
(or as 1 ≤ w(bird(r)) ≤ 1 in FOPL2 ) with the individual name tweety lifted at the
meta-level to serve as a label for the corresponding PABox.
However, this introduces other problems which are responsible for the limitations
of P-SHIQ. Since PABox constraints expressing probabilistic knowledge about differ-
ent probabilistic individuals must be isolated from each other, there appears to be no
straightforward way of combining them. In particular, this prohibits representation of
classical or probabilistic role assertions between different probabilistic individuals or,
in other words, the logic does not support probabilistic relational structures6 . Thus, it
can be concluded that, in essence, P-SHIQ is closer to a propositional probabilistic
logic rather than to a full-fledged probabilistic first-order formalism.
The problems mentioned above cannot be solved simply by adopting an appropriate
semantics for representing statistics, such as Type 1 semantics in which probability dis-
tributions are defined over the interpretation domain. Such an attempt has been made
by Giugno and Lukasiewicz in the early paper on P-SHOQ [1]. In that logic proba-
bilistic concept membership assertions were represented using nominals, for example,
(C|{a})[0.5, 1]. Unfortunately, as proved by Halpern, closed first-order formulas can
only have probability 0 or 1 in any Type 1 probabilistic model (see Lemma 2.3 in [3]) so
the representation is unsatisfactory. It is not hard to see that the probability of (C|{a}),
equivalent to P Pr(C⊓{a}) I
r({a}) , is 0 if a ∈/ C I or 1 if aI ∈ C I if P r is defined over ∆I .
All the features and limitations explained above are by no means unique to P-
SHIQ. They have been discovered and studied for first-order logics by a number of
authors who claimed that neither domain-based nor possible world-based semantics by
itself is suitable for representation and reasoning about different kinds of probabilities.
However, their proper combination (called Type 3 semantics [3]) has the required po-
tential. The corresponding logic (FOPL3 ) is free of any limitations described above, is
completely axiomatizable for a range of interesting fragments (e.g., logics with bounded
model property such as ALC), and can be used for defining probabilistic DLs.
5 Probabilistic Description Logic with Combined Semantics
In this section we briefly outline the syntax and semantics of the extended probabilistic
DL for representation and reasoning about different kinds of probabilities. The language
corresponds to the DL fragment of FOPL3 with the principle of direct inference [9]. We
loosely call it P-DL (where DL stands for a subset of SROIQ).
Syntax Analogously to P-SHIQ the syntax of P-DL is based on conditional con-
straints. However, we distinguish between statistical constraints and belief constraints
by providing different syntactic constructs for each. Statistical conditional constraints
are expressions of the form (D|C)stat [l, u] where D, C are concept expressions. Belief
constraints are expressions of the form (φ)belief [l, u] or (ψ|φ)belief [l, u] where ψ, φ are
ABox assertions. We define PTBox to be a set of statistical constraints, and PABox to
6
Allowing nominals in the classical part of the language lets us express probabilistic roles
R(a, b)[l, u] as (∃R.{b}|⊤)[l, u] for a [2]. However, this is still very restrictive because there
cannot be a PABox for b (in other words, b cannot be a probabilistic individual).
9
be a set of belief constraints. An ontology in P-DL is a triple (O, Pstat , Pbelief ) where
O is a DL ontology, Pstat is a PTBox and Pbelief is a PABox.
Semantics Both types of conditional constraints are interpreted using the Type 3 struc-
ture M = (∆, S, P rstat , P rbelief ) [3]. Here ∆ is a non-empty domain, S is a set of
states that correspond to interpretations of concept, role and individual names over ∆,
P rstat is a probability distribution over ∆, and P rbelief is a probability distribution
over S. For a state s ∈ S we use s(C) (resp. s(R), s(a)) to express the interpretation
of a concept C (resp. role R and individual a) in s. For an axiom η we write s |= η
if η is satisfied by the corresponding interpretation. Such combined structure is used to
interpret both statistical and belief statements respectively in the following way:
– Statistical probability of a concept C in M in a state s (denoted as C (M,s) ) is equal
(M,s)
to P rstat {d ∈ ∆|d ∈ s(C)}. (D|C)M,s is an abbreviation of (D⊓C) C (M,s)
.
– Subjective probability of an ABox assertion φ (denoted as φM is equal to
M
P rbelief {s ∈ S|s |= φ}. (ψ|φ)M is an abbreviation of (ψ⊓φ) φM
.
– M satisfies a statistical constraint (D|C)stat [l, u] if ∀s ∈ S, (D|C)(M,s) ∈ [l, u].
– M satisfies a belief constraint (ψ|φ)belief [l, u] if (ψ|φ)M ∈ [l, u].
Direct Inference FOPL3 provides means for representing and reasoning about differ-
ent kinds of probabilities but, as it stands, it does not support any relationship between
them. However, in most scenarios, e.g., in actuarial reasoning, it is desirable to infer
subjective beliefs from available classical and statistical knowledge. Such reasoning is
often called direct inference and it can be supported in FOPL3 and its fragments.
The main idea behind direct inference, that goes back to Reichenbach’s reference
class reasoning [11], is to consider every individual to be a typical representative of the
smallest class of objects which it belongs to and for which reliable statistics is available.
For example, the probability that Tweety flies should be equal to the probability that a
randomly taken object, having the same set of properties as Tweety, flies. There are a
few proposed ways to implement this idea, one of which we sketch below.
One can capture the notion of typicality directly by equating the degree of belief
in a ground formula to the expectation of the statistical probability of its randomized
version given the rest of classical and statistical formulas, as proposed in [9]. Ran-
domization is replacement of all constants in ground formulas by fresh variables. Ex-
pectation ofP a field term f is a rigid (i.e. not depending on a state) term defined as
(M,s)
E(f )M = s∈S P rbelief (s) × [f ] . The expectation operator and conditioning
on statistical formulae are only used on the semantic, not syntactic, level of P-DL.
Consider the example. Let {(F ly|Bird)[0.9, 1]} be PTBox and Bird(tweety) be
an ABox axiom. Then the degree of belief in Bird(tweety) is within the bounds of
E(bird(v)|0.9 ≤ w(f ly(v)|bird(v)) ≥ 1), where v is a fresh constant introduced
by randomization. The resulting interval is [0.9, 1], as expected. Note that P-DL will
probably require a non-monotonic mechanism similar to P-SHIQ to handle situations
when an explicitly specified subjective probability is different from the computed via
direct inference (e.g., when the individuals in question are not typical).
10
Direct inference via randomization serves the same purpose as P-SHIQ’s way of
combining PTBox and PABox constraints (in that sense P-SHIQ can be thought of
as an implementable, non-monotonic approximation of FOPL3 ). However, it is con-
siderably less restrictive because it does not require representing PABox statements as
universal PTBox constraints. Since all belief statements about particular individual are
ground formulas with proper constants (like tweety), they can be combined in a single
theory. Thus the representation supports arbitrary relational structures involving differ-
ent probabilistic individuals and does not force unnatural separation of PABoxes. It is
also possible to make the assumption that a pair of individuals are typical thus enabling
the inference of probabilistic role assertions. Finally, it supports smooth integration of
classical knowledge (i.e. ABox axioms) and beliefs about the same individual while
P-SHIQ requires separation between classical and probabilistic individuals.
6 Conclusion
In this paper we have presented a new look at the probabilistic DL P-SHIQ as a frag-
ment of probabilistic first-order logic. We gave a translation of P-SHIQ knowledge
bases into FOPL2 theories and proved its faithfulness. This brought an extra insight
into P-SHIQ, most importantly, into its limitations. It appears that the major restric-
tion, namely the lack of support of relational structure for probabilistic individuals, is
caused by attempt to use the possible world based semantics for different kinds of prob-
abilities. This makes the probabilistic component of P-SHIQ essentially propositional
(i.e. all probabilistic statements relate to a single constant r). We sketched how a more
direct fragment of FOPL, which we called P-DL, could overcome these limitations
while still retaining the ability to combine probabilities of different sorts. Future inves-
tigations include decidability, implementability, and modelling applicability of P-DL.
References
1. Giugno, R., Lukasiewicz, T.: P-SHOQ(D): A probabilistic extension of SHOQ(D) for prob-
abilistic ontologies in the semantic web. In: JELIA. (2002) 86–97
2. Lukasiewicz, T.: Expressive probabilistic description logics. Artif. Intell. 172(6-7) (2008)
852–883
3. Halpern, J.Y.: An analysis of first-order logics of probability. Artif Intell. 46 (1990) 311–350
4. Koller, D., Halpern, J.Y.: Irrelevance and conditioning in first-order probabilistic logic. In:
Advances in Artificial Intelligence Conference. (1996) 569–576
5. Baader, F., Calvanese, D., McGuiness, D., Nardi, D., Patel-Schneider, P.F.: Description Logic
Handbook. Cambridge University Press (2003)
6. Klinov, P., Parsia, B., Sattler, U.: On correspondences between probabilistic first-order and
description logics. In: Description Logic Workshop. (2009)
7. Cheeseman, P.: An inquiry into computer understanding. Comp. Intell. 4 (1988) 58–66
8. Bacchus, F.: Lp, a logic for representing and reasoning with statistical knowledge. Comp.
Intell. 6 (1990) 209–231
9. Bacchus, F.: Representing and reasoning with probabilistic knowledge. MIT Press (1990)
10. Abadi, M., Halpern, J.Y.: Decidability and expressiveness for first-order logics of probability.
Inform. and Comp. 112(1) (1994) 1–36
11. Reichenbach, H.: Theory of Probability. University of California Press, Berkeley (1949)