We discuss two approaches for defeasible reasoning in Description Logics that allow for the statement of defeasible subsumptions of the form “ subsumed by usually holds”. These approaches are known as prototypical reasoning and presumptive reasoning and are both rooted in the notion of Rational Closure developed by Lehmann and Magidor for the propositional case. Here we recast their definitions in a defeasible DL context and define algorithms for prototypical and presumptive reasoning in defeasible DL knowledge bases. In particular, we present a plug-in for the Prote´ge´ ontology editor which implements these algorithms for OWL ontologies. The plug-in is called RaMP and allows the modeller to indicate defeasible information in OWL ontologies and check entailment of defeasible subsumptions from defeasible knowledge bases.
Entailment in standard DL reasoning systems is monotonic. Monotonicity is a property of knowledge representation (KR) systems that are built upon classical logics. It specifies that knowledge is always ‘incremental’. That is, adding to (or strengthening) the information in a Knowledge Base (KB) cannot result in any previously known conclusions being retracted from the KB. In classical logics, monotonic behaviour is exhibited on two levels. Firstly, on the meta-level where if a statement ' follows logically from a KB K then ' also follows from any superset of K and, secondly, on the object level from v it follows that u v for any .
It turns out that there are applications in which monotonicity is undesirable, i.e., non-monotonic reasoning is required. A typical scenario is when one needs to model exceptions in a domain. Let us consider an example. We select a domain which describes power plants (specifically nuclear power plants) and their safety under certain conditions. The following concept and role names will be used: PP (power plants), NPP (nuclear power plants), BrNPP (Brazilian nuclear power plants), SeismicArea (tracts of land prone to seismic activity), DangerousPP (power plants which are unsafe due to some conditions) and isLocIn (a property of an entity indicating where it is located geographically). We specify a simple example using the vocabulary described above. Consider the following DL knowledge base
K =
From K we conclude classically that a Brazilian nuclear power plant is not a dangerous power plant (BrNPP v :DangerousPP). This conclusion displays typical monotonic reasoning behaviour. That is, enforcing that all Brazilian nuclear power plants are nuclear power plants (BrNPP v NPP) and that all nuclear power plants are not dangerous power plants (NPP v :DangerousPP), it is also implicitly enforced that all Brazilian nuclear power plants are not dangerous power plants. tu
From an ontology modeller’s perspective, the type of reasoning behaviour exhibited in the example may not be suitable always. This is because the modeller may want to be able to cater for exceptions. We may not want to enforce that all nuclear power plants are safe. Rather, we may want to represent something less rigid. For example, one may want to express that in the most normal cases nuclear power plants are not dangerous but that there may be some exceptional cases in which they are dangerous (defeasible information). The broad approach to reasoning with KBs that contain defeasible information is known as defeasible reasoning and is a popular way to introduce non-monotonic reasoning behaviour into knowledge representation systems.
Returning to the example above, we argue that one needs to develop a defeasible reasoning approach to capture intuitions like: In general, nuclear power plants are not dangerous but a specific type of nuclear power plant (e.g., a Brazilian nuclear power plant located in a seismic area) may be dangerous. It would be useful to have a robust system in the DL setting that is capable of implementing this kind of reasoning.
The goal of this paper is to present and demonstrate a preliminary version of the software defeasible reasoning system that we have developed to be used with OWL ontologies. This system, known as RaMP, has been packaged as a plug-in for the popular Prote´ge´ ontology editor. The plug-in is discussed in more detail in Section 4. 2
There are various approaches for introducing non-monotonic reasoning capabilities in
logic-based knowledge representation systems. Among these, the approach by Kraus,
Lehmann and Magidor (often called the KLM approach) [
Lehmann et al. characterize the notion of rational closure [9, Section 5] and
motivate this notion to be a suitable answer to the above question. The name given to the
reasoning approach that computes rational closure for conditional KBs is
prototypical reasoning. Lehmann and colleagues also discuss similar forms of reasoning that
may be suitable for computing inferences from conditional KBs. One such type of
reasoning is known as presumptive reasoning [
Our approach to defeasible reasoning is based on the work by Britz et al. [
Prototypical and presumptive reasoning are answers to the important question: given
a KB that contains defeasible subsumption statements like @ , what does it mean
for one to draw inferences from this KB and how do we compute these inferences?
Lehmann et al. have provided answers by developing the notions of prototypical and
presumptive reasoning (albeit in a propositional context) and also specifying
algorithms to compute these. It turns out that these notions are adaptable to the DL
setting [
Prototypical reasoning corresponds exactly to the propositional notion of rational
closure, lifted to the DL case. Due to space constraints, we are not concerned with the
semantics here. Interested readers may consult the work of Lehmann and colleagues [
The algorithm for prototypical reasoning, takes as input a subsumption statement (also called a query) which may be defeasible or classical and a defeasible KB. The output of the algorithm is true if the query ' follows (prototypically) from the given KB K (denoted K j=P rot '). Queries and defeasible KBs are currently restricted to subsumption statements for simplicity seeing that (in most cases) classical ALC TBox axioms can be rewritten as classical ALC subsumption statements.
The algorithm begins by performing a classical transformation of the input KB. Essentially this amounts to rewriting all defeasible statements in the KB as their classical counterparts and all classical statements into a specific normal form. The reason behind this transformation is two-fold: (i) It allows classical reasoning techniques to be used on the transformed KB and (ii) The normal form of the classical statements differentiates them (in the eyes of the algorithm) from the defeasible statements in the KB. As we shall see later, this last point also makes the next sub-procedure of the algorithm possible (the computation of a ranking of the statements in the KB). The transformation procedure is given below: Definition 1 (transformKB). Given a defeasible KB K: transf ormKB(K) := ftransf orm(')j' 2 Kg, where transf orm(') := uv: ; ivf ?';=if '@= v Example 1. Let K be the input of the procedure in Definition 1:
K = ><>8 BBrrNNPPPP vv 99ihsaLsoFcaIunl:tB;rBarzNil;PNPPvP @NP:P9;hasFault; >>=9 >> NPP u 9isLocIn:SeismicArea @ DangerousPP; > : 9hasFault @ DangerousPP; DangerousPP @ 9isLocIn:SeismicArea ;> If we execute the procedure in Definition 1 for K we get K0: 8>>< BBrrNNPPPP uu ::99ihsaLsoFcaIunl:tBvraz?il;vBr?N;PNPPuP:vN:P9PhvasF?a;ult; 9>>= >> NPP u 9isLocIn:SeismicArea v DangerousPP; > : 9hasFault v DangerousPP; DangerousPP v 9isLocIn:SeismicArea ;> tu
The second procedure of the prototypical algorithm is the computation of a
ranking of sentences in the KB according to the notion of exceptionality [
Note that a ranking can in practice be implemented as a collection where each element of this collection is a set of sentences from the KB. Each sentence in a particular set has the same magnitude of importance (we also call this a rank). In the prototypical reasoning algorithm, the ranking of a defeasible KB is computed according to the notion of exceptionality. Intuitively, a concept is said to be exceptional w.r.t. a defeasible KB K, if it is the case that > v : usually follows from K. That is, typically everything is in : , thereby making an exception to this rule. In the context of our algorithm, checking whether is exceptional w.r.t K can be reduced to checking if K0 classically entails v ? where K0 is the classical transformation of K. Definition 3 (Exceptionality). Let K be a defeasible KB and , concepts. Then: - is exceptional w.r.t. K iff K0 j= v ?. Where K0 is the transformation of K. - @ is exceptional w.r.t. K iff is exceptional w.r.t. K. - v is exceptional w.r.t. K iff u : is exceptional w.r.t. K. - K0 K, is exceptional w.r.t. K iff every element of K0 and only the elements of K0 are exceptional w.r.t. K (we say that K0 is more exceptional than K).
The above notion of exceptionality is included in the computation of the ranking for a defeasible KB as sub-procedure exceptional(E ) := f v 2 E j E j= v ?g.
Now that we have detailed the sub-procedures and principles needed to describe the computation of a ranking of the sentences in a defeasible KB, we specify the complete procedure for implementing this:
Procedure computeRanking(K)
Input: Defeasible knowledge base K
Output: The ranking, D, for K 1 i := 0; K0 := transformKB(K); E0 := K0; E1 := exceptional(E0); 2 while Ei+1 6= Ei do 3 i := i + 1; Ei+1 := exceptional(Ei); 4 n := i; D1 := En; D := fD1g; 5 for j := 1 to n do 6 Dj := Ej 1nEj ; D := D [ fDj g;
Recall that the ranking of the KB is computed as a collection of sets of sentences (D in Procedure computeRanking). Each element in any of such sets shares the same level of importance in the algorithm.
Example 2. Consider the transformed KB from Example 1: ><>8 BBrrNNPPPP uu ::99ihsaLsoFcaIunl:tBvraz?il;vBr?N;PNPPuP:vN:P9PhvasF?a;ult; =>>9 >> NPP u 9isLocIn:SeismicArea v DangerousPP; > : 9hasFault v DangerousPP; DangerousPP v 9isLocIn:SeismicArea ;> K0 (second statement on Line 1 of the computeRanking procedure) is calculated as in Example 1. Lines 2 to 3 of the computeRanking procedure are responsible for computing the different levels of exceptional sentences according to Definition 3. This segment of the procedure executes Procedure exceptional until Ei+1 = Ei (a fixed point is reached). In the example when Line 1 of computeRanking is executed E0 := K0 and E1 := exceptional(E0). If we do the computation as detailed in exceptional then we find: E1 = fBrNPP u :9hasFault v ?; BrNPP u :NPP v ?; BrNPP u :9isLocIn:Brazil v ?g.
We see that E1 6= E0 therefore we have to execute the while loop again to find E2. The result of this computation shows us that E2 = E1 and we have thus reached a fixed point. The while loop terminates and the final ranking D can be computed as specified by Lines 4 to 6 of the procedure. The final ranking D is composed of:
8 NPP v :9hasFault; 9hasFault v DangerousPP; 9 < =
tu
We now have a ranking for our original defeasible KB K (see Example 1). Once this ranking is identified, then given a query, the core prototypical reasoning algorithm (see Algorithm 1) can be executed to determine if this query follows from the original defeasible KB. D1 represents the infinite rank which contains the classical (nondefeasible) statements from the KB.
Algorithm 1: P rototypical reasoning
Input: The ranking D for some KB, K and a query ' of the form @ (or
Output: true if K j=P rot @ (or K j=P rot v ), false otherwise 1 n := 1; 2 if ' = v then 3 return D1 j= v ; v ) 4 else if ' = @ then 5 while S D j= v ? and D 6= ; do 6 D := DnfDng;n := n + 1; 7 return S D j=
v ;
We give an example to illustrate the prototypical reasoning algorithm below: Example 3. Consider the following defeasible KB K with six axioms: K = 8 BrNPP v NPP; NPP v PP; 9isLocIn v PP; 9 < =
Considering higher indices to represent more exceptional sentences, the ranking for this KB (computed using relevant procedures discussed) is the following:
If we compute prototypical reasoning (via Algorithm 1) for the following query ' = BrNPP @ DangerousPP then we get the positive result K j=P rot '. We find the following motivation for this: the condition on Line 5 of the algorithm holds because BrNPP v ? follows from D (D1 [ D1 [ D2) and D 6= ;. Therefore we execute the loop body and D becomes D1 [ D1. The loop condition no longer holds because S D 6j= BrNPP v ? and therefore the loop terminates.
Last, the classical entailment check (S D j= BrNPP v DangerousPP) on Line 7 is performed. This returns true in our example and therefore K j=P rot '.
An intuitive reading of this result shows us that typically nuclear power plants are not dangerous power plants (NPP @ :DangerousPP). If we examine the query ' we see that we are not in a typical situation because we have a specific type of nuclear power plant, i.e., A Brazilian nuclear power plant. Additionally, we know that typical Brazilian nuclear power plants are located in seismic areas stated by (BrNPP @ 9isLocIn:SeismicArea) and typical power plants located in seismic areas are dangerous (9isLocIn v PP, 9isLocIn:SeismicArea v DangerousPP). Given this information, prototypical reasoning allows for the possibility that this type of nuclear power plant is dangerous, which represents an exception to the general rule that
tu
Next we introduce an alternative defeasible reasoning algorithm to the prototypical approach just described. This approach is known as presumptive reasoning. 3.2
The presumptive reasoning algorithm is a venturous extension of the prototypical one.
Essentially the difference between them (from an algorithmic perspective) is that
presumptive reasoning computes an extended version of the ranking that prototypical
reasoning does. Presumptive reasoning has a semantics for the propositional case [
We let D be a prototypical ranking for some defeasible KB K. Each element Di 2 D (which we refer to as a rank) is a set of sentences from K. To convert D to a presumptive ranking D0 we add jDij 1 ranks above each Di in D.
Example 4. Let Di = f'1; '2; '3g be a rank in some prototypical ranking D: We recall that in order to extend D to a presumptive ranking we need to add jDij 1 ranks above each Di in D. For our example, let us consider that we have a prototypical ranking containing just one rank Di as defined above. We thus need to add two ranks above Di in D. To understand what these two ‘presumptive’ ranks will look like we have to explain how a prototypical ranking is used in the prototypical algorithm.
Recall that Lines 5-6 of Algorithm 1 essentially finds a maximal subset of the axioms in D in which the antecedent of the query is satisfiable. However, the prototypical algorithm does this in a ‘clunky’ way by removing entire ranks at a time (Line 6). Presumptive reasoning is more thorough in finding a maximal subset of the axioms in D because it first tries removing (all permutations of) one axiom from the highest rank, instead of the entire rank. If this does not make the antecedent satisfiable then it tries removing (all permutations of) two axioms from the same rank etc. until eventually (all permutations of) jDij 1 axioms are removed. We now show an elegant way to perform this fine-grained removal.
We start with the initial rank Di = f'1; '2; '3g. We want to only remove Di from D as a last resort but before that we want to try removing all permutations of one axiom and then two. Instead of doing this in a na¨ıve way by computing all these permutations, we use the fact that removing one axiom is the same as keeping two in a set of three axioms as in the example. In other words we would like to compute all instances of two axioms holding simultaneously in our Di. That is ('1and'2)or('1and'3)or('2and'3) in our example.
It turns out that there is a way to transform this ‘check’ or expression into a single axiom according to the following rules for DL axioms: and( i v i)in=1 = > v uin=1(: i t i) and, or( i v i)in=1 = uin=1 i v tin=1 i, where i v i = 'i.
If removing all permutations of one axiom (keeping two) does not make the antecedent satisfiable in our example then we try removing all permutations of two (keeping one). Therefore for our example the expression to check to verify this is '1or'2or'3. Therefore the presumptive conversion D0i for the prototypical rank Di is f(('1and'2)or('1and'3)or('2and'3)); ('1or'2or'3); f'1; '2; '3gg. This process is repeated on each Di in a prototypical ranking and the final presumptive ranking D0 is computed as S D0i. tu
It is important to note that other than the difference in the computation of the ranking, the prototypical and presumptive reasoning algorithms are identical. Therefore Algorithm 1 can be executed with a presumptive ranking as input to compute presumptive reasoning for a given defeasible KB and query. We have developed a Prote´ge´ plug-in that implements both prototypical and presumptive reasoning for DLbased (and therefore OWL) ontologies. We present this plug-in in the next section.
We have developed a plug-in for Prote´ge´ which allows the ontology modeller to represent defeasible information in the ontology without explicitly extending the underlying ontology language (OWL). This is possible through axiom annotations in Prote´ge´ which do not affect the logical meaning of the ontology. Furthermore, this plug-in implements the prototypical and presumptive reasoning algorithms. The plug-in is called RaMP1 which stands for Rational Monotonicity Plug-in. Figure 1 depicts the control panel of RaMP’s interface in Prote´ge´ 4.1.
This component of the RaMP interface is called the reasoning controller panel. This panel provides a text input field for the user to enter an axiom (defeasible or hard). The axiom can be verified to follow (or not follow) from the ontology, based on the currently selected reasoning algorithm. This task is accomplished by clicking the “check” button in the same panel. The reasoning algorithm can be selected from a drop-down menu. Currently, only prototypical and presumptive reasoning algorithms are available. There is also a checkbox for indicating if the axiom entered is defeasible or classical. If the axiom is classical, we also refer to it as a hard axiom. For convenience, RaMP provides a window display (Figure 2) in Prote´ge´ to show the user which axioms in the loaded ontology are indicated as defeasible axioms.
This brings us to the topic of how to assert that an axiom is defeasible in the loaded ontology. RaMP indicates axioms as defeasible in the ontology through a “flagging” process. In the Class Description window in Prote´ge´, the superclasses and equivalent classes of the selected class are indicated. Next to each of these classes there is a button, labelled “d” for defeasibility, which can be clicked to toggle whether that axiom should be viewed as defeasible or not by RaMP. When an axiom is indicated as defeasible the button turns pink and an axiom annotation is added to the ontology which stores this information (see Figure 3). 1 http://code.google.com/p/nomor/
The reasoning algorithms implemented by RaMP work in a similar way. They compute a ranking (ordering) of the axioms in the ontology and use this ranking to determine which axioms are more important than others in the ontology. The details of these algorithms will are provided in Sections 3.1 and 3.2 respectively. An example ranking is depicted below in Figure 4. The axioms appearing on the light pink background are defeasible axioms while the others are hard.
As an added feature of RaMP, we have also included a rudimentary facility for the user to fine-tune the computed ranking for the ontology. Adjacent to the defeasible toggle switch in Prote´ge´, there is a button labelled “r” to prompt the user to enter a numerical value representing the rank of the selected axiom. The specific numerical value chosen does not matter. What matters is the relative ordering between these values. If axiom ' has rank 1 and it is necessary for axiom '0 to have a higher rank then it does not matter whether axiom ' has rank 2 or 200 as long as the rank of '0 is greater than 2 or 200 respectively. The axiom ranking feature is depicted in Figure 5.
Fig. 5: RaMP: Axiom ranking feature
We have presented a description of a Prote´ge´ plug-in which implements a preliminary
version of non-monotonic reasoning for DL-based ontologies. The plug-in provides a
mechanism for indicating defeasible information in the ontology as well as an
implementation of two defeasible reasoning algorithms adapted from the work of Lehmann
and colleagues [
The financial assistance of the National Research Foundation (NRF) towards this research is hereby acknowledged. Opinions expressed and conclusions arrived at, are those of the author and are not necessarily to be attributed to the NRF. The work of Ivan Varzinczak was also supported by the National Research Foundation under Grant number 81225.