Does Probability Have a Place in Non-monotonic Reasoning?

Abstract

Arguments are presented in favor of the answer ''yes". A quantitative approach which overcomes the usual need for a priori probabilities is presented. Sorile of the practi­ cal advantages of using probabilities in a production sys­ tem are described.

§1. Introduction

The panel on uncertain reasoning at AAAI-84 con­ sidered the question of whether or not implementations of non-monotonic reasoning should be probabilistic. A va· ricty of (generally unsupported) claims were made to the effect that probabilities arc unintuitive, that the numbers needed arc unavailable, and that the method generally is inappropriate. The counterclaims that probabilities are intuitive, available and appropriate were similarly unsup­ ported.

My intention here is to present some results that deal with these questions . Let me stress that it is precisely the question posed in that last paragraph that interests me: Should probabilities be used to implement non-monotonic reasoning systems? The easier question of whether proba­ bilities can be used to implement some types of non-mono­ toic reasoning has been answered rather conclusively by MYCIN <md its offspring; more difficult questions involv­ ing the nature or definition of probability itself have been grappled with by philosophers for centuries, and I ant con­ tent to leave them to it .

I will attempt to address the issues of whether the numbers required by a probabilistic theory can in general be made available to a reasoning system, and whether or not probabilistic methods arc effective. The first of these is principally a theoretical issue, while the second is more one of pragmatics.

§2. A priori probabilities

A standing objection to the usc of probabilities in AI systems corresponds to the question , "Where do the num­ bers come from?" Bayesian methods require the existence of initial estimates for the probabilities in question, and it seems impossible to arrive at these estimates without a

Rcsl,arch supported hy the Oflice of Naval Reserach under grant number NOOOH-81-K-0004.

Does Probability Have a Place in N on-n1onotonic Reasoning?

Matthew L. Ginsberg

LOGIC GROUP KNOWLEDGE SYSTEMS LABORATORY

Stanford University Stanford, California 94305

great deal of knowledge about the domain being consid­ ered.

I have a great deal of sympathy with this objection. It has been pointed out, however, that by considering ranges of probabilities instead of specific values, it is possible to encode informa tion not only about the strength of our be­ lief in a given proposition, but also about our confidence in our estimate of that strength [1,7]. A precise formula­ tion of this observation will be the principle result of this section.

When we think of a statement as corresponding not to a precise probability but to a range [x, y], we can think of y - x as corresponding to the uncertainty we have in our probabilistic estimate. Thus a specific range { x} = [x, x] implies total confidence in our probabilistic knowledge, while the maximal range [0, 1] corresponds to total igno­ rance- the statement that a certain probability p lies in the range 0 :S p :S 1 has no informa tional content at all.

More generally, a probability range [x, y] with x # y corresponds to partial knowledge. Furthermore, it is possi­ ble to use Dempster-Shafer theory to combine probability ranges of this sort; an application of this to semantic nets is described in [4].

In order to see how to obtain the ranges from ob­ servational data (or the lack thereof), suppose that the probability of some specific default rule is p, although this value need not be known to us. Now fix some "gullibility" g E [0, 1], and suppose that we test the default rule ex­ perimentally t times . Then there is some p 111 ; 11 (p, t, g) such that the probability of our observing no more than lPmin successful applications of the default rule among the t tri­ als is equal to g. Intuitively, if the "real" probability is p, we require that the chance that the observed probability be at least Pmiu be at least g. Thus if g = 0, we get the extremely cautious approximation Pmin = 0.

We can define Pm .. x(P, t, g) similarly. Having done so, if some default rule D has been tested t times with s suc­ cesses, we can approximate the overall probability to be assigned t.o the nile by s/t, and consider the probabilis­ tic range [1J 111 ; 11 (s/t,t,g),p,11,.x( ·~/t,t,g)]. Conversely, given a probability range [x, y], we can usc this expression to recover s and t (for g fixed).

The details of the calculation require us to solve a fa­ miliar problem from probability theory: Given a series of t trials in an experiment where the probability of success on each trial is p, what is the probability that the observed probability of success will be in the range [Pmin,Pmax]? This problem is discussed in [8], among other places; there is no exact solution .in closed form, but rcsnlts can be ob­ tained either by using Tchebychev's approximation or by approximating the relevant binomial distribution with a Gaussian. Tchebychev's approximation gives

and identically for Pmax· We therefore need to solve

leading to

If g = 0, we get a probability range of [0, 1] independent of s and t (not very g1tlliblc at all!), as we do if s = t = 0. In the large t limit, we get the singleton s/t as expected- our confidence in our estimate increases as docs the amount of data.

Alternatively, we can use the Gaussian approximation, so that we need to solve

where <!>(x) is the cumulative normal distribution

with <I>(O) = 0 and <I>( oo) = .5. If we set g equal to <I> - 1 ((1 - g) / '2), (3) becomes

This is identical to (1) with 1/ [<I> - 1 ((1 - g) / 2)] 2 replacing g.

To solve the inverse problem (in either case), suppose we arc given a probability range [x,y] . Then if we set x = 1 -- x and fi = 1 -- y, inverting (2) gives

where we should replace g with g = 1/[<I> - 1 ((1 - g)/2)]2 in the Gaussian case. Note that 1/[<I>- 1 ((1 - g)/2W = 0 for g = 0; for g = 1, 1/[<I>- 1 ((1 -· g)/2) ] 2 = oo. Tlnts the only difference in substance between the two approximat ions is in the fact that g in (2) or (4) runs over the range [0, 1] while g in the Gaussian versions can take any value in [O,oo] .

As an example, suppose s = 3, t = 1 and g = 5/ 12. Then we get a probability range [3/ 8, 15/ 16] from (2) . Now (4) reconstructs s = 3, t = 4. If the ucxt trial produces success, the range becomes [.15, .95]; if failure, [.29, .85] .

In the Gaussian approximation, we have g = 1.5, lead­ ing to an initial range of [.55, .88], and subsequent ranges of [.62, .95] (success) or [.11, .76] (failure).

§3. Implementation issues

Existing formalisms of. non-mm10tonic reasoning gen­ erally proceed by attempting to determine whether or not a default inference will be valid before drawing it. Thus, before concluding that the bird Tweety can fly, we first try to prove that he can't; if the proof fails, we draw the inference that he can.

There are well known difficulties with this. The first is that the problem of proving that Twecty can't fly is only semi-decidable, and imple111entatioH~ of this scheme there­ fore tend to be painstakingly slow (at best!) . The second is that the need to use the appearance of a. new datum, such as the fact that Twecty is an ostrich , to reverse an earlier conclusion requires the introduction of a new formalism, such as truth maintcnaucc [2]. Probabilities provide a way around hoth of these dilliculties hy tll<trking the conc.lus ion of a proof to indicate that il: may he subsequently reversed in the presence of stronger contradictory evidence. We are not claiming here that they can replace a truth mainte­ nance system; it will still be necessary to store inform-.tion regarding either the use to which information has been put (in a forward-chaining system) or the source from which infomtatiou was obtained (in a backw;u·d-cha.ining one) .

lu the fH<~s<~ IICC of au <tdeq ual.<~ rule for prob<thilistic combination, llt<trty of the attr<tctivc properties of <1 n:ason maintenance system can be incorporated into a probabilis­ tic one. When the truth value of some conclusion changes as a. result of the appearance of new evidence, earlier infer­ ences made using this conclusion can be repeated, with the change in probability therefore propagating to the results thai were <krivcd from it.

3.1 Tags

Suppose that we are in fact considering ranges of prob­ abilities instead of specific values, <uHl let P be the set of all closed subinterv;ds of [0, 1]. Then there are six natural mappings from P to [0, 1], given by:

Intuitively, t corresponds to the extent to which a given statement is confirmed by the available evidence, and nil to the extent to which it is disconfirmed. mass reflects the completeness of our probabilistic information, and unc the incompleteness of it. Finally, poss and poss-not correspond to the degrees to which the statement might be true or false respectively.

We wiJI refer to these six functions as tags; they pro­ vide a natural and uniform framework in which to consider either the truth or falsity of any given proposition, or the extent of our knowledge about it.

3.2 Use of probability to limit inference

Non-numerical inference techniques must of necessity run to completion; there seems to be no way to use quali­ tative information to terminate the inference process. This can be avoided if quantitative methods are used.

There are two ways in which a probabilistic inference can be shortened. Suppose that we arc trying to prove some proposition p; the first cutoff can be implemented by not including in our analysis any inferences which will affect the eventual probability of p by less than some small value c 1 . For example, it never rains in southern California (or at least only very rarely) [6]; if we arc trying to show that our beach party will be a success, we do not need to consider rain as a reason for it not to be.

A second and independent way to shorten a proba­ bilistic inference is to assume that if the probability ex­ ceeds some value c2 (alternatively, if the result of applying some Lap; t.o t.he probability mnge exceeds c2), the iufer­ CIIC<~ is complete. H the All-Star game is heing played in Los Angeles on the sami! <lay a.s our beach party and we have a fri<·nd who is giving away tickets to it, then we are probably better off picking ;uwther day for the party than looking for an esoteric proof that it will be successful after all.

It is worth considering the effects on the inference pro­ cedure if we select. extremal values for c1 or c2 . Ta.ldng c1 == 0 allows allows all relevant information to be con­ sidered, while c2 = 1 ensures that the entire deduction will not be stopped early. This combination therefore re­ sults in all attempted dcrivat..ions running to their eventual conclusions as described at the beginning of this section.

(And as such, is no more efficient than any of the more conventional techniques for non-monotonic reasoning.) If we select c1 = 1, then only monotonic inferences will be considered, while c2 = 0 results in the rather preemptive strategy of considering only the first bit of applicable in­ formation . Finally, the combination c1 = c2 = 1 allows us to perform standard monotonic reasoning using a proba­ bilistic database.

3.3 Probabilistic resolution

The inference technique of resolution can be extended to deal with probabilistic information. Consider the deri­ vation of flies(Tweety) from bird(Twcety) and bird( x) ~ jlies(x):

Unifying the above two expressions by substit uting Tweety for x and resolving the results gives T ~ jlies(Twcety).

In general, we will view resolution as the combination of expressions of the form

where p and s are either positive literals or conjunctions thereof, and r and t arc either positive literals or disjunc­ tions thereof.

Intuitively, if p and s hold, then from the first rule be­ ing resolved in {5), either r holds (in which case the concht­ sion of the resolution is valid), or q holds, in which case ihe second rnle can be applied to conclude that t holds. The likelihood of the conclusion being probabilistically valid is therefore at least the product of the likelihoods of each of the original rules being valid.

The situation is complicated in the probabilistic case by the need to treat negation in a uniform fashion. The reason for this i~ that. lhe proh;thilit.y range assigned to the st.at.ctnent binl(x) -· jhes(:c) will ;tl ~o <:ontain information abont the likelihood of a randomly selected hird not be­ ing able to fly- in other words, ahout the validity of the statement bird( x) - · ·flies( x) .

Since the bird(x) -> · flies(x) can be rewritten as bird(x)/\jlies(x) ~ 1. , the effect of this is that it is possible to resolv<~ pairs in which the same clause appears in each conclusion. ln general, tltc the implication p ---> · (q V r) implies p 1\ q ~ 1., and we can resolve this with s ··--> q V t to get p 1\ s -> t. It follows that given the pair of rules

to obtain there will be two contributions to the confirmation of p 1\ s -> r V t given by the product of the confirmation of s - > q V t and the disconfirmation of p --> q V r (as above), and by the prod net of the dis confirmation of s - -> q V t and the confirmation of p -> q V r.

3.4 Implementation results

The ideas described in this paper have been imple­ mented in the expert system building tool MRS at Stan­ ford. We will conclude by describing some of the details of this implementation. Additional details can be found in [5].

MRS [3] is a logic-based expert system building tool. It supports a variety of inference methods, including for­ ward- and backward-chaining. Inform<ttion is currently en­ tered into MRS on two "levels". The meta-level is used to store information regarding control of inference or pro­ cedural attachments for the various MRS primitives (a demon is a procedural attachment to the primitive that stashes an item in the database, for example) . The base level is used to store more conventional expert system-type information about the domain in question . Although the inference methods for the two levels <ue distinct, all of the information is stored in a single database.

The probabilistic implementation associates to each fact in the database a pair ( c . d) corresponding to the probability range [c, 1 - d]. The probability ranges are thought of as the "truth values" of the propositions, and are combined using Dempster's rule as described in [4] .

Tags arc used to reduce the probability ranges to spe­ cillc values, as described in sectio11 4. 1. This has the im­ lllediatc advantage of unifying the treatment of negation within MRS itself- where the two propositions (not (os­ trich fred)) and (ostrich fred) had previcmsly been considered to be unrelated, they arc now simply differing apects of the same object, and interact more convcuiently with, for example, (known (ostrich fred)) or (unknown (ostrich fred)).

H.ea~on m;tint.ancnce facilities have lH~en implemented i 11 t.he forward chaiJH~r only. W ltt~ ll a rult! of inl't~rc~ nce is invoken, the truth value of the instantiated version of the premise is stored, along with infonn;tl.ion concerning the instantiation itself. The next time the rule is invoked, if the mass of the difl'ercnce between the previous truth value and the current one is no greater il1an the inference t:utolf c 1 , no action is taken . The effect of this is to avoic[ propagating a change in the database to a point. where it will have no significant elfect on the probabilities of the statements involved.

The backward chainer has been implemented using t.ltc pair of cutoff's described in the previous sccticin. Tim­ ing tests clone with c1 = c2 : -o l (s tandard monotonic inferencc only) indicate that the incorporation of the-prob­ abilistic facilities has at most a small effect (perhaps 5%) on the system's monotonic performance.

The most important experiment remains . Compara­ ble implementations of a large-sca:Jc non-monotonic prob­ lem using both probabilistic and non-probabilistic methods are needed; it is only when comparisons can he made that it will be possible to draw secure conclusions.·

§4. Conclusion

The efficacy of using probabilities in a non-monotonic inference system is both a theoretical and an experimental question, and we have attempted to address both issues in this paper. Our theoretical arguments dealt with the pos­ sibility of using probability ranges and Dempster-Shafer theory to sidestep the Bayesian need for a priori probabil­ ities.

The experimental question may well be more interest­ ing, but cannot be settled until a great deal more work is done on full-size non-monotonic systems that do and do not usc probabilistic inference methods. The work we have completed at Stanford seems to support the arguments we have presented, but no hard and fast conclusion can be drawn without a great deal more experimental evidence.

Acknowledgement

The author would like to thank Mike Gencsereth and John McCarthy for many enlightening (if heated) discus­ sions, and Russ Greiner for the care with which he exam­ ined an early version of this paper.