On Specificity in Default Logic

1 Introduction

Two kinds of weaknesses have been identified in non­ monotonic logics: insensitivity to specificity [Poole, 1985] and sensitivity to irrelevant premises [Geffner and Pearl, 1992] . Only the first kind of weakness is present in systems that are defined using some form of maxi­ mal consistency [Reiter, 1980; Moore, 1985; Poole, 1988] . In the well-known example, Tweety is a penguin, pen­ guins are birds, penguins usually cannot fly, birds usu­ ally can. Reiter's default logic does not say anything about the flying ability of Tweety. The rule concerning the flying ability of penguins is more specific than the rule about birds, and the rule about penguins should be used. Reiter and Criscuolo [1981] suggest that the appli­ cation of less specific defaults can be explicitly blocked by using semi-normal defaults. Others introduce pri­ orities [Lifschitz, 1985; Konolige, 1988; Brewka, 1989; Baader and Hollunder, 1993; Brewka, 1994; Rintanen, 1994]. Priorities are given as orderings of predicates, formulae, or default rules: in conflicting situations pref­ erence is given to items with a higher priority.

The second kind of weakness shows up in logics based on probability [Adams, 1975; Pearl, 1988] and in log­ ics that are defined directly by stating the properties a consequence relation should satisfy, for example the preferential logics of Kraus et al. [1990]. These logics give the correct answers in the standard examples about specificity, for instance concerning Tweety's flying abil­ ity. Their weakness is apparent when a set of premises is extended with an irrelevant premise: most of the use­ ful consequences are cancelled. For example, if Tweety is a black penguin, Tweety's inability to fly cannot be inferred.

In this paper, we investigate the applicability of lexi­ cographic priorities as a mechanism for resolving default conflicts according to specificity. Our approach is con­ servative: we do not propose any original notion of speci­ ficity. To date, the most successful area in defeasible rea­ soning - from the point of view of handling both sped~ ficity and irrelevant premises - is inheritance reasoning [Harty, 1994]. Therefore it seems desirable that solu­ tions to these problems in a more general setting would subsume some form of inheritance reasoning. Different inheritance theories propose different specificity notions. A weak but reasonable principle that is found for exam­ ple in the preferential logics of Kraus et al. and that is also respected by inheritance theories is the following: given a default that allows the conclusion of f3 from a, the premise a and no other premises, conclude /3. This principle is used in the definition of conditional entail­ ment [Geffner and Pearl, 1992] and we shall use it in de­ riving priorities froin specificity. We strengthen Reiter's default logic with a priority mechanism that uses lexico­ graphic comparison. Lexicographic comparison has been used in earlier work on explicit priorities, for example in [Lifschitz, 1985; Brewka, 1989; Geffner and Pearl, 1992; Ryan, 1992].

The outline of the paper is as follows . In Section 2 we present the specificity notion, and in Section 3 we ex­ tend default logic with a priority mechanism. In Section 4 we show how nonmonotonic reasoning that respects the specificity notion can be achieved in the extended default logic and how it subsumes an inheritance theory. In Sec­ tion 5 we discuss how the specificity principle is too weak for default theories in general, claim that priority mech­ anisms that lexicographically order extensions or models are in general too weak for achieving inheritance-like rea­ soning, and discuss the possibility of stronger priorities in more general but still restricted cases.

2 Specificity in default logic

Many formalizations of defeasible reasoning that address specificity [Kraus et al., 1990; Lehmann and Magidor, 1992; Adams, 1975; Pearl, 1988; 1990; Goldszmidt et al., 1990] employ or fulfill a principle not fulfilled by default logic. For default theories (D, B U C) with normal defaults D the principle can be expressed as follows.

Above D is the set of default rules of a default theory, B is a set of sentences that forms the background 1 , and f=., is a consequence relation. The consequence relation usually discussed in the context of default logic is cau­ tious reasoning ~ Fe </>, which means that the formula ¢is contained in all extensions of the default theory ~ ­ This consequence relation does not fulfill Condition 1.

Example 2.1 Consider the following set of defaults D .

The default theory ~ = (D, { P}) has two extensions. Both contain P and B, one contains ·F and the other contains F . Therefore~ ~e ·F. ·

In €-semantics [Pearl, 1988] a counterpart of Condition 1 is directly justified by the definition of conditional prob­ ability. Outside probabilistic systems, this condition has been used for example by Poole [1991]. A default can be viewed as expressing a rule that applies unconditionally in the context specified by the antecedent of the rule. In Example 2.1 above, if P is read as "x is a penguin", B as "x is a bird", and F as "x is able to fly". If B is all the information available, conclude that x flies . If P is all the information available, conclude that x does not fly.

Consequence relations for default logic that treat specificity properly should fulfill at least Condition 1. As shown above, Fe is not such a relation. A natural way to strengthen it is to consider only a subset of the extensions, those in which conflicts are resolved without violating specificity, and take their intersection. Such a subset can be selected for example by lexicographic comparison.

3 Priorities in default logic

Lexicographic priorities in the context of expressive non­ monotonic logics have been earlier investigated in [Rinta­ nen, 1994]. In that paper a definition of preferred stable expansions for autoepistemic logic was given. A similar definition can be devised for default logic. The signifi­ cance of defaults is represented by a strict partial order, that is, a transitive and asymmetric relation P. If de­ faults 8 and 8' are related as 8P8', then the application of 8 is more desirable than the application of 8'. The default 8 has higher priority.

Below, C denotes the language of the propositional logic, and V the set of all defaults 71 where {a, (3} ~ C.

1 This - possibly controversial - division between back­ ground B and evidence C (necessary and contingent facts) is made in all the afore-mentioned formalisms that address specificity. The background may affect the priorities, the ev­ idence may not .

Definition 3.1 (Application) A plied in E ~ C, if a 1\ (3 E E. default 71 is ap­ This is written as (~ ) app ~ ,E.

Definition 3.2 (Preferred extensions) Let ~ (D, W) be a default theory, and P a strict partial order on D . Let E be an extension of~- Then E is a P­ preferred extension if there is a strict total order T 2 P on D such that for all extensions E' of~' for all8 ED,

Definition 3.3 The fact that formula </> is contained in all P-preferred extensions of~ is written as ~ FP </>.

Example 3.1 For the default theory (D, 0) depicted in Figure 1 the following priorities are needed.

The default theory (D, { P}) has two extensions that re­ spectively apply { P~RR, ~} and { ~, 9.j!:-, R/}. Only the first one is P-preferred. The two extensions and all strict total orders T 2 P on the defaults are depicted below on the left (the default ~ is omitted because it is applied in both extensions). The most significant defaults are the lowest. Application is depicted as · and non-application as o.

If ( P~RR, ~s) were omitted in P, the strict total order R :S P:~R !:.:..9.. 9.:.!!: would extend P and consequently S ' ~R ' Q ' R ' there would be a P-preferred extension in which Pl were not applied. The diagram on the right depicts the unwanted total order.

·

4 Specificity-based priorities

Pre-computed explicit priorities are useful if the compu­ tation can be performed once and the priorities can be used in answering a wide variety queries concerning the knowledge base. Priorities for a default theory (D, BUC} depend only on the defaults D and the background B. As long as changes are made only to the contingent in­ formation C, no recomputation of priorities is needed.

Next we show how Condition 1 can be fulfilled in de­ fault logic with the lexicographic priority mechanism de­ fined in the preceding section.

Definition 4.1 Let (D, B) be a default theory and f a function from V x 2v x 2.c to 2v. Define P D..,J as follows.

If Do U · · · U Dn = D for non 2: 0, then we leave PD..,J undefined.

Given a function f, the above definition imposes an or­ dering on defaults. For a default 8, f(8,D,B) can be thought of as the set of defaults that may become ap­ plied if a default conflict is resolved so that Condition 1 or some stronger specificity notion is violated. To avoid this, 8 has to be given a higher priority than any of the defaults in f(8,D,B). Violation of Condition 1 is some­ times unavoidable, for example when D = { Al, A~1l }.

Next we give one such function f. The notation~ Fb ¢ means that ¢is in at least one extension of~.

Theorem 4.2 Let~= (D,B}. DefinefiU7/·,D,B) as

Then FP 6 , 11 fulfills Condition 1 for (D, B).

Proof: The relation P = P D..,ft is transitive and asym­ metric by construction. Let 7P be any default in D0 . Clearly (D, B U {a}} pp /3. Let 8 = 7P be any default in Di for some i E {1, ... , n }. Let T 2 P be any strict total order on D. Let E' be any extension of ~ that does not apply 7P (hence ·/3 E E'). By construction, there is an extension E of (D, B U {a, /3}} such that for all defaults 8' such that app(8',E'\E), 8P8'. Hence 8T8', and E' cannot be P-preferred. Therefore all P-preferred extensions contain /3. D

Gelfond and Przymusinska [1990] present theories of inheritance that are based on translating inheritance net­ works into sets of formulae in autoepistemic logic. In Section 4b of their paper, they give two formalizations of inheritance. It turns out that the one that explicitly orders extensions of an inheritance network is closely re­ lated to our definition of specificity-ba.Sed priorities and our priority mechanism 2 · Our result below provides a conceptual simplification of Gelfand's and Przymusin­ ska's work: reification of inheritance networks is avoided as links can be directly represented as default rules, and the ordering on extensions is justified by Condition 1. We restrict to inheritance networks with only defeasi­ ble links between classes. Strict links require stronger priorities or non-normal defaults a/ . .

Theorem 4.3 Assume that G is an inheritance network with only one object x, and that there are no strict links between classes. The translation of G into default logic is~ = (D, B U C), where

Let P D..,J 1 be the priorities for ~ as given in Definition 4.1. Then for any propositional variable P, P belongs to all P D..,ft -preferred extensions of~ if and only if H(x, P) belongs to all belief sets of Th{G).

Condition 1 imposes only a lower bound on the conse­ quence relation. Reasoning with lexicographic priorities is monotonic with respect to the priorities: the more pri­ orities there are, the more conclusions can be obtained. Consider the Nixon Diamond. No priorities on the de­ faults involved violate Condition 1. Some priorities pre­ fer "quakers are pacifists" to "republicans are not paci­ fists". There is no reason for this. It would seem that demanding that priorities are minimal would solve this problem. This is not the case.

If the second default is preferred to one or both of the last two, Condition 1 is satisfied. However, minimal such priorities give arbitrarily preference to one of the last two defaults. In conditional entailment [Geffner and Pearl, 1992], this problem is avoided by considering all (min­ imal) priorities. There is no obvious way to formalize this requirement about the fairness of priorities. Our priorities are not minimal and do not seem to be unfair because defaults are treated symmetrically in cases like the above.

2 0n page 412 in [Gelfond and Przymusinska, 1990], the relation better is defined. The results in the paper assume that this relation is asymmetric although it is not. Our results use a corrected definition.

5 Beyond inheritance networks

Example 3.1 demonstrates that it is not sufficient to pri­ oritize defaults the conclusions of which are contradic­ tory. To guarantee that a conflict is solved properly, it is necessary to give a lower priority also to those defaults that potentially become applied if a conflict is resolved in a wrong way. In inheritance networks, these defaults can be easily identified, as shown in Section 4. This is not the case with default theories in general. Next we give a variant of Example 3.1.

Example 5.1 Let D. = (D, 0) where

Priorities according to Definition 4.1 are {(P~RR, 9jf-)}, but (D, {P, A}) ~PLl..t 1 -.R. elusions with P t:.,h are too weak. Pt:. ,h The con- ·

This is a problem not recognized in earlier work on lex­ icographic priority mechanisms. To overcome it, it does not suffice to consider Condition 1 only. A more gen­ eral definition of specificity has to be devised. Such a definition should cover also cases where the contingent sentences are not just a prerequisite of one default. As hinted in Example 5.1, the contingent facts may in an intricate way affect the set of defaults that potentially become applied. As priorities are to be independent of the contingent facts, this creates new challenges for the definition of specificity based priorities, as illustrated in the following example.

Example 5.2 Consider the defaults D in Figure 2. We want (D,{A,C--+ P}) FP -.C. We also want (D, { P, R --+ A}) FP -.R. To fulfill these requirements, respectively the priorities A: ~c P P: ~R and P:~Rp A: ~c ~o ~R ~R ~c are needed. Hence no P fulfills these requirements. ·

Similar examples can be constructed for other systems of prioritized nonmonotonic reasoning that order exten­ sions or classical models by lexicographic or other form of comparison, for example [Geffner and Pearl, 1992; Brewka, 1989; Lifschitz, 1985; Ryan, 1992; Gardenfors and Makinson, 1994]. The presence of disjunctive for­ mulae in the sets of contingent facts is an obstacle to the possibility of inheritance-like reasoning in systems of default reasoning that use fixed priorities with lexico­ graphic comparison.

A natural line of research is to consider cases where the contingent facts may not contain the kind of prob­ lematic implicational formulae used in Example 5.2. A suitable restriction is to require that the consistent facts are propositional variables or their negations. With this restriction satisfactory defeasible reasoning with speci­ ficity can hopefully be achieved for a wide class of default theories.

6 Alternative definitions of prioritized reasoning

The priority mechanism introduced in Definition 3.2 is only one of several alternatives. That definition classifies defaults to those that are applied in an extension and to those that are not. Another reasonable classification is to defaults that are not defeated and to defaults that are defeated.

Definition 6.1 {Defeat) A default 7f is defeated in E ~ C, if a. 1\ -.(J E E.

For prerequisite-free defaults application and non-defeat coincide. The notions differ for a default 7f and an extension E when the prerequisite a. is not in E. Then 7f is neither defeated nor applied in E . Another choice - orthogonal to the choice between application and non­ defeat - is the way partiality in the priority partial orders is interpreted.

Definition 6.2 {Preferred2 extensions) Let D. (D, W) be a default theory, and P a strict partial or­ der on D. Let E be an extension of D.. Then E is a P-preferred2 extension if for all extensions E' of D., there is a strict total order T 2 P on D such that for all 8 ED,

Each P-preferred extension is P-preferred2 but not vice versa. The generalization of lexicographic comparison to partially ordered positions as given in the definition of preferred has been earlier used by Brewka [1989]. The generalization used in preferrefh has been earlier used for example by Geffner and Pearl [1992] and Ryan [1992]. The last two do not explicitly reduce lexicographic com­ parison with partially ordered positions to lexicographic comparison with totally ordered positions. Brewka per­ forms lexicographic comparison implicitly in a procedure for computing preferred sets of formulae.

There are no obvious differences in the expressivity of the priority mechanisms suggested by the above defini­ tions and the one given in Section 3. A theorem corre­ sponding to Theorem 4.3 for a priority mechanism that uses defeat instead of application requires stronger pri­ orities than those obtained merely on the basis of Con­ dition 1. The reason for this is that in inheritance net­ works, the number of defaults that are potentially de­ feated in the intended extensions but not in the unin­ tended extensions, may be increased by extending the set of contingent facts with propositional atoms.

7 Related work

Pearl's system Z is an improvement over p-entailment [Adams, 1975] and preferential logics of Kraus, Lehmann and Magidor [1990] because it handles irrelevant premises satisfactorily. System Z imposes an ordering on defaults (the Z-ordering), and models of the defaults are ordered according to the highest defeated default. This introduces a new kind of weakness: if a member of some class is in some respect exceptional, it is allowed to be exceptional in other respects as well. Conditional entail­ ment of Geffner and Pearl [1992] remedies this problem: comparison by highest defeated default is replaced by lexicographic comparison that considers significant also violations to defaults below the highest defeated one. Instead of the Z-ordering, all strict partial orders that - together with lexicographic comparison- satisfy a coun­ terpart of Condition 1, are used. Within our framework, conditional entailment can be defined as follows.

Definition 7.1 Let De be a set of defaults a => (3 and B ~ £ a set of formulae. Let D = { T~:-;/la => (3 E De}. Then ((De,B),C) conditionally entails -y, if-y is in all P-preferred2 extensions of (D, B U C) for all P such that (D,B U {a}) f=p (3 for all a=> (3 E De.

Delgrande and Schaub [1994] and Brewka [1994] present methods for computing priorities for Reiter's default logic. Both identify minimal sets of conflicting defaults, Delgrande and Schaub directly using the Z-ordering of Pearl, and Brewka using a closely related idea that takes into account the fact that default rules are unidirec­ tional. Delgrande and Schaub do not use priorities ex­ plicitly, but translate sets of defaults and the priority in­ formation to sets of semi-normal defaults rules. Brewka [1994] uses the priorities within his prioritized default logic that is based on a variant of Reiter's semiconstruc­ tive definition of extension. Similar priority mechanisms have been independently investigated elsewhere [Marek and Truszczynski, 1993; Baader and Hollunder, 1993]. Neither Delgrande and Schaub nor Brewka verify their systems against any correctness criteria or otherwise ex­ plicate the specificity notion they use. Both systems seem to fulfill Condition 1.

Default logic with specificity as defined in this paper differs in some aspects from most of the inheritance the­ ories. The priorities are fixed, that is, they are the same for all extensions and all sets C of contingent informa­ tion. Theories of inheritance have priorities implicitly hidden in the definition of preemption. There are exam­ ples where fixed priorities necessarily seem to produce too strong conclusions [Horty, 1994].

8 Conclusions

We have extended Reiter's default logic with a lexi­ cographic priority mechanism and presented a method for computing priorities according to specificity. The method produces priorities that are sufficiently strong for inheritance networks. Relaxing two restrictions made in inheritance networks - only propositional atoms as prerequisites and factual knowledge that is not disjunc­ tive - reveals the priorities insufficient. It seems that non-atomic prerequisites can be handled with a lexico­ graphic priority mechanism for a large class default the­ ories, but disjunctive contingent facts cannot.

Our research is closely related to Geffner's and Pearl'E work on conditional entailment [Geffner and Pearl, 1992]. Conditional entailment does not support inheritance rea­ soning. Delgrande [1994] extends conditional entailment towards inheritance reasoning. Our results are likely to have implications on research on that topic.

The computation of priorities from specificity is rather complex and tightly intertwined with default reasoning itself. In argument-based systems of defeasible reasoning [Simari and Loui, 1992; Pollock, 1994] these two things are combined: there is no division between the reasoning and priority components in these systems. This raises questions concerning the usefulness of such division, for example from the computational point of view.

Acknowledgements

This research was funded by the Academy of Finland. The author gratefully acknowledges additional financial support from the following foundations: Suomen Kult­ tuurirahasto, Emil Aaltosen s:t:ttiO.