Statistical Foundations for Default Reasoning

1 Introduction

Default reasoning, i.e., reasoning to plausible but de­ ductively invalid conclusions, has been an important re­ search area in AI for over a decade. Work in this area shows us how, given that we accept the default "Birds typically fly" and the fact "Tweety is a bird", we can ar­ rive at the reasonable (although possibly incorrect) belief that "Tweety flies".

*The work of Fahiem Bacchus was supported by NSERC under their operating grants program and by IRIS. The work of Adam Grove, Joseph Halpern, and Daphne Koller was sponsored in part by the Air Force Office of Scientific Re­ search (AFSC), under Contract F49620-91-C-0080. Adam Grove's work was performed while at Stanford University, where he was also supported by an IBM Graduate Fellow­ ship. Some of this research was performed while Adam Grove and Daphne Koller were at IBM Almaden Research Center. The United States Government is authorized to reproduce and distribute reprints for governmental purposes.

Joseph Y. Halpern

IBM Almaden Research Center 650 Harry Road San Jose, CA 95120- 6099 halpern@almaden.ibm.com

Daphne Koller

Computer Science Dept. Stanford University Stanford, CA 94305 daphne@cs.stanford .ed u

A different reasoning paradigm, which has been stud­ ied for an even longer period, is direct inference. Di­ rect inference is concerned with reasoning to conclu­ sions about particular individuals from general statisti­ cal knowledge. For example, from a knowledge base con­ sisting of the statistical information "90% of birds fly" and the fact "Tweety is a bird", theories of direct infer­ ence would allow us to conclude that our degree of belief in "Tweety flies" should be 0.9. Different systems for di­ rect inference that have been suggested include [Bacchus, 1990; Bacchus et al., 1992; Kyburg, 1974; Levi, 1980; Pollock, 1990; Reichenbach, 1949; Salmon, 1971].

Direct inference and default reasoning share a number of important characteristics. First, neither is a logically sound inference system. Neither statistical knowledge nor defaults about the class of all birds permit us to de­ duce anything for certain about a particular bird such as Tweety: Both "Tweety flies" and "Tweety does not fly" are logically consistent with "90% of birds fly" or "birds typically fly". Second, both direct inference and default reasoning are nonmonotonic. If we learn that penguins do not fly, and that Tweety is a penguin, direct inference would generate a different degree of belief in Tweety fly­ ing. Similarly, default reasoning systems would retract the conclusion that Tweety flies. And third, various properties, such as ignoring irrelevant information and preferring more specific information, are considered to be desirable in both default reasoning and direct infer­ ence.

So how deep is the connection between direct infer­ ence and AI default reasoning? Some applications of defaults seem to have little to do with statistics [Mc­ Carthy, 1986]. But equally often, defaults have some basis in statistics. For example, the default "Birds typ­ ically fly" appears to have as one of its justifications the statistical fact that most birds fly. Thus, it seems reasonable to adapt techniques from direct inference to reason with defaults of this type. Our theme in this paper is that this plausible connection between direct inference and default reasoning can be made precise. In particular, we show in Section 3 that a new method for direct inference, first introduced in [Bacchus et al., 1992; Grove et al., 1992b], can provide many of the features considered desirable in default reasoning. Among other things, it provides a preference for more specific defaults as well as the ability to ignore irrelevant information.

This is particularly important as there is a tension between these two requirements. Most theories of de­ fault reasoning fail to capture both of them simulta­ neously (see, for example, [Geffner and Pearl, 1990.; Lehmann and Magidor, 1992; Pearl, 1990; Reiter, 1980]). What is even more important is that for us these prop­ erties follow directly from an independently motivated semantics; they are not the result of adopting an ad hoc theory of irrelevance.

In our method, we presume that there is a knowledge base that consists of information about the world, in the form of first-order statements (such as "All penguins are birds") and statistical information. The statistical information might be quantitative, e.g., "90% of birds fly", or it might be in the form of qualitative default information. We interpret a default statement such as "Birds typically fly" as the statistical assertion "Almost all birds fly", which is given a precise semantic interpre­ tation within our formalism. This interpretation of de­ faults has a number of benefits. The first is simply that we understand what our knowledge base means. Many default theories will tell us how to reason with "Birds typically fly". But , as pointed out by [Neufeld, 1989], there is far less work telling us when we should adopt this default in the first place. Specifically, what is there about the world that makes this a good default? For us, the true proportion of flying birds offers a guide to how reasonable our approximation "Almost all birds fly" really is. In addition, the semantics imposes natural con­ straints on the defaults. For example, in our formalism the default "Birds typically fly" is inconsistent with both the default "Birds typically do not fly" and the logical assertion "No bird flies" .

A major advantage of our approach is that it allows for rich knowledge bases, with arbitrary first-order in­ formation and statistical information. Thus, it can sup­ port both quantitative and qualitative reasoning. In Sec­ tion 4, we demonstrate the advantages of being able to perform both types of reasoning in a unified framework, by considering both the Lottery Paradox and the Nixon Diamond example.

We are certainly not the first to apply a probabilis­ tic semantics to nonmonotonic logic (see [Pearl, 1989] for an overview). However, while all the other prob­ abilistic approaches we are aware of use the statisti­ cal interpretation as a motivation for using probabil­ ities, none make explicit use of statistical assertions. Nevertheless, there are close technical connections be­ tween our approach and €-semantics [Adams, 1975; Geffner and Pearl, 1990]. In particular, we show in Section 5 that the approach of Goldszmidt, Morris, and Pearl [1990], which extends €-semantics by apply­ ing ideas of maximum entropy, can be embedded in our framework. Besides providing further justification for the use of maximum entropy in [Goldszmidt et al., 1990}, this embedding allows us to use the algorithms they have developed to calculate degrees of belief for formulas in a fragment of our full language.

2 The Formalism

We assume that the knowledge base consists of sentences written in a formal language that allows us to express both statistical information and first-order information. We use the probability logic presented in [Grove et al. , 1992b], which is a variant of logics developed in [Bacchus, 1990; Halpern, 1990].

This logic augments first-order logic by allowing pro­ portion expressions of the form 111/J(x)llx · This term de­ notes the proportion of domain elements satisfying 1/J. We actually allow an arbitrary set of variables in the sub­ script. Thus, for example, IISon(x, y)llx describes, for a fixed y, the proportion of domain elements that are sons of y; IISon(x, y)lly describes, for a fixed x, the proportion of domain elements whose son is x; and IISon(x, y)ll{x,y} describes the proportion of pairs of domain elements that are in the son relation. We also allow conditional pro­ portion expressions of the form 111/J(x)IO(x)llx, which de­ notes the proportion of domain elements satisfying 1/J from among those elements satisfying 8. 1 A rational number is also a proportion expression, and the set of proportion expressions is closed under addition, subtrac­ tion, and multiplication.

One important difference between our syntax and that of [Bacchus, 1990] is the use of approximate equality to compare proportion expressions. It is not hard to see that exact comparisons are sometimes inappropri­ ate. Consider a statement such as "90% of birds fly". If this statement appears in a database, it is almost cer­ tainly there as a summary of a large pool of data. It is clear that we do not mean that exactly 90% of all birds fly. Among other things, this would imply that the number of birds is a multiple of ten, an implica­ tion that is surely not intended. We therefore use the approach described in [Grove et al., 1992b; Koller and Halpern, 1992], and compare proportion expressions us­ ing (instead of= and :::;) one of an infinite family of con­ nectives ::::::i and j i , for i = 1, 2, 3 ... ("i-approximately equal" or "i-approximately less than or equal"). 2 For ex­ ample, we can express the statement "90% of birds fly" by the proportion formula IIFiy(x)IBird(x)llx :::::::1 0.9. The intuition behind the semantics of approximate equal­ ity is that each comparison should be interpreted us­ ing some small tolerance factor to account for measure­ ment error, sample variations, and so on. The appro­ priate tolerance will differ for various pieces of infor­ mation, so our logic allows different subscripts on the "approximately equals" connectives. A formula such as IJFiy(x)IBird(x)llx :::::::1 1 A IIFiy(x)IBat(x)llx :::::::2 1 says that both IIFiy(x)IBird(x)llx and IIFiy(x)IBat(x)llx are approximately 1, but the notion of "approximately" may be different in each case.

We now briefly sketch the ·semantics of novel features of the logic. We evaluate the truth of a formula with respect to a triple (M, r, V), where M is .a finite first­ order structure, r = (r1 , r2 , ... }, Ti > 0, is a tolerance vector, used to .give semantics to the connectives :::;i and ji, and V is a valuation, which interprets the free vari­ ables as elements of the domainin structure M. For each proportion expression {, we can define a rational num­ ber [{]M,V which is the interpretation of { in structure M under valuation V. For example, [IISon(x, y)llx]M,v is the fraction of domain elements x which are sons of V(y). Proportion expressions are dealt with using 7: (M, 7, V) F= { :::;i e if I[{]M,V - .[(]M,vl ~ Ti. We write f= cp if (M, 7, V) f= cp for all (M, 7, V) .

1 We discuss the issue of conditioning on an event with probability zero in the full paper.

2 In IBacchus et al., 1992) the use of approximate equality was suppressed in order to highlight other issues.

We want the agent to use the information in the knowl­ edge base to assign degrees of belief to various assertions. F0llowing [Halpern, 1990], we give semantics to degrees of belief in terms of a set of finite first-order models or possible worlds, together with a probability distribution over this set. The degree of belief in a sentence cp is just the probability of the set of worlds where cp is true. 3 In particular, given a knowledge base KB and domain size N, we consider all the worlds of size N consistent with KB. Furthermore, since we assume that KB is "all the agent knows" , we view each of these possible worlds as equally likely; after all, the knowledge base does not give us any reason to prefer one world over any other. This is essentially an application of the principle of indifference due to Laplace [1820]. This method, which we call the random-worlds method, was investigated in some detail by Johnson [1932] and Carnap [1950, 1952] .

Formally, given a vocabulary <I>, a domain size N, and a tolerance vector 7, we define

where #worlds;.(,p) is the number of first-order struc­ tures Mover the domain {1, ... , N} such that (M, 7) f= '1/J.

Typically, we know neither N nor 7 exactly. All we know is that N is "large" and that 7 is "small". Thus, we would like to take our degree of belief in cp given KB to be lim-r ...... o limN--+oo PriV,-r(cpiKB) . However, there is no guarantee that this limit exists. A necessary condi­ tion for the limit to exist is that the knowledge base KB be eventually consistent: that is, for all sufficiently small 7 and sufficiently large N, #worlds;.(KB) > 0. Essen­ tially, eventual consistency $ays that not only is the KB consistent, but that there is nothing in the KB that limits the domain ·size (for example, a formula saying 7 domain elements"). For the remainder of the paper, we assume that all knowledge bases are eventually consistent. Even if KB is eventually consistent, the limit may not exist . In many cases, the nonexistence of a lirn>it can be intu­ itively justified, .and is sometimes related to the issue of multiple extensions.. (See Section 4 and [Grove et al., 1992b].) However, there are .cases where the limit does not exist for what seem to be the "wrong" reasons. For example, if PriV,-r('PI·KB) oscillates between a+ Ti .and a - Ti for some i as N gets larg-e, then the limit will not exist, although it "should" be a, since the oscillations about a go to 0 as 7 !gets small. We avoid such problems by considering the lim sup and lim inf, rather than the limit . 4

3 Note that we defi:IH! degrees of ·belief only when cp and KB are sentences, i.e., Closed formulas .

Definition 2.1: If lim-r ...... o liminfN--+oo PriV,-r(cpiKB) and lim-r ...... o limsupN--+oo PriV,-r(cpiKB) both exist and are equal, then the degree of belief in cp given KB, written Pr;::,(cpiKB), is defined as the common limit; otherwise Pr;::,(cpiKB) does not exist.

3 Default reasoning

As we mentioned above, we interpret default sentences such as "Birds typically fly" as statistical statements meaning "Almost all birds fly" . Our formalism gives us a straightforward way to represent such a default, by writing IIFiy(x)IBird(x)llx :::;i 1. 5 Note, however, that if the agent has more exact information about the propor­ tion of flying birds, then this information can also be expressed and used during reasoning (see Section 4).

We now review (and slightly extend) results from [Bac­ chus et al., 1992] showing that this type of translation does in fact capture several important features of default reasoning. We stress that all the results in this section hold for our language in its full generality: the formu­ las can contain arbitrary non-unary predicates, and have nested quantifiers and proportion statements.

Proposition 3.1 : The set D(KB) { cp Pr;::,(cpiKB) = 1} contains KB and is closed under valid implication (i.e., if f= () =:} '1/J and () E D(KB), then '1/J E D(KB)).

Hence, our system satisfies the minimal requirement for default reasoning, that it subsume standard deduc­ tive reasoning.

The next proposition shows that our approach goes be­ yond deductive inference to capture simple default infer­ ences. In the following propositions, let x = { x 1 , . .. , Xk} and c = { c1 , ... , Ck} be sets of distinct variables and dis­ tinct constants, respectively.

Proposition 3.2: Let cp(x), ,P(x) be formulas , where no constant inc appears in cp(x) or ,P(x). Then

For example, Pr;::,(Fiy(Tweety)IIIFiy(x)IBird(x)llx :::;i 1/1. Bird(Tweety)) = 1. That is, we can make the stan­ dard inference about Tweety. Note that the proposition also holds when we have quantitative information, i.e., it holds for arbitrary a.

Going beyond simple default reasoning, one sought­ after property we obtain is a preference for more specific defaults.

4 For any set S C JR., the infimum of S, inf S, is the greatest lower bound of S. The lim inf of a sequence is the limit of the infimums; that is, lim inf N-co aN = limN-co inf{a;};>N· The lim inf exists for any sequence bounded from below, even if the limit does not. The lim sup is defined analogously, where supS denotes the least upper bound of S. If limN-co UN does exist, then limN-co UN = liminfN-co UN= lim sup N-co UN.

5 We remark that, here and below, the actual choice of sub­ script for ~ is unimportant. Typically, however, we capture different defaults by using different subscripts. Intuitively, the different subscripts correspond to different measurements or defaults of different strengths.

Proposition 3.3 : Suppose KB has the form '~PI (C) 1\ (llcp(x)l'l/J1(x)llx- ~i a) 1\ (llcp(x)l'l/J2(x)llx- ~j /3) 1\ v x( 'l/J1 ( x) :::} 'l/J2 ( x))' where no constant in c appears in cp, 'l/J1, or 'l/J2· Then Pr:(cp(C)IKB) =a.

For example, if KB* is

then Pr:(Fiy(Opus)IKB*) = 0. That is, we conclude that Opus the penguin does not fly, even though he is also a bird and birds generally do fly.

Another important property of our approach lies in its ability to treat as irrelevant some information that there is no reason to believe is relevant. This is partic­ ularly interesting given the fact it is notoriously hard to achieve specificity and a correct treatment of irrelevant information in the same framework (see the discussion and references in Section 5) . There are a number of situ­ ations in which information will be treated as irrelevant by our approach, but here we restrict our attention to one special case:

Proposition 3.4: Suppose KB has the form '1/J(C) 1\ (llcp(x)l'l/J(x)llx- ~i a) 1\ KB', where no constant inc ap­ pears in '1/J(x) or cp(x), and neither '1/J nor KB' mention any symbol in cp. Then Pr:(cp(C)IKB) =a.

For example,

That is, Tweety the yellow bird continues to fly. There is no information in KB about any correlation between the properties "yellow" and "fly"; hence Tweety's yellow­ ness is treated as being irrelevant to his flying ability. Proposition 3.4 also shows that relevance is relative to a particular assertion cp. A property that is relevant to one assertion will not necessarily be relevant to another. For example, if we know that birds typically have beaks, we can conclude that Opus, a penguin, also has a beak, even though penguins typically do not fly (while birds typically do). More precisely, for the knowledge base KB* above (relating to penguins, birds, and flying) , we have:

That is, Penguins is an exceptional subclass of birds with respect to flying but not with respect to having beaks. Proposition 3.4 also allows the agent to ignore those parts of KB that do not concern Tweety at all.

4 Qualitative versus Quantitative

Systems of direct inference frequently cannot use quali­ tative information such as "birds typically fly", whereas standard default logics generally cannot use quantita­ tive information such as "90% of birds fly." Neverthe­ less, we often have both kinds of information available. One significant advantage of our approach is that it can use any combination of qualitative and quantitative in­ formation, supporting an entire spectrum of reasoning.

Furthermore, in those cases where qualitative defaults are insufficient, our approach can often pinpoint the ex­ tra information required to reach a definite conclusion. To demonstrate, we examine two examples that are well­ known to be problematic for pure default reasoning: the Lottery Paradox [Kyburg, 1961) and the Nixon Diamond [Reiter and Criscuolo, 1981].

In the Lottery Paradox, the assumption is that a large number of people buy tickets to a lottery in which there is only one winner. The standard assumption is that for any particular person c we would like to conclude by default that c does not win the lottery. This, how­ ever, seems to contradict the fact that someone must win it. In order to describe the problem in our framework, we assume for simplicity that the domain consists only of lottery ticket holders. Our knowledge . base KB will consist of the single statement 3!xWinner(x) (i.e., there is a unique winner). If we know the size of the lot­ tery, say N, our degree of belief that the individual denoted by a particular constant c wins the lottery is PrN-,.r(Winner(c)IKB) = f:t. Our degree of belief that someone wins will obviously be 1. These answers are clearly the "right" ones given our information. If, how­ ever, we do not know the exact number of ticket holders, but have only the qualitative information that this num­ ber is "large", then our degree of belief that c wins the lottery is Pr:(Winner(c)IKB) = 0, although, as before, Pr:(3xWinner(x)IKB) = 1. Thus, we conclude by de­ fault that c does not win the lottery for any constant c, although we still believe with full confidence that some­ one does win.

A major difficulty with using defaults is that they do not always provide sufficient information to reach a con­ clusion. A classical example is the problem of conflicting defaults, as demonstrated by the well-known Nixon Di­ amond. Suppose we have the following information:

To simplify matters, we further assume that there is a unique individual who is both a Quaker and a Re­ publican. We capture this by taking KB1 to consist of the above conjunction together with the formula 3!x (Quaker(x) 1\ Republican(x)) . Let cp be the formula Pacifist(Nixon).

What should be our degree of belief in Pacifist(Nixon) ; that is, what is Pr:(cpiKBI)? It turns out that this lim­ iting probability does not exist. This is because the limit is non-robust-its value depends on the way in which f goes to 0: if 71 « 72, so that the "almost all" in the first conjunct is much closer to "all" than the "almost none" in the second conjunct is closer to "none", then the limit is 1. Intuitively, in this case the information in the first conjunct is more precise and hence should be taken more seriously than the information in the second conjunct. Symmetrically, if 71 » 72, then the limit is 0. On the other hand, if 71 = 72, then the limit is 1/2.

The nonexistence of this limit is not simply a technical artifact of our approach. Rather, the fact that the limit fails to exist provides important information about the underlying incompleteness of our knowledge. It shows that in the presence of conflicting defaults, we often need more information about the precise nature of "almost all" and "almost none" to resolve the conflict; our ap­ proach pinpoints the type of information that would suf­ fice to reach a decision. Note that our formalism does give us an explicit way to state that the defaults have equal strength, if we wish; namely, we can use :::::: 1 to cap­ ture both default statements, rather than using ::::::1 and ::::::2 . In this case, we get the answer 1/2, as expected. However, it is not always appropriate to conclude that the defaults have equal strength. We can easily extend our formalism to allow the user to prioritize defaults, by defining the relative size of the components Ti of the tolerance vector.

If we have more quantitative information, then we can use it . For example, we may have information regarding the precise proportion of Quakers (resp., Republicans) who are pacifists. For example, assume that KB2 is

IIPacifist(x)IQuaker(x)llx ::::::1 a 1\ IIPacifist(x)IRepublican(x)llx ::::::2 {3 1\ Quaker(Nixon) 1\ Republican(Nixon) 1\ 3!x (Quaker(x) 1\ Republican(x)) ,

where {a, {J} =/= {0, 1}. In this case the limit does exist ; we get Pr:(cpiKB2 ) = ~' where a = 1 -a and o:{3Hi/3

Readers familiar with Dempster's rule of combination [Shafer, 1976) will note that this formula is precisely the result of combining the two probability functions that give probability a and {3, respectively, to Nixon being a Pacifist . If we view the fact that Nixon is a Quaker as giving evidence of degree a in favor of Nixon being a pacifist, and the fact that Nixon is a Republican as giving evidence of degree {3 in favor of Nixon being a pacifist, then our technique can be viewed as combining these two pieces of evidence. In the full paper, we show that our approach also captures more general instances of Dempster's rule of combination, and discuss why the appearance of the rule here is not coincidental.

Returning to the formula, notice that if a = 1 and {3 > 0, then the limiting probability is 1, while if {3 = 0 and a < 1, then the limiting probability is 0. That is, as expected, an "extreme" value will dominate. If 2 a = {3 , then the limiting probability is o: 2~02 . Thus, if 80% of Quakers are pacifists and 80% of Republicans are pacifists, the value of the limit would be around 0.94. This has a reasonable explanation: if we have two in­ dependent bodies of evidence, both supporting cp quite strongly, when we combine them we should get even more support for cp.

5 Maximum entropy

In this section, we show how the approach of [Gold­ szmidt et al., 1990) can be embedded in our framework. We begin by outlining £-semantics [Geffner and Pearl, 1990], on which the framework of [Goldszmidt et al., 1990) is based. Consider a language consisting of propo­ sitional formulas (over some finite set of propositional variables p1 , .. . , Pk) and default rules of the form B -+ C

(read "B's are typically C's"), where Band Care propo­ sitional formulas. Let n be the set of 2k propositional worlds, corresponding to the possible truth assignments to these variables. Given a probability distribution 11 on !1, we define 11(B) to be the probability of the set of worlds where B is true. We say that a distribution 11 £-satisfies a default rule B-+ C if 11(CIB) 2: 1- £.

A parameterized probability distribution (PPD) is a collection {11.}<>0 of probability distributions over n, parameterized by L A PPD {11. } ·>O £-satisfies a set R of default rules if for every £, 11< £-satisfies every rule r E R. A set R of default rules £-entails B -+ C if for every PPD that £-satisfies R, lim, ..... o 11< ( CIB) = 1.

As shown in [Geffner and Pearl, 1990], £-entailment possesses a number of reasonable properties typically associated with default reasoning, including a prefer­ ence for more specific information. However, there are a number of desirable properties that it does not have. Among other things, irrelevant information is not ignored. Pearl's notion of 1-entailment [Pearl, 1990) strengthens £-entailment by allowing it to ignore irrel­ evant information in certain cases. However , it suf­ fers from the problem that subclasses that are excep­ tional in one aspect are deemed exceptional in all as­ pects. In particular, using !-entailment, we cannot conclude that Opus the penguin has a beak. Since £­ entailment is equivalent to Lehmann and Magidor's pref­ erential entailment [Lehmann and Magidor, 1992], and !-entailment is equivalent to their rational closure, these approaches to default reasoning all suffer from difficul­ ties when trying to combine specificity with irrelevance. We showed above that our approach does not suffer from this problem.

In order to obtain additional desirable properties, £­ semantics is extended in [Goldszmidt et al., 1990] by an application of the maximum entropy principle [Jaynes, 1957). Instead of considering all possible PPD's, as above, only the PPD {11; n}·>O of maximum entropy is considered (see [Goldszmidt et al., 1990) for precise def­ initions and technical details) . A rule B-+ Cis an ME­ plausible consequence of R if lim, ..... 0 11; n ( CIB) = 1. The notion of ME-plausible consequence is 'analyzed in detail in [Goldszmidt et al., 1990], where it is shown to inherit all the nice properties of £-entailment (such as the pref­ erence for more specific information), while successfully ignoring irrelevant information. Equally importantly, al­ gorithms are provided for computing the ME-plausible consequences of a set of rules in certain cases.

Although no explicit use is made of maximum entropy in our framework, there is a close connection between the random-worlds approach and maximum entropy pro­ vided that the language consists only of unary predicates and constants, as shown in [Grove et al. , 1992b] . These results can be extended to show that the approach of [Goldszmidt et al., 1990) can be embedded in our frame­ work in a straightforward manner. We simply convert all default rules r of the form B -+ C into formulas of the form 9r =def ll'l/lc (x)i'I/IB(x)llx ::::::1 1, where 1/!B is the formula obtained by replacing each occurrence of the propositional variable Pi in B with Pi(x) . Note that the formulas that arise under this conversion all use the same approximately equals relation ::::::: 1 , since the approach of [Goldszmidt et al., 1990] uses the same f fm all default rules. Moreover, they all involve only unary predicates. Under this translation, we can prove the following theo­ rem, using techniques similar to [Grove et al., 1992b] .

Theorem 5.1: Let c be a constant symbol. Using the translation described above, for any set n of defeasible rules, B ___. C is an ME-plausible consequence of n iff Pr:('l/lc(c)l ArE'R. Br 1\ 1/IB(c)) = 1.

Thus, all the computational techniques and results de­ scribed in [Goldszmidt et al., 1990] carry over to this special case of our approach.

It is very encouraging that the results of [Gold­ szmidt et al., 1990] can be arrived at in two quite differ­ ent ways. Our result formalizes a connection between en­ tropy and indifference, well known in other contexts like statistical thermodynamics, in tll.e context of an agent reasoning by default. It shows that if one feels that it is reasonable for an agent to be indifferent between possi­ bilities left open by its knowledge, then one has an in­ dependent reason for accepting the theory of irrelevance generated by maximum entropy.

It should also be noted that our approach, which does not appeal to entropy maximization directly, has the ad­ vantage of being much more general. Most importantly, it can deal sensibly with languages that have predicates of arbitrary arity. It is unlikely that an approach that uses entropy directly could be extended to deal such lan­ guages. Once we have even a single- binary predicate in the language, all connection between our approach and maximum entropy disappears. As discussed in [Grove et al., 1992b], we cannot even find a suitable probabmty space to take entropy over. Resu.Its of [Grove et al., 1992a] showing that, with a binary predicate in the lan­ guage, degrees of belief are in general uncomputable sup­ port the conjecture that there is none to be found.

6 Discussion and conclusions

We have shown that a logic that allows statistical and first-order assertions, together with a principled ap­ proach for obtaining degrees of belief from a knowl­ edge base expressed in this logic, can give a general ap­ proach for capturing many aspects of default reasoning. Our framework has the added advantage of being able to deal with both default (qu·alititative) and statistical (quantitative) information. Our results. demonstrate the close connection between default reasoning and direct inference.

We close by briefly discussing two criticisms that have been made of entropy-based reasoning sys.tems: language and syntax depende11ce, a:nd the treatment o£ ca;usality [Pearl, 1988]. While the random-worlds method is: not. entropy-based, the relationship we observed in Section 5, suggests that similar problems may arise.

With regard to causality, [Goldszmidt et al., 1990; Pearl, 1988] and [Hunter, 1989] have observ.ed that knowledge about causal relationships greatly affects owr intuitions concerning the "right" answers to various problems, and that the naive maximum entropy ap­ proaches do not take this causal ~nformatio11 into. consideration. We would argue that this only shows that this information is not properly captured by the straightfor­ ward encoding of defaults, and that we may therefore have to include information about causality when ex­ pressing defaults in the knowledge base. [Hunter, 1989] presents one possibility for encoding causal information within the maximum entropy approach. In [Bacchus et al., 1993], we present a more general approach within the random-worlds framework, and show that it deals with many of the problematic aspects of causal reasoning.

The language problem is more subtle. Maximum­ entropy methods can draw different conclusions from knowledge bases that seem to refiect the same informa­ tion about the world. This is a. serious issue, because the choice of the "right" representation of our informa­ tion is not always dear. In general, we believe that the form in which our information is written down encodes knowledge-it reveals our biases and expectations. It is perfectly reasonable that our bias should affect inductive reasoning. In certain cases, our bias is sufficiently clear that the choice of representation becomes obvious. In physics, for example, the choice o£ language is sometimes based on the criterion of time-in variance. Moreover, in physics and in many other applications of maximum en­ tropy, there is an objective "reality check"-we can com­ pare the answers given by the formalism to reality, and thus independently verify the reasonableness of our rep­ resentation. In many AI applications, however, there might not be an obvious represe11tation, nor an appro­ priate rea.tity check. In these cases, we will have to for­ mulate criteria. fur choosimg the right. formal knowledge base, given a 111atural-language specii.cation of onr knowl­ edge. This is an importan.t research: problem, which we intend to investigate. Tlile· fact that our apJ>roach can deal with causality leads us to hope that it will be able to. deal with the language problem as well in a satisfac­ tory way.

Acknowledgements

We would like .to thank Moshe Va.rdi for helpful com­ ments.