=Paper=
{{Paper
|id=Vol-2052/paper7
|storemode=property
|title=A Study of Kernel Contraction in EL
|pdfUrl=https://ceur-ws.org/Vol-2052/paper7.pdf
|volume=Vol-2052
|authors=Amr Dawood,James Delgrande,Zhiwei Liao
|dblpUrl=https://dblp.org/rec/conf/commonsense/DawoodDL17
}}
==A Study of Kernel Contraction in EL==
https://ceur-ws.org/Vol-2052/paper7.pdf
A Study of Kernel Contraction in EL
Amr Dawood and James Delgrande and Zhiwei Liao
Simon Fraser University
Burnaby, B.C., Canada
{jim,amr dawood}@cs.sfu.ca
Abstract complexities. EL is one of the simplest DLs, yet is expres-
sive enough to have found significant application. Conse-
An intelligent agent must be able to change its beliefs in a ra-
tional manner and with a plausible outcome. While the cen-
quently it is of interest to consider change within an EL
tral belief change theories have well-developed formal char- knowledge base. A further point of interest in addressing
acterisations, there has been limited work on applying these change within a DL is that, because of the constructs for
theories in a practical setting. In this paper we examine be- structuring knowledge, heuristics can be introduced to se-
lief base contraction, specifically kernel contraction, in the lect the most “reasonable”, or perhaps commonsense, con-
framework of the description logic EL. This is potentially traction from among a set of candidate contractions.
interesting first, because EL is used in large-scale knowledge A key feature of EL is that an EL knowledge base (KB)
bases and second, because the EL constructs for structuring can be translated in polynomial time into a normal form of
knowledge allow the specification of heuristics to choose an
“small” independent assertions. Then contracting a formula
intuitive, commonsense result for the contraction. We intro-
duce algorithms that perform belief contraction based on hit- φ from a KB can be most easily accomplished by, first de-
ting sets, and examine different ways of finding a suitable termining all minimal sets of assertions (called kernels) that
hitting set. Heuristics based on localization and specificity imply φ and then removing an element of each kernel from
are introduced. As well, our main contraction operators are the KB. This means of contraction is called kernel contrac-
shown to conform to Hansson’s postulates for smooth base tion, and was first studied by Hansson (1994).
contraction. The problem of determining kernels has been previously
addressed (as described in the next section), so in this paper
Introduction we focus on the second part, determining which formulas
to remove from each kernel. We look at some basic im-
An agent interacting with some domain will be required to
plementations as well as more advanced ones. Our focus
modify its beliefs, perhaps as a result of receiving additional
is on investigating the algorithmic aspects of these different
information about the domain, or perhaps in correcting an
approaches. Algorithmic time complexity is taken into con-
inaccurate belief. The dominant approach to belief change
sideration as well as the overall suitability of the solutions
with respect to a static domain1 is the AGM approach. Two
found. “Suitability” can be measured in different ways, in-
primary belief change operators are considered, belief revi-
cluding optimality, but also in terms of what makes more
sion in which the agent must consistently (when possible)
sense as a “reasonable” solution.
incorporate a new belief into its belief corpus, and belief
contraction, in which an agent ceased to believes a given We begin by examining simplistic algorithms for remov-
formula. ing formulas from a kernel, and move on to examining things
In this paper we focus on belief contraction: It is seen from the point of view of the hitting set problem, where
as the more basic operation; it is applicable even when the the hitting set problem is simply the problem of finding the
underlying system lacks a notion of inconsistency; and as smallest set of elements that intersect with a given set of sets
covered in the Background section, revision may be defined of elements. However, approaches that only consider the
in terms of it. size of the solution do not always make a meaningful choice
Our goal is to address belief contraction in a Description on which beliefs to remove. A contributions of this study is
Logic called EL. A Description Logic (DL) is one of a the subsequent investigation of algorithms that perform ker-
family of formalisms that are used to represent knowledge. nel contraction based on the structure of a EL knowledge
Knowledge is structured, in that concepts are used to rep- base. These approaches exploit the structure of EL knowl-
resent classes of individuals and roles are used to represent edge bases to find most reasonable solutions. A first ap-
relationships between concepts. Different DLs have differ- proach is to select beliefs that are somehow related to each
ent expressive powers and different reasoners with different other, rather than selecting the beliefs that are not. This idea
motivates the heuristic that we call localization. A second
1 heuristic we introduce is specificity, which is based on the
The alternative, in which the domain may have changed, is
belief update, which we do not consider here. idea that removing beliefs about more specific matters is
more reasonable than removing beliefs about more general (more details can be found in (Peppas 2008) and (Gärdenfors
ones. So we can then use these heuristics as a tie-breaker 1988)):
step when we get more than one solution.
The next section covers background material, including (K-1) K − φ is a belief set.
the prominent approaches to belief change, and a brief intro- (K-2) K − φ ⊆ K.
duction to description logic, focusing on EL. The following
section covers basic approaches to belief contraction in EL (K-3) If φ ∈
/ K, then K − φ = K.
while the next section discusses commonsense heuristics, (K-4) If not ` φ, then φ ∈
/ K − φ.
specifically dealing with localization and specificity. Fur-
ther details and full descriptions of algorithms may be found (K-5) If φ ∈ K, then K ⊆ (K − φ) + φ.
in (Dawood 2017). (K-6) If ` φ ↔ ψ, then K − φ = K − ψ.
(K-7) K − φ ∩ K − ψ ⊆ K − φ ∧ ψ.
Background
In this section, we provide some background on the main (K-8) If φ ∈
/ K − (φ ∧ ψ), then K − (φ ∧ ψ) ⊆ K − φ.
building blocks of our work. We discuss belief change The fifth postulate, the so-called recovery postulate, is con-
first with respect to the AGM framework (Alchourrón, troversial; it asserts that following a contraction, all beliefs
Gärdenfors, and Makinson 1985) and second according to are recoverable by an expansion by the formula for contrac-
Hansson (1999). Following this, Description Logics (DLs) tion.
are briefly introduced, focusing on the DL EL. In (Alchourrón, Gärdenfors, and Makinson 1985;
Gärdenfors 1988), various constructions, including partial
Belief Change meet and epistemic entrenchment are developed, and shown
AGM Belief Change The AGM framework (Alchourrón, to exactly capture the set of functions that conform to the
Gärdenfors, and Makinson 1985), named after its founders, contraction postulates; we omit details, as they are not di-
is the most prominent framework for belief change. Belief rectly pertinent here.
change is described on an abstract level, independent of how Both revision and contraction are formulated to follow a
beliefs are represented and manipulated. Belief states are principle of informational economy. In the case of contrac-
modeled by sets of sentences, called belief sets, closed un- tion, this informally means not giving up a formula if there
der the logical consequence operator of a logic that includes is no need to do so. Compared to revision, contraction is
classical propositional logic in a language L. Thus a belief usually seen as a more basic change function, since a belief
set K satisfies the constraint: set can only decrease. However, revision can be regarded
If K logically entails φ then φ ∈ K. as a combination of contraction and expansion, via the Levi
Identity:
Three types of belief change are identified: expansion, K ∗ φ = (K − ¬φ) + φ.
revision, and contraction. For expansion, a new belief is
simply added to a belief set and the deductive closure taken. Belief Bases The AGM approach presents belief change
That is, for belief set K and formula φ, the expansion of K at a high level, independent of how a belief is represented,
by φ is defined by and where the agent’s beliefs are described by a deductively-
. closed belief set. Hansson (1999) presents an approach to
K + φ = Cn(K ∪ {φ}) belief change where the agent’s beliefs are represented by an
where Cn(·) is the deductive closure of its argument. Ex- arbitrary set of formulas, called a belief base. The intuition
pansion can be reasonably applied when new information is is that a belief base may be “closer” to how an agent’s beliefs
consistent with a belief set; it is also useful in specifying the may be represented in a finite computer.
postulates for revision and contraction, and in their relation. Two constructions for a belief base contraction B − φ are
Revision represents the situation in which new informa- described:
tion may be inconsistent with the reasoner’s beliefs, and 1. Remainders: Compute all maximal subsets of B that do
needs to be incorporated in a consistent manner where possi- not entail φ. The contraction is defined as the intersection
ble. Consequently, if a new formula is inconsistent with re- of some “select” set of these subsets.
spect to an agent’s beliefs, some beliefs have to be dropped
before the formula can be consistently incorporated. 2. Kernels: Compute all minimal subsets of B that entail φ.
Contraction represents the situation in which the reasoner Remove (in some fashion) an element of each such set to
loses information. Informally, the contraction of a belief set obtain a belief base that does not entail φ.
by a formula is another belief set in which that formula is not Here, we consider kernel contraction on belief bases. The
believed. We denote the belief set resulting from contracting function in a kernel contraction that removes an element of
the belief set K with respect to sentence φ by K − φ. Since each subset is called an incision function.
contraction is the subject of this study, we discuss the ratio- For example, consider the following set where we wish to
nality criteria (or postulates) of such change. In the AGM remove the element b:
framework, the following eight postulates are introduced as
a basis for ensuring the rationality of contraction functions {a, a → b, b, c}
It is not enough to simply remove b from the set; if we do so, See (Hansson 1999) for details.
we get: {a, a → b, c} which still implies b. In this example, Although the AGM framework is very popular, we find
there are two kernels, {b} and {a, a → b}. An incision the postulates introduced by Hansson more suitable to be
function must remove {b} and one of a, a → b. The two applied to kernel contraction. First, in our approach we work
possible resulting belief bases after contraction are: with a normalized form of an EL knowledge base, which is
{a, c} and {a → b, c} to say, a belief base of formulas. Second, as we show at the
end of this section, contraction of EL belief bases do not
In the following, B will refer to an arbitrary belief base. satisfy the recovery postulate of the AGM framework.
We refer to the set of φ-kernels of B by B ⊥ φ.
Definition 1 (Kernel Set (Hansson 1999)) For a belief base Description Logic
B and a formula φ, B ⊥ φ is a set such that X ∈ B ⊥ φ if A Description Logic (DL) is one of a class of logics based on
and only if: describing sets of individuals using concepts and describing
the relationships between them using roles. Two types of
1. X ⊆ B,
knowledge are represented: Intensional knowledge is gen-
2. X ` φ, and eral knowledge about a problem or a domain, while exten-
3. if Y ⊂ X then Y 0 φ. sional knowledge is knowledge about a specific problem in-
B ⊥ φ is a kernel set that contains all φ-kernels of B. stance. For this purpose, a knowledge base3 is composed of
two corresponding components: A TBox containing the in-
Kernels are the smallest subsets of the knowledge base that tensional knowledge and an ABox containing the extensional
imply a specific belief. Therefore, in order to give up that knowledge.
belief, every one of those kernels needs to be incised. If The ABox gives assertions, much like in a relational
the kernels are not minimal, they might contain a belief that database, such as Female(Sally) and FatherOf(Adam, Sally).
does not contribute to the implication of the belief to be con- Since our focus is on contraction in TBoxes, we don’t con-
tracted. For example, in {p, q}, q is a belief that does not sider the ABox further. A TBox is composed of a set of
contribute to make the set imply p. In this case, removing q .
assertions, made up of equivalences such as Man = Human
only would not help in giving up p. u Male (the individuals satisfying Man are exactly those sat-
An incision function is defined in as follows: isfying Human and Male) and subsumptions such as Man v
Definition 2 (Incision function (Hansson 1999)) An inci- Human (every individual that is a Man is a Human). The
sion function σ is a function such that for all beliefs φ: latter are referred to as General Concept Inclusions (GCIs).
S Every equivalence can be trivially broken down into two
1. σ(B ⊥ φ) ⊆ (B ⊥ φ) GCIs.
2. If ∅ =
6 X ∈ B ⊥ φ, then X ∩ σ(B ⊥ φ) 6= ∅ There are many members of the DL family; they vary
Contraction is carried out by removing the beliefs that are widely in expressivity power and the complexity of their
selected by the incision function from the original knowl- reasoning algorithms. In the following section we discuss
edge base. Contraction using the incision function σ 2 can be a well-known member of the DL family, EL, which we will
defined as: use the representation language for the rest of this study.
Definition 3 (Hansson 1999) (Contraction) The EL Description Logic EL is a description logic that
has recently attracted much attention. It is a “light-weight”
B − φ = B r σ(B ⊥ φ) DL, in that it is limited expressively, although it is used in
Hansson provides the following postulates that are shown well-known ontologies such as SNOMED CT (Spackman
to exactly capture belief base contraction based on incision 2000), a large-scale commercial medical ontology with well
functions: over 300000 concepts (Baader 2011). EL contains the fol-
lowing concept constructors:
(B-1) If 6` φ then B − φ 6` φ (Success)
• Conjunction (u):
(B-2) B − φ ⊆ B (Inclusion)
If C1 and C2 are concepts, then C1 u C2 is a concept
(B-3) If ψ ∈ B and ψ 6∈ B − φ then there is a set B 0 ⊆ B standing for the conjunction of C1 , C2 .
such that B 0 6` φ but B 0 ∪ ψ ` φ (Core retainment)
• Existential restriction (∃):
(B-4) If for every B 0 ⊆ B we have B 0 ` φ iff B 0 ` ψ, then If C is a concept and R is a role, then ∃R.C is the concept
B − φ = B − ψ. (Uniformity) of those individuals that are R-related to an item belong-
As well, Hansson provides the following postulate which, ing to concept C.
along with the preceding, characterises smooth kernel con- • The top concept >, true of all individuals.
traction:
Assertions express either equivalences between concepts
(B-5) B ∩ Cn(B − φ) ⊆ B − φ. (Relative closure) or a subsumption relation. The following are example asser-
2
tions in EL.
Technically the contraction function − should be parame-
3
terised by σ. For simplicity and because no confusion arises, we By knowledge base we refer to a belief base – a set of sentences
omit it. that represent the beliefs of an agent.
.
1. Woman = Human u Female. depends on defining an alternative semantics, called type se-
A Woman is exactly a Human and a Female. mantics, that skirts the problem that a knowledge base with
. a finite signature may have an infinite number of models.
2. Mother = Female u∃ParentOf.Human.
A (human) Mother is a Female and a ParentOf of an indi- Kernel Contraction
vidual that is a Human.
For the kernel contraction of a formula φ from a belief base
EL is simple and easy to use; as well it has a polynomial- B there are three steps:
time subsumption algorithm, where the subsumption algo- 1. Determine the kernels K of B with respect to φ.
rithm determines whether a specific subsumption relation
holds or not in a given knowledge base. 2. Determine a set of incised formulas I from K.
The subsumption algorithm is made up of four steps: 3. Set B ← B \ I.
1. Normalize the TBox. The third step is trivial. As well, the first step has been ad-
dressed, in the pinpointing algorithm introduced in (Baader,
2. Translate the normalized TBox into a graph. Peñaloza, and Suntisrivaraporn 2007).
3. Complete the graph using completion rules. The pinpointing algorithm computes all kernels using a
4. Read off the subsumption relationships from the normal- modified version of the EL subsumption algorithm. It finds
ized graph. a monotone Boolean formula called a pinpointing formula;
the propositions of the pinpointing formula are GCIs of the
We are most interested in the first step, normalization. It TBox, and a propositional valuation represents the kernels.
is shown (Baader et al. 2007) that any EL TBox can be trans- The approach may take exponential time (w.r.t the size of
lated in polynomial time into a set of GCIs of the following the TBox) to find all kernels, because there may be expo-
form: nentially many kernels. However, (Baader, Peñaloza, and
• AvB Suntisrivaraporn 2007) also gives a polynomial-time algo-
rithm that computes a single kernel.
• A1 u A2 v B
Example 1 ((Baader, Peñaloza, and Suntisrivaraporn
• A v ∃r.B 2007)) Let the TBox, T , be:
• ∃r.A v B ax1 : A v ∃r.A, ax2 : A v Y ,
A, A1 , A2 , and B are concept names, and r is a role name. A ax3 : ∃r.Y v B, ax4 : Y v B.
normalized TBox can be thought of as a knowledge base that We have that T |= A v B. Let φ = A v B. We obtain:
has been translated into a canonical form, where each GCI T ⊥ (A v B) = {{ax2 , ax4 }, {ax1 , ax2 , ax3 }}
represents an individual item of information. For our con-
Since we can use the pinpointing algorithm to get the set
traction functions, we will work with a normalized TBox.
of all kernels, we just need to consider the issue of removing
Such TBoxes can be thought of as corresponding to a (non-
an element from each kernel to perform a contraction. This
closed) equivalent of a belief set.
is the role of the incision function. We next look at some
basic incision functions to set the stage for later considera-
Related work
tions.
There has been some related work regarding contraction in
light-weight description logics. In (Booth, Meyer, and Varz- Incision Functions
inczak 2009a) a contraction operator is introduced that con- We are given an EL TBox, T , and a formula for contraction
tracts EL belief sets (rather than belief bases) using remain- φ. We assume without loss of generality that T has been
ders. A representation result is given relating the first six normalized; this has the important consequence that for ψ ∈
contraction postulates, adapted to EL, to the construction of T that T \ {ψ} 6|= ψ.
infra-remainder sets (Booth, Meyer, and Varzinczak 2009b). The main contraction algorithm is shown in Algorithm 1;
Zhuang and Pagnucco (2009) also address belief con- as discussed, the only issue is specifying the incision func-
traction in EL. They point out that the recovery postulate tion CUT.
doesn’t hold in EL. Informally the problem, as in other
inferentially-weak approaches (see e.g. (Delgrande 2008) Algorithm 1 Contraction algorithm
regarding Horn clause theories), is that EL doesn’t support
1: procedure CONTRACT(T , A)
negation or disjunction. For a problematic example, con-
2: kernelset = PINPOINT(T , A)
sider where the TBox contains just the closure of A v B
3: giveUpSet = CUT(kernelset)
and one wishes to contract by A u C v B; in the contrac-
4: T = T / giveUpSet
tion, A v B must be removed, but it is not “recovered” if
5: end procedure
one expands the result by A u C v B. The authors pro-
pose a suitable alternative to the recovery postulate based on
the notion of logical difference, and develop algorithms that We next consider simple ways of implementing CUT. Due
implement this approach. to space considerations, here and elsewhere we omit the
A model-based approach to contraction of DL-Lite belief pseudocode; see (Dawood 2017; Liao 2014). We first con-
bases is introduced in (Zhuang et al. 2016). The approach sider non-optimal solutions, followed by optimal solutions.
Basic Incision Functions The first incision function is is a hitting set. In the context of kernel contraction in EL,
overly simplistic, but serves to provide a base case. In this we can define the minimal hitting set contraction as:
case, one simply removes a formula from each kernel. The Definition 5 (Minimal hitting set contraction) Given a ker-
time complexity is O(m), where m is the number of ker- nel set K = {k1 , k2 , ..., kn } of n kernels, a minimal hitting
nels (size of the kernelset), assuming that a formula selec- set giveUpSet is a set such that:
tion takes constant time. However, this is clearly a poor al-
gorithm. For example, given a kernel set {{a, c}, {b, c}}, ∀ki ∈K [ki ∩ giveU pSet 6= ∅] ∧
one might remove a from the first set followed by c from the @giveU pSet0 ⊂giveU pSet [∀ki ∈K (ki ∩ giveU pSet0 6= ∅)]
second set. Then the result of giveU pSet = {a, c} is {b},
which unnecessarily removes a. Removing a is unnecessary Since kernels are subsets of the TBox, and our goal to find
because removing c alone is enough for contraction. More a giveU pSet that hits all kernels, we can use approaches to
generally, removing more beliefs than needed is undesired, the minimal hitting set problem to solve it. The computation
as it violates the informational economy principle. of all such hitting sets is known to be NP-hard (Garey and
The second incision function improves on the previous by Johnson 1979); there are however known very good approxi-
selecting a formula from every kernel, as before. However mation algorithms, such as the one introduced in (Abreu and
each time a formula is selected, every kernel that contains van Gemund 2009), for the minimal hitting set problem, that
that formula is excluded from consideration in the following are feasible in terms of running time.
iterations. This algorithm has a worst-case time complex- The following result shows that we obtain a well-behaved
ity of O(m2 ): There are basically two loops, first scanning contraction function:
through the kernels, and second, once a formula has been Theorem 1 Let T be a normalized TBox, φ a (normalized)
selected, scanning the remaining kernels to see whether they set of GCIs, and with kernel set K and set giveU pSet de-
contain that formula.4 termined as in Definition 5. Then for − defined by: T − φ =
The third function implements a greedy approach: At T \ giveU pSet, we have that T − φ satisfies the postulates
each step, the algorithm finds the formula that appears in for smooth kernel contraction (B-1)-(B-5).
the most kernels and removes it; these kernels are not con-
sidered in the following steps. An sketch of the implemen- Heuristics for Contraction
tation in (Dawood 2017) is given as follows. First, for every In the last section, we discussed contraction algorithms
formula in a kernel, the number of kernels in which that for- where the goal was to remove the least number of beliefs.
mula occurs is determined. Then the formula that has the Here we consider heuristics based on the EL language and
greatest number of occurrences is added to the set of incised subsumption hierarchy. The idea is to bring in commonsense
formulas; the kernels containing that formula are removed principles that may be expected to yield intuitive or “reason-
from consideration; the count of formula occurrences in ker- able” results for a contraction. With localization we choose
nels is updated and the process continued. If the number of a hitting set that in some fashion affects a minimal region of
formulas in kernels is n, the number of kernels is m, and the the TBox; with specificity we prefer hitting sets that refer to
size of the largest kernel is k, then the time complexity is more specific concepts.
O(m2 · k · n). This however could be significantly enhanced
by using more clever data structures. Localization
Hitting Set Approach According to the principal of in- The idea here is that change should be as local as possible in
formation economy (Gärdenfors 1988), in every change to a knowledge base. Intuitively, this will involve a lesser over-
an agent’s beliefs, loss of information should be minimized. all change to a KB; as well, pragmatically, it would seem that
To satisfy the requirement of minimum change we require if a belief is incorrect, then it may be expected to arise from
an algorithm that removes the fewest GCIs while hitting all a specific part of the KB (much like in diagnosis where prag-
the kernels. This however is exactly the minimal hitting set matically one would prefer a diagnosis with fewer faults).
problem (Garey and Johnson 1979), which has already re- Consider following EL example:
ceived extensive study. (1) A v B, (2) B v D, (3) A v C, (4) C v D.
Consequently, another approach to cutting kernels in or- These imply that (5) A v D. We see that there are two
der to perform contraction is the minimal hitting set algo- (5)-kernels: {1, 2} and {3, 4}
rithm. The minimal hitting set problem is defined as follows So, to contract the knowledge base by (5), we need to re-
(Abreu and van Gemund 2009): move a belief from each kernel. However, removing (1) and
Definition 4 Given a set S = {s1 , s2 , ..., sn } of n non- (4) seems unreasonable because it means removing informa-
empty sets, a minimal hitting set d is a set such that: tion concerning all four concepts. Removing (1) and (3), on
the other hand, removes knowledge concerning only three
∀si ∈S [si ∩ d 6= ∅] ∧ @d0 ⊂d [∀si ∈S (si ∩ d0 6= ∅)] concepts: A, B, and C. Not only that, but pragmatically,
Thus, d is a minimal hitting set if and only if it contains at (1) and (3) together imply that perhaps our knowledge of
least one element from every set, and no proper subset of d A is wrong; conceivably our knowledge of B and C is not
necessarily false. Similar considerations apply to removing
4 (2) and (4), which together would suggest that the source of
This assumes that looking up a formula in a kernel takes con-
stant time, for example if kernels are stored as hash tables. incorrectness lies with D.
Localization is implemented in (Liao 2014) using a graph- However, we can say that A is more specific than B and B
based approach. The algorithm operates by defining a graph is more specific than C. Removing A v B, in this case, is
based on a set of GCIs, where an edge connects GCIs shar- more reasonable than removing C v D, because A v B in-
ing a concept or role. Then notions involving graph connec- volves concepts that are more specific than the ones involved
tivity and graph clustering can be used to determine local- in C v D. This also means that removing C v D results
ized change. in all individuals that are Cs no longer believed to be Ds,
while removing A v B only affects the subset of the Cs
Definition 6 (Connected GCIs) Given a set of GCIs K, de-
which are As.
fine an undirected graph G = (V, E) by: V is the set of
To begin, for a GCI A v B, we say that A is a child con-
GCIs in K and for g1 , g2 ∈ K, (g1 , g2 ) ∈ E just if g1 and g2
cept relative to B. Similarly, for A1 u A2 v B, we say that
share a concept or role name.
A1 and A2 are both child concepts relative to B. Moreover,
So, for a normalized TBox, given that the set of kernels we ignore the structure of a concept expression of the form
has been determined and a set of minimal hitting sets H = ∃R.C, which is to say, we treat a concept expression ∃R.C
{h1 , . . . , hn } has also been found, localization can be used as if it were a primitive concept name.
to select the preferred hitting set(s), based on the structure The approach assigns weights to every GCI, where a
of each hitting set: weight reflects its relative generality. Then we select the
1. For each hi ∈ H, determine the underlying graph (Defi- kernels with minimum overall weight. A GCI A v B gets
nition 6), and determine the number of connected compo- weight 0 if A has no children; and a GCI A v B gets weight
nents, ci , in the graph. i+1 if the maximum weight of the GCIs of form X v A is i.
Similarly, a GCI A1 u A2 v B gets weight i + 1 if the max-
2. Select a hitting set hi whose number of connected com- imum weight of the GCIs of form X v Aj for j ∈ {1, 2}
ponents, ci , is minimum. is i. For simplicity, we assume that the TBox is acyclic – so
In the previous example, we find, the following candidate we avoid the problems that will be caused by loops.
sets to contract (5): In more detail, let A and B be concept expressions ap-
{1, 3} and {2, 4}. pearing in a normalized TBox.
Thus contraction is given by one of these alternatives, and 1. If A has no children, assign A v B a weight of 0. If A1 ,
not the inferior possibilities {1, 4} or {2, 3}. A2 have no children, assign A1 u A2 v B a weight of 0.
For time complexity, each hitting set must be considered; 2. For GCI A v B (A1 u A2 v B), assign the GCI a weight
and for a hitting set the number of connected components of i + 1 if the maximum weight of GCIs of the form X v
determined. This latter problem can be solved via Tar- A (resp. X v Aj j ∈ {1, 2}) is i.
jan’s (1972) algorithm, which is O(|V | + |E|) for a graph
G = (V, E). Another pass through the hitting sets finds the Then, given that a set of hitting sets H = {h1 , . . . , hn }
minimum, for overall time complexity O(m · (|V | + |E|)). has been found, choose the preferred hitting set hi where the
Since all we are doing is selecting a particular hitting set, as sum of the weights of the GCIs in hi is a minimum.
given in Definition 5 the resulting contraction operator is a As a simple example, consider the previous example:
smooth kernel contraction, as given in Theorem 1. • A v B has weight = 0
Clearly this procedure can be enhanced or modified. • B v C has weight = 1
A more sophisticated notion of localization could be em-
ployed, for example, or the localization heuristic could be • C v D has weight = 2
applied just to the hitting sets of minimum cardinality (and In this case, the hitting set consisting of the GCI A v B is
so help serve as a tie-breaker). selected.
The time complexity of the underlying algorithm is poly-
Specificity nomial. Let m be the size of the normalized TBox T , and n
The assumption underlying this heuristic is that in choos- the number of hitting sets. Determining the depth labeling
ing which GCIs to remove, it is preferable to remove those of GCIs in T takes linear time, and determining the weights
involving more specific concepts over those involving less of the hitting sets is O(n·k) where k is the maximum size of
specific concepts: Arguably more general concepts are more a hitting set. Hence the overall complexity is O(m+(n·k)).
entrenched; as well, removing a more general concept sub- As with localization, the resulting operator is a smooth ker-
sumption may be expected to be more disruptive to the TBox nel contraction.
as a whole. Again, the basic approach to specificity can be enhanced
The subsumption hierarchy implicit in a normalized EL or modified. For example, one could just look at hitting
TBox categorizes concepts into different levels of generality. sets of minimum cardinality, and so the specificity heuristic
Consider the relations: would be a tie-breaker for equal-sized hitting sets. As well,
there are other ways of determining overall specificity of a
A v B, B v C, C v D . set of GCIs. One appealing candidate is to choose the hitting
Suppose we would like to contract the TBox by the implied set hi whose maximally-weighted GCI is a minimum. That
relation A v D. We have three options, corresponding to is: rank the hitting sets by the maximum weight assigned
removing one of the three given subsumptions. Removing to a contained GCI, and then choose the minimum ranked
any of the three GCIs would guarantee minimum change. hitting set in the resulting ranking.
Last, it might be objected that since there may be an expo- Baader, F.; Calvanese, D.; McGuiness, D.; Nardi, D.; and
nential number of hitting sets, any approach is bound to be Patel-Schneider, P., eds. 2007. The Description Logic Hand-
intractable in the worst case. This difficulty can be pragmati- book. Cambridge: Cambridge University Press, second edi-
cally addressed by employing an anytime algorithm for gen- tion.
erating an acceptable candidate: simply run through hitting Baader, F.; Peñaloza, R.; and Suntisrivaraporn, B. 2007.
sets, keeping track of the best candidate found so far, until Pinpointing in the description logic EL. In Proceedings
either a “good enough” candidate is found, a time bound is of the 2007 International Workshop on Description Log-
hit, or some other stopping criterion is met. ics (DL2007), volume 250 of CEUR-WS, 171–178. Brix-
en/Bressanone, Italy: Bozen-Bolzano University Press.
Conclusion Baader, F. 2011. What’s new in description logics.
In this paper we have studied belief contraction in the de- Informatik-Spektrum 34(5):434–442.
scription logic EL. The overall goal is to apply the formal Booth, R.; Meyer, T.; and Varzinczak, I. 2009a. First steps
theory of belief base change in a practical setting. To this in EL contraction. In Workshop on Automated Reasoning
end, kernel contraction seems to most appropriate approach about Context and Ontology Evolution (ARCOE-09), 16–18.
for contraction. We chose to work with EL first, because
it used in large-scale knowledge bases and second, because Booth, R.; Meyer, T.; and Varzinczak, I. 2009b. Next steps
the EL constructs for structuring knowledge allow the spec- in propositional Horn contraction. In Proceedings of the In-
ification of heuristics to choose intuitive, commonsense out- ternational Joint Conference on Artificial Intelligence, 702–
comes for a contraction. We first examined ways of find- 707.
ing (or approximating) hitting sets. We also proposed two Dawood, A. 2017. An algorithmic study of kernel contrac-
heuristics, based on localization and specificity, for deter- tion in EL. Master’s thesis, Simon Fraser University.
mining suitable hitting sets for contraction. Our main con- Delgrande, J. 2008. Horn clause belief change: Contraction
traction operators are shown to conform to Hansson’s postu- functions. In Brewka, G., and Lang, J., eds., Proceedings of
lates for smooth base contraction. All of our algorithms are the Eleventh International Conference on the Principles of
efficient, being polynomial in (one or both) of the size of the Knowledge Representation and Reasoning, 156–165. Syd-
TBox or the number of hitting sets. The bottleneck then lies ney, Australia: AAAI Press.
in the number of hitting sets, which may be exponential in Gärdenfors, P. 1988. Knowledge in Flux: Modelling the
the size of the TBox. Dynamics of Epistemic States. Cambridge, MA: The MIT
For future work there are two main ways to go. First, Press.
the present heuristics can be further explored, elaborated on,
and variants developed; as well, these approaches should be Garey, M., and Johnson, D. 1979. Computers and In-
implemented to determine what works best in practice. Sec- tractability: A Guide to the Theory of NP-Completeness.
ond, is to explore belief change in a more expressive de- New York: W.H. Freeman and Co.
scription logic. To this end, there are enhancements to EL Hansson, S. O. 1994. Kernel contraction. Journal of Sym-
that preserve the polynomial-time features, but also bring bolic Logic 59(3):845–859.
in a notion of consistency (by allowing the concept ⊥), for Hansson, S. O. 1999. A Textbook of Belief Dynamics. Ap-
which the present approach should apply without change. plied Logic Series. Kluwer Academic Publishers.
This would allow a definition of revision in EL, in terms Liao, Z. 2014. Kernel contraction in EL. Master’s thesis,
of the Levi Identity. As well, belief change in significantly School of Computing Science, Simon Fraser University.
more expressive DLs, such as in the ALC family, can also
be addressed. Peppas, P. 2008. Belief revision. In van Harmelen, F.;
Lifschitz, V.; and Porter, B., eds., Handbook of Knowledge
Acknowledgements Representation. Elsevier Science. 317–359.
We thank the three reviewers for their very helpful com- Spackman, K. 2000. Managing clinical terminology hierar-
ments. Financial support is gratefully acknowledged from chies using algorithmic calculation of subsumption: Experi-
the Natural Sciences and Engineering Research Council of ence with SNOMED-RT. J. of the Amer. Med. Inf. Assn.
Canada. Tarjan, R. E. 1972. Depth-first search and linear graph al-
gorithms. SIAM J. Comput. 1(2):146–160.
References Zhuang, Z., and Pagnucco, M. 2009. Belief contraction in
Abreu, R., and van Gemund, A. J. C. 2009. A low-cost ap- the description logic EL. In Proceedings of the 22nd In-
proximate minimal hitting set algorithm and its application ternational Workshop on Description Logics (DL2009), vol-
to model-based diagnosis. In Bulitko, V., and Beck, J. C., ume 477 of CEUR-WS.
eds., Eighth Symposium on Abstraction, Reformulation, and Zhuang, Z.; Wang, Z.; Wang, K.; and Qi, G. 2016. DL-Lite
Approximation (SARA 2009). AAAI Press. contraction and revision. Journal of Artificial Intelligence
Alchourrón, C.; Gärdenfors, P.; and Makinson, D. 1985. Research 56:328–378.
On the logic of theory change: Partial meet contraction and
revision functions. Journal of Symbolic Logic 50(2):510–
530.