Measure-Free Conditioning, Probability and Non-Monotonic Reasoning

1 Introduction

Some analogy has been recently observed between Bayesian approaches to automated reasoning, and non­ monotonic logics [Pearl, 1988, chap. 10]. Independently, the question of representing conditionals in accordance with conditional probability, that has puzzled philosophers in the seventies [Harper et al., 1981] is currently revived by mathematicians [Calabrese, 1987 ; Goodman and Nguyen, 1988] ; they have proposed an algebraic solution that contrasts with earlier attempts relying on possible world semantics and modal logics. At the same time, the debate between various numerical approaches to uncertainty in automated reasoning is still raging (see [Cheeseman, 1988] and the appended comments) ; the main defense of probabilistic orthodoxy seems to be founded on Cox [1946]'s axiomatic approach to conditional probability. This paper aims to put together these research trends and make the following observations : i) measure-free conditioning may be a good approach to the representation of inference rules (such as production rules in expert systems) which allow to capture non-monotonic features of commonsense reasoning; basically, a conditional 'if b then a' denoted by alb, can be true, false or inapplicable in the proposed approach ; ii) Cox's system of conditional probability axioms is an example of homomorphism between a Boolean algebra augmented with measure-free conditionals and the unit interval ; however this homomorphism is not unique, and there is room for other non-additive measures of uncertainty, contrary to what is claimed by probability theory tenants ; iii) viewed as inference rules, measure-free conditionals satisfy the properties suggested by Gabbay [1985], as basic ones for non-monotonic reasoning systems ; these properties were already put forward by Adams [1975] ten years before in a probabilistic logic as recently advocated by Pearl [1988]. The three sections of this where * is the conjunction operation on {0,1}, defmed by 1 * 1 = 1 and 1 * 0 = 0 * 1 = 0 * 0 = 0. Note that (1) obviously agrees with probabilities. Indeed if t(b) = 1 then t(alb) coincides with Prob(alb), and when t(b) = 0, Prob(b) = Prob(a A b)= 0.

This work is partially supported by a grant from the PRC­ GRECO Intelligence Artificielle.

Any proposition x such that t(a A b)= t(x) * t(b) can stand for alb. Note that filling the incomplete truth-table can only be done in four ways, equating alb to one of the following propositions : a A b, a, a H b, b ~ a in a language containing only a and b as proposition symbols, and assuming that t(a) and t(b) can be independently valued (H is the equivalence symbol). alb can be thus identified to a set of propositions and "I" does not defme a connective in the usual sense.

At this point, it is interesting to recall the following definition, due to Goodman and Nguyen [1988], where a, b, x denote elements of a Boolean algebra ffi

A slightly different defmition which turns to be equivalent in the finite case has been independently proposed by Calabrese [1987]. It is easy to verify that (1) corresponds to the semantics of the above definition. Moreover alb = {a A b ~ x ~ -.b v a} where ~ denotes the usual partial ordering in the Boolean algebra, expressing entailment, i.e. b ~ a if and only if -.b v a = 11., where 11. denotes the greatest element in al.

Considering a Boolean algebra al of propositions with tautology 11. and contradiction ([), we can define the set all al={alb, (a, b) E al2}. al can be identified as the subset {al11., a e al}. Indeed t(al11.)= t(a) from (1). Note that in the languag~ of expert systems a subset :K of all al is a knowle<Jge base, % n ~ may be viewed as a factual base, and % n( all al - al) as a rule base. Rules of the form al([) are not very interesting since they are never applicable (t(al([)) = ? , Va). Besides, ala= o(a) = {x, a~ x} and thus contains a and 11. ; thus ala cannot be identified with 11.. This is natural since the rule ala is applicable only if a is known to be true, so thatt(ala) e {1,?}. More generally, if a~ b = 11. then t(bla) *0 only.

It can be checked using (2) that

as already noticed by De Finetti [1964]. The following equalities are worth pointing out

They are in agreement with our interpretation of alb in terms of a production rule. Here we have four ways of describing the same rule.

Since alb= {x, a A b ~ x ~ -.b v a} and cld = {y, cAd~ y ~ -.d v c} the following natural partial ordering can be defined on ffil ffi and will be also denoted by ·~·

This definition was introduced by Goodman and Nguyen [1988]. Letting b = d = 11., it appears that this ~efinition ~xten~s the usual entailment relation in al. In the rule mterpretauon th1s ordering relation corresponds to an entailment relation. Indeed, it means that each time alb is true cld is true also, and that each time cld is false, alb is false too, that is any example of the rule alb is also an example of the rule cld, and any ex~eption to _cld is an exception to alb. It can be checked that (5) 1s compatible with (3), i.e. alb ~ cld and alb ~ cld => alb = cld.

For instance "generally, birds are small flying animals" entails that "generally, small birds fly", with a = "small and fly", b ="bird", c ="fly", d ="small bird". Rule cld has more examples and less exceptions than alb.

Besides, as pointed out in Dubois and Prade [1988], the relation ~ defmed by (5) corresponds in terms of truth-values, to the ordering 0 ~ ? ~ 1, still using the same symbol "~" between values of the truth function, i.e. alb ~ clb if and only if t(alb) ~ t(clb) in all possible situations, and consequently alb= cld if and only if their truth-tables coincide. In particular we have

which means that if the rule alb holds, any more imprecise conclusion a v c can be also produced. But,

More precisely, the rule alb may be true or may be false while the rule al(b A c) is not applicable. This contrasts with the material implication. Thus we capture a form of non­ monotonicity in this framework.

The problem of extendin_g operations such as negation, intersection and union to all ~ has been addressed by Schay [1968], Calabrese [1987], and Goodman and Nguyen [1988] sometimes in different ways. There is a consensus about negation, i.e.

In terms of truth-values, it corresponds to extend the negation operation by postulating that t(-,a) =?if t(a) =?. That is to say -.(alb) corresponds to the converse rule "if b then not a". This is quite different from what happens with the material implication where -.(b ~a)= b A -.a* b ~-,a!

There exist three different proposals for defining the conjunction of (alb) and (cld), which may appear under various equivalent forms, since due to (4) there are at least four ways of describing the same rule.

In terms of truth-values it is pointed out in [Dubois and Prade, 1988] that these three definitions correspond to three possible extensions of the binary conjunction operation which preserve the symmetry and which take into account the symbol ? introduced in Table 1. Namely, the three different conjunctions, denoted by ""'"· ., n are defined by

The first conjunction is such that the combination of something true (resp. false) with something inapplicable is true (resp. false). The second conjunction is defined in agreement with the ordering 0 ~ ? ~ 1. Note that these conjunction operations were first considered in the framework of trivalent logics, by Sobocinski, Lukasiewicz and Bochvar respectively ; see Rescher [1969] . Using the same notation for combining propositions or their truth values, the first conjunction is equivalent to the following definition considered by Schay [1968] and Calabrese [1987] (under other equivalent forms due to (4))

From the point of view of rule-based systems, A means that the two rules alb and cld are available and form a rule base. It is natural to define the applicability of a rule base {ailbi, i = 1,n} to a factual base fF whenever at least one rule i is applicable to fF, i.e. v i=l n bi is true. The two other conjunctions correspond to different points of view ; see [Dubois and Prade, 1988]. Their expressions are

and they have been considered by Goodman and Nguyen [1988] and by Schay [1968] respectively. Note that

so as the three conjunctions differ only when b "'-d. (11) and (12) are not very natural when alb is viewed as a rule. For instance (12) assumes that a rule base containing alb and cld is applicable when both rules are applicable.(lO), (11) and (12) basically differ by the conditions in which they are applicable, and the advantage of (10) is that it is the least demanding in that respect.

Three disjunction operations can be derived by duality using De Morgan laws. Lastly, the conditioning process can be iterated in such a way that ffil $ remains closed under this process. Calabrese [ 1987] has proposed the following defmition : (alb)lc = al(b "c) ; it corresponds to the convention ?10 =? = ?11 (using the same symbol 'I' for propositions and for values of the truth function). Two meanings can be envisaged for the companion expression al(blc) namely i) al(blc) = al(b" c) stating 11? =? = 01?, or ii) a l(blc) = al(c ~b) (this is Calabrese's definition) and corresponds to set 11? = 1 and 01? = 0. See [Dubois and Prade, 1988] for other results and discussions.

Schay [1968] indicates that A and its dual .., are not distributive with respect to each other so that ( $1$, A, v, -.) is no longer a Boolean algebra. See also Calabrese [1987].

3 About Cox's Axioms

As recalled by Cheeseman [1988], Cox [1946] has postulated the following axioms that degrees of "reasonable expectation" valued on the unit interval should satisfy:

Al : P(-.alb) = S(P(alb))

A3: Sis strictly decreasing; F is strictly increasing in each place ; S and F are continuous.

Using these assumptions only, it is possible to prove that S(x) = 1 - x up to an isomorphism, that F is associative (due to the Boolean structure of the set of propositions a, b ... ), and is a product up to an isomorphism ; so that the set function P is a probability measure. See also Aleliunas [1988] for a slightly different approach to the same question.

Shafer [1988] has criticized A2 as being natural only for someone who is familiar with the usual defmition of conditional probability. For instance conditional probability can also be defmedas

and it may look natural to start with the "natural" requirement that P(alb) be defined as a function of P(a " b) and P( -.a " b)

only, since it reflects the relative strength of a and -.a in the environment where b is true. It would lead to an axiom

which explicitly defines P(alb) while A2 only provides an implicit defmition. It is hard to choose between A2 and A'2 as to which is the most natural axiom !

It turns out that Al and A2 take full meaning not only as axioms postulated from pure commonsense, but as expressing an homomorphism between the structure $1 $ described in section 1 and the unit interval. Indeed, measure-free conditionals satisfy the following property, which is easy to prove from (10) and (4).

A similar identity holds with the conjunction defmed by (11) but not with the one defined by (12). So that A2 becomes natural as a compositionality assumption with respect to the extended conjunction A of conditionals of the form ale and bl(a " c).

Axiom Al clearly requires the negation of a measure-free conditional as it appears in (8). However this axiom also presupposes that the meaning of the extreme values of P(alb) (i.e. 0 and 1) is well-understood. This is clearly a matter of convention. Cox's convention is that 1 means certainty (Probability = 1) and 0 means impossibility (Probability = 0). Axiom Al becomes very natural since it means (along with A3) the more probable a, the less probable -.a. However, another convention is reasonable as well, namely 1 means possibility (i.e. consistency with available knowledge) and 0 means impossibility. Under this new convention, Al does not sound reasonable at all, since it would mean, along with A3 : the more possible a, the less possible -.a . But in case of incomplete knowledge, one may find that a and -.a are equally and totally possible. A more natural substitute to A 1 would be : the more impossible -.a, the more certain a. In other words, when P(alb) rang~s from impossibility (0) to possibility (1), ~(P(alb)) = P(-.alb) does not qualify -.a !n the same way : P(-.alb) = 1 means that -.a is certain while P(-.alb) = 0 means that -.a is totally uncertain (i.e. it corresponds to a state of ignorance). Hence changing the meaning of the end-points of the unit interval may lead to drop axiom Al, and to consider two set-functions, one for possibility, say rr. one for certainty say C, that exchange via the duality property

and it that may act as a substitute to Al.

Axiom A3 is technical, and was stated in a stronger form by Cox [1946], originally. It is remarkable that only probability measures emerge as the unique solution to Al-A3. However one must be aware that if A3 is further relaxed by requiring that F be strictly isotonic only, i.e.

then, Al-A3 have solutions which are !lQ1 probability measures. Indeed F =minimum is isotonic, and there exist set-functions g such that g(alb) = 1 - g(-.alb), g(a" b) = min(g(alb), g(b)), \fa, b such as the following one on a 4-element set n = {1,2,3,4}

They are such that Va, Vb, g(a A b)< g(b) and g(-.a A b) < g(b) ~ g(a A b) = g(-.b v a)= g(a)) . See Dubois and Prade p988J. for more discussions on this point. g is monotonic under mclus10n, but not decomposable through disjunctions of mutually exclusive propositions.

~~other impo~t.ant issue is the compatibility between condiUonal probability and the entailment relation :s; between rules alb. The following result can be established [Dubois and Prade, 1988] :

Proposition 1 : alb :s; cld implies P(alb) :s; P(cld), when Pis a probability measure.

Proof : Let g be a monotonic function, i.e. such that a :s; b implies g(a) :s; g(b) . Let alb :s; cld; then g(a A b) :s; g(c A d) and ~(-,b v .a) :s; g(-.d ':c) due to the monotonicity of g; the latter mequahty also wntes g(b A -.a) :2: g(d A -.c), since d A -,c :s;

This result can be extended to Shafer [1976]'s plausibility measu~es, as well as possibility measures [Zadeh, 1978], [DuboiS and Prade, 1988b]. Indeed let us assume that ll is a plausibility measure, and that ll satisfies A2 and A3. Note that F = product is once again the unique operation for the definition of conditioning, up to an isomorphism (e.g. Aczel [1966]). A2 corresponds to Shafer [1976]'s definition of conditional plausibility, in accordance with Demspter rule of conditioning. Now the extension of proposition 1 writes :

Proposition 2: alb :s; cld implies ll(alb) :s; ll(cld) where n is a plausibility measure or a possibility measure.

Proof : it is enough to express

where K(a,b) ~ :L{m(e~l~ A b .,_([), e A a A b = ([)}, and m denote~ the basi~ probability assignment defining ll. K(a,b) is the weight beanf!g on exceptions to the rule alb. If alb :s; cld then ll(a A b) :s; Il(c Ad~, and K(a,b):::: K(c,d) (see [Dubois and Prade, 1988] for details). When ll is a possibility measure, the result also holds since n is a plausibility measure such that ll(a v b) = max(Q(a), ll(b)), .va,b. A direct proof is to use th~ one of propositiOn 1 changmg f(x) = 1/(1 + x) into f(x) = rmn(1, 1/x). Q.E.D.

As a con~equ~nce, plausibility and possibility measures, although vwlaung ~xiom Al (due to a matter of convention) d~fine homomorphisms between fa I fa and the unit interval. Sm~e alb :S; cld ~ -.alb <: -.cld, the dual measure of certainty (belief measure or necessity measure) also satisfies Proposition 2, nam~ly _alb_:s; cl~ ~ C(alb) :s; C(cld). Proposition 2 is an algebraic JUStification of Dempster's rule of conditioning. However several problems are still pending such as the extensi?~ of prOJ?OSition 2 to more general upper and lower probability ~unctions, and more generally the independence between axwms A2, A3 and the compatibility property expressed by proposition 2, when A1 is dropped.

4 Measure-Free Conditionais as Default Rules

Several authors, and especially Pearl [1988] have suggested !hat a default rule such as "generally, b's are a's" could be mterpreted as Probability(alb) = HlGH. It may be tempting to consider the measure-free conditional alb as a model of default in t~e ~pirit ?f Reiter [~ 980]'s logic, i.e. without refering to any statistical mterpretation, considering that the statistical coml:'<;>nent is carried by the probability attached to the conditional, and not by the conditional itself.

There are two conditions under which alb represents a default:

• -)there exists at least one interpretation for which t(alb) = 1 (otherwise a A b = ([) and it makes no sense to assert alb)
• -) the:e may exist exceptions to the rule, i.e. interpretations for which t(alb) = 0 (otherwise a :s; b and alb is nothing but a standar.d. monotonic inference rule ; particularly, for any probability measure P, P(alb) = 1, while here we wish to allow for P(alb) E (0,1)).

Asserting "alb" can thus be interpreted as : b "# ([) and (alb) ,_ (([) lb) ; these tv;:o conditions hold if and only if a A b "# ([), so that alb means there are examples of b's that are a's", i.e. the weakest kind of default rule one may apparently think of.

As a next step, it seems possible to use the ordering relation :S; between defaults and the conjunction A for the definition of a consequence relation. A default elf can be deduced from {alb,cld) if and only if

(15) means the following : any example of one of the rules alb or cld, that is not an exception to the other rule is an example of elf ; and any exception to elf is an exception to one of the rules alb, or cld. Particularly (alb) A (cld) :s; (alb) does not hold because an example of cld can be simply irrelevant for alb (i.e. t(c A d)= 1 and t(b) = 0 so that t((alb) A (cld)) = 1 while t(alb) = ?. On the contrary a rule elfthat satisfies (15) takes into account QQ!h rules since its examples are at least all those of each rule when the two rules do not contradict each other. This remark suggests that (15) defines elf as a weak substitute to the set of defaults {alb, cld) in which both rules are still acting. By contrast we have (alb) · (cld) :s; (alb) with the conjunction defined by (11). Hence using this inequality as an inference rule does not look proper.

The following properties of the consequence relation :s; are noticeable, and easily checked using truth-tables :

(16) holds with the two other conjunctions as well since (a A c)lb :s; cl(a A b); (17) which is a direct consequence of (13) and (6) holds also for the conjunction defined by (11) ; by contrast (18) does not hold with any of the two other conjunctions. These relations can serve as inference rules that produce new defaults from existing ones. In Adams [1975]'s conditional logic alb is interpreted as P(alb) :2: 1 - e where e is arbitrarily close to 0 and denoted b ~ a. This interpretation is much more demanding than ours. However Adams [1975] found inference rules that are exactly (16-18), namely:

disjunction a ~ c b ~ c ~ (a v b) ~ c The rules are used by Pearl [1988] to build a probabilistic-like default logic. Starting from purely logical assignments, Gabbay [1985] proposed several axioms a non-monotonic deduction operation tv should satisfy, and especially:

Clearly, restricted monotonicity becomes triangularity in the probabilistic setting and correspond to ( 16), while (17), related to Bayes rule, is simply a transitivity property that deduction must satisfy. These remarks suggest that a non-monotonic logic where defaults are modelled by measure-free conditionals is likely to have all the properties that a well-behaved non­ monotonic logic should satisfy, especially the possibility to infer new defaults, and the reasoning by cases (due to (18)). In probabilistic terms, alb means P(alb) > e where e is positive but can be arbitrarily small. Thus it is more general than Adams [1975]'s interpretation; (16-18) then translate into the following inequalities :

5 Conclusion

This paper is meant to investigate some consequences of recent results about measure-free conditioning. Our contention is that measure-free conditionals could be a good way of modeling non-monotonic production rules in accordance with numerical theories of uncertainty ; in other words this approach equips uncertain rules in expert systems with clear semantics. However the use of uncertainty coefficients is not compulsory : propositional logic augmented with measure-free conditionals can be used as a formal system of non-monotonic logic. Properties of this system will be investigated in the future.