Tóm tắt Luận án Methods of processing inconsistent knowledge in ontologies
HUE UNIVERSITY
UNIVERSITY OF SCIENCES
NGUYEN VAN TRUNG
METHODS OF
PROCESSING INCONSISTENT KNOWLEDGE
IN ONTOLOGIES
MAJOR: COMPUTER SCIENCE
CODE: 62.48.01.01
SUMMARY OF DOCTORAL THESIS
OF COMPUTER SCIENCE
HUE - 2018
The thesis has been completed at:
Hue University of Sciences - Hue University
Supervisor:
Assoc. Prof. Dr Hoang Huu Hanh
Reviewer 1: ......................................................................................
......................................................................................
Reviewer 2: ......................................................................................
......................................................................................
Reviewer 3: ......................................................................................
.......................................................................................
The thesis will be presented at the Committee of Hue University,
to be held by Hue University at ...... ..... , 2018
The thesis can be found at the following libraries:
• National Library of Vietnam
• Library Information Center University of Science, Hue University
PREFACE
1. The necessity of the topic
In 2001, Tim Berners Lee and coworkers have propose a new “a new form of Web
content that is meanningful to computers”. The new generation of web that use this
form of content called as Semantic Web, allows computers can “understand” stored
knowledge, by that way can share and re-use knowledge bases in information systems of
several domains. Compare with current generation web – as a repository of documents
that links together, Semantic Web is a platform that stores information in a form of
explicit definition, allow computers and human can work together.
Semantic Web is a research domain that quickly expands and is interested in by re-
search community in the last decade. Semantic Web technologies are applied in several
aspects. The most important component in Semantic Web applications is ontology.
In an ontology people define entities (concepts, properties, instances) and rela-
tionships between these entities by semantics of a specific logic. Ontology language
that using most popular today and standarized by W3C is OWL. The newest ver-
sion of this language is OWL 2 (introduced in 2009) based on the Description Logics
SROIQ(D).
The important issue of Semantic Web is handling inconsistent knowledge in onto-
logies. This issue come from properties of building and using ontologies in Semantic
Web applications: Extensibility and shareability, distributed and multi-users potenti-
ally cause occurring inconsistent knowledge.
Actually, if an ontology is inconsistent, queries against it are meaningless. Reason
of this is any axiom is logic consequence of an inconsistent ontology. In another way,
inconsistency causes ontology useless in Semantic Web applications. Due to that rea-
son, processing inconsistent knowledge in ontologies is the important problem and has
practical sense and attracts computer science community.
2. Research motivation and researching approaches
Approaches of processing inconsistent knowledge in ontologies are classified in two
categories: (1) approaches that tolerate existence of inconsistent knowledge in ontology,
and (2) approaches that try to remove inconsistency from ontologies:
(1) Approaches that tolerate existence of inconsistent knowledge in ontology. Some
approaches in this category define Description Logics with para-consistent semantics
and building ontology in these logics. Using para-consistent logics to build ontology,
although allows to model comprehension knowledge but have difficulties in reality
deployment because of popularity of ontology language that standarzed and recom-
mended by W3C.
Actually, in many circumstances, Semantic Web application need to query infor-
mation which are integrated from ontologies coming different sources (and may be
inconsistent) without modification permission. A solution for this issue is framework
of reasoning with inconsistent ontology using linear extension strategy, proposed by
Zhisheng Huang, Frank van Harmelen and coworkers. This framework evaluates mea-
ningful results for queries against inconsistent ontologies by select a subset of axioms
from input ontology: axioms in this set relevant to query in a given criteria. The most
important component of reasoning framework is selection function that use to select
1
the axioms set. Two typical selection functions of the authors are: the syntactic-based
selection function and Normal Google Distance based selection function. Both of the
two selection functions have advantages due to dependence of syntax of axioms. Over-
coming these advantages is a research motivation of the thesis: We propose a way to
select axioms set by semantic relevance of axioms to input query. The relevance is
evaluated based on semantic distance between concept expression when place them in
concepts hierarchy of the so-called referenced ontology.
(2) Approaches that try to remove inconsistency from ontologies. Creation of on-
tology is based on two strategy: the first strategy is finding and suggesting to modify
or remove axioms from ontologies; and the second strategy is apply consensus theory
to process of determining axioms set, which best represents (in the given criteria) for
input ontologies. The first strategy is often used for maintaining consistency of an
ontology. In the meanwhile the second strategy is used to resolve conflicts in process
of integrating ontologies coming from severals distributed, independent sources.
Methods of resolving conflict of knowledge that based on consensus theory have
been proposed by professor Ngoc Thanh Nguyen and co-workers in 2002 extended in
following years. Authors classify conflicts in ontologies integration to levels of concepts,
relationships, instances and propose methods to resolving these levels of conflict.
By structure of a concept in ontology integration process, people consider two
aspects: the list of attributes to describe the concept, and their domain. However, the
current researches of handling conflict at concept level only resolve conflict of the list
of attributes while domain of each attribute in the integration concept is determined
as sum of the participant domains. This means that conflict of attributes’ domain is
omitted. Thesis will apply general consensus-based models for integrating knowledge
and propose a new approach to resolve conflict at the concept level in both of two
aspects: list of attributes and their domains.
Another level of conflict may also occurs in process of ontology integration is level
of axiom, such that axioms set of participant ontologies are different or even contradict
each other. This circumstance also occurs in building process of ontology collaborati-
vely and distributively by multiple users (volunteer users in wiki environment or the
like, or hired experts) Conflict in level of axiom in ontology integration currently has
no good and effective resolution (like other levels of conflict). By representing an axiom
by a literal, each participant ontology can be modeled as conjunction of literals. In
this way, the problem of resolving conflict of axioms set can be treated as the problem
of resolving conflict at syntactic level of conjunctions. We propose a distance function
between two conjunctions, analyze postulates for consensus’s conjunction and formu-
late a strategy to determine consensus conjunction. The result of this process can be
applied to problem of process conflict at the axiom level.
3. Research objectives and scope of research
Research subjects of the thesis are ontology, inconsistent knowledge in ontologies
and methods of processing inconsistent knowledge in ontologies. By analyzing research
motivations, we address objectives of research for processing inconsistent in ontologies
by the two tasks: querying and integrating. In particularly, we restrict the objectives
of research by three problems following:
• The first problem: Determine meaningful result for querying inconsistent onto-
2
logy. In this problem, we research and propose a method to use the referenced
ontology for evaluating semantic distance between two concepts, between two
concept expression, between two axioms. This semantic distance will be used to
formulating a selection function that applying in framework of reasoning with
inconsistent ontology.
• The second problem: Resolving conflict of concept level in ontology integration.
We apply general consensus-based models for integrating knowledge to determine
consensus for the concept’s structure. The conflict of concept’s structure will be
resolved in both attributes list and their domains.
• The third problem: Resolving conflict of axiom level in ontology integration. By
representing conflict of axiom level in ontology integration as conflict of syntactic,
we evaluate difference of axiom sets and formulate a method to determine the
consensus axiom sets that satisfies postulates which based on this difference.
Chapter 1
OVERVIEW ON PROCESSING
INCONSISTENCY IN ONTOLOGIES
1.1. Ontology and inconsistent knowledge
Definition 1.1 (Ontology). An ontology is a quadruple hC, I, R, Zi, where: C is a set
of concepts (classes); I is a set of instances of concepts; R; R is a set of relationship;
Z is a set of axioms which can be interpreted as integrity constraints or relationships
between entities (concepts, instances, relationships).
ꢀ
We also call R in the Definition 1.1 as the set of properties. One classify two kinds
of properties: object property which links instances, and datatype property which links
instance to a data value.
An ontology is called as inconsistent if it has no model. The reason of this is the
set of its axioms contains contradiction. Querying against an inconsistent ontology
is meaningless because every axiom is logic consequence of the set of axioms which
contains contradiction.
In this theses, we deal with the inconsistency in ontology by addressing the fol-
lowing two problems: querying inconsistent ontologies and, resolving inconsistency in
ontology integration. Basic theories for these problem – general framework for reaso-
ning with inconsistent ontologies, and consensus theory — will be introduced in this
overview chapter.
1.2. Framework for reasoning with inconsistent ontologies using linear extension
strategy
1.2.1. Basic definition
Framewotk for reasoning inconsistent ontology was proposed by Zhisheng Huang,
Frank van Harmelen etal in 2005. In this framework, ontology is viewed as a set of
axioms and not restricted to any ontology language. Call L as an ontology language,
we denote 2L as the set of all set of axioms in L. Ontology Σ can be view as a set of
3
axioms in L: Σ ∈ 2L. In the following, we use |= to denote the classical entailment, and
use |≈ to denote some non-standard inference relation, which may be parameterized
to remove ambiguities.
Definition 1.2 (Soundness). An inconsistency reasoning |≈ is sound if every axiom,
which is logic consequence of an inconsistent ontology Σ by |≈, is also inferred from
consistent subset of axiom of Σ (called as sub-ontology) by |=.
ꢀ
Definition 1.3 (Meaningfulness). A result of inconsistent reasoning is meaningful if
it is sound and consistent: Σ |≈ φ ⇒ Σ |≈ ¬φ.
A non-standard reasoner |≈ is meaningful if and only if all of its results are mea-
ningful.
ꢀ
Definition 1.4 (Quering against inconsistent ontology using non-standard reasoner).
A query φ againts inconsistent ontology Σ using a non-standard reasoner |≈ is a
evaluating the relations “Σ |≈ φ?” and “Σ |≈ ¬φ?”. There are four possible answers:
(a) Overdetermined: Σ |≈ φ and Σ |≈ ¬φ.
(b) Accepted: Σ |≈ φ and Σ |≈ ¬φ.
(c) Rejected: Σ |≈ φ and Σ |≈ ¬φ.
(d) Undetermined: Σ |≈ φ and Σ |≈ ¬φ.
ꢀ
Definition 1.5 (Local completeness). Let Σ is an inconsistent ontology, Σ0 ⊂ Σ is
a consistent sub-ontology of Σ. φ is an axiom, result of Σ |≈ φ is called as locally
complete by Σ0 if: Σ0 |= φ ⇒ Σ |≈ φ.
The non-standard reasoner |≈ for Σ is called as locally complete by Σ0 if all of it
results are locally complete by Σ0.
ꢀ
Definition 1.6 (Local soundness). Let Σ is an inconsistent ontology, Σ0 ⊂ Σ is a
consistent sub-ontology of Σ. A result of query φ againts Σ is called as locally sound
by Σ0 if and only if: Σ |≈ φ ⇒ Σ0 |= φ.
A non-standard reasoner |≈ for ontology Σ is called as locally sound by Σ0 if all of
it query results Σ |≈ φ are locally sound by Σ0.
ꢀ
Definition 1.7 (Maximality). Let Σ is an inconsistent ontology, Σ0 ⊂ Σ is a consistent
sub-ontology of Σ. The non-standard reasoner |≈ with Σ is called maximal by Σ0 if:
(Σ0 |= > v ⊥) ∧ (∀Σ00 ⊂ Σ : Σ00 ⊃ Σ0 ⇒ Σ00 |= > v ⊥) ∧ (∀φ : Σ0 |= φ ⇔ Σ |≈
φ) .
ꢀ
Zhisheng Huang etal proved that:
Theorem 1.1. Let Σ is an inconsistent ontology, Σ0 ⊂ Σ is a consistent sub-ontology
of Σ, |≈ is a non-standard reasoner, φ is an axiom. We have: (a) Local soundness
implies soundness and meaningfulness.
(b) Maximality implies locally completeness.
4
1.2.2. Selection function
Let L is an ontology language, Σ ∈ 2L is an ontology, φ ∈ L is an axiom in L.
The selection function s which returns a subset of Σ at the step k > 0 (k ∈ N) in the
process of evaluating query “Σ |≈ φ?”, is generally defined as:
Definition 1.8 (Selection function). The function s is a mapping s: 2L ×L×N → 2L
such that s(Σ, φ, k) ⊆ Σ với ∀Σ ∈ 2L, φ ∈ L, k ∈ N.
ꢀ
Definition 1.9 (Monotonic selection function). A selection function s is called as mo-
notonic is called monotonic if the subsets it selects monotonically increase or decrease
by steps.
ꢀ
1.2.3. Non-standard reasoner using monotonic selection function
The reasoner using monotonically increase (decrease) selection function is called
as reasoner using linear extension strategy (reduction strategy). A linear extension
strategy works as Figure 1.1.
Figure 1.1: Linear Extension Strategy
Theorem 1.2 (Properties of Linear Extension Strategy). A reasoner using a linear
extension strategy satisfies the following properties:
(a) never over-determined (b) may be undetermined
(c) always sound
(d) always meaningful
(e) always locally complete (f) may not be maximal
(g) always locally sound.
1.2.4. Non-standard reasoning using relevance syntax-based selection function
Relevance syntax-based selection function sSyn
With an axiom φ, we denote I(φ), C(φ), R(φ) as set of instance names, concept
names and relationship names which occur in the axiom.
5
Definition 1.10 (Direct relevant). The two axioms φ, ψ are directly relevant if there
is a common name which appears both in φ and ψ, i.e.:
ꢀ
ꢁ
ꢀ
ꢁ
ꢀ
ꢁ
I(φ) ∩ I(ψ) = ∅ ∨ C(φ) ∩ C(ψ) = ∅ ∨ R(φ) ∩ R(ψ) = ∅ .
(1.1)
ꢀ
Definition 1.11 (Direct relevant to a set). The axiom φ is directly relevant to the
axiom set Σ if there exists an axiom ψ ∈ Σ such that φ and ψ are directly relevant.
ꢀ
Definition 1.12 (Syntax relevance-based selection function). A syntax relevance-
based selection function is defined as:
2L × L × N → 2L
(Σ, φ, k) → sSyn(Σ, φ, k)
where: sSyn(Σ, φ, 0) := ∅; sSyn(Σ, φ, 1) := {ψ ∈ Σ | ψ directly relevant to φ}; và
sSyn(Σ, φ, k) := {ψ ∈ Σ | ψ is directly relevant to sSyn(Σ, φ, k − 1)} (k > 1).
Non-standard reasoner using the selection function sSyn
ꢀ
The syntax relevance-based selection function sSyn is monotonically increase. The
reasoner using the selection function sSyn in general reasoning framework has been
presented in previous section is denoted as |≈Syn, often quickly extend to an incon-
sistent axiom set. We can refine the procedure with a backtracking step, which tries
to reduce sSyn(Σ, φ, k) to a set that still extends sSyn(Σ, φ, k − 1), but that is still
consistent. This process is called as overdetermined processing (ODP). However, ODP
introduces a degree of non-determinism: selecting different maximal consistent subsets
of sSyn(Σ, φ, k) may yield different answers to the query Σ |≈Syn φ.
1.2.5. Related works of framework of reasoning with inconsistent ontology
using linear extension strategy
Selection function plays an important role in the framework of reasoning with
inconsistent ontology using linear extension strategy. We introduce the two typical
selection functions – syntactic-relevant based selection function and Normal Google
Distance-based selection function.
The syntactic-relevant based selection function has some disadvantages:
• The reasoning process often apply the ODP procedure.
• Number of extension axioms in a step of reasoning process often large.
The semantic relevant based selection function, which uses Normal Google Distance
(NGD) proposing intend to address these advantages. However, it also has advantages
due to depend on syntax of axioms:
• The linear extension strategy depends on syntax of representing entities (concept
name, relationship name, instance name) in axioms.
• The linear extension strategy doesn’t consider entities in its overall expression.
We address these advantages and propose a new way to evaluate the relevance
of axioms in the extension process, which uses semantic of a so-called the referenced
ontology: concept expressions in axioms are placed on the hierarchy of concepts of the
referenced ontology.
6
1.3. Resolving inconsistent knowledge in integration of ontologies using consensus
theory - based methods
1.3.1. Conflict profile
By U we denote a finite set of objects representing possible values for a knowledge
Q
state; (U) is the set of all nonempty subsets with repetitions of set U. An element
in (U) is called as a conflict profile. We classify class of conflict profiles as below.
Q
Q
Definition 1.13 (Class of conflict profiles). A conflict profile X ∈ (U) is called as:
(1) Homogeneous, if all its elements are identical; that is X = {n ∗ x} where x ∈ U
and n ∈ N.
(2) Heterogeneous, if it is not homogeneous.
(3) Multiple of Y, written as X = n ∗ Y, if Y = {x1, x2, . . . , xk} và X = {n ∗ x1, n ∗
x2, . . . , n ∗ xk} where k, n ∈ N and n > 1.
(4) Regular if it is distinguishable or a multiple of some distinguishable profile.
ꢀ
1.3.2. Inconsistency of knowledge
Inconsistency of knowledge of a set of agents about certain subject can be repre-
sented by a conflict profile.
Definition 1.14 (Knowledge Inconsistency). Knowledge of agents when reference
to a subject s can be formula as conflict profiles X+(x) and X−(s). These profiles
reflect knowledge states from the universe set U and represent positive and negative
knowledge for the subject s of the agents. We say there exists inconsistency or conflict
knowledge about subject s if X+(s) or X−(s) is not homogeneous.
ꢀ
Definition 1.15 (Distance function). The function d: U × U → [0, 1] is called as
distance function between two elements in the universe set U if it satisfies the following
conditions:
1) Non-negative: ∀x, y ∈ U : d(x, y) ≥ 0 ;
2) Reflexive: ∀x, y ∈ U : d(x, y) = 0 iff x = y ;
3) Symmetrical: ∀x, y ∈ U : d(x, y) = d(y, x) .
ꢀ
The distance function is used for evaluating inconsistency degree and formulating
consensus for conflict profiles. Inconsistency of a conflict profile is measured by function
Q
c as: c : (U) → [0, 1]. One propose the set of postulates P for inconsistency
functions .(Definition 1.16)
7
1.3.3. Consensus function
Definition 1.17. Consensus function in a half-metric space (U, d) is a mapping
Q
C : (U) → 2U where, 2U denotes a set of all subsets of U.
Definition 1.18 (Postulates for consensus functions). Let U is the universe set, (U, d)
is a half-metric space. A consensus function should sastify one or more postulates
(called as postulates for consensus functions): Reliability, Unanimity, Simplification,
Quasi-unanimity, Consistency, Condorcet consistency, General consistency, Propor-
ꢀ
tion, 1-Optimality O1, 2-Optimality O2.
ꢀ
In general, for a conflict profile we can not always formulate a consensus. The
below definition shows criteria for O1 consensus susceptibility for a profile X.
Definition 1.19 (Consensus susceptibility). Let (U, d) is a half-metric distance, pro-
Q
file X ∈ (U) is susceptible to O1 iff:
dt_mean(X) ≥ dmin(X) .
(1.2)
ꢀ
1.3.4. Related works of resolving inconsistency knowledge in ontologies
integration using consensus-based methods
Extensibility , shareability of ontologies are reasons that promote realizing of visi-
ons of the Semantic Web.
Four levels of conflict in ontologies integration are: concept level, instance level,
relationship level and axiom level.
In concept level of conflict, related works consider only the list of attributes of
the concept and omit the conflict of domain of these attributes. Based on consensus-
based general model of integration, we will propose a method that resolving conflict
on concept level and consider both list of attributes and domain of them. The main
challenge of resolving conflict of attributes’ domain is we have to formula distance
functions for domains. Approaches to this will be details in the Chapter 3.
There is still no research that resolve conflict for axiom level in ontologies inte-
gration or ontology building in collaborate manner. By representing an axiom as a
literal, knowledge of a user can be represented as a conjunction of literals. In this way,
the problem of resolving conflict of axioms set in collaboratively ontologies building
can be seen as resolving conflict on syntactic level. The problem of resolving conflict
on axiom levels in ontologies integration has the same essence. Challenges for these
problems are: (1) Formulating distance function of two conjunctions of literals; and
(2) Analyzing relationship of postulates of consensus functions in the half-metric dis-
tance space, so that we can propose a method to formulate consensus for a conflict
profile. Chapter 4 will details this content.
1.4. Summary of Chapter 1
In this chapter we show overview of ontology and inconsistency in ontology. The
two problems have been set to solved are how to evaluate meaningful results of query
against inconsistent ontology and how to resolve conflict in ontologies integration. Ba-
sic notions and overview of approaches have been also introduced in this chapter.
8
Chapter 2
REASONING WITH INCONSISTENT ONTOLOGY
USING SELECTION FUNCTION BASED ON
SEMANTIC OF REFERENCED ONTOLOGY
Ontology can be seen as a set of axioms where each of axiom is formulated from
entities: concepts, roles, instances as rules of an ontology language. Subsume axioms
of an ontology formulate hierarchy of entities: concepts hierarchy, properties hierar-
chy. Due to similarity of concept and property in theirs hierarchies, we only analyze
semantic distance between two concepts in a concept hierarchy.
There have several methods to evaluate semantic distance of two concepts. In this
thesis we use the approach of Wu and Palmer to evaluate semantic distance between
the two name concepts in ontology: measure by number of edges between them in the
concept hierarchy.
2.1. Semantic distance between two concepts in ontology
Let O is an ontology, C is set of named concept in O. With c1, c2 ∈ C , we
O
O
denote:
• DP (c1) is set of named concepts in O that is direct parent concepts of c1.
O
• DC (c1) is set of named concepts in O that is direct child concepts of c1.
O
• LCP (c1, c2) is set of named concepts in O that is least common parent concept
O
of c1 và c2.
Definition 2.1 ([Minimum number of direct edges µ of two concepts in ontology). Let
O is an ontology. With two concepts c1, c2 ∈ C , we say k ∈ N is minimum number of
O
direct edges from c1 two c2 in the concept hierarchy of O, denoted as µO (c1, c2) = k,
is there exists d1, d2, . . . , dk is the shortest series of named concepts in O such that:
c1 ≡ d1, c2 ≡ dk, di ∈ DC (di+1) where ∀i = 1, 2, . . . , k − 1. We assume that:
O
• µ (c, c) = 0 where ∀c ∈ C .
O
O
• µO (c1, c2) = +∞ when c1 ≡ ⊥ or O |= c1 v c2 (there exists no path from c1 to
c2 in the concept hierarchy of O).
ꢀ
With an ontology O and its named concepts set C , we can calculate µ (c1, c2)
O
O
(c1, c2 ∈ C ) by applying algorithms such as Floyd, Ford-Bellman, . . . for graph that
O
be formulated by subsume relationship (@) of concepts in the ontology.
Definition 2.2 (Semantic distance δ of two concepts in ontology). Semantic distance
δ of the two name concepts c1, c2 in ontology O, denoted as δ (c1, c2), defined as:
O
n
o
µO (c1, c0) + µO (c2, c0)
δ (c1, c2) := min
O
| c0 ∈ LCP (c1, c2)
O
µO (c1, c0) + µO (c2, c0) + 2.µO (c0, >)
(2.1)
ꢀ
9
The function δ has disadvantage: it can not evaluate semantic distance between
concepts that > is super-concept. We can improve this by using the semantic distance
µ0 instead of µ:
Definition 2.3 (Minimum number of direct edges µ0 between two concepts in hier-
archy). Minimum number of direct edges µ0 between two concepts c1, c2 ∈ C in
O
hierarchy O,denoted as µ0 (c1, c2), is defined as:
O
(
µ (c1, c2)
if c2 = > ,
O
µ0O(c1, c2) =
(2.2)
µ (c1, c2) + 1 if c2 = >
O
Trong trường hợp ontology O đã xác định, chúng ta viết µ0 thay vì viết µO0 .
ꢀ
2.2. Semantic distance between concept expressions by references ontology
Let O is an ontology, CE1, CE2 are arbitrary concept expressions. We call se-
mantic distance between CE1 và CE2 while place them in the concept hierarchy O
is semantic distance between concept expressions by ontology O. The ontology O is
called as referenced ontology.
Definition 2.4 (Semantic distance between concept expression by referenced onto-
logy). Let O is an ontology, CE1, CE2 are concept expressions. Distance between
CE1 and CE2 by the referenced ontology O is defined as:
δ (CE1, CE2) =
O
n
o
µO (CE1, c0) + µO (CE2, c0)
µO (CE1, c0) + µO (CE2, c0) + 2.µO (c0, >)
min
| c0 ∈ LCP (CE1, CE2)
O
where:
• µO (CE1, CE2) is minimum number of direct edges between concept expressions
CE1, CE2 while placing them in the concept hierarchy of ontology O.
• c0 is the least common parent concept of CE1 and CE2.
ꢀ
(1) The set of the least common parent concept LCP (CE1, CE2) can be deter-
O
mined by the following cases:
(i) If CE1 v CE2 then LCP (CE1, CE2) = {CE2};
O
(ii) If CE1 w CE2 then LCP (CE1, CE2) = {CE1};
O
(iii) Otherwise, LCP (CE1, CE2) is determined by the definition as Section 2.1:
O
n
ꢀ
LCP (CE1, CE2) = c ∈ C | CE1 v c ∧ CE2 v c ∧ ∀c0 ∈ C : CE1 v
O
O
O
o
ꢁ
c0 ∧ CE2 v c0 ⇒ c v c0
.
(2) We can determine µ (CE1, CE2) by values of µ (c1, c2) where c1, c2 ∈ C by
O
O
O
dynamic strategy.
10
(i) There exists c1, c2 ∈ C where c1 ≡ CE1 and c2 ≡ CE2. This is the simplest
O
case and: µO (CE1, CE2) = µO (c1, c2) .
(ii) There exists c1 ∈ C where c1 ≡ CE1, and there exists no concept in O that is
O
equivalent to CE2. In this case:
µ (CE1, CE2) = µ (c1, CE2) = min{µ (c1, c) + 1 | c ∈ DC (CE2)} .
O
O
O
O
(iii) There exists c2 ∈ C where c2 ≡ CE2, and there exists no concept in O that is
O
equivalent to CE1. In this case:
µ (CE1, CE2) = µ (CE1, c2) = min{µ (c, c2) + 1 | c ∈ DP (CE1)} .
O
O
O
O
(iv) There exists no concepts in O that is equivalent to CE1 or CE2. In this case:
µ (CE1, CE2) := min{µ (c, c0) + 2 | c ∈ DP (CE1), c0 ∈ DC (CE2)} .
O
O
O
O
In short, we always determine minimum number of direct edges between two ar-
bitrary concept expressions when placing them in the concept hierarchy of ontology
based on values of µ (c1, c2) which can be pre-calculate ∀c1, c2 ∈ C .
O
O
2.3. Semantic distance between two axioms by referenced ontology
Definition 2.5 (Semantic distance between two sets of concept expressions by refe-
renced ontology). Let O is an ontology, A and B are nonempty set of concept expres-
sions. Semantic distance between the two set by a referenced ontology O, denoted as
d (A, B), is defined as:
O
X
δ (CEa, CEb)
O
CEa∈A,CEb∈B
d (A, B) :=
O
.
(2.3)
card(A).card(B)
We assume, d (A, B) = 1 if A = ∅ of B = ∅ .
ꢀ
O
Definition 2.6 (Semantic distance between two axioms by referenced ontology). Let
O is an ontology. Semantic distance between two axioms φ, ψ by referenced ontology
O, denoted as d (φ, ψ), is defined as:
O
ꢂ
ꢃ
d (φ, ψ) := d CE(φ), CE(ψ) ,
O
O
where, CE(φ), CE(ψ) is a set of concept expressions of the axiom φ, ψ.
ꢀ
2.4. Reasoning with inconsistent ontology using selection function based on seman-
tic distance
We formulate selection function basing on semantic distance to use in framework
of reasoning with inconsistent ontology which introduced in Section 1.2. The selection
function specify Definition 1.8 by using a referenced ontology for evaluating semantic
distance.
Definition 2.7 (Selection function based-on semantic distance by referenced onto-
logy). Let O is a referenced ontology; Σ is an inconsistent ontology in the ontology
11
language L. A selection function based-on semantic distance by referenced ontology O,
denoted as sOSem, is defined as:
2L × L × N → 2L
(Σ, φ, k) → sOSem(Σ, φ, k)
where sOSem(Σ, φ, k) is recurse defined as:
- sOSem(Σ, φ, 0) = ∅;
- sOSem(Σ, φ, k) = sSOem(Σ, φ, k − 1) ∪
n
o
ψ ∈ Σ | ¬∃ψ0 ∈ Σ : ψ0 ∈/ sSOem(Σ, φ, k − 1) ∧ d (ψ0, φ) < d (ψ, φ) , (k ≥ 1).
O
O
ꢀ
The selection function sOSem is monotonically increase. We can formulate a reasoner
|≈O using this selection function to extending the axiom set in the reasoning framework
of Section 1.2.
2.5. Benchmarks and analyzing results
We do benchmarks with the test set which contains 3 ontologies Madcow, MiniE-
conomy and Transportion coming from SEKT project (http://www.sekt-project.
com). Table 2.1 describes information of ontologies in the test set.
Table 2.1: Experiment ontologies
Number of
unsatisfiable concepts
Ontology
Number of concepts
Number of axioms
Madcow
54
1
174
MiniEconomy
Transporation
338
445
51
62
2 314
2 380
For each of experiment ontology Σ, let UΣ is the set of unsatisfiable concepts of Σ,
the query to do testing has form of Σ |≈ “C v D?00 where C ∈ UΣ and D ∈ CΣ \ UΣ.
Table 2.2 and Table 2.3 show results of the experiments for two reasoners |≈O and
|≈Syn when applying with ontologies in the test set.
Table 2.2: Comparison by number of determined results
Experiment results show that:
12
Table 2.3: Comparison by extension of axiom set
• The reasoner |≈O returns number of determined resuts much more than the re-
asoner |≈Syn. So that, |≈O allow to exploit an inconsistent ontology much more
efficient than |≈Syn
.
• Number of addition axioms in each of the reasoner |≈O is much lesser than |≈Syn
.
The experiment result is tally with the feature of the selection function sOSem that
has quantitative measure semantic distance of axioms for querying (contrast to
the selection function sSyn).
• Number of removing axioms in the ODP process of the reasoner |≈O is much
lesser than |≈Syn: lesser than 10 times in the test set. By this way, total cost for
the ODP process of |≈O is much lesser than |≈Syn
.
2.6. Summary of Chapter 2
In this chapter, we formulate an effectively dynamic approach to evaluate semantic
distance between two concept expression by a referenced ontology. We also classify
axioms in an ontology OWL 2, split expression of entities in these kinds of axioms in
order to evaluating semantic distance between two axioms by the referenced ontology.
Base on this semantic distance, we formulate the selection function and apply it to
the framework of reasoning with inconsistent ontology. Effectiveness ot the proposed
selection function compared to the syntactic-based selection function is clearly showed
in experiments at the end of chapter. Results of this chapter have published in Journal
of Science and Technology (Hue University of Sciences) [CT6].
13
Chapter 3
RESOLVING CONFLICT ON CONCEPT LEVEL
IN ONTOLOGIES INTEGRATION
3.1. Consensus theory-based model of integration knowledge
Definition 3.1 (Real world (A, V)). Let A is the set of attributes. Each of attribute
S
a ∈ A has a domain Va containing elementary values. With V = a∈A Va, we say
that, a real world can be represented by the pair (A, V).
ꢀ
S
S
T
With T ⊆ A, we denote VT =
Va, 2V
=
a∈T 2Va.
a∈T
Definition 3.2 (Complex tuple of type T). Complex tuples T are formulated by the
function r: T → 2V where r(a) ⊆ Va, ∀a ∈ T. In stead of writing r(a) we can
T
write ra and a tuple of type T can be written as rT. A tuple rT can also be written as:
rT = {(a, ra) | a ∈ T}. The set of all tuples of type T is denoted as TUPLE(T).
ꢀ
Definition 3.3 (Elementary tuple of type T). Elementary tuples of type T are for-
mulated by the function r: T → VT where r(a) ∈ Va, ∀a ∈ T. If Va = ∅ then
r(a) = ε, where, the symbol ε represents a special value, which is used when domain
of the attribute is empty. The set of all elementary tuple of type T is denoted as
E-TUPLE(T).
ꢀ
Definition 3.4 (Sum of two tuples). Sum of two tuple rT and r0T is a tuple r00
,
0
T00
where T00 = T ∪ T0 and
0
for a ∈ T ∩ T0
for a ∈ T \ T0
for a ∈ T0 \ T
ra ∪ r
ra
ra0
a
ra00 =
ꢀ
Definition 3.5 (Product of two tuples). Product of two tuples rT and r0T is a tuple
0
r00 where T00 = T ∩ T0 and r00 = ra ∩ r0 for each a ∈ T00.
ꢀ
T00
a
a
Definition 3.6 (Relationship ≺). Let r ∈ TUPLE(T) and r0 ∈ TUPLE(T0) where
T ⊆ T0. We say r is included in r0, denoted as r ≺ r0, if ra ⊆ ra0 for each a ∈ T.
ꢀ
The problem of knowledge integration is state as: For a conflict profile X = {ri ∈
TUPLE(Ti) | Ti ⊆ A where i = 1, 2, . . . , n}, we have to determine a tuple r∗ of type
T∗ ⊆ A such that r∗ is best represented for tuples. The consensus tuple r∗ is called as
the integration tuple for X.
The “best represented” tuple is understood as the consensus which satisfied as
much postulates as possible in the postulates of integration (Definition 3.7): Closure
of knowledge - 1 (T1), Closure of knowledge - 2 (T2), Consistency of knowledge (T3),
Superiority of knowledge - 1 (T4), Superiority of knowledge - 2 (T5) and Maximal
similarity (T6).
14
3.2. Levels of conflict in ontologies integration
There are four levels of conflict in ontologies integration: (1) In instance level: In-
stances that have the same name but are described differently in ontologies. (2) In
concept level: Concepts that have the same name but have different structures in
ontologies. (3) In relationship level: The relationship is described differently in ontolo-
gies.(4) In axiom level, the axiom sets are different in ontologies.
3.3. Resolving conflict of concept level in ontologies integration
Definition 3.14 (The problem of ontologies integration at concept level). Let O1, O2, . . . , On,
(n ∈ N) are ontologies in the real world - (A, V). We assume that concept c in ontology
ꢄ
Oi is (c, Ai, Vi), i = 1, 2, . . . , n. From the profile X = (Ai, Vi) | i = 1, 2, . . . , n ,
we have to determine (A∗, V∗) that best represent structure of c.
ꢀ
We propose algorithm 3.1 that determine the optimum structure for the concept.
ꢄ
Proposition 3.1. For any profile X = (Ai, Vi) | i = 1, 2, . . . , n , algorithm 3.1
has the following properties:
(a) The consensus that determined by the algorithm satisfies postulates T1, T2, T3, T4.
(b) If the rule R5 is not used in the algorithm, the consensus satisfies postulate T5.
(c) The consensus satisfies postulate T6.
Some remarks of algorithm 3.1:
• The algorithm determines structure of the concept c while resolving conflict in
both attribute list and their domains.
• We can choose to apply the rule R5 or not depend on the answer of question “do
we want to select all of attributes of the concept in ontologies?”:
− Answer “Yes” reflects the expectation of exploit ideas of all experts.
− Answer “No” reflects that we prefer the high agreement of knowledge agents.
• We can modify the Step 3 of the algorithm: If Xa is not O1consensus susceptible,
rather than removing attribute a from A∗, we select the domain Va∗ as sum
of domains in pairs (Ai, Vi). This modification helps getting more attribute
specifications for the integrating concept.
3.4. Problem of formulating distance function for domains of attributes
In order to apply algorithm 3.1, we have to formulate the distance function da
between domain of attribute a as Definition 1.15. There are two types of properties
in ontology: object property and datatype property: an object property links instances
together while a datatype property links instances to data values. In the full version
of the thesis we show details to formulate distance functions for types of domains of
the two types of properties in an OWL 2 ontology, such as concept expression và data
range expression.
15
Algorithm 3.1: Determine the consensus of concept’s structure
Input:
ꢄ
• Conflict profile X = (Ai, Vi) | i = 1, 2, . . . , n , where (Ai, Vi) is structure of concept c in
ontology Oi.
• Ua (a ∈ A) is the universe set, containing all possible values for Va (domain of attribute
a).
• da (a ∈ A) is a distance function between two values in Ua.
Output: The pair (A∗, V∗) best represents the structure of the concept c.
begin
S
n
Step 1
Step 2
A∗ := i=1 Ai;
foreach a, b ∈ A∗ do
if (a ↔ b or a ↓ b) then
Replace a by b;
A∗ := A∗ \ {a};
foreach a, b ∈ A∗ do
if (a → b) then
A∗ := A∗ \ {b};
Step 3
foreach a ∈ A∗ do
n
if (number of occurences of a in all pairs (Ai, Vi) is less than ) then
2
A∗ := A∗ \ {a};
else
3a
3b
Formulate profile Xa := {V1, V2, . . . , Vk} where Vj is domain of attribute a in
pair (Ai, Vi), j = 1, 2, . . . , k và i = 1, 2, . . . , n;
if (Xa is O1consensus susceptible) then
Select Va∗ as O1 consensus in half-metric space (Ua, da):
ꢄ
da(Va∗, Xa) = min da(Va, Xa) | Va ∈ Xa ;
Set Va∗ as domain of attribute a in A∗;
else
A∗ := A∗ \ {a};
Step 4
foreach a ∈ A∗ do
if (there exists a relationship a ↔ b or a → b or a ↓ b) then
A∗ := A∗ ∪ {b};
16
3.5. Summary of Chapter 3
In this chapter we have propose method to resolve conflict at concept level in the
ontologies integration using consensus theory - based model of knowledge integration.
The consensus which is determined by proposed method has been proved that satisfies
important postulates of integration tuple. Ihe chapter also shows methods to formu-
late distance functions for types of domain of properties in OWL 2’s ontology: object
property and datatype property.
Results of this chapter have published in International Conference on Computita-
tional Collective Intelligence - ICCCI (2014) [CT2], Journal of Computer Science and
Cybernetics (2014) [CT1] and Transactions of Computitational Collective Intelligence
(2016) [CT5].
Chapter 4
RESOLVING CONFLICT AT AXIOM LEVEL
IN ONTOLOGIES INTEGRATION
4.1. Model of resolving conflict at syntactic level
We assume that a knowledge agent or an expert uses a definitive set of symbols L
to represent positive logic values that reference to events and objects in a certain real
world. Each symbol represents a different element in the real world. A literal exists in
one of two form: either positive literal or negative literal.
An agent can give its opinion about the certain subject in the real world as a
conjunction of literals: t1 ∧ t2 ∧ · · · ∧ tk, where ti ∈ L or ti = ¬t0i, for ti00 ∈ L, i =
1, 2, . . . , k and ti = tj với i = j; i, j = 1, 2, . . . , k.
Let Conj(L) as a set of all conjunctions of literals in the set L. A conjunction x
is represented by a pair (x+, x−), where x+ (respectively, x−) contains symbols in the
conjunction that are positive literal (respectively, negative literal).
Definition 4.1. A conjunction (x+, x−) where x+, x− ⊆ L is called consistent if
x+ ∩ x− = ∅ .
ꢀ
+
−
Definition 4.2. Let x = (x+, x−), x0 = (x0 , x0 ) ∈ Conj(L) are consistent con-
junctions. We say:
−
+
(a) Conjunction x is inconsistent with x0 if x+ ∩ x0 = ∅ or x0 ∩ x− = ∅ ,
(b) Conjunction x is calle−d sharply inconsistent x0 if they are inconsistent and x+ ∩
+
x0 = ∅ và x− ∩ x0 = ∅ .
ꢀ
Definition 4.4. Distance between two set of symbols X1, X2 ⊆ L is defined as
a
a
card(X1 X2)
η(X1, X2) =
, where, X1 X2 represents different symmetric of X1
card(L)
and X2.
ꢀ
Definition 4.5. Distance between two conjunctions x1, x2 ∈ Conj(L) is defined as
d (x1, x2) = w1.η(x+, x+) + w2.η(x−, x−) where
∧
1
2
1
2
17
• η(x+1 , x+2 ) (respectively, η(x1−, x−2 )) is distance between sets of positive symbols
(respectively, negative symbols) in conjunctions x1, x2.
• w1, w2 is weights of distance η(x+, x+) and η(x−, x−) in d (x1, x2), where w1 +
∧
1
2
1
2
w2 = 1 và 0 < w1, w2 < 1 .
ꢀ
In the thesis, we consider role of positive knowledge and negative knowledge are
1
2
equal, i.e. w1 = w2 = . The function d satisfies properties of distance function which
∧
specified Definition 1.15 in the universe set Conj(L).
4.1.1. Problem of finding consensus for conjunctions and postulates for
consensus
The problem of finding consensus for conjunctions are stated as: “Let X := {xi =
(x+i , x−i ) ∈ Conj(L) : i = 1, 2, . . . , n} is a profile. We have to determine the con-
junction x∗ ∈ Conj(L) which best represents for conjunctions in X (called as consen-
sus of X)”.
Q
The “best representation” of X determined by consensus function C : (Conj(L)) →
2Conj(L). The function should satisfy one or more postulates which proposed in Defi-
nition 4.6.
Definition 4.6 (Cosensus function of conjunctions profile). A mapping
Y
C : (Conj(L)) → 2Conj(L)
.
is a consensus function of conjunction profile if it satisfies one or more postulates.
T
T
+
−
+
−
H1. Each conjunction (x∗ , x∗ ) ∈ C(X) should be
x+ ⊆ x∗ , and
x− ⊆ x∗ .
x∈X
x∈X
S
S
+
−
+
−
H2. Each conjunction (x∗ , x∗ ) ∈ C(X) should be x∗ ⊆
x+, and x∗ ⊆
x−.
x∈X
x∈X
S
H3. If X is consistent then ( x+,
x∈X
S
x−) should be a consensus of X.
x∈X
+
−
+
−
H4. For all (x∗ , x∗ ) ∈ C(X), we have x∗ ∩ x∗ = ∅.
H5. A consensus x∗ ∈ C(X) should be minimize total of distances:
ꢅ
ꢆ
P
P
d (x∗, x) = min
d (x0, x) | x0 ∈ Conj(L) .
∧
∧
x∈X
x∈X
H6. For each symbol z ∈ L and a consensus x∗ ∈ C(X), the form of apperance of z
in x∗ depends only on its forms of apperances in conjunctions belong to X.
+
−
+
−
In consensus (x∗ , x∗ ) ∈ C(X), the set x∗ (respectively, the set x∗ ) is called as
positive component (respectively, negative component) of consensus.
ꢀ
4.1.2. Analysis of postulates
Let Cco is a set of consensus function for profile of conjunctions. Relationship of
satisfiability of postulates are reflected in the following theorems.
18
Tải về để xem bản đầy đủ
26 trang
19620
Free
Bạn đang xem 20 trang mẫu của tài liệu "Tóm tắt Luận án Methods of processing inconsistent knowledge in ontologies", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- tom_tat_luan_an_methods_of_processing_inconsistent_knowledge.pdf
