=Paper=
{{Paper
|id=Vol-2954/paper-13
|storemode=property
|title=An Aleatoric Description Logic for Probabilistic Reasoning
|pdfUrl=https://ceur-ws.org/Vol-2954/paper-13.pdf
|volume=Vol-2954
|authors=Tim French,Thomas Smoker
|dblpUrl=https://dblp.org/rec/conf/dlog/0002S21
}}
==An Aleatoric Description Logic for Probabilistic Reasoning==
https://ceur-ws.org/Vol-2954/paper-13.pdf
An Aleatoric Description Logic for Probabilistic
Reasoning
Tim French1[0000−0002−0748−8040] and Thomas Smoker1
The University of Western Australia, tim.french@uwa.edu.au
thomas.smoker@research.uwa.edu.au
Abstract. Description logics are a powerful tool for describing ontolog-
ical knowledge bases. That is, they give a factual account of the world
in terms of individuals, concepts and relations. In the presence of un-
certainty, such factual accounts are not feasible, and a subjective or
epistemic approach is required. Aleatoric description logic models un-
certainty in the world as aleatoric events, by the roll of the dice, where
an agent has subjective beliefs about the bias of these dice. This provides
a subjective Bayesian description logic, where propositions and relations
are assigned probabilities according to what a rational agent would bet,
given a configuration of possible individuals and dice. Aleatoric descrip-
tion logic is shown to generalise the description logic ALC, and can be
seen to describe a probability space of interpretations of a restriction of
ALC where all roles are functions. Several computational problems are
considered and aleatoric description logic is shown to be able to model
learning, via Bayesian conditioning.
Keywords: Probabilistic Reasoning · Belief Representation · Learning Agents
1 Introduction
Description logics [1] give a formal foundation for ontological reasoning: rea-
soning about factual aspects of the world. However, many reasoning tasks are
performed in the presence of incomplete or uncertain information, so a rea-
soner must apply some kind of belief model to approximate the true state of
the world. This work investigates the application of description logics to de-
scribing uncertain and incomplete concepts, following the recent development of
aleatoric modal logic [7]. The term aleatoric has its roots in the Latin aleator,
meaning dice player, and it is this origin that motivates this work. Concepts are
not simply described as matters of fact, but can be more generally described as
reasonable bets. While a person may definitely have a virus or not, a virus test kit
with 95% accuracy is effectively a role of a dice. That is, on receiving a positive
test a rational person would accept a 20-1 bet that they’re not infected. There-
fore concepts may be modelled using probabilities corresponding to a rational
Copyright © 2021 for this paper by its authors. Use permitted under Creative
Commons License Attribution 4.0 International (CC BY 4.0).
2 Tim French and Thomas Smoker
bet that the concept holds true, along the lines of the Dutch book argument
of Ramsey [21] and de Finetti [5]. The fundamental assumption of this work is
that an agent models the world aleatorically, where events correspond to the roll
of dice, and the bias of the dice is treated epistemically. That is, the agent has
prior assumptions about the bias of the dice, and may refine these assumptions
through observing the world.
Aleatoric description logic aims to model reasoning in uncertain and sub-
jective knowledge settings [10, 12]. However, aleatoric description logic takes an
approach where the probabilistic and logical aspects of the knowledge base are
completely unified, rather than several other approaches where these are inde-
pendent facets of the knowledge base [4, 23, 17]. Therefore all concept and roles
are represented by “dice rolls” corresponding to an agent’s beliefs on the likely
configuration of the world.
An advantage of this “probability first” approach is that aleatoric descrip-
tion logic is naturally able to model learning via Bayesian conditioning over
complex observations (i.e. logical formula). Aleatoric modal logic is introduced
in [7], where the semantics are presented along with a proof theoretic calculus.
This paper extends that syntax and semantics to an aleatoric description logic,
following the correspondence between description logics and modal logics [1].
2 Aleatoric Description Logic
This section presents the core syntax and semantics for Aleatoric Description
Logic (ADL). This is a generalisation of standard description logics, such as
ALC, in the same sense that complex arithmetic is a generalisation of real-
valued arithmetic: the true-false/0-1 values of description logics are extended to
the closed interval [0, 1].
The syntax of ADL varies from that of ALC in a number of ways: there is
a ternary operator, if-then-else, in place of the typical Boolean operators, and a
marginalisation operator in place of the normal role quantifiers. These operators
add expressivity, but also better capture the aleatoric intuitions of the logic.
The syntax for ADL is specified with respect to a set of atomic concepts, X
and a set of roles, R:
α ::= ⊤ | ⊥ | A | (α?α:α) | [ρ] (α | α)
where A ∈ X is an atomic concept, and ρ ∈ R is a role. Let the set of ADL
formulas generated by this syntax be LADL . This syntax uses non-standard op-
erators and the following terminology is used: ⊤ is always; ⊥ is never; A is some
named concept that may hold for an individual; (α?β:γ) is if α then β, else γ;
and [ρ] (α | β) is ρ is α given β.
We also identify a special role id ∈ R referred to as identity, which essentially
refers to different possibilities for the one individual, and write (α | β) in place
of [id] (α | β).
In these semantics every thing is interpreted as a probability dependent only
on the individual: ⊤ always has probability 1.0 and ⊥ always has probability
An Aleatoric Description Logic for Probabilistic Reasoning 3
0.0; an atomic concept A has some probability that is dependent only on the
current individual; (α?β:γ) has the probability of β given α or γ given not α;
and [ρ] (α | β) is the probability of α given β over the set of individuals in the
probability distribution corresponding to ρ.
2.1 Probabilistic Semantics
A formula of aleatoric description logic is interpreted with respect an aleatoric
belief model, that is based on the probability model of [7] and the probability
structures defined in [10]. Given a countable set S, we use the notation PD(S)
to notate the set of Pprobability distributions over S, where µ ∈ PD(S) implies:
µ : S −→ [0, 1]; and s∈S µ(s) = 1.
Definition 1. Given a set of atomic concepts X, and a set of roles R, an
aleatoric belief model is specified by the tuple B = (I, r, ℓ), where:
– I is a set of possible individuals.
– r : R × I −→ PD(I) assigns for each role ρ ∈ R and each individual i ∈ I, a
probability distribution r(ρ, i) over I. We will typically write ρ(i, j) in place
of r(ρ, i)(j).
– For the role id, we include the additional constraint: for all i, j, k ∈ I,
id(i, j) > 0 implies id(j, k) = id(i, k).
– ℓ : I × X −→ [0, 1] gives the likelihood, ℓ(i, C) of an individual i satisfying
an atomic concept C. We will write C(i) in place of ℓ(C, i).
Given some i ∈ I, we let Bi be referred to as a pointed aleatoric belief model.
Definition 2. Given an aleatoric belief model B = (I, r, ℓ), some i ∈ I, and
some α ∈ ADL we specify the probabilityPB assigns i satisfying α, Bi (α), recur-
sively. We use the abbreviation Eiρ α = j∈I ρ(i, j)Bj (α), where ρ ∈ R. Then:
Bi (⊥) = 0 Bi ((α?β:γ)) = B
Pi
(α).Bi (β) + (1 − Bi (α)).Bi (γ)
ρ(i,j)Bj (α)Bj (β)
Bi (⊤) = 1 Bi ([ρ] (α | β)) = j∈I E ρ β if Eiρ β > 0
i
Bi (C) = C(i) Bi ([ρ] (α | β)) = 1, if Eiρ β = 0
In these semantics each proposition can be seen as an event (or a series of
conditional events), and the interpretation describes the probability of that event
being observed.
For example, the following proposition describes the concept of someone hav-
ing been exposed to a virus, given they were in contact with someone who had
a fever
exp = (virus?⊤:[contact] (infectious | fever)) (1)
“The person was either already (asymptomatically) infected, or some person
selected from the population of contacts who have a fever, was infectious”.
To evaluate this the concept virus is sampled, to see if they already have
the virus (there may be a 1% chance). In the cases where they didn’t already
4 Tim French and Thomas Smoker
have the virus, random individuals are sampled from the population of contacts,
and the concept fever is sampled from the individuals until a febrile contact is
selected. The probability associated to the proposition exp is the probability of
this process selecting an individual where infectious is sampled.
An important property of these semantics is the weak independence assump-
tion: All formulas of ADL are contingent only on the individual at which they
are evaluated. This means that two formulas evaluated at the same individual
may be viewed as independent probabilistic events.
That is, the probability of a coin landing heads twice in a row is independent
of the probability of the same coin landing heads once. Both events are contingent
on the bias of the coin, so in universes where the coin is more likely to land heads,
both events are more likely, but the event are conditionally independent given
the universe (or the possible individual). This simplifies the representation of
complex dependencies, as the joint probability of all events can be constrained
to be a probability distribution of individuals, where all event are conditionally
independent given an individual.
2.2 Aleatoric Knowledge Bases
An aleatoric knowledge base is defined over the same signature of atomic con-
cepts X and roles R, including id. Additionally there is a set of named individ-
uals, N, which may be thought of as special concepts for grounding assertions
and framing queries. In line with the epistemic nature of these knowledge bases
each named individual can be any one of a number of possible individuals, and
the distribution of these possible individuals is represented by the role id.
As with ALC we have terminological axioms and assertional axioms. The
aleatoric terminological axioms or T-Books describe rules that are universally
true for all individuals, and thus provide a non-probabilistic intensional defi-
nition of the concepts and roles in the logic. Aleatoric assertional axioms or
A-Books describe subjective extensional information by listing the probabilities
with which individuals satisfy given concepts and roles. It is not the case that
T-Books describe concept inclusion nor subsumption as TBoxes do in ALC, as
these concepts do not have a strong intuitive foundation in an aleatoric setting.
Instead T-Books provide a means to constrain strength of belief.
Definition 3. The aleatoric terminological axioms have the form:
α β (α is no more likely than β) and α ≈ β (α is exactly as likely as β).
A T-Book is a set of aleatoric terminological axioms.
These axioms place universal constraints on the likelihoods of aleatoric for-
mulas being true. For example we might include an axiom first place, meaning
coming first in a race is no more likely than placing (coming first, second or
third). Alternatively, we could define placing precisely as coming first, second
or third, via the axiom place ≈ first ⊔ second ⊔ third, and then first place is
implicitly true.
An Aleatoric Description Logic for Probabilistic Reasoning 5
Definition 4. The aleatoric assertional axiom (or simply assertions) have the
form:
– a :p α, where a ∈ N, p ∈ [0, 1] and α ∈ ADL asserts a belief that individual
a satisfies concept α, with probability p.
– (a, b) :p ρ, where a, b ∈ N, p ∈ [0, 1] and ρ ∈ R asserts that individual b
satisfies the role ρ for a with probability p.
An A-Book A is a set of aleatoric assertional
Paxioms, and A is a well-formed
A-Book if for every a ∈ N , for every ρ ∈ R, b∈N {p | (a, b) :p ρ} ≤ 1.
While T-Books give intensional definitions of concepts, A-Books give an exten-
sional definition by describing the concepts and roles in terms of the individuals.
As such an A-Book captures an agent’s current state of belief, just as a book-
maker’s book describes the current odds for a race. An A-Book is well-formed if
the roles described can be extended to a probability distribution (i.e. the prob-
abilities sum to less than 1).
While an A-Book is existentially quantified, T-Books are universally quanti-
fied and consequently a very powerful formalism.
Definition 5. An aleatoric knowledge base K = (A, T ) is a pair consisting of
a set of assertional axioms A and a set of terminological axioms T .
An aleatoric knowledge base describes a belief, or subjective position of an
agent, that can correspond to a number of different interpretations. The seman-
tics for these interpretations are given below.
An interpretation satisfies the aleatoric knowledge base K = (A, T ) iff it
satisfies all the axioms in A and T .
Definition 6. Given an aleatoric knowledge base K = (A, T ) over the signature
(X, R, N), and an aleatoric belief model B = (I, R, ℓ) over the signature (X∪N, R)
satisfies K iff:
– For every a ∈ N, for every i ∈ I, a(i) ∈ {0, 1} and for all i, j ∈ I, a(i) = 1
and id(i, j) > 0 implies a(j) = 1. That is, the names are absolute concepts,
and two possibilities for a single individual will share a name.
– For axioms α β ∈ T , for all i ∈ I, Bi (α) ≤ Bi (β).
– For axioms α ≈ β ∈ T , for all i ∈ I, Bi (α) = Bi (β).
– For axioms a :p α ∈ A, for all i ∈ I with a(i) = 1, Bi (Eα)
P = p.
– For axioms (a, b) :p ρ ∈ A for all i ∈ I with a(i) = 1, j∈I ρ(i, j) · b(j) = p.
We say that a knowledge base K is consistent if it is supported by at least one
aleatoric belief model.
Table 1 gives a set of abbreviations familiar in the context of description
logics.
The abbreviation in the right column of the table corresponds to a process
n
of repeated sampling: Where n, m ∈ ω, α m corresponds to the likelihood of α
being sampled at least n times out of m. (A similar abbreviation can be defined
6 Tim French and Thomas Smoker
Table 1: Some abbreviations of operators in ADL.
term formula interpretation
α ⊓ β (α?β:⊥) Bi (α).Bi (β)
α ⊔ β (α?⊤:β) Bi (α) + Bi (β) − Bi (α).Bi (β)
n
1
if n = 0
¬α (α?⊥:⊤) 1 − Bi (α) α =
m 0 if m < n
n−1 n
α ⇒ β (α?β:⊤) 1 − Bi (α) + Bi (α).Bi (β) α?α m−1 :α m if n < m
P
Eρ α [ρ] (α | ⊤) j∈I ρ(i, j).Bj (α)
∃ρ.α ¬[ρ] (⊥ | α) 1 if Eρ α 6= 0, 0 otherwise.
for α coming up ⊤ exactly n times out of m.) Note that this does not describe
4
a probability or frequency, but an event. So α 5 does not mean α is sampled at
least 80% of the time. Instead it describes the event of α being sampled 4 times
out of 5, which would be quite likely (0.88) if α had probability 0.8, and unlikely
(0.19) if α had probability 0.5. This formalism can encode degrees of belief in
an elegant way. If an agent were to perform an action only if they believed α
9
very strongly, one might set α 10 as a precondition for the action, and if an agent
were informed of a proposition β by another agent who is considered unreliable,
2
they may update their belief base with the proposition β 3 .
These operators may not appear logical: ⊓ is not idempotent, and appears
similar to the product t-norm of fuzzy logic [25]. However, Section 3 shows that
these new operators are inherently probabilistic and represent the process of
reasoning over a probability space of description logic models. Furthermore, re-
stricting the concept probabilities to be 0 or 1, it can be seen that the semantic
interpretation of ⊓, ¬ and ∃ρ agrees with the standard description logic se-
mantics, so classical description logic can be seen as a special case of aleatoric
description logic.
2.3 Example
For example, suppose we have three agents: Hector, Igor and Julia. They each
may have a virus (V), or not, and they also may have a fever (F), whether
they have the virus or not. For each possible individual, there is a probability of
them having a fever, which is naturally higher for possible individuals with the
virus. Each agent will occasionally come into contact with another agent, and
the identity of this agent is described by the probability distribution contact.
Finally, for each possible individual there is the probability of them being the
actual agent (id).
An aleatoric knowledge base could model that Hector is very likely not to
have the virus; Julia is likely to have the virus, Julia is very likely to have a
fever and it is likely that Hector came into contact with Julia. Furthermore, a
terminological axiom can specify the belief that a new exposure to the virus
(exp) occurs if an agent did not already have the virus, but came into contact
with some febrile person who did have the virus. We can calculate the probability
An Aleatoric Description Logic for Probabilistic Reasoning 7
of an agent being newly exposed to the virus:
E(¬V ⊓ [c] (V | F )) exp
Thus the aleatoric knowledge base K = (A, T ) is:
A = Hector :0.1 V, Julia :0.7 V, Julia :0.69 F, (Hector, Julia) :0.3 c
T = {E(¬V ⊓ [c] (V | F )) exp}
To determine if the knowledge base necessitates that there is a greater than 25%
chance of Hector being newly exposed to the virus, the axiom Hector :0.25 exp
can be inserted into the knowledge base, and consistency checking can be applied.
This process is described in the following section.
An interpretation that satisfies the knowledge base is presented below. For
each agent, we suppose that there are two possible individuals (PI), one with
the virus (e.g. Hector1) and one without (e.g. Hector0). Note that the weighted
probabilities of these agents satisfy the constraints of the A-Book, A.
The probabilities for this scenario are given in Table 2, and a graphical rep-
resentation is given in Figure 1.
Fig. 1: A graphical example of the virus
transmission scenario.
I0
V : 0.0
Table 2: Initial probabilities for agent, F : 0.3
0.5
contacts, virus and symptoms
H0 id 0.5
PI id V F H0 H1 I0 I1 J0 J1 V : 0.0 0.3 I1
Hector0 0.9 0.0 0.1 0.0 0.0 0.15 0.15 0.21 0.49 F : 0.1
c 0.6 V : 1.0
Hector1 0.1 1.0 0.6 0.0 0.0 0.15 0.15 0.21 0.49 0.4 F : 0.8
0.1
Igor0 0.5 0.0 0.3 0.04 0.36 0.0 0.0 0.18 0.42 id c
0.9
Igor1 0.5 1.0 0.8 0.04 0.36 0.0 0.0 0.18 0.42 0.4 J0
c 0.6 V : 0.0
Julia0 0.3 0.0 0.2 0.04 0.36 0.3 0.3 0.0 0.0 H1
V : 1.0 0.7 F : 0.2
Julia1 0.7 1.0 0.9 0.04 0.36 0.3 0.3 0.0 0.0
F : 0.6 id 0.3
0.7
J1
V : 1.0
F : 0.9
Interpreting this for Hector, we see the probability Hector was newly ex-
posed to the virus is approximately 0.7. The working for this is shown in Table 3.
2.4 Reasoning with Aleatoric Description Logic
This section will consider computational properties of aleatoric description logic.
The particular questions considered are:
Model Checking: Given an aleatoric belief model Bi and some formula α, what
is the value of Bi (α)?
Satisfiability: Given an aleatoric knowledge base, K = (A, T ), is it consistent?
8 Tim French and Thomas Smoker
Table 3: A calculation of the chance of Hector being newly exposed with the
virus, after a chance encounter with a person with a fever.
I0 FI0 = 0.3, (V ⊓ F )I0 = 0.0, c(H0 , I0 ) = c(H1 , I0 ) = .15
I1 FI1 = 0.8, (V ⊓ F )I0 = 0.8, c(H0 , I0 ) = c(H1 , I0 ) = .15
J0 FJ0 = 0.2, (V ⊓ F )J0 = 0.0, c(H0 , J0 ) = 0.21, c(H1 , J0 ) = .49
J1 FJ1 = 0.9, (V ⊓ F )J0 = 0.9, c(H0 , J0 ) = 0.21, c(H1 , J0 ) = .49
PJ1
x=I0 c(H0 ,x)·(V ⊓F )x
H0 V0 = 0.0, id0 = 0.9, [c] (V | F ) = PJ1 = 0.78
x=I0 c(H0 ,x).Fx
PJ1
x=I0 c(H1 ,x)·(V ⊓F )x
H1 V1 = 1.0, id1 = 0.1, [c] (V | F ) = PJ1 = 0.78
x=I0 c(H1 ,x)·Fx
P1
H E(¬V ⊓ [c] (V | F )) = x=0 (1 − Vx ) · idx .[c] (V | F ) = 0.7
The main question of interest is whether there is any interpretation that
could possibly correspond to a given aleatoric knowledge base. However, by as-
signing flat priors to all unknown (or ambivalent concepts) one can define an
interpretation and get a partial answer via model-checking.
Theorem 1. Given a pointed belief model Bi consisting of n possible individuals,
and a formula α consisting of m symbols, the value Bi (α) can be computed in
time O(n2 m).
See [8] (Lemma 4.7) for proof.
To be able to perform inference based on an aleatoric knowledge base, we
must first determine if it is consistent (i.e. agrees with at least one aleatoric belief
model). A partial solution is given here for acyclic aleatoric knowledge bases.
Definition 7. A concept C is an atom if C ∈ X ∪ {⊤, ⊥} (i.e. C is an atomic
concept, always, or never). A terminological axiom is simple if it has the one of
the forms
– C ≈ (D?E:F ) where C, D, E and F are all atoms.
– C ≈ [ρ] (D | E) where C, D and E are all atoms.
A simple T-Book, T , is a T-Book consisting only of simple terminological ax-
ioms. A simple T-Book, T , is acyclic if there is no sequence of concepts C0 , . . . , Cn
where:
– for all i = 1, . . . , n, either:
• there is some C ≈ (D?E:F ) ∈ T , where Ci , Ci−1 ∈ {C, D, E, F } ∩ X;
• there is some C ≈ [ρ] (D | E) ∈ T , where Ci , Ci−1 ∈ {C, D, E} ∩ X;
– there is some i where C ≈ [ρ] (D | E) ∈ T and Ci , Ci−1 ∈ {C, D, E} ∩ X;
– C0 = Cn .
An A-Book, A is simple if for all aleatoric assertional axioms σ ∈ A of the form
a :p α, it is the case that α is an atomic concept. If A is a simple A-Book and
T is a simple T-Book, the K is a simple aleatoric knowledge base, and if T is
also acyclic K is an acyclic simple knowledge base.
An Aleatoric Description Logic for Probabilistic Reasoning 9
The following lemma is a useful simplification.
Lemma 1. Every aleatoric knowledge base K = (A, T ) is equivalent to a simple
aleatoric knowledge base, K′ .
See [8] (Lemma ???) for proof.
Theorem 2. Given a simple aleatoric knowledge base K = (A, T ) where T is
acyclic, it is possible to determine if K is consistent with complexity PSPACE.
The process for the satisfiability theorem is to build a system of polynomial
equalities and inequalities corresponding to the axioms in K. This system of
constraints is satisfiable if and only if K is satisfiable. The number of variables,
inequalities and equalities in the system is polynomial in the size of K, so deter-
mining if the system is satisfiable reduces to ∃R (the satisfiability of existentially
quantified polynomial equations) which is in PSPACE [2]. See [8] (Theorem 4.8)
for a full proof. The case for non-acyclic T-Books is left to future work.
3 Expressivity
From Table 1 it can be seen that aleatoric description logic generalises ALC, in
the sense that ALC can be mapped to the 0 − 1 fragment of ADL. However,
this mapping overlooks the probabilistic aspect of ADL and how this relates to
uncertainty in description logics.
The semantic interpretation of aleatoric description logic can be seen as in-
terpreting ALC over a probability space of interpretations where all roles are
functions. The aleatoric belief models of ADL describe a probability space of
these simple descriptions, and the semantics of ADL recursively define the like-
lihood of a formula holding in models sampled from this probability space.
A probability space [13] is a tuple (Ω, F , P), where Ω is a set, F is a σ-algebra
over Ω (the events), and P is a probability measure on F that is countably
additive.
Theorem 3. Given a formula α of ALC and an aleatoric belief model Bi , there
exists: a formula α∗ that is logically equivalent to α in ALC; and probability
space (Ω Bi , F , P Bi ) where: Ω Bi is a set of functional ALC models; F is an
algebra over Ω Bi consisting of an element β̂ for every ALC formula β; and P Bi
is a probability measure on F derived from Bi . This probability space is such that
P Bi (α̂) = Bi (α∗ ).
The proof and necessary constructions can be found in [8] Section 5. This re-
sult gives a foundation for the semantics of ADL, establishing a correspondence
between the probabilistic operations of ADL, and the deterministic operations
of ALC applied over a probability space of interpretations. This way, ADL rep-
resents reasoning where an agent has in mind a probability space of possible
interpretations for the state of the world. By observing the world, the agent is
able to refine this probability space, and learn a better representation for their
beliefs.
10 Tim French and Thomas Smoker
4 Learning
An aleatoric belief model describes an agent’s beliefs and prior assumptions and
the agent may update these beliefs based on observations, via Bayesian condi-
tioning. This section will introduce two learning mechanisms, role learning and
concept learning whereby an agent may update the distribution of individuals
fulfilling a role, and also update the aleatoric probabilities associated with an
atomic concept at an individual. These mechanisms are unique to ADL and pro-
vides a compelling advantage over alternative probabilistic description logics [4,
17, 9, 23, 20].
4.1 Role learning
Role learning refines the probability distribution associated with a role ρ. For a
pointed aleatoric belief model, Bi = (I, r, ℓ, i), for every j ∈ I, ρ(i, j) is the prior
probability that j fulfils the role of ρ for i. Given an observation which is an
ADL formula of the form [ρ] (α | ⊤), Bj (α) is the probability of this observation
holding, given j fulfils the role of ρ for i. Via Bayes’ rule, it follows that the
probability of j fulfilling the role of ρ for i, given the observation is:
ρ(i, j) · Bj (α)
ρ′ (i, j) =
Bi ([ρ] (α | ⊤))
(the prior probability of j is multiplied by the probability of α given j, divided
by the probability of α).
Definition 8. Let Bi = (I, r, ℓ, i) be an aleatoric belief model, and φ = [ρ] (α | β)
an observation, made at i. The φ-update of Bi is the aleatoric belief model Biφ =
(I, ri,α , ℓ, i), where for all ρ′ 6= ρ and j 6= i, ri,φ (ρ′ , j) = r(ρ, j) and for all j ∈ I
ρ(i, j) · Bj (α)
ri,φ (ρ, i)(j) = .
Bi ([ρ] (α | β))
Thus an agent with an aleatoric model of the world may update their epis-
temic uncertainty of the distribution of roles, via Bayesian conditioning. The
φ-update of Bi is the agent’s posterior model of the world.
Given the example in Subsection 2.3, suppose that Hector’s belief model is
B = (I, r, ℓ, i), and Hector is informed that the contact has tested positive for the
virus. Hector is also informed that the test used has a 10% false positive rate, so
Hector’s belief model now includes an atomic concept FP that is 0.1 everywhere.
Let φ = [c] ((F P ?⊤:V ) | ⊤) and then the φ-update of BH0 is computed by:
c(i, j) · (0.1 + 0.9 · Bj (V )
rH0 ,φ (c, H0 )(j) = .
BH0 ([c] ((F P ?⊤:V ) | ⊤))
Substituting in the values from Table 2, Hector is able to discount the possible in-
dividuals without a virus and condition the distribution for contact accordingly.
The φ-update of BH0 is represented in Figure 2.
An Aleatoric Description Logic for Probabilistic Reasoning 11
I0 H0 1
V : 0.0 F : 0.84
F : 0.3
H0 0.1 J0 J0
V : 0.0 id 0.9 F : 0.9 F : 0.9
F : 0.1 0.25 0.8 0.5 (0.42) 0.8
I1 H0
0.4 c V : 1.0
0.1 0.6 F : 0.6
id F : 0.8 0.2 0.5 (0.58) 0.2
0.9 J1 H1
c F : 0.2 F : 0.2
0.4
H1 c J0 H0 2
V : 1.0 0.6 V : 0.0 F : 0.36
F : 0.6 0.75 F : 0.2
id 0.05 Fig. 3: Concept learning applied to the
0.95
J1 aleatoric belief model in Figure 1, where
V : 1.0Hector applies the belief that he would
F : 0.9
only have a fever if and only if a contact
Fig. 2: The φ-update of the aleatoric belief had a fever. The model on the left is the F -
model in Figure 1, after Hector is told a extension, and the probabilities in brackets
contact has tested positive for the virus. are the values after role learning has been
The updated values are bold. applied to id.
4.2 Concept learning
Role learning is a natural application of Bayes’ law since the learning is applied
to a probability distribution of possible individuals. However, the probabilities
of atomic concepts are modelled as dice, and hence independent of all other
variables beyond the possible individual. This means we gain no additional in-
formation from applying Bayes’ law. If it was possible to observe atomic concepts
directly (and often) it would be simple to refine a statistical model of the prob-
abilities. Observations in ADL are complex formulas, so it is preferable to find
a more general solution.
Concept learning addresses these issues by introducing new possible indi-
viduals in such a way that they do not affect any expected values for named
individuals but with variations in the aleatoric probability of concepts, which
may then be learnt via role learning, given arbitrary observations. The details
of such a construction are given in [8], Section 6.
In the example of Subsection 2.3, suppose that the assessment that the
likelihood of Hector having a fever is to be reassessed, based on the obser-
vation (or possibly erroneous belief) that Hector would have a fever if and
only if Hector’s contact had a fever. A new world H0 is replaced by H0 1 and
H0 2 where H0 1 (F ) = 2H0 (F ) − H0 (f )2 = 0.84, and H0 2 (F ) = H0 (F )2 = 0.36.
The probabilities are then updated via role learning over id, given the observa-
tion φ = Eid (F ?Ec F :Ec ¬F ), where the relevant fragment of the aleatoric belief
model is shown in Figure 3. Note, the model has been revised to make the exam-
ple clearer. Aggregating H0 1 and H0 2 back into a single node by taking weighted
sums of the likelihoods gives the updated probability of F at H0 to be 0.56.
12 Tim French and Thomas Smoker
5 Related work
There is a substantial amount of work on logics for reasoning about uncertainty
[10], including [15, 14, 24], and going back to the works of Ramsey [21], Carnap
[3] and de Finetti [5].
Markov Logic Networks [22] (generalising Bayesian networks and Markov
networks) address a similar problem of providing a logical interface to machine
learning methods. These approaches attach a probabilistic interpretation to for-
mulas in a fragment of first order logic, rather than providing a probabilistic
variation of first order logic operators.
There is some commonality in purpose with probabilistic logic programming
[16, 6], although the concepts are constrained to be Horn clauses, where atomic
formula are mutually independent.
There is a growing body of work addressing the need for probabilistic rea-
soning in knowledge bases. In [11], an inductive reasoning approach is applied
to include probabilities with rules; in [9], a subjective Bayesian approach is pro-
posed to describe the probabilities associated with a concept or role holding; and
Lukasiewicz and Straccia [17] have proposed a method to include vagueness (or
fuzzy concepts [25]) in descriptions logics. Probabilistic extensions of description
logics have also been proposed by Rigguzzi et al [23] and Pozzato [20]. These
approaches extend knowledge bases to include probabilistic assertions and ax-
ioms, and provide an extended syntax for querying probability thresholds. Some
work on learning parameters and structure of knowledge bases via probabilistic
description logics has been done, including Ceylan and Penaloza [4], who have
proposed a Bayesian Description Logic that combines a basic description logic
framework with Bayesian networks [19] for representing uncertainty about facts,
and Ochoa Luna et al [18] who applied statistical methods to estimate the most
likely configuration of a knowledge base.
These approaches are very different to the work presented here, as proba-
bilities are not propagated through the roles, and they do not permit learning
based on the observation of complex propositions.
6 Conclusion
This paper has introduced a novel approach for representing uncertain knowledge
and beliefs. Generalising the description logic ALC, the aleatoric description logic
is able to represent complex concepts as independent aleatoric events. The events
are contingent on possible individuals so they give a subjective Bayesian inter-
pretation of knowledge bases. This paper has also given computational reasoning
methods for aleatoric knowledge bases, and shown how aleatoric description logic
corresponds to a probability space of functional ALC models. The aleatoric con-
cepts and roles enable a simple learning framework where agents are able to
update their beliefs based on the observations of complex propositions.
Future work will examine the complexity of the satisfiability problem for
non-acyclic T-Books, and investigate implementing a reasoning system for aleatoric
description logics.
An Aleatoric Description Logic for Probabilistic Reasoning 13
References
1. Baader, F., Calvanese, D., McGuinness, D., Patel-Schneider, P., Nardi, D., et al.:
The description logic handbook: Theory, implementation and applications. Cam-
bridge university press (2003)
2. Canny, J.: Some algebraic and geometric computations in PSPACE. In: STOC ’88
(1988)
3. Carnap, R.: On Inductive Logic. Philosophy of science 12(2), 72–97 (1945)
4. Ceylan, I.I., Penaloza, R.: The Bayesian Description Logic BE L. In: IJCAR. pp.
480–494. Springer (2014)
5. De Finetti, B.: Theory of Probability: A critical introductory treatment. John
Wiley & Sons (1970)
6. De Raedt, L., Kimmig, A., Toivonen, H.: Problog: A probabilistic prolog and its
application in link discovery. In: IJCAI. vol. 7, pp. 2462–2467. Hyderabad (2007)
7. French, T., Gozzard, A., Reynolds, M.: A Modal Aleatoric Calculus for Probabilis-
tic Reasoning. In: ICLA. pp. 52–63. Springer (2019)
8. French, T., Smoker, T.: An aleatoric description logic for probabilistic reasoning
(long version) (2021), http://arxiv.org/abs/2108.13036
9. Gutiérrez-Basulto, V., Jung, J.C., Lutz, C., Schröder, L.: Probabilistic Description
Logics for Subjective Uncertainty. Journal of Artificial Intelligence Research 58,
1–66 (2017)
10. Halpern, J.: Reasoning about Uncertainty. MIT Press, Cambridge MA (2003)
11. Heinsohn, J.: Probabilistic Description Logics. In: Uncertainty Proceedings 1994,
pp. 311–318. Elsevier (1994)
12. Jøsang, A.: Subjective logic. Springer (2016)
13. Kolmogorov, A.N., Bharucha-Reid, A.T.: Foundations of the Theory of Probability:
Second English Edition. Courier Dover Publications (2018)
14. Kooi, B.P.: Probabilistic Dynamic Epistemic Logic. Journal of Logic, Language
and Information 12(4), 381–408 (2003)
15. Kozen, D.: A Probabilistic PDL. Journal of Computer and System Sciences 30(2),
162–178 (1985)
16. Lukasiewicz, T.: Probabilistic logic programming. In: ECAI. pp. 388–392 (1998)
17. Lukasiewicz, T., Straccia, U.: Managing Uncertainty and Vagueness in Description
Logics for the Semantic Web. Web Semantics: Science, Services and Agents on the
World Wide Web 6(4), 291–308 (2008)
18. Ochoa-Luna, J.E., Revoredo, K., Cozman, F.G.: Learning probabilistic descrip-
tion logics: A framework and algorithms. In: Mexican International Conference on
Artificial Intelligence. pp. 28–39. Springer (2011)
19. Pearl, J.: Causality: Models, Reasoning, and Inference. Econometric Theory
19(675-685), 46 (2003)
20. Pozzato, G.L.: Typicalities and probabilities of exceptions in nonmotonic descrip-
tion logics. International Journal of Approximate Reasoning 107, 81–100 (2019)
21. Ramsey, F.P.: Truth and probability (1926). The Foundations of Mathematics and
other Logical Essays pp. 156–198 (1931)
22. Richardson, M., Domingos, P.: Markov logic networks. Machine learning 62(1-2),
107–136 (2006)
23. Riguzzi, F., Bellodi, E., Lamma, E., Zese, R.: Probabilistic description logics under
the distribution semantics. Semantic Web 6(5), 477–501 (2015)
24. Van Benthem, J., Gerbrandy, J., Kooi, B.: Dynamic Update with Probabilities.
Studia Logica 93(1), 67 (2009)
25. Zadeh, L.A.: Fuzzy Sets. In: Fuzzy Sets, Fuzzy Logic, And Fuzzy Systems: Selected
Papers by Lotfi A Zadeh, pp. 394–432. World Scientific (1996)