Approximate Reasoning Based on Fuzzy Logic

1. INTRODUCTION

It has long been recognized that much, perhaps most, of human reasoning is approximate rather than exact in nature.** And yet, logicians and cognitive scientists have devoted scant atten­ tion to the development of theories of approxi­ mate reasoning, partly because of the deeply entrenched tradition of respect for what is precise and disdain for what is fuzzy, and partly because there was no compelling need for such theories before the advent of artificial

intelligence.

In recent years, however, the rapid growth of interest in natural language processing and the emergence of expert systems as an important application area within AI have made it increas­ ingly clear that a better understanding of the

*Research supported by Naval Electronic Systems Command Contract N00039-78-C-0013 and National Science Foundation Grant ENG-7823143

**The terms "approximate reasoning" and "fuzzy reasoning" are frequently used inter­ changeably in the literature. A comprehensive exposition of the foundations of fuzzy reason­ in& may be found in the paper by B.R. Gaines

[lJ.

processes of approximate reasoning is a prere­ quisite to the development of knowledge-based systems which can manipulate information that is imprecise, incomplete or not totally reliable.

In a series of papers starting in 1973 [2-7], we have advanced the view that conventional logical systems do not provide an appropriate basis for approximate reasoning and have sug­ gested a fuzzy logic, FL, for this purpose. In contrast to two-valued and multi-valued logics, the truth-values of FL are linguistic rather than numerical, as are quantifiers exemplified by many, most, not very many, few, several, almost all, etc. Furthermore, the rules of inference-in FL are approximate rather than exact. Thus, in spirit as well as in substance FL represents a sharp break with the long­ standing tradition of extreme precision in logic and a move toward an accommodation with the pervasive imprecision of human thought, perception, language and decision-making.

Another important difference between FL and classical logical systems centers on the con­ cept of truth. Thus, whereas in the latter systems [8,9] the truth of a proposition

serves as a starting point for the definition of various basic concepts, the corresponding role in FL is played not by truth but by the concept of a possibility distribution, by which is meant a mapping associated with a variable X, rrx: U + [0,1], which assigns to each point u in the domain of X, U, the possibility that X could take u as a value. The concept of truth, then, is employed to express the compatibility of the possibility distribution induced by a proposition p with that of a reference proposi­ tion r. In this sense, the truth of a proposi­ tion is a relative concept and is a measure of its compatibility or consistency with a collec­ tion of propositions which constitute a database.

Our main concern in the present paper is with (a) the establishment of translation rules for various types of imprecise propositions; (b) inference from such propositions; and (c) the development of a conceptual framework for dealing with the issues of belief and credi­ bility. The latter issues play a particularly important role in expert systems [10-17] as well as in the theories of evidence and decision analys is [18-24].

2. THE CONCEPT OF A POSSIBILITY DISTRIBUTION

As a preliminary to the consideration of trans­ lation rules for various types of propositions, it will be helpful to establish some of the properties of possibility distributions which will be needed in later sections.*

Informally, if X is a variable taking values in U, then a possibility distribution, ITX, asso­ cia ted with X may be viewed as a fuzzy (or clast ic) constraint on the values that may be assigned to X. Such a distribution is charac­ terized by a possibility distribution function rrx: U + [0, 1] which associates with each u E U the "degree of ease" or the possibility that X

may take u as a value.

In some cases, the constraint on the values of X is physical in origin. For example, if X is the numbe r of students in a classroom which has, say , SO seats, then rrx(u) = 1 for u up to SO, with rrx(u) gradually declining to 0 at, say, u = 7S. In this case, an intermediate value of rrx, say rrx(6S) = 0.3, would signify that, by some explici t or tmplicit criterion, the degree of ease with which 6S students could be crowded into the class room is 0.3 (on the scale from 0 to 1).

*An introductory exposition of possibility theory may he found in [29]. A historical account of the concepts of possibility and pro­ babil ity is contained in [30].

In most cases, however, the possibility distri­ bution which is associated with a variabie is epistemic rather than physical in origin. A basic assumption in fuzzy logic is that such epistemic possibility distributions are induced by propositions expressed in a natural language. In more concrete terms, this assumption may be stated as the

Possibility Postulate. IfF is ·a fuzzy subset of U characterized by its membership function )lF: U + [0,1], then the proposition "X is F" induces a possibility distribution rrx which is equal to F. Equivalently, "X is F" translates into the possibility assignment equation ITX = F, i.e.,

which signifies that the proposition "X is F" has the effect of constraining the values that may be assumed by X, with the possibility dis­ tribution ITX identified with F.

As a simple illustration of (1), if in the pro­ position "X is small" small is regarded as a label of a fuzzy subset of U = {0,1,2, .·· } which is defined by*

SMALL 1/0+1/1+0.8/2+0.6/3+0.4/4+0.2/S (2)

where Poss{X = u} = lTX(u) is the possibility that X may take u as a value.

An important aspect of the concept of a possi­ bility distribution is that it is nonstatisti­ cal in nature. As a consequence, if Px is a probability distribution associated with X then the only connection between ITX and Px is that impossibility (i.e., zero possibility) implies improbability but not vice-versa. Thus, ITx can­ not be inferred from PX nor can PX be inferred from rrx.

As in the case of probabilities, one can define joint and conditional possibilities. Thus, if X andY are variables taking values in U and V, respectively, then we can define the joint and and conditional possibility distributions through the ir respective distribution functions:

*The notation F = )l 1 /x 1 +· · ·+)ln/x signifies that F is a fuzzy subset of the set Yx 1 , ··· ,xn}, with lli· i = 1, ··· ,n, being the grade of member­ ship of xi in F. Uppercase symbols (e.g., F, SMALL) are employed to denote names of sets (fuzzy or nonfuzzy).

whe re ( 5) rPpresents the conditional. distribu­ tion function of X given Y.

If we know the distribution function of X and the conditional distribution function of Y given X, then we can construct the joint dis­ tribution function of X and Y by forming the conjunc tion ( ~ ~ min)

Howeve r, unlike the identity that holds in the case of probabilities, we can also obtain TT (X,Y)(u,v) by forming the conjunction of

In yc>t another deviation from parallelism with prohahl.lities, the marginal possibility distri­ bution function of X may be expressed in more than ont· way in terms of the joint and condi­ tional possibility distribution functions. More specifically, we may have

where v v denotes the supremum over v E V;

where, for a given u, v(u) is the value of v at which TI (Y\X)(v\u) = 1, if v(u) is defined for eve ry u E U.

Tntu!. t !.ve l.y, (a) represents the possibility of assigning a value to X as per ceived by an ob­ server ((X,Y) observer) who observes the joint possibility distribution IT(X,Y)" Similarly, (b) represents the perception of an observer ((X\Y) observer) who observes only the condi­ tional possibility distribution IT(X\Y) and is unconce rned with or unaware of IT(Y\X)" And (c) expres ses the perception of an observer who assumes that v is assigned that value, if it exists, which makes TI(Y\X)(v\u) equal to unity.

In relating TIX to TI (X I Y) through the operator V (supremum), we are tacitly invoking the princi­ ple of maximal restriction [4], which asserts that, in the absence of complete information about ITx, we should equate ITx to the maximal (i.e., least restrictive ) possibility distribu­ tion which is consistent with the partial infor­ mation about ITx· In the case of (a), for exam­ ple, this would be the supremum of TI(X Y)(u,v) over v E V. '

As will be seen in Sec tion 3, the concept of a conditional possibility distribution plays a basic role in the formulation of a generalized form of modus ponens and in defining a measure of belief. What is as yet an unsettled iss ue revolves around the question of how t o derive TI(X\Y) and TI(Y\X) from 1r(X,Y). Somewhat diffe r­ ent answers to this question are presented in [25-27]. It may well turn out to be the case that, in contrast to probabilities, there does not exist a unique solution to the problem and that, in general, the answer depends on the perspective of the observer.

3. POSSIBILITY THEORY AND FUZZY LOGIC

As was alluded to already, the concept of a possibility distribution and the possibility theory which is based on it, play a central role in fuzzy logic by providing a means for the representation of the meaning of imprecise premises and the generation of propositions which follow logically from them.

Typically, a variable in fuzzy logic is treated as a linguistic variable [4], that is, a varia­ ble whose values are represented as words or sentences in a natural or synthetic language, with each such value defining a possibility distribution in the domain of the variable. In effect, what this implies is that a linguistic variable is a microlanguage with its own syntax and semantics. For example, in the case of FL, the linguistic values of the variable Truth may be generated by a context-free grammar and interpreted by an attributed grammar [28]. Thus, starting with (a) the primary term true and its antonym false; and (b) a finite set of modifiers and connectives such as and, or, not , very, more or less, quite, extremely, etc., the linguistic value of Truth may be represented as not true and not false not ::e~y_true and not very false In FL, a linguistic truth-value is regarded as a composite label of a possibility distribution in the interval [0,1], which is the set of truth-values in Lukasiewicz's LAlephl logic. What this means is that in FL we generally deal not with numerically-valued truth-values but with their possibility distributions.

An important distinction between FL and LAleph 1 is that in LAleph 1 --as in all other multi­ valued logics--there are only two quantifiers all and some, whereas in FL we can employ a ·large variety of fuzzy quantifiers exemplified by few, several, many, most, almost all, very many, not very many, etc. This feature of FL makes it possible to translate, and infer from, imprecise premises exemplified by

Most tall women are not very fat. Among the many men who are heavy smokers, quite a few are overweight and some are heavy drinkers.

Carol has several close friends who have many children.

The meaning of a quantifier in FL is based on the concep t of the cardinality of a fuzzy set. Thus, if F is a fuzzy subset of a finite set U = {u 1 , .·· ,un} characterized as

where lli is the grade of membership of ui in F, i = 1, ·.. , N, then the power of F--which is roughly a measure of its cardinality--may be defined as

Alternatively, and perhaps more appropriately, the cardinality of F may be defined as a fuzzy number, as is done in [6]. Thus, if the ele­ ments of F are sorted in descending order, so that lln ~ 11m if n ~ m, then the truth-value of the proposition

is defined to be equal to lln' while that of q,

is taken to be 1-pn+l" From this it follows that the truth-value of the proposition r,

is given by lln A (1-lln+~· An illustration of these alternative definitions of cardinaLity is provided by Example 5 in Section 4.

The translation rules for propositions ~x­ pressed in a natural language form an Important part of PRUF--a meaning representation languagt> based on possibility theory [7].* In what fol­ lows, we shall present in a summarized form a subset of such rules which play a basic role in FL.

Translation Rules

where m is a modifier such as not, very, more or less, etc., and F+ is a modification o~ induced by m. More specifically: If m = not, then p+ = F' =complement ofF, i.e.,

As a simple illustration of (15), if SMALL is defined as in (2), then

where

It should be noted that (16)-(18) should be viewed as default rules which may be replaced by other translation rules in cases in which some alternative interpretations of the modi­ fiers very and more or less are more appropriate.

2. Conjunctive, disjunctive and implicational rules. If

where F and G are fuzzy subsets of U and V,

*There are several implemented languages which have extensive facilities for the mani­ pulation of fuzzy propositions and execution of fuzzy instructions. Prominent among these are FUZZY [23] and FSTDS (30).

respectively, then

where II(YIX) denotes the conditional possibil­ ity distribution of Y given X, and the bounded sum e is defined by

As simple illustrations of (22), (24) and (27),

then

and

3. Quantification rule. If U = {u 1 , ... ,uN}, Q is a quantifier such as many, few, several, ~ some, most, etc., and

then the proposition "QX are F" (e.g., "many X's are large") translates into

where Count(F) denotes the number (or the pro­ portion) of elements of U which are in F. By definition (11), if the fuzzy set F is expressed as

then

As a simple illustration of (35), if the quan­ tifier several is defined as

and then

where llLARGE(ui) is the grade of membership of the ith value of X in the fuzzy set LARGE.

4. Truth qualification rule. Let T be a fuzzy truth-value, e.g., very true, quite true, more or less true, etc. Such a truth-value may be regarded~a fuzzy subset of the unit interval which is characterized by a membership function ].lT: (0,1) + (0,1).

A truth-qualified proposition, e.g., "It is T that X is F," is expressed as "X is F is T." As shown in [5), the translation rule for such propositions is given by

As an illustration, consider the truth-quali­ fied proposition

Bob is young is very true

which by (40), (41) and (17) translates into

Now, if we assume that

and

then (41) yields

as the possibility distribution of the age of Bob.

Used in combination, the translation rules stated above provide a system for the determi­ nation of the possibility distribution induced by a fairly complex composite proposition. For example, the proposition

If X is not very large and Y is more or less small then Z is very very large.

induces the conditional possibility distribu­ tion described by

It should be noted that rules of this type have found practical applications in the design of fuzzy logic controllers in steel plants, cement kilns and other types of industrial process con­ trol applications in which instructions expres­ sed in a natural language are transformed into control signals [31-33].

Rules of Inference

In our approach to approximate reasoning, the translation rules for imprecise propositions serve as a preliminary to the application of various rules of inference to the possibility distributions which are induced by such propo­ sitions, leading to other possibility distribu­ tions which upon retranslation yield the con­ c lusions which may be drawn from the premises.

More specifically, the basic rules of inference in FL are the following.

1. Projection rule. Consider a fuzzy proposi­ tion whose translation is expressed as

and let ble X ~ X(s) denote a subvariable (Xl·····~), i.e., of the varia-

where the index sequences~ (il·· .· ,ik) is a subsequence of the sequence (l, ... ,n).

Fur thermore, let Ilxfs) denote the marginal pos­ sibility distribution of X(s); that is,

where Ui, i = 1, ... , n, is the universe of dis­ course associated with Xi;

and the projection of F on U(s) is defined by the possibility distribution function

where s' ~ (j 1 , ... ,jm) is the index subsequence which is complementary to s, and ~F is the mem­ bership function of F.

Now let q be a retranslation of the possibility assignment equation

Then, the projec tion rule asserts that q may be inferred from p. In a schematic form, this assertion may be expressed more transparently

2. Conjunction rule. Consider a proposition p which is an assertion concerning the possible values of, say, two variables X andY which take values in U and V, respectively. Simi­ larly, let q be an assertion coqcerning the possible values of the variables Y and Z, tak­ ing values in V and W. With these assumptions, the translations of p and q may be expressed as

Let F and G be, respectively, the cylindrical extensions of F and G in U x V x W. Thus,

Using the conjunction rule, we can infer from p and q a proposition which is defined by the fol­ lowing scheme (the reverse arrow +- denotes retranslation, i.e., reverse translation):

On combining the projection and conjunction rules, we obtain the compositional rule of inference (67) which includes the classical modus ponens as a special case.

More specifically, on applying the projection rule to (64), we obtain the following inference scheme

where the composition of F and G is defined by

In particular, if p is a proposition of the form "X is F" and q is a proposition of the form "If X is G then Y is H," then (65) becomes

and The rule expressed by (67) may be viewed as a generalized form of modus ponens which reduces to the classical modus ponens when F = G and F, G, H are nonfuzzy sets.

Stated in terms of possibility distributions, the generalized modus ponens places in evidence the analogy between probabilistic and possibil­ istic inference. Thus, in the case of proba­ bilities, we can deduce the probability distri­ bution of Y from the knowledge of the probabil­ ity dl s trlbution of X and the conditional pro­ bab.l1lty distrlbution of Y given X. Similarly, in the case of possibility distributions, we can infer the possibility distribution of Y from the knowledge of the possibility distribu­ tion of X and the conditional possibility dis­ tribution of Y given X.

It is important to note that the generalized modus ponens as expressed by (67) may be used to enlarge significantly the area of applica­ bility of rule-based systems of the type employed in MYCIN and other expert systems. This is due primarily to two aspects of (67) which are not present in conventional rule­ based. systems: (a) in the propositions "X is F" a nd "If X is G then Y isH," F, G and H may be fuzzy sets; and (b) F and G need not be identical. Thus, as a result of (a) and (b), a rule-based system employing (67) may be designed to have an interpolative capability [ 6].

Note. Due to limitations on space, the sec­ tions dealing with credibility analysis and examples of approximate reasoning have been dele t ed. Full text of the paper is available on request.

REFERENCES AND BIBLIOGRAPHY

• (1] B.R. Gaines, "Foundations of fuzzy reason­ ing," Int . .:!..:._ Man-Machine Studies 6: 623668, 1975.
• [2) L.A. Zadeh, "Outline of a new approach to the analysis of complex systems and deci­ sion processes," IEEE Trans. Systems, Man ~Cybernetics SMC-3: 28-44, 1973.
• L.A. Zadeh, "Fuzzy logic and approximate reasoning (in memory of Grigore Moisil)," Synthese 30: 407-428, 1975.
• (4] L.A. Zadeh, "The concept of a linguistic variable and its application to approxi­ mate reasoning," Pt. I, Inf. Sci. 8: 119249; Pt. II, Inf. Sci. 8: 301-357; Pt. III Inf . Sci. 9: 43-80~75.
• [ 5] L.A. Zadeh, "Local and fuzzy logics" (with R.E. Bellman), in Modern Uses of Multiple-Valued Logic, J.M. Dunn & G. Epstein (eds.), D. Reidel, Dordrecht, 1977, pp. 103-165.
• [6) L.A. Zadeh, "A theory of approximate rea­ soning," Memo M77 /58, Elec tronics Research Laboratory, University of California, Berkeley, 1977. To appear in Machine Intelligence 9.
• (7] L.A. Zadeh, "PRUF--a meaning representa­ tion language for natural languages," Int. .:!..:._Man-Machine Studies 10: 395-460, 19~
• [8) A. Tarski, Logics, Semantics, Metamathe­ matics, Clarendon Press, Oxford, 1956.
• [9) S. Haack, Jhilosophy of Logics , Cambridge University Press, Cambridge, 1978.
• [ 10] E. Feigenbaum, B.G. Buchanan and J. Lederberg, "On generality and problem solving: a case study using the DENDRAL program," Machine Ingelligence 6, Edinburgh University Press, 1971.
• [11) G.A. Corry, J.P. Kassirer, A. Essig and W.B. Schwartz, "Dec ision analysis as the basis for computer~aided management of acute renal failure," Am. l._._ Medicine 55: 473-484, 1973.
• [12) E.H. Shortliffe and B.G. Buchanan, "A model of inexact reasoning in medicine, " Mathematical Biosciences 23: 351-379, 197~
• [13) E. Shortliffe, MYCIN: Computer-Based Medical Consultations, American Elsevier, New York, 1976.
• [ 14) R. Duda et al., "Development of a computer based consultant for mineral exploration (PROSPECTOR)," Annual Report SRI Interna­ tional, Nos. 5821 and 6415, 1977.
• [15) P. Szolovits, L.B. Hawkinson and W.A. Martin, "An overview of OWL, a language for knowledge representation," LCS Memo, M. I. T., 1977.
• [ 16) J. McCarthy, "Epistomological problems of artificial intelligence," Proc. 5th IJCAI, M.I.T., 1977, pp. 1038-104-4-.----
• [17) D.G. Bobrow and T. Winograd, "An overview of KRL, a knowledge representation lan­ guage," Cognitive Science 1: 3-46, 1977.
• [18) R.G. Swinburne, An Introduction to Confirmation Theory, Methuen, London, 1973.
• P. Suppes, "The measurement of belief," .:!..:._~Statist. Soc.~ 36: 160-175, 1974.
• K.M. Colby, "Simula tions of belief sys­ tems," in Computer Models ~ Thought and Language, R.C. Schank & K.M. Colby (eds.), W. Freeman, San Francisco, 1973.
• G. Shafer, ~Mathematical Theory ~ Evidence, Princeton University Press, Princeton, 1976.
• B.C. Bruce, "Belief systems and language understanding," N.I.H. Report CBM-TR-41, Rutgers University, 1975.
• K. Noguchi, M. Umano, M. Mizumoto and K. Tanaka, "Implementation of fuzzy artifi­ cial intelligence language FLOU," IECE Tech. Report On Automation and Language, 1976.