=Paper=
{{Paper
|id=Vol-2438/paper3
|storemode=property
|title=Multiple Revision in Description Logics
|pdfUrl=https://ceur-ws.org/Vol-2438/paper3.pdf
|volume=Vol-2438
|authors=Fillipe Manoel Xavier Resina
|dblpUrl=https://dblp.org/rec/conf/ruleml/Resina19
}}
==Multiple Revision in Description Logics==
https://ceur-ws.org/Vol-2438/paper3.pdf
Multiple Revision in Description Logics
Fillipe Manoel Xavier Resina?[0000−0002−8753−3621]
University of São Paulo, São Paulo - SP, Brazil
fmresina@ime.usp.br
Abstract. The AGM paradigm is the most used framework in Belief
Revision. Among its various operations, a revision occurs when a rational
agent receives a new information inconsistent with its epistemic state and
has to revise it in order to accomodate the new belief in a consistent way.
However, this new information may come as a set of beliefs (instead of
a single one), a problem known as Multiple Revision. There may be two
approaches to this operation: to accomodate the whole new set of beliefs
or to incorporate only a subset of it. In the second case, the agent has
to be able to determine which part of the set will be added to its state.
In this project, we are particularly interested in this last case.
In addition to that, the agent may deal with different kinds of belief.
Thus, the purpose of this research plan is to define how to operate a
multiple revision and, more specifically, how to do this in non-classical
logics.
Keywords: belief revision · multiple revision · choice revision · descrip-
tion logics · ontology · ontology debugging.
1 Introduction
The problem of Knowledge Representation is one of the central areas in Artificial
Intelligence. With the advancement of technology, it became clear that we need
to enable computers to efficiently represent information regarding a domain in
order to be able to proceed with other tasks. In this context, ontologies came
out as a valuable option. Among the formalisms that were coined to represent
ontologies formally we have Description Logics (DLs)[2]. In addition, DLs form
the basis for OWL (Web Ontology Language), which is recommended since 2004
by W3C as the standard language to represent ontologies on the Web.
However, according to Gärdenfors[10], it is not very useful to know how to
represent knowledge if at the same time we do not know how to change it when
we receive new information. The motivation of this idea is that knowledge is not
static, what means that we need to be able to deal with its dynamics. That is
?
Supported by CAPES (Brazilian Coordination for the Improvement of Higher Edu-
cation Personnel)
Copyright c 2019 for this paper by its author. Use permitted under Creative Com-
mons License Attribution 4.0 International (CC BY 4.0).
the context of the studies in the area of Belief Revision, which aims to handle
the problem of adding or removing new information to a knowledge base in a
consistent way. Most of the literature about Belief Revision is based on the AGM
paradigm[1].
In the AGM paradigm, given a set of beliefs, there are three possible changes
in relation to a new belief: expansion, contraction and revision. Expansion oc-
curs when the base simply absorbs the information without loss. A contraction
consists in retracting beliefs from the base until the specified information is not
derivable from it anymore. Finally, revision happens when the new belief is added
in a consistent way, possibly demanding a repair in order to eliminate inconsis-
tency. In this project, we are particularly interested in this last operation.
In the original framework, the new belief is assumed to be represented by
a single formula. Nevertheless, there are situations in which the information by
which we are going to revise a set of beliefs comes in block. This generalized
operation is called Multiple Belief Revision. It is not the same as applying re-
vision in an iterated way, since in Multiple Revision it is assumed that there is
no preference over the input sentences, which means that all of them have equal
priority and should be processed at the same time.
However, when you consider the described scenario, there may be two ways
to achieve the goal. On the one hand the intention may be to absorb the new
sentences completely, which is called package. On the other hand, it may be
enough to incorporate a subset of the new sentences, which is called choice. In
this research project we are going to explore this last option in more detail.
From [3], we can visualize a practical scenario for choice revision. Suppose
you have a multi-agent system where there are some agents and also a main
agent as a coordinator. This last one receives information from the others and
has to process it in order to take some decisions. If there is a credibility degree
associated to each agent, for example, the coordinator may decide to take into
account only the information coming from the most reliable ones, characterizing
a kind of multiple version of Selective Revision[4]. On the other hand, it is
possible to have some agents with the same (or similar) reliability while you are
not sure about the impact of absorbing all the information given by them. In
this case, it would be interesting for the coordinator to process the new beliefs in
some way before performing a decision. Then it is important to define desirable
properties and constructions associated to them that will be able to guide this
process.
Combining this and the need to change ontologies, we investigate in this work
how to apply Belief Revision in a multiple context, especially for Description
Logics, with a particular attention to OWL ontologies.
This proposal is structured as follows. In the next section, we provide a
background in Belief Revision and Ontologies. In Section 3, we detail the goals,
objectives and methodology of this proposal. Finally, in Section 4 we organize
the tasks according to the remaining semesters.
2 Background
2.1 Belief Revision
In the AGM paradigm, the revision operation is defined from contraction via
the Levi Identity[10]. Let K be the belief set of an agent and α an incoming
belief. The referred identity defines the revision operation in the following way:
K ∗ α = (K − ¬α) + α, where − stands for contraction and + for expansion.
Besides establishing properties which the operations should obbey (known as
postulates), constructions were elaborated to give means of executing the desired
procedures. Among them, we highlight two: Partial Meet[1] and Kernel[11]. As
revision used to be considered just a compound operation, the Partial Meet and
Kernel versions of revision were given by just using the corresponding version of
contraction in the Levi Identity.
Within the Belief Change area, the operations, properties and constructions
were initially defined thinking of the initial beliefs as being a belief set, i.e., a set
of beliefs closed under logical consequence. However, since sets conceived this
way are usually infinite, there are some disadvantages with this approach, espe-
cially for computational purposes. Considering this problem, instead of working
with belief sets, some authors began to work also with belief bases, which are
knowledge bases not necessarily closed. For practical purposes in change opera-
tions it is much more convenient and is of particular interest for us.
2.2 Multiple Change and Multiple Revision
In [7] we have a first picture of a change operation that is not necessarily by
a single input. The author claims that sometimes we need to withdraw more
than one proposition of a belief set at the same time, proposing the name Mul-
tiple Contraction for this case. Following [7], we also see the discussion of some
properties of revision operations that receive as input more than one sentence
simultaneously, named Multiple Revision. Analogously to Multiple Contraction,
when the result of K ∗ A should contain some elements (but not necessarily
all) of A (Cn(K ∗ A) ∩ A 6= ∅), then we have (multiple) choice revision (here
denoted by ∗c ), while when the result of K ∗ A should imply everything in A
(A ⊆ Cn(K ∗ A)) we have (multiple) package revision (denoted by ∗p ).
Now, the package revision operation can be defined via a generalized version
of the Levi Identity using package contraction: K ∗p A = (K −p ¬A) + A, where
¬A = {¬α : α ∈ A}. By this approach, the properties of a package revision
operation become dictated by the ones of the package contraction operation.
Nevertheless, considering that some logics lack negation, it would be interesting
to study the definition of revision operations in a direct way, i.e., without using
contraction as an intermediate step. This is one of the main goals of the work
developed in [3], which is focused on package revision.
Still about the generalized Levi Identity, we have in [8] a further exploration
of the topics initiated in [7]. Fuhrmann adresses the issue focusing on the package
variety and the Partial Meet construction. He also shows how the operations of
revision and contraction can be interdefinable.
In multiple operations, one of the questions that emerge is whether it is
possible to reduce them to operations by singletons. For the revision case, the
following
V result for finite sets was obtained in [8]: for every finite set A, K ∗ A =
K ∗ A. It means that in the finite case it is possible to reduce a multiple revision
to a revision by the conjunction of all the elements of the input. However, this
identity works only for languages that allow logic conjunction of sentences, which
is not the case of Description Logics and some other non-classical logics.
In [3], the authors defined some postulates for a direct operation, most of
which were adapted from postulates for singleton revision. By generalizing the
techniques from classical belief base revision, the authors defined two kinds of
construction: Package Kernel Revision and Package Partial Meet Revision1 .
In [15], the author explores choice revision (a non-prioritized multiple revi-
sion). This means that incoming beliefs do not have total priority with respect
to the initial beliefs. Before defining the operation, the author introduces Partial
Expansion (denoted by u), which is a generalization of the traditional expansion
operation. Roughly speaking, given a belief set K and an input set A, the result
of a partial expansion of K by A is formed by the union of K with a subset of
A. Using the definition of negation set of a set of sentences A (¬A), the Choice
Revision operation is defined in [15] as follows: K ∗c A = K −c ¬A u A. Due to
the usage of set-negation to perform the contraction part of the choice opera-
tion, this approach depends on negation and on disjunction of sentences, which
excludes some interesting logics, such as Description Logics.
2.3 Selective Revision
In [4], Fermé and Hansson explored a new possibility of revision which is capable
of incorporating only a part of the input belief, calling it selective revision.
In order to achieve the partial acceptance, we need to apply a transformation
function f to every input sentence α aiming to extract the “most trustworthy”
part of it.
With these tools in mind, it is possible to construct a model for selective
revision. Let K be a belief set, ∗ a partial meet revision for K and f a trans-
formation function. The selective revision ◦, based on ∗ and f , is the operation
such that for all sentences α, K ◦ α = K ∗ f (α).
However, it is not suitable neither for belief bases (given that it depends on
a postulate of closure) nor for Description Logics (once some properties of the
transformation function apply negation, disjunction and conjunction of sentences
and DLs are not closed under any of these operators).
1
In the original article, Package Revision is called Prioritized Change, in the sense
that all the sentences from A should be present in the new belief base. Then, for the
constructions, the names originally given were Prioritized Multiple Kernel Revision
and Prioritized Multiple Partial Meet Revision.
2.4 Ontologies and Description Logics
An ontology provides a description of individuals, their aspects (attributes) and
restrictions, how they can be categorized (classes) and how they interact with
each other (relations), in relation to a given domain.
Ontologies can be used in a growing range of applications, such as medical
diagnosis, biological and biomedical research. In Artificial Intelligence, we can
see ontologies in the modeling of Natural Languages and also in Knowledge
Representation, being useful for robotic path planning.
As a main language used for describing ontologies, we can cite OWL (Web
Ontology Language), part of the standards defined by the World Wide Web
Consortium (W3C) to represent ontologies and organize data2 .
The theoretical basis both for OWL and for the profiles associated to it are
formed by Description Logics (DLs), which are structured subsets of First Order
Logic and have a well defined formal semantics.
Due to the dynamics of knowledge, it is important to know how to modifi-
cate an ontology when there is a need for change (a new information, changes
dictated by an ontology engineer, etc). As ontologies are usually huge and in-
tricate structures, this problem is of considerable importance, what gives rise
to the ontology change issue[6] (also called ontology evolution) and makes clear
the relevance of the Belief Change area. The composite kind of ontology change
(changes that are applied at the same time) shows the applicability of Multiple
Revision in this field.
3 Proposal, Objectives and Method
Our main goal with this project is to propose postulates, constructions, theorems
and algorithms that make it possible to perform operations of Multiple Belief
Revision, especially in Description Logics. We detail below the specific objectives,
pointing, when relevant, what has already been done or is in progress.
In order to develop this research plan, we are going to apply a formal mathe-
matical analysis. To accomplish this, our bases will be previous works on Multiple
Contraction, Multiple Revision, Merging and on the problems of the Levi identity
in non-classical logics, aiming to analyze and extract mathematical formalisms
already developed in the area to conduct our steps.
3.1 A survey of the field
Before going deeper in the project, we searched for all the works that had already
been developed in the area of Multiple Revision. Along the process, it came to us
the need to systematize the theories developed, organizing and comparing them.
Then, we have started to produce a survey on the topic, using as main ref-
erences the works in [7,8,3,15].
2
https://www.w3.org/standards/semanticweb/
https://www.w3.org/TR/owl2-overview/
3.2 Compatibility with Description Logics and Constructions
Firstly, we want to identify and establish all the limitations of the existing theory
for Multiple Belief Revision when it comes do DLs, more specifically through the
choice approach. After that, we have to define all the postulates needed to make
feasible the compatibility between Multiple Revision and DLs.
One of the first steps is to analyze and compare the aspects studied in works
such as [13] in order to identify all the limitations that DLs bring to classical
AGM theory. From the limitations collected in the previous step, it will be
possible to make a comparison with the properties and requirement of what
was exposed in [8,15] in order to establish precisely in which points the existing
theory of Multiple Belief Revision is not applicable to DLs and needs adaptation.
Using Partial Meet and Kernel approaches, it will be possible to create con-
structions capable of executing (Multiple) Choice Belief Revision in DLs. With
these resources in hand, we will be able to propose and demonstrate representa-
tion theorems that prove the validity of the connection between the postulates
defined and the constructions created.
Regarding this topic, after studying the limitations, it was possible to identify
the incompatibilities presented in [7,8,15], what motivated us to use an approach
similar to the one found in [3] in order to propose new postulates for Multiple
Choice Revision that are appropriate to Description Logics. We defined as well
the corresponding Partial Meet and Kernel constructions to this operation. So,
we still need to refine the postulates and finally use them to propose and prove
representation theorems.
A valuable resource can be obtained analyzing and comparing the properties
and constructions used in the development of the theories about Multiple Be-
lief Contraction[9,5], Multiple Belief Revision in Horn Logic[14] and Merging[8],
aiming to extract theoretical and mathematical tools possibly useful to develop
the theory of Multiple Belief Revision in DLs.
3.3 Selective Revision
When we compare the choice approach of Multiple Revision and the operation of
Selective Revision it is possible to identify some similarities. Although this last
one has been developed to singleton inputs, it shares with choice the property
of selecting a part of the incoming information to incorporate. It could be a
possible way to perform multiple choice revision. Then, we aim to explore the
Selective Revision operation in order to study the possibility of extending it to
the multiple case and, more specifically, to Description Logics.
3.4 Algorithms
Regarding the practical aspects of the theory to be developed, we plan to develop
algorithms that correspond to the constructions studied and proposed, in order
to pave the way for implementation of the theory developed. In addition, it will
be possible to compare, in this context, the Partial Meet and Kernel approaches
in relation to the computational complexity of the operations.
In order to get closer to what has already been developed in the field, we
intend to analyze the algorithms for singleton Belief Revision[13] and for Multiple
Contraction[12] aiming to analyze the constructions and properties used and,
then, create algorithms that correspond to the desired constructions.
In relation to Package Revision, following the approach presented in [3], we
have already developed the algorithms (both for Partial Meet and Kernel) and
proved their correctness. So, it remains necessary to develop the ones for Choice
Revision, after the correct definition of the corresponding constructions.
3.5 Comparison with Merging
Due to the non-prioritized nature of Multiple Choice Revision, i.e., the possibility
of partial acceptance in relation to the input beliefs, there may be a correlation
between this operation and the merging operators.
Merging is also a type of non-prioritized change that happens when you need
to harmonize multiple sources of information. Depending on the entrenchment
of the beliefs you already have and on the integrity constraints required to the
operation, the input knowledge base may be partly or totally discarded, although
there is no precedence established to the different sources, i.e., previous and new
beliefs have symmetric roles during the process.
Therefore, we intend to study it more deeply to understand what are the
differences between the operations and also the similarities, especially if some
properties can be shared. For more details about the operation, its properties
and constructions, see [3].
4 Project Schedule
So far, the student has already accomplished the requisites from the post-graduate
program: the mandatory courses and the approval in the qualifying exam. Our
research plan is scheduled as follows:
2nd Semester of 2019:
– Survey of the field;
– Proposal of the postulates for Multiple Choice Revision;
– Development of Partial Meet and Kernel constructions for Multiple Choice
Revision;
– Proposal and proof of representation theorems between the constructions
and the postulates;
1st Semester of 2020:
– Development and proof of the Partial Meet and Kernel algorithms for Choice
Revision;
– Analysis of the complexity of the algorithms developed;
– Implementation and testing of the algorithms developed;
– Identification of the limitations of Selective Revision for Description Logics;
– Analysis of the Selective Revision operation in order to extend it to the
multiple case;
2nd Semester of 2020:
– Proposal of an adaptation of Selective Revision to the multiple case;
– Proposal of an adaptation of Multiple Selective Revision for Description
Logics;
– Comparison between Multiple Choice Revision and Merging to identify pos-
sible connections;
1st Semester of 2021:
– Conclusion of the comparison with Merging;
– Final refinements;
– Thesis defense.
References
1. Alchourrón, C., Gärdenfors, P., Makinson, D.: On the logic of theory change. Jour-
nal of Symbolic Logic 50(02), 510–530 (1985)
2. Baader, F., Horrocks, I., Lutz, C., Sattler, U.: Introduction to Description Logic.
Cambridge University Press (2017)
3. Falappa, M., Kern-Isberner, G., Reis, M., Simari, G.: Prioritized and non-
prioritized multiple change on belief bases. Journal of Philosophical Logic 41(1),
77–113 (2012)
4. Fermé, E., Hansson, S.O.: Selective revision. Studia Logica 63(3), 331–342 (1999)
5. Fermé, E., Saez, K., Sanz, P.: Multiple kernel contraction. Studia Logica 73(2),
183–195 (2003)
6. Flouris, G., Manakanatas, D., Kondylakis, H., Plexousakis, D., Antoniou, G.:
Ontology change: Classification and survey. The Knowledge Engineering Review
23(2), 117–152 (2008)
7. Fuhrmann, A.: Relevant Logics, Modal Logics and Theory Change. Ph.D. thesis,
Australian National University, Camberra (1988)
8. Fuhrmann, A.: An Essay on Contraction. FOLLI (1997)
9. Fuhrmann, A., Hansson, S.O.: A survey of multiple contractions. Journal of Logic,
Language and Information 3(1), 39–75 (1994)
10. Gärdenfors, P.: Knowledge in Flux - Modeling the Dynamics of Epstemic States.
MIT Press (1988)
11. Hansson, S.O.: Kernel contraction. Journal of Symbolic Logic 59(3), 845–859
(1994)
12. Resina, F.M.X.: Revisão de Crenças em Lógicas de Descrição-Um Plug-In para o
Protégé. Master’s thesis, Universidade de São Paulo (2014)
13. Ribeiro, M.M.: Belief revision in non-classical logics. Springer (2013)
14. Valdez, N.J., Falappa, M.A.: Multiple revision on Horn belief bases. In: Proceedings
of the XVII Workshop Agentes y Sistemas Inteligentes (WASI). pp. 45–54 (2016)
15. Zhang, L.: Choice revision on belief bases. arXiv preprint arXiv:1805.01325 (2018)