On the Comparison of Theories: Preferring the Most Specific Explanation

1. Introduction

Various formalisms have been proposed to give a semantics to systems with knowledge with exceptions (Reiter[80] , McDermott and Doyle[80j, McCarthy[80,84j, Moore[83J, Poole[84b,c]). One problem which arises, particularly with respect to inheritance sys­ tems (Etherington and Reiter[83j, Touretzky[84]), is how to resolve ambiguity when different defaults can be used to produce different answers.

Poole[84b] gives a model theoretic definition of default reason­ ing with defaults as possible hypotheses in a scientific theory. An answer is explainable if it logically follows from some consistent set of default instances (a theory) together with the facts. In this paper we propose, in the case of ambiguous answers, a theory comparator to find the answer supported by the best explanation. This is applied to the problem of default inheritances in semantic net­ works, where the most specific theory is preferred. If there is gen­ eral knowledge applicable to an answer, and more specific knowledge also applicable, then the most specific knowledge is pre­ ferred.

2. Default Logie

2.1. Syntax

The syntax is an extension of the first order predicate calculus. A wff is a well formed formula of the first order predicate cal­ culus. The input of the system is defined as follows:

<input>::-- <wff> ] <list-of-variables> ASSUME <wff>

Inputs of the first type are called facts, and inputs of the second type are called defaults. An instance of a default is the wff with values substituted for the variables appearing before the ASSUME.

The facts correspond to the axioms in a normal logic, and the defaults are knowledge which can be used as long as they are con­ sistent.

2.2. Formal Semantics

If F is the set of facts, and .:1 the set of defaults, we say that g is explainable if there is some D, a set of instances of elements of .:1 such that

On the Comparison of Theories: Preferring the Most Specific Explanation

David L Poole

Logic Programming and Artificial Intelligence Group Department of Computer Science University of Waterloo Waterloo, Ontario, Canada N2L 3Gl

FUD~g and FUD is consistent.

D is said to be the theory that explains g. D is like a "scien­ tific" theory. Theorems(FUD) is the corresponding " logical" theory.

That is, g is explainable if there is a theory which explains it. The instances of defaults are the possible hypotheses in this theory. This theory must be consistent with all of the facts.

2.3. Example 1.

Consider the knowledge that "birds fly". This is knowledge we may want to use although it has exceptions (eg. emus, penguins, roast ducks, little chicks etc.). The default "a bird can fly unless it can be shown not to" is given by:

(x) ASSUME bird(x):;)flies(x)

If we are also given the knowledge that emus are birds that don't fly, and that Tweety is a bird, and Edna is a.n emu, we input

Vx emu(x):;,~flies(x) Vx emu(x):;)bird(x) bird( tweety) emu(edna)

From this knowledge we can explain flies(tweety) with the theory

{bird( tweety):;, flies ( tweety )}

which is consistent (its negation cannot be proven), and together with the facts can be used to prove flie s (tweety ).

We cannot explain flies (edna) as the corresponding theory for edna is not consistent, as its negation can be proven from the facts .

2.4. Example 2

Suppose that we modify the first example to have "emus don't fly" as a default rather than a fact. We get the following system:

(x) ASSUME bird(x):;,flies(x) (x) ASSUME emu(x):;,~flies(x) Vx emu(x):;,bird(x) bird(tweety) emu(edna)

We can now explain everything we could in example 1, and can also explain flie s (edna) with the theory D1={bird(edna ):;, flies( edna )} , as well as ~ flies(edna) with the theory D2-{emu(edna):;)~flies(edna)}.

This is an example where there are two different things which can be explained, and where one is preferred. We prefer to say that edna does not fly, as our knowledge that emus don't fly is more specific than our knowledge about birds flying .

3. A Theory Comparator

So far we have given the semantics of a default logic, closely related to the normal defaults of Reiter[80] (see section 5.2) . Our theories differ from his extensions, as our theories are intended to be minimal (the simplest theory to explain the results) , whereas his extensions are the theorems following from maximal sets of instances of defaults which are consistent.

As in example 2 above, a problem arises with normal defaults when two different answers can be produced in two extensions, but where one is preferable over the other (Reiter and Criscuolo[81]).

Within inheritance hierarchies we want default links, but want to use the most specific knowledge to deduce an answer (Ethering­ ton and Reiter[83J, Touretzky[84]). Within our system this is done by preferring the most specific theory to explain the results. We want our definition of more specific to be a semantic rather than a syntactic definition so that it can be understood and justified independently of any implementation, and so that it does not fall into the problems of shortest paths and redundant knowledge which arise with particular syntactic definitions of best inheritance (Touretzky[84]).

To formalise the notion of one theory being applicable when­ ever another one is, we need to be able to talk about, "what if something else were the case". To do this we divide the facts into two classes:

Fn those facts necessarily true in any world in our domain.

1. those facts which happen to be true in the case we are consid­ ering.

In the birds fly example above, "emu(x):Jbird(x)" is a neces­ sary part of our domain. We do not want to consider the case "what if emus were not birds?". This should be contrasted with the fact emu(edna ). In this we want to say the theory which explains flies (edna) is more general as it is applicable even if we only knew Edna was a bird. Thus we do want to consider the case where Edna is not an emu.

Fn and F. can be seen to correspond to the network links and the starting nodes in NETL (Fahlman[79]), or to the necessary and contingent facts in modal logic (Hughes and Cresswell[68]).

. Suppose we have a system consisting of necessary facts Fn, con­ tmgent facts F. and defaults Ll. A solution S is a pair <D ,g> , where Dis a theory to explain g. That is, FnUF.UD~g.

For some possible fact FP, we say solution S-<D ,g> is a.ppli­ ca.ble if FP UD UFn ~g. That is, if D can be used to prove g given FP and Fn.

We say FP is a.dequa.te to make D explain g if Fn UD UFP ~g.

Given two solutions S 1-<Dvg 1 > and S 2 -<D 2 ,g 2 >, we say S 1 is more genera.! than S 2 (written S 1:sS 2 ) , if there is possible fact FP for which S1 is applicable, S2 is not applicable and F is not adequate to make D 2 explain g 1 . P

That is <Dvg1>:S<D2,g 2 > if there is an FP, such that FPUD 1 UFn~g1 and FPUD2UFn'f"g2 and FPUD2UFni"g1

The first two conditions say there is a fact that makes D 1 applicable and D2 not applicable. The third condition puts a res­ triction on the FP to make sure FP does not make g 1 follow independently of D 1· We want FP to actually need D 1 to prove gl> rather than, for example, being g 1 itself.

Another· way of looking at it is to define more specific, which is to mean that one is applicable whenever another is. Define S 1 is more specific than S 2 (written S 1.,S 2 ) if S 1 is not more general than S2. That is if, for every FP which is not adequate to make D 2 explain g1, if S 1 is applicable then S2 is applicable. More formally , if for every FP

if FPUD 1 UFnFog 1 and FP UD2UFni"g1 then FP UD2UFn ~g2

We say S1 is strictly more specific than S 2 , written S 1 >S 2 , if S 1 is more specific than S2 and S2 is not more specific that S 1 . Thus strictly more specific is the irreflexive version of more specific.

The preferred solution is the most specific solution. We prefer the most specific knowledge to be used in an explanation. If there is no most specific solution, because two solutions are not compar­ able, or because they are both more specific than each other (i.e . there is no strictly more specific solution) then an ambiguous answer is produced.

3.1. Exa.mple 2 Revisited

Within example 2, divide the facts into the necessary facts Fn-{emu(x):Jbird(x)} and the contingent facts F. -{bird(tweety ),emu(edna)}.

To show D 1 is more general than D2 , choose FP to be bird(edna ). In this case, <D 1 ,flies(edna )> is applicable, but <D2,-flies(edna)> is not applicable. FP is not adequate to make D2 explain flies(edna ).

We cannot show D2 is more general than D 1, as the only facts which are adequate to make D2 explain -flies(edna), are emu (edna) and -flies (edna) (or anything which logically implies either). For the first, <D2,flies(edna )> is also applicable. For the second, -flies(edna) is adequate to make D 1 explain -flies(edna). So the third condition in the definition of more general is used to reject this.

Thus we have shown that the solution <-flies(edna),D 1 > is strictly more specific than <flies(edna ),D2>. Our definition pro­ duces the intuitive answer for this case.

3.2. Exa.mple 3

Consider the example of university students being typically adults, adults being typically employed, and university students being typically unemployed. This is expressed with

• ( x) ASSUME university_student ( x) :>adult (x)
• (x) ASSUME adult(x):Jemployed(x)
• ( x) ASSUME university_student ( x) :J -employed ( x)

From this knowledge, given the contingent fact that Fred is a university student, there is a theory to explain her being unem­ ployed, namely the theory D 1 -{university_student(Fred) :J - employed(Fred)}. There is a theory to explain her being employed, namely the theory D2 - {university-student(Fred) :J adult(Fred) , adult(Fred) :J employed(Fred)}. The reason that we prefer the first theory is that we have more explicit knowledge about university students than about adults in general. Using our theory comparator defined above we have D 1 .,D 2 , as the only fact that makes D 1 applicable to - employed(Fred), that is not the goal itself is university_student(Fred). If this is the case then theory D2 is also applicable. However we can not show D 2 ;;,D 1 as FP -adult(Fred) together with D2 produces the goal employed(Fred). With adult(Fred), D 1 does not give the goal - employed(Fred). The theory comparator produces the desired result, namely D 1>D2·

Note that the same result is produced if university students being adults is given as a fact . The same contingent fact will pro­ duce the same comparisons. In this case, the above description holds. In fact any set of defaults and facts that makes university_student(Fred) imply adult(Fred) will produce the same results. However, the same results are not produced if adults being employed is given as a fact instead. This is because the corresponding D 1 is adequate to prove employed(Fred) given adult(Fred) . There is then a symmetry between adulthood and unemployment. Both theories are more specific than each other (neither is more general) .

3.3. Exa.mple 4.

For examples where there is no preferable theory an ambiguous result is still obtained. Consider the republican-quaker-pacifist example. In this example the defaults are

• (x) ASSUME republican(x ):::>pro-defence(x)
• (x) ASSUME pro-defence(x):J-pacifist(x)
• (x) ASSUME quaker(x ):::>pacifist(x)

If we are given the world fact that Dick is a republican and a quaker then we can explain both his pacifism and his non-pacifism.

The two corresponding theories are both more general than each other. This can be shown by considering the possible facts republican(dick) , which makes the theory explaining his non­ pacifism more general, and the fact quaker( dick) making the alter­ nate theory more general. Thus we prefer neither explanation.

3.4. Example 5

To show that we can handle more complex cases, even where no contradictory results are obtained, consider the following exam­ ple:

(:r) ASSUME bird(x):Jans(x,flies)

(:r) ASSUME emu(:r):Jans(x,runs)

(:r) ASSUME at_emu_farm(:r):Jemu(x)

ASSUME soothsaying

V:r emu(:r):Jbird(:r)

V:r Vy ans ( :r ,y )/\soothsaying :Jsay( :r ,y)

From the contingent fact , at_emu_farm(randy ), we can explain say(randy ,runs) and say(randy ,flies). The solution of say(randy,flies) is more general, as it is also applicable for the fact bird(randy). However, we cannot show that the solution explaining say(randy,runs) is more general. Thus we prefer the solution of say(randy ,runs).

3.5. Example 6.

The following example shows how the comparitor may produce a seemingly unintuitive answer. Consider the defaults ..:1- {a :Jb , b:Jc, a:J~c , d:Je , e:Jf d:J~f} , F.- {~c/\~f:Jgl> c/\f:JgJ, F,­ {a/\d}. Although the theories to explain ~c and ~d are strictly more specific than the corresponding theories to explain c and d, and the theory to explain g2 is more general than the theory to explain gl> the theory to explain g 1 is more general than the theory to explain g2. This can be shown by considering FP -a 1\ ~f . This problem cannot be fixed up by simply making FP be compatible withD1.

4. Implementation

For the general case of finding the best explanation a standard first order predicate calculus deduction system can be used ( eg. Poole[82,84a]). To prove that a goal is explainable, we use the deduction system in two phases. In the first we try to prove the goal using the facts and the defaults as the axioms in the deduction system. The defaults used in the proof of the goal can be collected into a potentially explaining theory. This theory can be checked for consistency by using the same deduction system to try to prove the theory and the facts are inconsistent. This is, of course, unde­ cidable, in general. See Poole[84c] for a provably correct procedure lor such a system, together with a description of the reverse Skolemisation needed to match the instances giving an incon­ sistency with those explaining the goal.

The general proof for more specific is also a set of standard first order proofs. In general, standard first order proof techniques are adequate for handling the default system. There will, of course, need to be ways to improve the efficiency of such a system by allowing the proofs to interact to prune each other's search spaces, and by exploiting the structure of specific domains (see for example Poole[84c]).

If we have a restricted language, for example in inheritance sys­ tems where logical entailment can be implemented by looking up the lattice, the corresponding efficiency can be transferred to han­ dling the problem of finding the most specific theory. For the case of inheritance in semantic networks, Touretzky[84] has provided an efficient way to implement our preference of the most specific theory by conditioning an inheritance system so that a shortest path reasoner will work.

5. A Comparison With Other Systems

5.1. Semantic Networks

An attempt to characterise the notion of using the most specific knowledge is incorporated in preferring the shortest inference path in NETL (Fahlman[79]). As pointed out in Touretzky[84], this causes problems when there are redundant links and ambiguous extensions. As our system uses a semantic notion of more specific rather than some syntactic notion, it does not fail into these prob­ lems of shortest paths.

When everything is in the form of a semantic network, our logic provides a semantics for the inferential distance of Touretzky[84]. The inferential distance is whether there is an inheritance path from the subclass (the more specific) to the super­ class. The superclass then provides the fact which makes it more general. Our logic is not, however , restricted to the simple implica­ tions found in semantic networks, but can use arbitrary wffs as both defaults and facts. It also handles a mixture of defaults and facts rather than treating all arcs as defaults. As shown in example 5, our system can find more specific theories when there are dif­ ferent, but not necessarily contradictory answers.

5.2. Reiter's Default Logie

This work can be most directly compared with the defaults of Reiter[80J. The definition of default above corresponds to his defin­ ition of a normal default . His normal defaults of the form o(x):Mw(x)/w(x) are expressed as (x) ASSUME o(x):Jw(x), the difference being that we allow the contrapositive of our defaults. We have a simple model-theoretic semantics as well as a proof theory (see Poole[84c] for a detailed comparison).

The problems which gave rise to non-normal defaults, have however been solved in a very different manner. We have more modular statements than the corresponding semi-normal defaults (Reiter and Criscuolo[81], Etherington and Reiter[83]), as we do not need to change the more general rules to add in exceptions to them, or know all of the more specific rules that may override a general rule we may have . We can add both more specific and less specific knowledge in a modular way without needing to change the other knowledge, or even needing to know that there are excep­ tions. The use of abnormality conditions (McCarthy[84]) still does not give the modularity of our system, but rather allows the excep­ tions to a general rule to be stated in a more modular way, but it must still be changed. In summary we have the notion that more specific knowledge is preferred as an integral part of the logic, rather than needing to be explicitly given.

6. Conclusion

We have outlined how defaults can be treated as possible hypotheses in a scientific theory used to explain the results. The problem of multiple answers can be overcome by allowing a com­ parison of theories to choose the answer which is supported by the "best" theory. When we have a set of knowledge which consists of general knowledge and more specific knowledge we want to choose the more specific knowledge in preference to the more general knowledge when there is a conflict.

This paper gives a formal account of a system for such reason­ ing. This is defined in terms of normal first-order model-theoretic semantics, and is defined so a normal first-order predicate calculus deduction system can be used to derive results.

We also provide an alternate semantics, and motivation for the "correct" inheritance in inheritance systems (Touretzky[84]). There are considerable advantages over non-normal defaults in terms of modularity for solving the same problem.

This is not an attempt to solve all of the problems of when one theory is better than another. This may change from domain to domain, for example in the diagnosis domain (Jones and Poole[85]) where it is the theory, which is the diagnosis, that is important, and for example in learning systems where we want the most general theory (within constraints) which explains the observations. There are examples one can imagine where there is more domain-specific knowledge about which explanation is better.

Acknowledgements

Thank to Eric Neufeld, Paul Van Arragon, Randy Goebel and Sumo Kindersley for valuable comments on an earlier draft of this paper. This research was sponsored by no defence department .