Syllogistic Reasoning as a Basis for Combination of Evidence in Expert Systems

Abstract

In the presence of uncertainty, computation of the cer­ tainty factor of a hypothesis requires, in general, the availa­ bility of rules for combining evidence under chaining, dis­ junction and conjunction. The method described in this paper is based on the use of what may be viewed as a gen­ eralization of syllogistic reasoning in classical logic - - a gen­ eralization in which numerical or, more generally, fuzzy quantifiers assume the role of probabilities. For example, the proposition QA's are B's, in which Q is a numerical or fuzzy quantifier, may be interpreted as "the conditional probability of B given A is Q." In this sense, the knowledge base of an expert system may be assumed to consist of propositions of the general form "QA's are B's."

It is shown that six basic syllogisms are sufficient to provide a systematic framework for the computation of cer­ tainty factors. A comparison with the rules of combination of evidence in PROSPECTOR, MYCIN and other expert sys­ tems is presented and a connection between syllogistic rea­ soning and the Dempster-Shafer theory is established. The syllogistic method of reasoning lends itself to a computation­ ally efficient implementation and thus provides an effective tool for the management of uncertainty in expert systems.

I. SYLLOGISTIC REASONING

In the eXIstmg expert systems, the computation of certainty factors of hypotheses and conclusions is carried out through the use of probability-based methods (Barr and Feigenbaum, 1982). More recently, the use of belief functions in the con­ text of the Dempster-Shafer theory has attracted increasing attention (Wesley, Lowrance and Garvey, 1984).

In a different approach which is outlined in this paper, syllogistic reasoning is employed to provide a basis for the formulation of rules for combination of evidence. Classically, the major and minor premises in syllogistic reasoning are allowed to contain only the standard quantifiers all and some. For example, the paradigmatic syllogism Barbara is expressed by the rule

where A, B and C are arbitrary predicates in two-valued logic. This syllogism expresses the transitivity of set con­ tainment and, as such, provides the basis for property inheri­ tance in knowledge representation systems.

L.A. Zadeh·

Computer Science Division, University of California, Berkeley, California, 94720

In a more general sense which is employed m this paper, a syllogism is an inference rule of the form

where Q 1 , Q 2 and Q 3 are numerical or, more generally, fuzzy quantifiers (e.g., 80%, most, many, few), and A,B,C,D,E and F are crisp or fuzzy predicates (e .g., positive, >5, small, tall, heavy). The predicates A, B, ... , F are assumed to be related in a specified way, giving rise to different types of syllogisms. For example, the consequent conjunction syllogism corresponds to the relations A=C=E, F=B A D, where 1\ stands for conjunction.

The following syllogisms play a basic role in the formu­ lation of rules for combining evidence in expert systems.

Intersection/ product syllogism: C=A F= B 1\ D. B, E= A, Consequent conjunction syllogism: A=C=E, F=BII D. Consequent disjunction syllogism: A=C=E, F=B V D. ( v ~ disjunction) Antecedent conjunction syllogism: B= D=F, E=A 1\ C. Antecedent disjunction syllogism: B=D=F, E=AV C.

Chaining syllogism: B=C, E= A, F=B.

(The chaining syllogism may be viewed as a special case of the intersection/ product syllogism).

A quantifier in a premise of a syllogism plays a role analogous to that of conditional probability. More specifically, the proposition "QA's are B's," may be inter­ preted as "the conditional probability of B given A is Q." with the understanding that A and B may be fuzzy events such that the conditional probability of B given A is a fuzzy probability Q. Viewed in this perspective, the consequent conjunction syllogism, for example, may be viewed as a gen­ eralization of the combining rule for the conjunction of hypotheses in PROSPECTOR and MYCIN.

A combining rule expressed as a syllogism differs from standard combinin~~: rules in several important respects. First, when Q 1 and Q 2 are numerical quantifiers or, equivalently, numerical probabilities, the resultant quantifier Q 3 in the conclusion is, in general , interval-valued. For example, in the case of the consequent conjunction syllogism, Q 3 is given by

where A and v' stand for min and max, respectively. The interval-valuedness of Q reflects the incomplete state of knowledge regarding the ~ependence between the major and minor premises. In the conventional approaches, the under­ lying events are assumed to be conditionally independent, which accounts for a numerical value-rather than an inter­ val value-for the certainty factor of the conclusion.

In the more general case where Q 1 and Q 2 are fuzzy quantifiers, Q 3 is also a fuzzy quantifier g1ven by

where~ ' $' e and® are the operations of max, +,- and min in fuzzy arithmetic (Kaufmann and Gupta, 1985). In this sense, when QJ. and Q 2 are fuzzy numbers, so is Q 3 . As an illustration, an mstance of the consequent conjunction syl­ logism is

Most students are young Most students are healthy Q students are young and healthy

where 0~(2 most81) :S Q :S most.

When B is contained in A, and Q and Q are mono­ tonic (i .e., at least Q 1 is equivalent to Q 1 , and 1ikewise for Q 2 ) the intersection/ product syllogism reduces to the chain­ ing syllogism:

where ® denotes multiplication in fuzzy arithmetic. For example,

Most students are undergraduates Most undergraduates are young

Most 2 students are young

where mo~t 2 is a fuzzy quantifier which is the product of most with itself. In this way, the chaining syllogism provides a mechanism for dealing with chains of rules or facts whose constitutents (i.e., predicates and quantifiers (or probabili­ ties)) are not sharply defined .

II. DEMPSTER-SHAFER THEORY

A special case of syllogistic reasoning which provides a link with the Dempster-Shafer theory of belief functions, relates to premises in which the quantifiers can take only three values: 1 ( all}, > 0( ~orne) and 0 {none}. Thus, all premises are of the form QiA's are R, i=1, ... , n, where Qi is 1, > O or 0, and the Ai and R are subsets of the universe of discourse, with R representing a range query and A; being the value of an attribute. For example, if the attribute is Age, the query may be, "What fraction of individuals in the database are in the age range [20, 25], with R being the interval [20, 25]. For an individual i, A· would represent the possible values of the age of i, so that t~e proposition "All :\ are R," would signify that all possible values of the age of 1 are contained in the interval R and hence that it is certain that the age of i satisfies the condition of the query.

The answer to the query, then, would have two com­ ponents. The first component, called belie/ in the Dempster­ Shafer theory, is, in effect, the fraction of the Qi which are equal to 1. The second component, plau~ibility, is the frac­ tion of the Qi which are greater than ·zero. These com­ ponents may be interpreted, respectively, as the measures of certainty (or necessity) and possibility (Zadeh, 1981).

The advantage of viewing the Dempster-Shafer theory as a variant of syllogistic reasoning in which the quantifiers ~re th~ee-valued, is that it suggests a more general approach m wh1ch the quantifiers may be quantized to any desired number of levels. In this way, the number of levels may be adjusted to fit the granularity of the information in the knowledge base .

ill. USUALITY

An important application of syllogistic reasoning relates to what might be called the concept of u~uality. In essence, usuality is concerned with the usual values of variables, e.g., the usual price of a cup of coffee, the usual duration of a par­ ticular event, etc. More specifically let X be a variable tak­ ing values in a universe of discourse U, and let F be a fuzzy subset of U characterized by a membership function Jl.F which associates with each point p. E U a number in the interval [0,1] which represents its grade of membership in F. As shown in (Zadeh, 1978), the proposition X is F- - which may be interpreted as the assignment of a fuzzy value F to X - - induces a possibility distribution in U such that the possi­ bility that X= u is given by Jl.F {u). For example, the pro­ position X is ~mall induces a possibility distribution on the space of real numbers such that the possibility that X = u, where u is a real number, is equal to Jl.SMALL ( u ), (i.e ., the degree to which u fits the definition of the predicate ~mall, with SMALL being a fuzzy subset of real numbers which represents the denotation of ~mall. Similarly, in the case of the proposition Mary i~ young, if X is taken to be the age of Mary and U is the interval [0,100], then the proposition in question induces a possibility distribution of X such that the possibility that Age {Mary) =26, say, equals the degree to which 26 fits the definition of the predicate young in the con­ text in which the proposition Mary i~ young is asserted.

With this possibilistic interpretation of the proposition X is F as the point of departure, the meaning of the disposi­ tional proposition u~ually (Xi~ F) or, equivalently, X i· usu ­ ally F, may be defined as follows (Zadeh, 1984b):

where Z is the conditioning variable and R is a fuzzy value of Z which constrains Z away from exceptional values for which the proposition most X'~ are F does not hold. For example, in the case of the proposition usually it take~ about an hour to drive from Berkeley to Stanford, Z may be the time at which the trip is started and R is the non-rush-hour period. If R is U, then usually is unconditioned and the definition of usually {X is F) reduces to

which implies that usually plays the role of a fuzzy quantifier, that is, a fuzzy number which represents the rela­ tive count of elements in a fuzzy set (Zadeh, 1983). More specifically, if the observed values of X are u 1, . .. , u. then the relative count of X's which are F is expressed by

and the degree to which r fits the definition of most is given by

where MOST is the fuzzy subset of the unit interval which represents the denotation of the fuzzy quantifier moat. In this way, the meaning of the propositipn tuually (X ia F) may be expressed in terms of the meanings of F and moat. In a simi­ lar fashion, in the case of conditioned usuality, the meaning of usually (X is F) may be expressed as

where ECount (F / R) denotes the relative count of elements of F which are in R.

The concept of usuality makes it possible to extend the domain of applicability of syllogistic reasoning by allowing a premise· in a syllogism to be qualified - - implicitly or expli­ citly - - by the adjunction of uaually, with the understanding that uaually may be interpreted as a conditioned or uncondi­ tioned fuzzy quantifier. As a simple illustration, a special case of the intersection/product syllogism is the diapoaitional modua ponens

or, more generally

where usually 2 is the product of the fuzzy number uaually with itself in fuzzy arithmetic. Syllogisms of this type are of particular relevance to commonsense reasoning.

In summary, syllogistic reasoning provides a systematic framework for inference from premises which are imprecise and/ or not totally reliable. In this mode of reasoning, numerical quantifiers play a role analogous to that of proba­ bilities in probabilistic reasoning (Nilsson, 1984). However, the facility provided by syllogistic reasoning for manipulation of fuzzy quantifiers as fuzzy numbers within the framework of fuzzy arithmetic goes beyond the capabilities of existing probability-based methods and makes it possible to deal computationally with rules and facts whose certainty factors are not known with sufficient precision to justify the use of numerical probabilities.