Extended Plausible Inference

ABSntACT

A generalized theory of plausible inference has been developed, extended to arbitrary expressions of propositional calculus from Shortliffe and Buchanan's original MYCIN formulation. The theory represents uncertainty of belief, and invokes four rules of inference, instead of the two of standard logic. Areas of application include diagnostic problems and deciding between alternative hypotheses. The theory has been implemented in the PI system. The intended area of application for PI is the trouble-shooting of a failed spacecraft, and the solution to a simplified problem drawn from this area is described.

FOREWORD

After this paper was submitted for review, the work of two mathematicians,· Arthur Dempster and Glenn Shafer, was brought to my attention. Shafer has published a book, 'A Mathematical Theory of Evidence', which establishes a rigorously founded theory of reasoning under uncertainty (1]. Plausible inference is based on the uncertainty formulas devised by Shortliffe and Buchanan, who took pains to point out that their formulas were ad hoc [2) or (3]. Comparison with Shafer's formulas reveals that the formulas employed in plausible inference must be revised to be correct. The principal errors are of two kinds: neglect of conflicting evidence, for which the conjunction is false with certainty; and neglect of set inclusion (whereby some assertions either may or may not be arranged as subsets of others).

In particular, Theorem 10.4, on page 224 of the paperback edition of Shafer's book states that the minimum rule for conjunctions (support for a conjunction is the minimum of the supports for its arguments) applies if and only if the assertions that are the arguments are 'consonant'; i.e., that they can be arranged by some criterion for set inclusion and accordingly do not support conflict in the evidence. This, of course, also applies to the maximum rule for disjunctions. Shafer gives the corr~ct rules for heterogeneous and conflicting

· This paper represents the results of one phase of research carried out at the Jet Propulsion Laboratory, California Institute of Technology, under contract with the National Aeronautics and Space Administiation.

EXTENDED PLAUSIBLE INFERENCE

Leonard Friedman

Jet Propulsion Laboratory, C.I.T. Pasadena, CA 91109

evidence in paragraphs 4 and S of chapter 4. Heterogeneous evidence refers to conjunctions which may be true, whose arguments cannot be arranged in s~bsets, and which may support conflict in the evidence. Support for this type of conjunct is given by the product of the support for the arguments. Conflicting evidence refers to conjuncts whose support is guaranteed to be false with certainty (support = 0). Thus we discover that the principal impact of the corrections to plausible inference is on the formulas for calculating the support for conjunctions and disjunctions, and the knowledge required as to when to apply which formula.

Happily, the conceptual framework of plausible inference survives intact, as do many of the formulas. For example, the formula for 'credibility summation' is correct for consonant and heterogeneous evidence. Dempster's rule for orthogonal summation reduces to the same result for those cases. A different summation formula results when evidence is guaranteed to be conflicting. We retain the assumption of directed propagation of support in implications, whereby conditional support is proportional to a 'relevance factor'. These calculations, based on the relevance factors or Al's, are not considered by Shafer. Various inconsistencies are removed by employing Shafer's formulas. In particular, the law of the excluded middle always holds, as well as normalization, so that belief in a defined 'frame of discernment' or universe of discourse always adds up to 1, and the conjunction of support for and aaainst an assertion is always certainly false.

Note also that two other proceedings rely on Dempster and See (4] and [S). papers in Shafer's these work.

BACKGROUND

One of the basic assumptions of standard logic is that the truth value of predicates is known with certainty. This assumption is justified for some domains of reasoning, but is not valid when, for example, we are confronted by problems of diagnosis or hypothesis generation in scientific experiments. In such domains there may be conflicting evidence for . or against particular assertions and a human, when reasoning about them uses measures of belief other than true or false to characterize his uncertainty.

Logicians and philosophers have studied this phenomenon for many years and have proposed various criteria as formal models, particularly for confirming evidence. The mathematician, George Polya, wrote a book about the modes of reasoning employed by fellow mathematicians, and emphasized the importance of uncertainty even in mathematical reasoning. He suggested that humans used non-standard rules of inference that included confirmation and denial in addition to ponens and tollens [6]. Recently Zadeh and his school have developed the concept of fuzzy logic which deals extensively with uncertainty [7]. An approach which has been useful in a limited domain of medical diagnosis was formulated by Shortliffe and Buchanan for their AI system, MYCIN. MYCIN is a production system and reasons only in a confirmation mode for a particular subset of logical expressions in the propositional calculus.

This paper presents a generalization of Shortliffe and Buchanan's theory to the four modes of reasoning suggested by Polya, and to arbitrary expressions of the propositional calculus. The resultant theory of reasoning with uncertain beliefs is called plausible inference and has been implemented as the PI system. PI has been applied to the trouble-shooting of a spacecraft after the execution of an experiment has failed, and this example's operation will be described briefly here.

Shortliffe and Buchanan (hereafter referred to as S and B) give an extensive discuasion of their choice of measures of uncertainty as functions of conditional probabilities. In particular, they point out that humans reasoning about uncertain assertions do not· employ evidence FOR an assertion to measure their disbelief. Independent evidence is required in normal human reasoning to bolster disbelief in the assertion. As a result their model and ours treat measures of belief and disbelief as independent quantities.

This is asserts unlike P(-Z(A) conditional probability, which 1- P(Z(A). It is evident then that these measures are NOT probabilities, however tempting it may be to regard them as such. We shall not duplicate Sand B's justification of the theoretical foundations of the measures we are using which is fundamentally based on its success in modelling human reasoning. Schefe has also investigated the foundations of this model, and concludes that it is valid [8]. In Schefe' s opinion, Zadeh's 'Linguistic Modelling' is 'inadequate' (his wording).

We shall begin by comparing the basic reasoning methods employed by or available to PI with those used by the MYCIN and PROSPECTOR systems . Then we shall describe the example actually running. Finally, the details of the underlyina plausible inference theory will be explained.

COMPARISONS AND POTENTIALS

MYCIN and PROSPECTOR employ similar inference strategies to reach conclusions. PROSPECTOR is described in [9]. In both systems a tree structure of evident·ial assertions supporting various hypotheses converges to several root conclusions. (See Fia. 1) The reasoning is essentially one directional and in the confirmation mode, with the evidence given possibly supporting more than one conclusion. The choice of conclusion is then made on the basis of degree of certainty or subjective probability assianed to each conclusion that is supported by the evidence, with the most certain being chosen. Dearee of certainty is propaaated to the conclusions by setting up a weighting system of numbers assigned to each arc linking the nodes. The arc numbers are proportionality factors that determine the amount of confidence transmitted from evidence towards conclusions. Once confiience in the evidence has been assigned, various combining rules determine the propagation of certainty toward conclusions, with the system working in the confirmation mode.

The PI working example has a tree structure shown in Fig. 2. The nodes converge to a goal state which is the root of the tree. In this example, we assume that the nodes constitute a plan of physical processes and conditions leading to the goal state, and that, after execution of the plan, the goal state is not achieved; i.e., it is false. Thus we are seeking to isolate the cause of the failure in one of the leaves of the tree. We proceed from the root of the tree toward the leaves, attempting to isolate the failed leaf by pruning off those parts of the tree closest to the root that are still working; i.e., that are true. Once again we are proceeding in essentially one direction, in a rather rigid manner as compared with a human, but in this example PI employs two modes, tollens and confirmation.

PI also requires the same type of numbers assigned to its arcs, and I have given them the name 'relevance factors'. In both the MYCIN and PROSPECTOR systems they are determined by the subjective estimates of human experts in the knowledge domain, and are not altered except for system debugging purposes. By contrast, for the type of solution method described above, the PI system has been provided with a simple heuristic that permits it to estimate how the value of the relevance ~actors should be altered in a given neighborhood, on the basis of evidence it receives. This ability enables it to work on problems for which the relevance factors are not known in advance, and prepares the way for embedding in a learning system.

Clearly we are not exploiting the full power of the PI system by using only the solution methods illustrated by Fig. 2. A far more interesting and efficient approach is described by Fig 3. We presume that for any realistic problem the tree of Fig. 2, describing the states and actions, will be very large. Fig. 3 shows only a small neighborhood of that tree. What a human very often does, when confronted with such a problem, is to select, on the basis of (usually unconscious) criteria and inferences, a specific neighborhood of the web of relations, and test the function represented by that neighborhood.

An augmented PI might be able to do the same thing by using a set of criteria stored in a separate knowledge base. Examples of such rules are, 'What was the last thing altered since this plan worked correctly?' or 'What is the cheapest test that can be performed verifying the nodes of the tree?'. Such a body of knowledge would form a meta-rule domain of the kind described by Davis, and the same PI inference engine that reasons about spacecraft experiments could be used to reason about where to choose the next neighborhood for testing[10]. In fact, in this case all the nodes of the tree are candidates for control selection, making his approach imperative.

Let us assume that either an augmented PI system has selected a node for checking as shown in Fig. 3, or simply that a human has suggested it. If a test is then made that determines the truth or falsity of that node, a degree of certainty can be assigned to that node. The PI system already has the capacity to propagate that change in certainty in both directions, thus providing much more information on the choice of the next test to perform.

AN EXAMPLE OF FAULT DIAGNOSIS

The specific example implemented is intended to exercise some of the belief propagation processes of plausible inference. It also demonstrates the feasibility of writing an algorithm for estimating relevance factors, which measure the strength of binding between antecedents and consequents as evidence is adduced.

This is an unrealistically small problem. (See [11] for a detailed description.) The pruning methods employed are clearly too costly for large plans so long as the method of solution is that of making every test from the root towards the leaves as in Fig 2. The example itself is taken from the application domain being worked on at JPL, and uses as its knowledge base a model of normal operation of a spacecraft generated by another operating module, the JPL planner, for commanding the spacecraft.

The personnel monitoring the spacecraft are rarely experts in all of the complex sub-systems that can fail. Therefore it would be most useful if these already available plans of normal operation could be made to serve as guides for focussing attention on specific subsystems, a kind of spacecraft first-aid. For in-depth fault diagnosis, detailed models of failure modes would be required, just as doctors and AI researchers have built up models of disease to guide automatic diagnosis systems.

The planner is system which generates specified goal state. the part of a plan for The actions the JPL AI achieving a leading to aub-aoal atatea are lt.ited to the repertoire of co .. anda of the apacecraft coaputer, 10 that when theae action· are atripped out after a plan ia aenerated, they conatitute a valid proaraa for the coaputer. Tbua the planner is a aiaple autoaatic code aenerator. It uaea a repreaentation of phyaical cauaality borrowed froa Chuck Rieaer'a Coaaon Sanae Alaoritba wort [13]. Fiaure 4 ahowa the repreaentatioa for an action cauaiaa a atate provided that the pre-conditiona, atatel and atate2, are firat true.

RBPUSENTATION OF CAUSALITY Fiaure 4

In Fiaure 5 a aiaplified plan ia ahown for tranaaittina a aianal froa the apacecraft to earth. The action of 'Ground Antenna Receivina' ia required, plua the pre-conditioaa that (1) the apacecraft ia poiated correctly at the earth, and (2) · aianal waa tranaaitted by the apacecraft. The pre-conditioaa, in turn, require action· and pre-condition· to aate thea true, etc. to the desired level of repreaentatioa of the phyaical proc····· involved.

To reaaoa in a loaically correct aanner about cauaal relation· of thia type require· a apecial function, the CAUSAL apecialiat, that can tate into account the teaporal relatioaa, verifyiaa that the pre-condition· were aade true before the action proceaa waa atarted. The IPL planner baa auch a fnaction, but a aiailar oae haa not yet been incorporated ia PI. laatead, the loaical relationa have beea approziaated by repreaentina the action and pre-condition· ·· arauaenta of a conjunction iaplyina the aubaoal or aoal atate. If the aoal atate is the aaaertion A, it aay be repreaented by [(Z1 A ··· A Zn) -> A], where Z1, , Zn are the arauaenta repreaentina action and pre-conditiona.

In operation, we aaauae that a uaer would have firat aenerated the plan to obtain a co .. and aequeace that would run the apacecraft computer to achieve the deaired aoal. If, after coaaandina the apacecraft to execute the plan, a failure were detected, that iaforaation would be entered into the data baae ·· ['Sianal Received' ia falae.]. Tbia reaulta in a propaaation of neaative credibility to all the conditiona (action· and pre-condition·) on which the failed atate depended. le alao propaaate a 'aarter' truth value of PF, atandina for poaaibly falae, to theae conditiona. Aa far as inference ia concerned, PF behaves exactly lite falae, except that it cannot override an F or T atate. Tbia ia becauae it ia baaed on a priori or preauaptive evidence only, whereaa F or T are baaed on direct evidence.

The PI ayatea aodela event aucceaaion by uaina PLANNER-lite context layera. Tbua it can deal with non-aonotonic loaic, where a aiven atate can be true or falae with varyiaa dear··· of certainty ·· aucceaaive action· are taken. A aon-aonotoaic inference rule has been impleaeated in the followina aanner. Suppose a aoal atate depend· on n conditions beiaa true to be attained. If, after executina the process, the aoal atate ia not obaerved, thea we conclude that one of the n condition· muat be falae, and all are possibly falae. If, after perforaiaa appropriate testa, a huaan aathera evidence that one of the condition· is true and eater· that fact, it aay be elt.inated froa coaaideratioa ·· a cauae of failure, and belief in the falsity of the reaainina conditions should increaae.

If all but one condition ia eliaiaated in thia way, PI conclude· that the reaainiaa condition auat be falae. If this condition dependa in turn on otbera, the ···· proceaa aay be applied aaain to narrow down the auapected fault to a leaf of the tree. Of course, if at aoae ataae teat ina eatabliahea that all the condition· on which a aiven failed condition directly depend are true, then PI conclude· that the failure condition ia not repreaeated in the plan.

PI proceed· by reaaonina in the manner just described in either of · two coaputina aodea. The firat aode duplicates the MYCIN and PROSPECTOR approach in that a priori relevance factor· are entered in advance. They conatitute a human eatiaate about the ~ertainty of the falaeneaa of the arauaeata of the aatecedent conjunction, aiven that the conaequence ia false. The aecond ia a default mode, in which there ia no auch information. In default, the proaraa counts the nuaber of arauaenta and aaaiana a relevance factor of 1/n for n arauaenta. For either aode, A is either falae or poaaibly false and the Zi are poaaibly false. If a aubaet (Zj} of arauaenta of the conjunction are then ahown to be true, the reaainina arauaenta fora a new aubaet {Zi} that are possibly false with increased certainty. Tke relevance factors, Al'a in our notation, are then given by

where C(Zj) ia the dearee of certainty or credibility of Zj. The aiaple ratio 11 reduced to the dearee that we lack coafldeace in the bellefa of the factors teatina true. If there are three factors, then in the default aode the Al'a are all 1/3 without teat tnowledae. If one of the factors has been shown to be true with certainty, we aet Alnew · 1/3 I 213, or Alnew · 1/2, aa it should be. Fiaure S ahowa a priori relevance factors entered. For this aode, if the Groaad Antenna Receivina tested true, we would aet Alnew .3 or .7, for the reaainina PF factora, reflecting the huaan judaeaenta accurately.

E1TENDED PLAUSIBLE INFEIU!NCE

One of the basic concepts of plausible inference ia credibility. This la a aeaaure of the certainty that a aiven assertion A i1 true or false, and is denoted C(A). It la a nU8ber lyiaa between -1 and +1. -1 denotes falee with certainty, +1 repreeente true with certainty, and 0 stands for no infor.ation. Inter.edlate values stand for varloue deareea of certainty. (Thie quantity ia called the Certainty Factor by S and B. I have introduced a new notation that clarifiee the role of the par .. etere, and peralta repreeentina many equations by a einale equation. For thoee familiar with Shortliffe and Buchanan's notation, Appendix I define· the equivalent ter.e.)

In standard propoeitional calculue, a eat of assertions may be linked by connective· euch ae AND, OR or IMPLIES. If any aesertion linked to others by euch connectives chana·· truth value, this 'disturbance' aay be propaaated to the linked assertions by well-known rulea. The calculu1 of plausible inference coneiats of rules to deter.ine the propaaation of credibility to the linked assertion·. and peralta propaaation of dieturbances in directions forbidden in propositional calculue.

There are two distiactively different waye in which this propaaation aay tate place. The first applies only to the antecedents and consequents of iaplicationa and is called directed propaaation. The second way is deduced propasation; the assertions to be chanaed auet be deduced fro. the circU8atances. Antecedent· or consequents transait all or a fraction of their credibility to their partners, and only their partners, when they chana· credibility. If we resard assertions linked by iaplication as nodes in an iaplication apace, then we have propaaatioa alons the arcs connectina linked nodes. (See Fig. 6) The aaount propaaated depends on their own credibility reduced by a factor called the relevance factor, Al, defined below. The relevance factor may be reaarded as a directed quantity, aoaewhat lite a vector, while credibility is lite a scalar. Fia. 6 show· that there are at least four Al's for every node pair linked by Deduced propaaation applies to the credibilitiee aeeociated with the connectives AND, 01, and IIPLIBS theaeelvee rather than the antecedent· or coaeequente of iaplicatione. The collective credibilitiee of euch expressions are aivea by the aa&t. .. or ainiaU8 credibility of one of their ara .. eate. This aethod of aeaianins credibility wae ··aaeated by Zadeh [7). Deduced propaaation alao applies to a case such as an OR expreaaioa that ia defined true. If all but one of ita araU8enta ia taown to be false, the reaainins ar&U8ent auat have a positive credibility reaardleaa of which one it aiaht be. This difference in the way credibility is propaaatod aodela our intuitive notion that the believability of the ... bars of an lapllcatlon is linked; whereae, the ara .. enta of a conjunction or diajuactioa are treated as independently believable factors.

Aa pointed out above, we desire to aodel the independence of coaflralna and denyins evidence, 10 we aeed separate aeaeure1 of aaouat of belief for or aaaiaat an aeeertlon 'A'. These are denoted I(A) aad D(A), etandlna for the ... of all increaeata to belief in A and the ... of all decreaeata to belief ia A. The a ... ation is noa-liaear aad will be defined below. Aleo,

In words, the belief in A true equals the disbelief la A false. We define

Credibility caa oaly be deter.ined calculated I and D. Also, by lncreaente and decreaenta, we aet after hav ins lnterchanslng

the introduce a nU8ber A, to represent or decreaeat propaaated between

· ARCS ARE UNitS I(TWIEN ANTt:CEDOITS AND CONSEQUENCES. · NOOES ARE ASSERTIONS.

antecedeat and conaaquant notation ia: of aa i .. lioatioa. Oar

A(ZJA), tJaa propaaatacl from A to Z, wJaara 0 i A(ZJA) i 1. or claor ... nt

There are three caaea to diatia,.iaJa in ooapatina the tranafar of belief between antaoaclanta ancl conaaquanta in an iaplication. Caaa 1 appliaa when neither the antecedent nor conaetaent ia aa assertion with aultiple ara ... nta; i.e., aaither A nor Z ia an aaae~tion iaYolviaa AND, 01, or IMPLIES. Caae 2 appliea when one aaeertioa Jaaa aultiple ara ... ata and oae loea not. Caaa 3 appliaa when botJa antecedeat ancl oonaequeat haYa aultipla arauaeata.

Caaa 1. Neither aultiple arauaenta. antecedent aor ···

The fundaaental rule of plauaible inference ia:

A(ZJA) · A1(ZfA) · IC(A)I ,

where Al ia the Yalae of A whaa JC(A)f ia 1, A ia tJae aaaertioa with cJaaaaad creclibility. Z ia tJae taraat aaaertioa. Propaaatioa ia from A to Z. TV(A) ia trutJa-value of A.

If A -> Z, and TV(A) · T;

A(ZJA) is added to I(Z); Poaeaa

TV(A) · F; A(ZJA) ia added to D(Z); Denial.

If Z -> A, aad TV(A) · T;

A(ZIA> is aclded to I(Z); Coafir.atioa

TV(A) · F;

A(ZJA) is add.d to D(Z); Tollaaa.

Note tJaat unlike propositioaal cal .. las, ia plaasible iafereace, belief is propaaated ia the Denial and Coafir.atioa aodas. Nota also tJaat Ponena and Confiraation are eqaiYaleat, as are Denial and Tollens. Tbis aqaiYalaaca aaaaasts that plausible reasoniaa could be s,.aatric; i.e., for a aiven knowledae base, if avery aatacaclaat and consequent were interchanaed, toaathe~ witJa their Al'a, the ···e iafareace1 would be aada liYan the s1me evidence. Iadiffareaoa to the direction of reasonina would aodel what appaara to be a 1iailar huaan capability to reason with antaceclaats and conaequenta interchanaed. Initially, as this system was developed froa propositional calculus, exclusive u1e of a aoa-1y..etric coaaactiYe, implication, for cliractad propaaation of credibility concealed thia po1sibility [13].

Another connective il aYailable for repre1entina directed propaaatioa tJaat is symmetric, however. Equivalaace differ· from U.plication only with respect to oaa truth v1lue. When antecedent is fal1e and consequent i1 traa, implication is true and equivalence is fal1e. There are situations wJaare aqaivalaaca aiaht be a

more 1uitable connective to eaploy ia the data b···· apply. in which case 1,..atric raasonina Such lituatioas bear invaltiaation.

Note al1o that ia plau1ible raa1onin1 the conaactiYas have a cliffaraat aaaaina than tJaat conYayed ia propo1itioaal calculu1. Tbu1, in plaa1ibla ree1oaina. u1e of the equivalence coaaective would only iaply a connection in belief, not loaical equivalence. Only ia tJaa lt.itina caae where plausible infareaca deaeaaratal to propo1itioaal calculus cloa1 loaical equivaleace hold. Tbi1 would occur wlaan tJae releYanca factors were all equal to 1 aad tJae credibilitie1 were liaited to 1 or -1. In what follow· we shall uae the iaplicatioa conaactive becau1e of ita fuiliarity, but couupoadiaa foradu for aqaivalaaca are aa1ily derived.

c ... 2. aultiple Oae ara .. aat of tJaa iaplication hal arauaants. Tba other arauaent doe· not .

Tba loaical stetaaaat1 of areataat iatereat are those involYiaa the AND and 01 coaaective1. To avoid the confusioa of too auch detail, we 1hal l aive tJaa rule· of Caaa 2 only for tho·e coaaactivas. Tbe corre1poadiaa rales for antecedent· and con1equant1 wJaich are tJaeaaelYes iaplication· ia aiven ·ia Appendb II. All iaplication rulea are deriYed from the AND/OR rule a in any evant.

Before aiYiaa tJaa details of Case 2, we nota that the followiaa ···uaption· are aada for plausible inference. If I(Z) · 1, thea aYidance for di1balief i1 di1reaardad. If D(Z) · 1, then evi .. ace for belief i1 di1reaarded. If both equa l 1, then we have contradiction. The calculation of credibility ia the aaae reaardle·· of the order of application of evideace (co .. utatiYity).

Cue 2a. [(CONN Al ··· An) -> Z], or [Z -> (CONN Al Aa)) ·

wJaau (CONN Al ··· Aa) . h tJae 1ource with cha11aed cradibil i ty,

Z i1 the taraet a1sartion, CONN ia oae of AND, OR, NOT AND, NOT 01.

Cue 2a-1.

Jf CONN ia AND or NOI' 01 with TV(CONN) "' T, 01 or NC71' AND with T'V(CONN) "' F,

thea after calculatioa of the collective credibility of the 1ource expreaaion, ca1e 2a-1 reduces to Ca1e 1 with A · (CONN Al ··· An). The reduction i1 done accordina to the followina r ulea:

Let the 1et Al ··· An be repre1ented by (Ai} .

For CONN · AND or NC71' OR:

I(A) · ain ( I(Ai) },

D(A) · aax ( D(Ai) ),

where -Ai i1 1ubstituted for Ai in NC7I' OR.

For CONN · 01 or NOI' AND:

I(A) max HAil l,

D(A) min D(Ai) l,

where -Ai is substituted for Ai in NOT AND.

Therefore, A(ZIA> A1(ZIA> · lc<A>I. added I(Z) for AND, NOT OR true, and to D(Z) for NOT AND false. to OR,

The extrema are always calculated with+1>-1.

Case 2a-2. (Convergence)

If CONN is AND or NOT OR with 1V(CONN) F,

OR or NOT AND with 1V(CONN) T,

the credibility transferred to Z is the credibility summation of the arguments of A, calculated as if each arrument individually propagates credibility to Z. Credibility summation, defined here, guarantees that the sum of n summands is less than 1, provided that each summand lies between 0 and 1.

Let 0 ~ Yi ~ 1, then

Note that credibility summation satisfies commutativity and associativity. We can now give a precise formulation of Case 2a-2, which is a case of convergence because many arguments are contributing support to one assertion.

where ID(ZIA) is added to D(Z) if: CONN = AND or NOT OR, 1V(CONN) = F;

and 6(Ai) 1, for C(Ai) < 0,

6(Ai) 0, for C(Ai) > 0.

ID(ZIAl is added to I(Z) if: CONN= OR or NOT AND, 1V(CONN) = T;

and 6(Ai) 1' for C(Ai) 0, 6(Ai) 0, for C(Ai) o.

(-Ail substitutes for (Ai) in CONN's containing NOT. (De Morgan's theorem)

Let us sum up Case 2a in words. For a conjunction that is true, the belief that is transmitted is no more than the least belief in its arguments. For a conjunction that is false, the more arguments that are false, the more strongly supported is disbelief in the co-member of the implication. The arguments which are true make no contribution. For a disjunction, true and false are interchanged.

Case 2b. (Fanout)

[A-> (CONN Z1 ··· Zn)], or [(CONN Z1 ··· Zn) ->A] ·

A is the source assertion that has changed credibility.

Z = (CONN Z1 ··· Zn) is the taraet expression. CONN is one of AND, OR, NOT AND, NOT OR.

Then, A(ZiiAl = A1(ZiiA) · IC(A)I.

For AND, NOT OR,

I(Z) min I (Zi) }, D(Z) max D(Zi) } .

For OR, NOT AND,

(-Zi) substitutes for (Zi) in CONN's containing NOT.

In words, when a single assertion provides support to a conjunction or disjunction in an implication, first the increment or decrement to the belief in each araument must be found as if there were only the assertions A and Zi (Case 1) . Then the appropriate extrema will aive the belief in the conjunction or disjunction.

Case 3 . Both arauments of the implication possess multiple arauments.

Once aaain, we shall aive conjunctions and disjunctions, Appendix III rules involvina consequents that are implications. rules only reserving antecedents for for or

[(CONN A1 ··· An) -> (CONN Z1 .·· Zm)),

or [(CONN Z1 Zn) -> (CONN A1 ··· An)].

Case 3a. If the CONN of the source expression satisfies the conditions of Case 2a-1, the source expression supports belief in the target as a sinale assertion, calculated as an extremum as in Case 2a-1. The resultant belief in the taraet expression is then calculated as a fanout from the collective source as in Case 2b.

Case 3b. In all other cases, the source expression is treated as a convergence as in Case 2a-2. Now, however, the convergence is from all Ai's to each Zj. After the credibilities of all the Zj's have been calculated, the collective credibility of Z is aiven by the appropriate extremum. Equivalently, this may be calculated by fanning out from each Ai to all the Zj's, and summina the support provided by successive Ai's. The results are the same since credibility summation obeys the associative law.

VALIDITY, SELF-REFERENCE, SAME-SOURCE, AND EXCLUDED MIDDLE.

As S and B noted, plausible inference is only an approximation, and depends on assuming the independence of convergent assertions just as Bayesian probability does. To the extent that the assumption is violated our calculation of credibility will be in erro~. This is borne out when we examine particular cases such as self-reference.

Because we are allowing arbitrary expressions of the propositional calculus, assertions of the form [(A VA) -> A] must be considered. Care must be taken to prevent the application of credibility summation to all self-referent expressions. An expression like the above, if credibility were allowed to propagate blindly, would lead to

a<AIA V A) = a<AIA> + a<AIA> - A<AIA> · a<AIA>.

which is clearly in error if A(AJA) is not either 0 or 1. We therefore define 1\l(AJA) = 0 for all modes. An axiom of plausible inference is that there shall be no propagation of credibility from an assertion to itself.

A similar difficulty arises when we model sequential events by using planner-like context layers. Such modelling permits a single source of support to change credibility only slightly in a new context layer, in effect leading to adding its previous contribution to itself. This situation can be avoided in implementation by always removing the previous contribution if the present contribution is from the same source as the previous one. The contribution from other sources is then given by

where B is the balance left, T is the total credibility summation, and S is the old contribution from the same source. Obviously, care must be taken not to try to remove a contribution of certainty, S = 1. Such an attempt is regarded as contradictory. Note that this overcomes a difficulty in S and B's monotonic system. Plausible inference is rendered non-monotonic by the use of the above equation.

The law of the excluded middle in propositional calculus may be stated as D(A A-A)= 1. In plausible inference, the equation no longer holds, because D(A A-A)= max{D(A),D(-A)J For A true, this would be simply D(-A). This seemingly bizarre result does reduce to the normally accepted value when IC(A)f = 1. We could interpret this as a statement about credibility rather than truth.

[Note added after submission. Use of Shafer's equations for this case avoids the difficulty. Excluded middle falls under the case of conflicting evidence and is always false with certainty.]

DISCUSSION

The work development. The reported here is still in theoretical generalization of propositional calculus has been completed, but applying it to realistic problems has only begun. Nevertheless, an inference engine implementing the theory has been built, and an example of trouble-shooting, exercising the system, is running. Obviously, realistic debugging is an examplar of the general problem of pruning a large search tree. The methods suggested here for tackling the problem offer the possibility of bringing to bear all the domain specific knowledge available to the system for tree pruning, while avoiding exhaustive search.

APPENDIX I

The equivalent terms employed by Shortliffe and Buchanan are as follows:

Plausible Inference

1. credibility, C(Z)
2. A(ZfA)
3. relevance factor, 1\l(ZJA)
4. I(Z), D(Z)

MYCIN

• (1') Certainty Factor, CF(Z,A)
• (2') ~ffi(Z,A) or MD(Z,A)
• (3') MB'(Z,A) or MD'(Z,A)
• (4') MB(Z,A),MD(Z,A)

Note that Sand B's notation does not distinguish between an increment or decrement to an assertion and the sum of increments or decrements.

Appendix II

The case involving corresponds to Case 2a is: implication which

where A (P -> Q) is the source assertion changed credibility. with

Then, recalling that D(P) = 1(-P),

I(A) max {D(P),I(Q))

D(A) min {D(P),I(Q))

This follows since:

A true is logically equivalent to (-P V Q).

A false is logically equivalent to (P A-Q) .

Case 2al-l. When TV(A) = T, this case reduces 2a-2, with an OR that is true. Thus to

1\(ZIAl = A(ZJ-P) + A(ZJQ)- A(ZI-Pl · A(ZJQ),

where A(ZfA) is added to I(Z).

Case 2ai-2 . When TV(A) = F, this case reduces to 2a-l, with an AND that is true. Thus

1\(ZJA) = 1\l(iJA)·[min{I(P),D(Q)) - max{D(P),I(Q))],

where A(ZJA) is added to D(Z).

In words, when one of the arguments of an implication is itself an implication that has changed credibility, the calculation reduces to case 2a-1 and 2a-2 by substituting the equivalent disjunction or conjunction for the implication. When A is true, the support of its arguments converges on Z, supporting its belief to the extent that NOT P and Q support belief in Z, added together as a credibility summation. When A is false, it propagates its credibility as an implication. Note, however, that when A is true, the convergence rule usually conforms to the more intuitive notion that the credibility of the implication is what is transmitted. This follows because normally the beliefs are (P true, Q true), or (P false, Q false). When that is the case, only one term contributes to the support for Z, the same result as the extremum rule.

Case 2bl. We have another fanout case where

As above, case 2bl reduces to Case 2b. For Z true, we have

a<-PIA> = A1(-PIA> · C(A) added to D(P) or l(P) as A is true or false.

a(QIA> = a1(QIA> · C(A) added to l(Q) or D(Q) as A is true or false.

l(Z) max ( D(P), l(Q) }.

D(Z) min ( D(P), l(Q) }.

For Z false, we have

a(PIA> = A1(PIA) · C(A), added to I(P) or D(P) as A is true or false.

a(-QIA> = A1(-GIA> · C(A), added to 1(-Q) or D(-Q) as A is true or false.

C(Z) =min (D(P), I(Q)) -max (l(P), D(Q))

APPENDIX .III

Case 3al. This is the case where either

[(P -> Q) -> (CONN Z1 ·.· Zn)) or [(CONN Z1 Zn) -> (P -> Q)),

The A term reduces to Case 2al-1 or 2al-2, according to whether A is true or false. A then fans out to the z terms, with or without convergence, as in case 3

Case 3bl. This is the case for

where z = (P -> Q) is the target assertion, and CONN is one of AND, OR, NOT AND, NOT OR. If the (CONN ··· ) expression reduces to a collective credibility as in Case 2a-1, 3bl reduces to 2bl.

If it is a handled as source is convergence, as in in 2bl except that adding support to both appropriate. 2a-2, then it is each term of the P and Q, either to I or D as