An intelligent agent must be able to change its beliefs in a rational manner and with a plausible outcome. While the central belief change theories have well-developed formal characterisations, there has been limited work on applying these theories in a practical setting. In this paper we examine belief base contraction, specifically kernel contraction, in the framework of the description logic EL. This is potentially interesting first, because EL is used in large-scale knowledge bases and second, because the EL constructs for structuring knowledge allow the specification of heuristics to choose an intuitive, commonsense result for the contraction. We introduce algorithms that perform belief contraction based on hitting sets, and examine different ways of finding a suitable hitting set. Heuristics based on localization and specificity are introduced. As well, our main contraction operators are shown to conform to Hansson's postulates for smooth base contraction.
An agent interacting with some domain will be required to modify its beliefs, perhaps as a result of receiving additional information about the domain, or perhaps in correcting an inaccurate belief. The dominant approach to belief change with respect to a static domain1 is the AGM approach. Two primary belief change operators are considered, belief revision in which the agent must consistently (when possible) incorporate a new belief into its belief corpus, and belief contraction, in which an agent ceased to believes a given formula.
In this paper we focus on belief contraction: It is seen as the more basic operation; it is applicable even when the underlying system lacks a notion of inconsistency; and as covered in the Background section, revision may be defined in terms of it.
Our goal is to address belief contraction in a Description Logic called E L. A Description Logic (DL) is one of a family of formalisms that are used to represent knowledge. Knowledge is structured, in that concepts are used to represent classes of individuals and roles are used to represent relationships between concepts. Different DLs have different expressive powers and different reasoners with different 1The alternative, in which the domain may have changed, is belief update, which we do not consider here. complexities. E L is one of the simplest DLs, yet is expressive enough to have found significant application. Consequently it is of interest to consider change within an E L knowledge base. A further point of interest in addressing change within a DL is that, because of the constructs for structuring knowledge, heuristics can be introduced to select the most “reasonable”, or perhaps commonsense, contraction from among a set of candidate contractions.
A key feature of E L is that an E L knowledge base (KB)
can be translated in polynomial time into a normal form of
“small” independent assertions. Then contracting a formula
from a KB can be most easily accomplished by, first
determining all minimal sets of assertions (called kernels) that
imply and then removing an element of each kernel from
the KB. This means of contraction is called kernel
contraction, and was first studied by
The problem of determining kernels has been previously addressed (as described in the next section), so in this paper we focus on the second part, determining which formulas to remove from each kernel. We look at some basic implementations as well as more advanced ones. Our focus is on investigating the algorithmic aspects of these different approaches. Algorithmic time complexity is taken into consideration as well as the overall suitability of the solutions found. “Suitability” can be measured in different ways, including optimality, but also in terms of what makes more sense as a “reasonable” solution.
We begin by examining simplistic algorithms for removing formulas from a kernel, and move on to examining things from the point of view of the hitting set problem, where the hitting set problem is simply the problem of finding the smallest set of elements that intersect with a given set of sets of elements. However, approaches that only consider the size of the solution do not always make a meaningful choice on which beliefs to remove. A contributions of this study is the subsequent investigation of algorithms that perform kernel contraction based on the structure of a E L knowledge base. These approaches exploit the structure of E L knowledge bases to find most reasonable solutions. A first approach is to select beliefs that are somehow related to each other, rather than selecting the beliefs that are not. This idea motivates the heuristic that we call localization. A second heuristic we introduce is specificity, which is based on the idea that removing beliefs about more specific matters is more reasonable than removing beliefs about more general ones. So we can then use these heuristics as a tie-breaker step when we get more than one solution.
The next section covers background material, including
the prominent approaches to belief change, and a brief
introduction to description logic, focusing on E L. The following
section covers basic approaches to belief contraction in E L
while the next section discusses commonsense heuristics,
specifically dealing with localization and specificity.
Further details and full descriptions of algorithms may be found
in
In this section, we provide some background on the main
building blocks of our work. We discuss belief change
first with respect to the AGM framework
AGM Belief Change The AGM framework
2 K:
Three types of belief change are identified: expansion, revision, and contraction. For expansion, a new belief is simply added to a belief set and the deductive closure taken. That is, for belief set K and formula , the expansion of K by is defined by
K + : = Cn(K [ f g) where Cn( ) is the deductive closure of its argument. Expansion can be reasonably applied when new information is consistent with a belief set; it is also useful in specifying the postulates for revision and contraction, and in their relation.
Revision represents the situation in which new information may be inconsistent with the reasoner’s beliefs, and needs to be incorporated in a consistent manner where possible. Consequently, if a new formula is inconsistent with respect to an agent’s beliefs, some beliefs have to be dropped before the formula can be consistently incorporated.
Contraction represents the situation in which the reasoner
loses information. Informally, the contraction of a belief set
by a formula is another belief set in which that formula is not
believed. We denote the belief set resulting from contracting
the belief set K with respect to sentence by K . Since
contraction is the subject of this study, we discuss the
rationality criteria (or postulates) of such change. In the AGM
framework, the following eight postulates are introduced as
a basis for ensuring the rationality of contraction functions
(more details can be found in
The fifth postulate, the so-called recovery postulate, is controversial; it asserts that following a contraction, all beliefs are recoverable by an expansion by the formula for contraction.
In
Both revision and contraction are formulated to follow a principle of informational economy. In the case of contraction, this informally means not giving up a formula if there is no need to do so. Compared to revision, contraction is usually seen as a more basic change function, since a belief set can only decrease. However, revision can be regarded as a combination of contraction and expansion, via the Levi Identity:
K
= (K
: ) + :
Belief Bases The AGM approach presents belief change
at a high level, independent of how a belief is represented,
and where the agent’s beliefs are described by a
deductivelyclosed belief set.
Two constructions for a belief base contraction B are described: 1. Remainders: Compute all maximal subsets of B that do not entail . The contraction is defined as the intersection of some “select” set of these subsets. 2. Kernels: Compute all minimal subsets of B that entail .
Remove (in some fashion) an element of each such set to obtain a belief base that does not entail .
Here, we consider kernel contraction on belief bases. The function in a kernel contraction that removes an element of each subset is called an incision function.
For example, consider the following set where we wish to remove the element b: fa; a ! b; b; cg
It is not enough to simply remove b from the set; if we do so, we get: fa; a ! b; cg which still implies b. In this example, there are two kernels, fbg and fa; a ! bg. An incision function must remove fbg and one of a, a ! b. The two possible resulting belief bases after contraction are: fa; cg and fa ! b; cg
In the following, B will refer to an arbitrary belief base. We refer to the set of -kernels of B by B ? .
Definition 1 (Kernel Set
is a kernel set that contains all -kernels of B.
Kernels are the smallest subsets of the knowledge base that imply a specific belief. Therefore, in order to give up that belief, every one of those kernels needs to be incised. If the kernels are not minimal, they might contain a belief that does not contribute to the implication of the belief to be contracted. For example, in fp; qg, q is a belief that does not contribute to make the set imply p. In this case, removing q only would not help in giving up p.
An incision function is defined in as follows:
Definition 2 (Incision function
B = B r (B ? )
Hansson provides the following postulates that are shown to exactly capture belief base contraction based on incision functions: (B-1) If 6` (B-2) B then B
B (B-3) If 2 B and such that B0 6`
62 B but B0 [ (B-4) If for every B0
B = B .
6`
` B we have B0 `
(Success) (Inclusion) As well, Hansson provides the following postulate which, along with the preceding, characterises smooth kernel contraction: (B-5) B \ Cn(B )
B 2Technically the contraction function should be parameterised by . For simplicity and because no confusion arises, we omit it. then there is a set B0 B (Core retainment) iff B0 ` , then (Uniformity)
Although the AGM framework is very popular, we find the postulates introduced by Hansson more suitable to be applied to kernel contraction. First, in our approach we work with a normalized form of an E L knowledge base, which is to say, a belief base of formulas. Second, as we show at the end of this section, contraction of E L belief bases do not satisfy the recovery postulate of the AGM framework.
A Description Logic (DL) is one of a class of logics based on describing sets of individuals using concepts and describing the relationships between them using roles. Two types of knowledge are represented: Intensional knowledge is general knowledge about a problem or a domain, while extensional knowledge is knowledge about a specific problem instance. For this purpose, a knowledge base3 is composed of two corresponding components: A TBox containing the intensional knowledge and an ABox containing the extensional knowledge.
The ABox gives assertions, much like in a relational database, such as Female(Sally) and FatherOf(Adam, Sally). Since our focus is on contraction in TBoxes, we don’t consider the ABox further. A TBox is composed of: a set of assertions, made up of equivalences such as Man = Human u Male (the individuals satisfying Man are exactly those satisfying Human and Male) and subsumptions such as Man v Human (every individual that is a Man is a Human). The latter are referred to as General Concept Inclusions (GCIs). Every equivalence can be trivially broken down into two GCIs.
There are many members of the DL family; they vary
widely in expressivity power and the complexity of their
reasoning algorithms. In the following section we discuss
a well-known member of the DL family, E L, which we will
use the representation language for the rest of this study.
The E L Description Logic E L is a description logic that
has recently attracted much attention. It is a “light-weight”
DL, in that it is limited expressively, although it is used in
well-known ontologies such as SNOMED CT
Conjunction (u): If C1 and C2 are concepts, then C1 u C2 is a concept standing for the conjunction of C1; C2.
Existential restriction (9): If C is a concept and R is a role, then 9R:C is the concept of those individuals that are R-related to an item belonging to concept C.
The top concept >, true of all individuals.
Assertions express either equivalences between concepts or a subsumption relation. The following are example assertions in E L.
3By knowledge base we refer to a belief base – a set of sentences that represent the beliefs of an agent.
E L is simple and easy to use; as well it has a polynomialtime subsumption algorithm, where the subsumption algorithm determines whether a specific subsumption relation holds or not in a given knowledge base.
The subsumption algorithm is made up of four steps:
4. Read off the subsumption relationships from the normalized graph.
We are most interested in the first step, normalization. It
is shown
A v B A1 u A2 v B A v 9r:B 9r:A v B A, A1, A2, and B are concept names, and r is a role name. A normalized TBox can be thought of as a knowledge base that has been translated into a canonical form, where each GCI represents an individual item of information. For our contraction functions, we will work with a normalized TBox. Such TBoxes can be thought of as corresponding to a (nonclosed) equivalent of a belief set.
There has been some related work regarding contraction in
light-weight description logics. In
A model-based approach to contraction of DL-Lite belief
bases is introduced in
For the kernel contraction of a formula B there are three steps: 1. Determine the kernels K of B with respect to . 2. Determine a set of incised formulas I from K. 3. Set B B n I.
The third step is trivial. As well, the first step has been
addressed, in the pinpointing algorithm introduced in
The pinpointing algorithm computes all kernels using a
modified version of the E L subsumption algorithm. It finds
a monotone Boolean formula called a pinpointing formula;
the propositions of the pinpointing formula are GCIs of the
TBox, and a propositional valuation represents the kernels.
The approach may take exponential time (w.r.t the size of
the TBox) to find all kernels, because there may be
exponentially many kernels. However,
Example 1 (
= A v B. We obtain:
T ? (A v B) = ffax2; ax4g; fax1; ax2; ax3gg Since we can use the pinpointing algorithm to get the set of all kernels, we just need to consider the issue of removing an element from each kernel to perform a contraction. This is the role of the incision function. We next look at some basic incision functions to set the stage for later considerations.
We are given an E L TBox, T , and a formula for contraction . We assume without loss of generality that T has been normalized; this has the important consequence that for 2 T that T n f g 6j= .
The main contraction algorithm is shown in Algorithm 1; as discussed, the only issue is specifying the incision function CUT.
1: procedure CONTRACT(T , A) 2: kernelset = PINPOINT(T , A) 3: giveUpSet = CUT(kernelset) 4: T = T / giveUpSet
We next consider simple ways of implementing CUT. Due
to space considerations, here and elsewhere we omit the
pseudocode; see
The second incision function improves on the previous by selecting a formula from every kernel, as before. However each time a formula is selected, every kernel that contains that formula is excluded from consideration in the following iterations. This algorithm has a worst-case time complexity of O(m2): There are basically two loops, first scanning through the kernels, and second, once a formula has been selected, scanning the remaining kernels to see whether they contain that formula.4
The third function implements a greedy approach: At
each step, the algorithm finds the formula that appears in
the most kernels and removes it; these kernels are not
considered in the following steps. An sketch of the
implementation in
Hitting Set Approach According to the principal of
information economy
Consequently, another approach to cutting kernels in
order to perform contraction is the minimal hitting set
algorithm. The minimal hitting set problem is defined as follows
The following result shows that we obtain a well-behaved contraction function: Theorem 1 Let T be a normalized TBox, a (normalized) set of GCIs, and with kernel set K and set giveU pSet determined as in Definition 5. Then for defined by: T = T n giveU pSet, we have that T satisfies the postulates for smooth kernel contraction (B-1)-(B-5).
In the last section, we discussed contraction algorithms where the goal was to remove the least number of beliefs. Here we consider heuristics based on the E L language and subsumption hierarchy. The idea is to bring in commonsense principles that may be expected to yield intuitive or “reasonable” results for a contraction. With localization we choose a hitting set that in some fashion affects a minimal region of the TBox; with specificity we prefer hitting sets that refer to more specific concepts.
The idea here is that change should be as local as possible in a knowledge base. Intuitively, this will involve a lesser overall change to a KB; as well, pragmatically, it would seem that if a belief is incorrect, then it may be expected to arise from a specific part of the KB (much like in diagnosis where pragmatically one would prefer a diagnosis with fewer faults).
Consider following E L example:
(1) A v B; (2) B v D; (3) A v C; (4) C v D. These imply that (5) A v D. We see that there are two (5)-kernels: f1, 2g and f3, 4g
So, to contract the knowledge base by (5), we need to remove a belief from each kernel. However, removing (1) and (4) seems unreasonable because it means removing information concerning all four concepts. Removing (1) and (3), on the other hand, removes knowledge concerning only three concepts: A, B, and C. Not only that, but pragmatically, (1) and (3) together imply that perhaps our knowledge of A is wrong; conceivably our knowledge of B and C is not necessarily false. Similar considerations apply to removing (2) and (4), which together would suggest that the source of incorrectness lies with D.
Localization is implemented in
Definition 6 (Connected GCIs) Given a set of GCIs K, define an undirected graph G = (V; E) by: V is the set of GCIs in K and for g1, g2 2 K, (g1; g2) 2 E just if g1 and g2 share a concept or role name.
So, for a normalized TBox, given that the set of kernels has been determined and a set of minimal hitting sets H = fh1; : : : ; hng has also been found, localization can be used to select the preferred hitting set(s), based on the structure of each hitting set: 1. For each hi 2 H, determine the underlying graph (Definition 6), and determine the number of connected components, ci, in the graph. 2. Select a hitting set hi whose number of connected components, ci, is minimum.
In the previous example, we find, the following candidate sets to contract (5):
f1, 3g and f2, 4g.
Thus contraction is given by one of these alternatives, and not the inferior possibilities f1; 4g or f2; 3g.
For time complexity, each hitting set must be considered;
and for a hitting set the number of connected components
determined. This latter problem can be solved via
Clearly this procedure can be enhanced or modified. A more sophisticated notion of localization could be employed, for example, or the localization heuristic could be applied just to the hitting sets of minimum cardinality (and so help serve as a tie-breaker).
The assumption underlying this heuristic is that in choosing which GCIs to remove, it is preferable to remove those involving more specific concepts over those involving less specific concepts: Arguably more general concepts are more entrenched; as well, removing a more general concept subsumption may be expected to be more disruptive to the TBox as a whole.
The subsumption hierarchy implicit in a normalized E L TBox categorizes concepts into different levels of generality. Consider the relations:
A v B; B v C; C v D .
Suppose we would like to contract the TBox by the implied relation A v D. We have three options, corresponding to removing one of the three given subsumptions. Removing any of the three GCIs would guarantee minimum change. However, we can say that A is more specific than B and B is more specific than C. Removing A v B, in this case, is more reasonable than removing C v D, because A v B involves concepts that are more specific than the ones involved in C v D. This also means that removing C v D results in all individuals that are Cs no longer believed to be Ds, while removing A v B only affects the subset of the Cs which are As.
To begin, for a GCI A v B, we say that A is a child concept relative to B. Similarly, for A1 u A2 v B, we say that A1 and A2 are both child concepts relative to B. Moreover, we ignore the structure of a concept expression of the form 9R:C, which is to say, we treat a concept expression 9R:C as if it were a primitive concept name.
The approach assigns weights to every GCI, where a weight reflects its relative generality. Then we select the kernels with minimum overall weight. A GCI A v B gets weight 0 if A has no children; and a GCI A v B gets weight 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 maximum weight of the GCIs of form X v Aj for j 2 f1; 2g is i. For simplicity, we assume that the TBox is acyclic – so we avoid the problems that will be caused by loops.
In more detail, let A and B be concept expressions appearing in a normalized TBox. 1. If A has no children, assign A v B a weight of 0. If A1,
A2 have no children, assign A1 u A2 v B a weight of 0. 2. For GCI A v B (A1 u A2 v B), assign the GCI a weight of i + 1 if the maximum weight of GCIs of the form X v A (resp. X v Aj j 2 f1; 2g) is i.
Then, given that a set of hitting sets H = fh1; : : : ; hng has been found, choose the preferred hitting set hi where the sum of the weights of the GCIs in hi is a minimum.
As a simple example, consider the previous example: A v B has weight = 0 B v C has weight = 1
C v D has weight = 2 In this case, the hitting set consisting of the GCI A v B is selected.
The time complexity of the underlying algorithm is polynomial. Let m be the size of the normalized TBox T , and n the number of hitting sets. Determining the depth labeling of GCIs in T takes linear time, and determining the weights of the hitting sets is O(n k) where k is the maximum size of a hitting set. Hence the overall complexity is O(m + (n k)). As with localization, the resulting operator is a smooth kernel contraction.
Again, the basic approach to specificity can be enhanced or modified. For example, one could just look at hitting sets of minimum cardinality, and so the specificity heuristic would be a tie-breaker for equal-sized hitting sets. As well, there are other ways of determining overall specificity of a set of GCIs. One appealing candidate is to choose the hitting set hi whose maximally-weighted GCI is a minimum. That is: rank the hitting sets by the maximum weight assigned to a contained GCI, and then choose the minimum ranked hitting set in the resulting ranking.
Last, it might be objected that since there may be an exponential number of hitting sets, any approach is bound to be intractable in the worst case. This difficulty can be pragmatically addressed by employing an anytime algorithm for generating an acceptable candidate: simply run through hitting sets, keeping track of the best candidate found so far, until either a “good enough” candidate is found, a time bound is hit, or some other stopping criterion is met.
In this paper we have studied belief contraction in the description logic E L. The overall goal is to apply the formal theory of belief base change in a practical setting. To this end, kernel contraction seems to most appropriate approach for contraction. We chose to work with E L first, because it used in large-scale knowledge bases and second, because the E L constructs for structuring knowledge allow the specification of heuristics to choose intuitive, commonsense outcomes for a contraction. We first examined ways of finding (or approximating) hitting sets. We also proposed two heuristics, based on localization and specificity, for determining suitable hitting sets for contraction. Our main contraction operators are shown to conform to Hansson’s postulates for smooth base contraction. All of our algorithms are efficient, being polynomial in (one or both) of the size of the TBox or the number of hitting sets. The bottleneck then lies in the number of hitting sets, which may be exponential in the size of the TBox.
For future work there are two main ways to go. First, the present heuristics can be further explored, elaborated on, and variants developed; as well, these approaches should be implemented to determine what works best in practice. Second, is to explore belief change in a more expressive description logic. To this end, there are enhancements to E L that preserve the polynomial-time features, but also bring in a notion of consistency (by allowing the concept ?), for which the present approach should apply without change. This would allow a definition of revision in E L, in terms of the Levi Identity. As well, belief change in significantly more expressive DLs, such as in the ALC family, can also be addressed.
We thank the three reviewers for their very helpful comments. Financial support is gratefully acknowledged from the Natural Sciences and Engineering Research Council of Canada.