PII: 0888-613X(87)90013-2 Extended Fuzzy Relations: Application to Fuzzy Expert Systems J. J. Buckley M a t h e m a t i c s D e p a r t m e n t , University o f A l a b a m a at B i r m i n g h a m Douglas Tucker Carraway M e d i c a l Center, B i r m i n g h a m , A l a b a m a A B S T R A C T This paper introduces the concept o f an extended f u z z y relation, which is a relation whose values are vectors o f f u z z y relations, some o f which may also be extended f u z z y relations. Our motivation is to use extended fuzzy relations to replace blocks o f rules in a f u z z y expert system with one rule. The extended f u z z y relation method is shown to contain the generalized modus ponens as a special case. The construction o f extended f u z z y relations is illustrated in two examples taken f r o m diagnosing mental disorders and image processing. We argue that the existence o f an extended f u z z y relation f o r a block o f rules may be a criterion f o r parallel execution o f this block instead o f sequential firing o f the rules. K E Y W O R D S : e x p e r t systems, f u z z y relations, p a t t e r n recognition " l 1. I N T R O D U C T I O N The purposes o f this article are to introduce extended fuzzy relations (EFR), explain their application to fuzzy expert systems, and show how they m a y be employed to decide between parallel and sequential firing o f production rules in a fuzzy expert system. W e begin with defining extended fuzzy r e l a t i o n s . Let S and T be any two nonempty sets. A regular fuzzy relation R is a function on a subset o f S x T w i t h values in [0, 1]. The strength o f the relation between s E S and t E T is given b y s R t , the value o f R at (s, t), a number between zero and one. An E F R (R w i l l be defined in a sequence o f steps. The domain o f (R will be a Address correspondence to J. J. Buckley, Mathematics Department, University of Alabama at Birmingham, Birmingham, Alabama 35294. International Journal of Approximate Reasoning 1987; 1:177-195 © 1987 Elsevier Science Publishing Co., Inc. 52 Vanderbilt Ave., New York, NY 10017 0888-613X/87/$3.50 177 178 J . J . Buckley et al. subset o f U x V, where U = {Ul, " ' ' , Urn} and V = {Vl, " " , on} are two finite sets. The value o f 61 at (ui, vj) will be denoted by ui61v-i. Level Zero We have ui61v-i = 7i-i (1) where 70 E [0, 1]. A level zero E F R is a regular fuzzy relation. A level zero EFR will be represented by 61o. Level One For all levels e, f _ 1, the elements o f U m a y be vectors; so let ui = ( / d i l , " ° " , uiki), a vector o f length Ki. Assume that the possible values o f uik all belong to some universal set Uik. Then ui61vj= R # = (Rijl, "" ", Rok i) (2) where each Rijk is a regular fuzzy relation 610. RO is a vector o f length Ki o f regular fuzzy relations, and the length o f R 0 is the same as the length o f u~. A level one E F R is written as 611. Level T w o We have ui61vj = R 0 (3) where Rij is a vector o f length Ki whose components are 61~ or 61o extended fuzzy relations. A level two E F R is denoted by 612. Level L The value o f 61 is ui(Rv-i = Ri-i (4) where the components o f R t / a r e (Re, 0 __< g _< L - 1. Let 61L be a level L EFR. The definition o f an E F R will be completed when we specify the domains o f all the relations mentioned in the foregoing statements. The formal, recursive definition o f extended fuzzy relations is rather involved, and the reader may wish to turn to an example near the end o f this section which illustrates the notation. Because U and V are finite, we may use matrix notation to describe an EFR. Extended Fuzzy Relations: Application 179 Let the rows o f a m x n matrix be labeled by Ug and the columns by vj. W e then place Rij, or "Yij for a 6/0, in the (ij)th cell. I f some ui is not related to some vj, then we leave the corresponding ( i j ) cell empty. When some cells are empty, the domain o f the E F R will be a proper subset o f U x V. Obviously, extended fuzzy relations are generalizations o f regular fuzzy relations, because for levels e _ 1 the cells contain vectors o f relations. W e are primarily interested in evaluating an E F R given some data D . W e will represent D as ,u l , , , where di = (dil, " " , diki) is a vector o f length Ki if ui is a vector o f length Ki. Suppose each dgk takes its values in some universal set ~3ik. The structure o f the data will vary with the levels o f the extended fuzzy relations. The data for some (Re will b e c o m e (generate) all the data for all the extended fuzzy relations contained in (Re. Any E F R (Re under discussion will have its domain a subset o f U × V w i t h data D , but any E F R within (Re will be assumed to be defined on a subset o f O × I7 with d a t a / ) . There may be many 61y, 0 _< j _< g - 1, contained in (Re, but we will use the same notation O × f " a n d / 5 for all these 61j extended fuzzy relations. W e will now specify the domains o f all the relations contained in a given EFR. For L e v e l Zero 61o is defined on a subset o f U x V with values in [0, 1]. For L e v e l One each Rijk is defined on a subset o f ~ k X Uik with values in [0, 1]. For L e v e l T w o each Rijk is defined on a subset o f ~ i k X Uik with values in [0, 1]. Suppose some Rijk is a 611. This 611 is also defined on a subset o f O × I7 with d a t a / ) . W e require Uik C lTand 33ik contain the possible data v a l u e s / ) for 611. Finally, for L e v e l L each RUk is defined on a subset o f ~Da x Ua with values i n [ 0 , 1 ] . I f R i j k = (Re, 0--< e_< L - 1, then Ugk C l " a n d D C_ ~ k . W e now introduce some general notation for the evaluation o f an EFR. The evaluation o f 61, given D , produces output O given by O = D o 61 (6) where ,,o,, is some type o f composition o f D and 61. The output O will be a fuzzy subset o f V given by ,o 1 The composition o f D and 61 will be determined from the inner product di * Rij o f di and Rij and a generalized matrix product. Let CVk = dik RijkUik (8) 180 J . J . Bucldey et al. and c i j = d i * R u = F i j ( c o ' l , " " , ci.iki) (9) where F~/is some function that aggregates the cuk values into one value c U. Then we define oj in the output O to be o j = f ( c l j , c 2 j , " ' ' , C m j ) (10) where f is some other function that combines the c U values into one number o j . The entire fuzzy output O is represented as D o (R, so let D ( R v i = o 1 denote a single membership value. The evaluation procedure is easily visualized using the matrix representation for 61. Given the data ( d i , • • ", din), we first take the product o f this vector with the column vector under v 1. The individual products o f di and Riy are defined by the inner product d~ * R i i . We then " s u m " or aggregate these inner products o v e r an entire column into the output value oj. Therefore, the composition D o 61 may be interpreted as a generalized matrix product. Now we may present a more precise definition o f an EFR. LEVEL ZERO Let cij = g ( d i , "Yij), where g is some function that combines d; and 3'ij into one number c o in [0, 1]. No F,j function is required, and oj = f ( c U, • • . ~ C m j ) . LEVEL ONE The ciik values are obtained from dikRi.ikUik; t h e Fii functions produce the c U, and then f gives the output oy for all j . LEVEL TWO When R i j k is a 610, the cuk values are computed directly from dikRijkUik. S o a s s u m e Rijkis a (RI. We know Uik C I7", so let uik = 0j E 17". W e also know dik will be a data value D for (Ri. Then Cijk = d i k ( R l Uik :-- D ( R l ()j = O j (11) where 6j is an output o f (R i. When Riik is a level one EFR, c,)-k is the correct level one output. LEVELL SupposeRijk = (Re, 0 - < e_< L - 1. Then cijk = dik (ReUik = D (ReO i = Oj (12) where D , 0j, and 6 / a r e the correct level e values for (Re. Our intended use o f extended fuzzy relations is to model and evaluate simultaneously blocks o f rules in a fuzzy expert system. Let us consider constructing a level one E F R for the following block o f rules. If xilRijlAil and/or " " X i k i R i j k i A i k i (13) t h e n y is B j f o r 1 <_ i <_ m , 1 < j <_ n . L e t vj = By and R i j = ( R i j l , " " " , RiJki) Extended Fuzzy Relations: Application 181 be the vector o f regular fuzzy relations. Also let ui = ( A / l , • • " , Aiki), I <_ i < m , be a listing o f the attributes on the left side. The data D contains di = (xil, • " , xiki), 1 <_ i <_ m . In the matrix representation o f the EFR, each ( i j ) cell containing an Ri.i corresponds to a rule in equation (13). Cells are left empty when a uj and vy are not related through a rule. The entrees in a v~ column represent all rules with the same conclusion oj. The items in a ui row are all the rules with the same left-side attributes. The function F u is chosen to reflect the structure (ands, ors, nots) in the left side o f the rule. I f only " a n d " is used in a rule, then we would consider using minimum for F u. W e would also consider employing m a x i m u m f o r f b e c a u s e we are " o r i n g " over all rules with the same conclusion to obtain our confidence oj in vj. The block o f rules in equation (13) becomes, using the level one EFR, if x is D , then y is 0. (14) Example Let us now consider an example that requires a level three EFR. This is a fuzzy expert system for diagnosing mental disorders (Siler and Tucker [8]). The information flow in this system is shown in Figure 1. The user is first asked a number o f questions that, together with their answers, create a set o f facts 5:. The system asks i f certain behavioral manifestations exists in the patient, and the user is to enter his/her confidence, f r o m zero to one, that they are present in the patient. A subset o f these facts 5:0 are input to a level one E F R (Rs that produces a fuzzy set o f symptoms. Let ITs = {depressive ( D i ) , manic ( M ) , schizophrenic (SI)} be the set o f symptoms. The output from (Rs will be a fuzzy subset o f Vs. Now, (Rs represents a block o f rules. An example o f a rule from this block is as follows: I f [fact = excess energy] A N D [fact = many big plans] A N D [fact = hallucinations], then [symptom -- M ] (15) Let us code " e x c e s s e n e r g y " as E E , " m a n y big p l a n s " as M B P , and " h a l l u c i n a t i o n s " as H . I f the number o f this rule, within this block, is seven, then u7 = ( E E , M B P , H ) . Next assume that the u s e r ' s response to questions about these conditions produced confidences c f ( E E ) , c f ( M B P ) , and c f ( H ) , respectively. The data input Ds for 6Is would then contain ( c f ( E E ) , c f ( M B P ) , c f ( H ) ) U 7 (16) I f this rule has prior confidence 0.80 (discussed further in the section on the generalized m o d u s p o n e n s ) , then to evaluate (Rs we must first find all the c O 182 J . J . Buckley et al. Q L v c3 ~... O .1.4 r - I 0 J P.4 o~ o~ o ~ o -r-/ r-4 ¢0 ° ~ ~J ..= _o L L o Extended Fuzzy Relations: Application 183 and, in particular, c72 = F72(cf(EE)R721EE, cf(MBP)R722MBP, cf(H)R723H) = min (cf(EE), cf(MBP), cf(H), 0.80) (17) We have assumed the columns of (Rs are labeled D l , M , and $1, so the second column is for manic. The relations in 6Is are very simple in that they pick off the confidence in the given condition. (More complicated relations are presented in the example in the section on application.) In this way all the c U are determined, and after taking column maximums we obtain the output O ~ = [ ° ~ l ' M ' S 1 0 2 03 1 (18) We next input O~, together with more facts 5:1, into a level two ERF (Rp to determine a fuzzy set of preliminary diagnoses. Let Vp = {depression (/)2), schizophrenia ($2), paranoid (P)} be the set of preliminary diagnoses. Here (Rp also represents a block of rules, and a rule from this block is If [symptom = M ] AND [symptom = D d AND [fact = persecutory or jealous delusions] AND [fact = H I , then [preliminary diagnosis=DE] (19) We code "persecutory or jealous delusions" as PJD. I f the number of this rule is five, then u5 = (Mr, Dl, PJD, H ) , and the data Dp for (Rp will contain (5:0, 5:0, cf(PJD), cf(H)) (20) U5 The columns in 6~p are labeled DE, $2, P, so csl = Fsl(5:o6isM, 5:o(RsDi, cf(PJD)RsI3PJD, cf(H)RsI4H) = rain (o2, ol, cf(PJD), cf(H), 0.90) (21) where 0.90 is the prior confidence in this rule. The output from CRp is OP= [0~22 ' $2 'o2 ~I (22) Lastly, Op and other facts 5:2 are put into a level three EFR (R: to obtain a fuzzy set of final diagnoses. Let V: = {D31, D3E, D33, S3I, S32, $33, $34, Pl, PE} be the collection of final diagnoses where, for example, D32 = manic- depressive, $33 = paranoid-schizophrenic, and so on. A rule from fRf is If [preliminary diagnosis = $2] AND [fact = PJD] AND [fact = H], then [final diagnosis = $33] (23) 184 J . J . Buckley et al. This rule has number three, so u3 = ( $ 2 , PJD, H) and ((5:0 U 5:1), c f ( P J D ) , c f ( H ) ) U3 is in Df. The column number for $33 is six, so C36=F36[(5:o O 5 : l ) ( ~ p S 2 , cf(PJD)R362PJD, cf(H)R363H] (24) = min [02, c f ( P J D ) , c f ( H ) , 1.01 if the rule confidence is one. The final output is , ° 21 (25) (26) Using (~f all the rules become I f the facts are 5:, then the (final) diagnosis is Of (27) Notice that multiple copies o f columns from (Rs can be in different cells in CRp, and multiple copies o f columns from ~ p may be in many different cells in (Ry. It may happen that we have two rules with the same attributes ui, same conclusion oj = Bj, but different relations Rij and R~. We would place both Rij t and Rij in the same (ij) cell but use possibly different functions F U and F:. to U obtain c U and c~, respectively, given data D. Then both cij and c~. would be input into f to obtain oj. The model can be easily extended to incorporate compound right sides. I f rules have multiple conclusions, then we would add more columns to the EFR; each vj would thus be a vector o f conclusions. We may also consider generalizing to process multidata simultaneously. The data D were assumed to be all the information necessary for one problem (run). To process many problems at once, the data are a vector ( D I , / ) 2 , " " ) and the output is separated into (Oi, 02, "" "). In the example in the section o f application, we process multidata simultaneously. In the next section we compare the generalized modus ponens approach to the extended fuzzy relation technique for modeling fuzzy production rules. We illustrate the use o f level one and level two extended fuzzy relations in an image processing problem in the section on application. We then argue, in the section o f parallel versus sequential processing, that the existence o f an EF R is a key to knowing when a block o f rules may be executed in parallel instead o f sequentially in a fuzzy expert system. The last section contains a brief summary and conclusions. Extended Fuzzy Relations: Application 185 T H E G E N E R A L I Z E D M O D U S P O N E N S The structure o f the generalized m o d u s p o n e n s (GMP) is (Zadeh [115, 16]) if x is A , then y is B x is D , then y is O (28) where A and D are fuzzy subsets o f U = {u~, . . . , urn} and B and O are fuzzy subsets o f V = {vl, • • ", v,}. One constructs, using A and B, a regular fuzzy relation R on U x V with values uiRvj = ~/ij (Mizumoto and Z i m m e r m a n [5], Mizumoto [6], Whalen and Schott [13], Yager [14]). Then O = D o R for some composition , ' o " . This is exactly our level zero evaluation o f an EFR. We m a y also model the G M P as a level one EFR. Consider the following block o f rules: I f xiRijui, then y is vj (29) for 1 _ i _ n, 1 < j _ m . The definition o f Rij is cij = diRijui= g ( di, "Yij) (30) and we therefore obtain the same conclusion that y is O as in the G M P . Both the G M P and the E F R method are used to construct fuzzy sets; however, there are basic differences in the two approaches. The G M P employs a fuzzy set B, which is actually part o f the rule, to obtain the fuzzy relation on U x V, whereas the E F R procedure uses the structure o f the left side o f a block o f rules to build the relation on U x V. In general, an EFR cannot be modeled as a single GMP. There are three main reasons for this conclusion: (1) the EFR method allows for general input; (2) a high-level EFR is evaluated differently than a G M P ; and (3) the E F R approach can incorporate prior rule confidence, thresholding, and consideration o f preexisting data stored in working m e m o r y . In the G M P the di belong to [0, 1], as D is a fuzzy subset o f U; in an EFR, however, the components o f a di can be numbers, strings, fuzzy numbers, or discrete fuzzy sets. The only restriction on the di is the data types and relations allowed in the system. The example in the next section has the di vectors o f fuzzy numbers and strings. Therefore, the E F R technique allows for general input, whereas the G M P accepts only discrete fuzzy set input. T o understand the second reason given above, consider a level two E F R 612. N o w 612 represents blocks o f rules, and each block could possibly be modeled as a GMP. W e m a y even be able to construct a larger G M P , say &, to model all the blocks and 612. However, the evaluation o f 612 and (P would be different. Assume we are employing the traditional m a x and min for finding final confidences. Then the output f r o m 612 is a fuzzy set O where oj is the column m a x o f a group o f numbers each the min o f other numbers c~/k, and each cuk could be the output o f a level one EFR, hence is the column max o f a set o f numbers each the min o f 186 J . J . Buckley et al. other numbers. None o f the suggested methods o f evaluating (P will produce the oj numbers. The third reason will be discussed below. Modeling the G M P as a level one E F R was artificial because we never use 7o = uiRvj tO evaluate an EFR. That is, our fuzzy production system (Buckley, Siler, and Tucker [3]; Buckley, Siler, and Tucker [4]; Siler, Buckley, and Tucker [10], Siler, Tucker [8]) does not require a fuzzy set B to obtain O. However, we do take into consideration the preexistence o f some fuzzy set for y . Suppose, through other blocks o f rules or from the initial data base, we already have in working m e m o r y y is E , where E is a fuzzy subset o f V. W e would not use E to evaluate the EFR, given x is D , but instead we would combine O and E into one final fuzzy subset for y . The G M P method does not allow for the existence o f this fuzzy set E . We will now show how the E F R procedure can handle E together with prior rule confidence and thresholding b y simply changing the Fi/functions. Consider the block o f rules given in equation (13) modeled by a level one E F R (Rj. Let r U, a number between zero and one, be the prior confidence in the rule given in the (ij)th cell in (R i. Thresholding is a procedure by which time is saved by not completely executing a rule whose left side has low confidence. Let T, a number between zero and one, be the threshold value. Suppose there already exists in working m e m o r y y is E where E = [ e ~ e ~ l , . . . , ( 3 1 ) Given that x is D , we first compute cok = d~k Ri/kUik (32) and ~ij=di * Riy=hu(col, "" ", cok i) (33) where now hi~ is the function that aggregates the ci/k into c,7- Then I e j if t?/7 < T c U m a x [min (t?i/, ri/), e/I, if G0_> T (34) The function F U is the method o f obtaining the c 0 from the cok, so now F 0 contains hi~ and equation (34). Given the c#, we find oj, our final confidence in o/, as before, using the f function. We use the term " w e a k l y m o n o t o n i c " for the procedure given in equation (34) because it never allows a confidence to decrease. That is, we never replace a preexisting confidence e / w i t h a lower value. The weakly monotonic method may be summarized as follows. First, the confidence in the left side o f a rule t~t/ is tested for threshold. Second, if t?i/ passes threshold, then the new rule confidence is the minimum o f t? U and the prior rule confidence r/j. Last, i f the new rule confidence exceeds e/, then the new rule confidence becomes our new Extended Fuzzy Relations: Application 187 confidence in oj; otherwise, there is no change in our confidence in oj. The final confidence in vj is still given as oj, a function o f the c U. O f course, one may consider using other appropriate functions for max and min in equation (34). The main difference between the GMP method and the level one EFR approach is their use o f preexisting fuzzy sets for the right sides o f rules. The GMP technique employs a fuzzy set, as part o f the rule, for the right side o f a rule in order to evaluate the rule. The EFR method, in contrast, is used to construct the fuzzy set for the right sides o f a block o f rules. Also, the EFR approach allows for preexisting fuzzy sets in working memory for the right sides o f rules. It is our experience that the G M P is not generally applicable to rule- based fuzzy expert systems because (1) we usually do not have fuzzy sets for right sides o f rules but instead wish to construct these fuzzy sets; and (2) we quite often have to deal with preexisting fuzzy sets, in working memory, for the right sides o f rules. A P P L I C A T I O N Our problem was to design an expert system to medically classify regions that were previously identified in an echocardiogram. All these details have been reported elsewhere (Buckley and Siler [2]; Siler, Tucker, Buckley, Hess and Powell [7]; Tucker, Siler, Powell, and Stanley [11]); therefore, we will be concerned here only with the facts necessary to construct fuzzy relations. Numerical feature extraction was first carried out for each region. The features o f each region used are area (a fuzzy number a); x-coordinate o f the centroid (a fuzzy number ~); y-coordinate o f the centroid (a fuzzy number .P); type; and border. Type equals 1(0) if the pixels in the region are turned on (off), and border equals 1(0) if the region touches (does not touch) the border o f the picture. Using the fuzzy numbers a, .~, and.~, we first constructed fuzzy subsets o f sets SIZE, XPOS, and YPOS, respectively. We will now discuss in detail the type one EFR that goes with SIZE. The set SIZE equals {teeny, small, medium, large, huge}. N(r) denotes an appropriate fuzzy number centered at r, and L T E (GTE) are regular fuzzy relations less than or equal to (greater than o f equal to) defined on fuzzy numbers. The block o f rules used to build the fuzzy subset o f SIZE are as follows: I f a L T E N(100), then SIZE teeny I f a L T E N(200) and G T E N(100), then SIZE small I f a L T E N(500) and G T E N(200), then SIZE medium I f a L T E N(1000) and G T E N(500), then SIZE large I f a G T E N(1000), then SIZE huge 188 J . J . Buckley et al. We now define a level one EFR 6t a to take the place o f this block o f rules. Let V = SIZE and ul = N(100), u2 = (N(100), N(200)), u3 = (N(200), N(500)), u4 = (N(500), N(1000)), and u5 = N(1000) with U = {Ul, " " , us}. The values o f the R U are Rll = LTE, R22 = R33 = R44 = (GTE, LTE), R55 = GTE, and all the ( i j ) cells are empty for i g: j . The data D values are d l = d5 = a and d2 = d3 = d4 = (a, a). This is a very simple EFR because all the cells o ff the main diagonal are empty. The output O = D o 61a, a fuzzy subset o f V = SIZE, is given by O = I °te--~ny " " " h~gge05 1 (35) where we use minimum for h22, h33, and h44, and n o f i s required because 61~ is diagonal. For example, c22 = min (a G T E N ( 1 0 0 ) , a LT E N(200)). (36) and 0 2 =- min (£~22, r 2 2 ) (37) where r22 is the prior confidence in this rule. The confidence o2 will be the same confidence in " s m a l l " as obtained in the second rule in the foregoing block o f rules. In constructing the fuzzy set SIZE we do not employ thresholding and the weakly monotonic procedure discussed in the preceding section. In this situation we would not have a preexisting fuzzy set for SIZE in working m e m o r y . Using 61~, this block o f rules is replaced by one rule: if the area is a, then SIZE is 0 (38) In a similar manner two other fuzzy subsets o f XPOS = {far left, left, center, right, far right} and YPOS = {very high, high, middle, low, very low} are constructed using ~? and y , respectively. The blocks o f rules used to accomplish this may be represented by level one extended fuzzy relations 61x and 61y, respectively. Sometimes blocks o f rules, each represented by an EFR, will form a network, with the output o f some EFR being the input into another EFR. This is what occurred in the image processing problem, as shown in Figure 2. The four EFRs in Figure 2 will now be combined into one level two EFR 612. The block of rules forming the primary classification may also be represented by an EFR 61c. Instead o f discussing how to define 61c, we will concentrate on combining the EFRs into one level two EFR. A sample o f the primary classification rules is as follows: I f SIZE teeny and Border = 1, then Artifact I f SIZE small and XPOS left and YPOS low, then RA I f SIZE large and YPOS low and Type = 0 and Border = 1, then Dead-Zone Extended Fuzzy Relations: Application i e~ .o ~.~ 0 189 .o 3 ~ N N N I,< Z d 190 J . J . Buckley et al. I f S I Z E small and X P O S right and Y P O S low and T y p e = 0, then L A I f X P O S c e n t e r and Y P O S v e r y high and T y p e = 0 and B o r d e r = 1, then D e a d - Z o n e I f S I Z E m e d i u m and X P O S left and Y P O S high, then R V I f S I Z E h u g e and V P O S l o w and T y p e = 0 and B o r d e r = 1, then D e a d Z o n e T h e r e a r e 11 p o s s i b l e classifications, which w e will call C l , • • ", Cll and then let V = {C1, " " , C11}. E a c h ui is a v e c t o r , o f length at m o s t 5, w h o s e c o m p o n e n t s a r e m e m b e r s o f S I Z E , X P O S , o r Y P O S , o r uik = 1 (0) f o r T y p e , o r uik = 1 (0) f o r B o r d e r . Also, e a c h R 0 is a v e c t o r w h o s e c o m p o n e n t s a r e ffi~, 61,~, ffty, R r , o r RB w h e r e R r (RB) is a b i n a r y relation f o r T y p e (Border). F o r the classification rules p r e s e n t e d a b o v e , let C1 = Artifact, (?2 = R A , C3 = D e a d - Z o n e , C4 = L A , C5 = R V, and ul = (teeny, 1) u2 = (small, left, low) u3 = (large, l o w , 0, 1) u4 = (small, right, l o w , 0) us = (center, v e r y high, 0, I) u6 = ( m e d i u m , left, high) u7 = (huge, l o w , 0, 1) T h e n w e see that R l l = ((Ra, RB) R22=((Pta, (R.¢, (Pry) R 3 3 = ( ( R a , (Ry, R r , RB) R44= (ffto, 61~, 6ty, R r ) R53 = ((R~, 61y, R T , R n ) R65 = (6ta, fft,~, 6~y) R73 = ((Ra, (Ry, R T , RB) T h i s is a level t w o E F R b e c a u s e the R o contain level o n e e x t e n d e d f u z z y relations. T h e structure o f the data e l e m e n t s di m a t c h e s the structure o f the ui. F o r the rules p r e s e n t e d , w e see that f o r a g i v e n r e g i o n dl = (a, B o r d e r ) d2 = ((a, a ) , (.~, .¢), (.~, y ) ) Extended Fuzzy Relations: d3 d4 d5 d6 d7 Application = ((a, a), ( y , y ) , Type, Border) = ((a, a), (.¢, .¢), ( y , y ) , Type) = ((.~, ~¢), fl, Type, Border) = ((a, a), (~, ~), ( y , y ) ) = (a, (.P, y ) , Type, Border) 191 The fuzzy set o f primary classifications O is determined by D o CR2. We use min for the hij functions, max for f , prior rule confidence ru, but no thresholding or weakly monotonic methods in equation (34). Let us illustrate the method by finding o3 for Dead-Zone. We have ~33=min ((a, a)(Ra large, ( y , y)¢Ry low, Type RrO, Border RB1) (39) and C33 = min (e33, 7"33) (40) The value o f (a, a)(Ra large is the 64 output from the CRa EFR. The relation Type RrO is one if Type = 0 and zero otherwise, and Border R s 1 is one if Border = 1 and zero otherwise. Similarly, we compute c53, c73, ct3, and so forth and obtain 03 = f ( ¢ 3 3 , C53, C73, "" ") (41) Using (R2, the entire primary classification becomes one rule: if the data is D, then the classification is O (42) In a fuzzy expert system not all rules or blocks o f rules may be modeled by extended fuzzy relations. One obvious situation is where the right side o f a rule calls for user interaction. Any action in the right side o f a rule that cannot be interpreted as making or changing a fuzzy set will not come under the domain o f extend fuzzy relations. PARALLEL VERSUS SEQUENTIAL An important question being asked by many computer people (both algorithm and hardware oriented) is the question o f when a problem is suitable for parallel processing. In his book Uhr [12] points out that parallel processing will be an important part o f future computing systems but that many obstacles must be overcome prior to widespread use o f these techniques. Through our work with a parallel rule-firing expert system (Siler, Tucker, and Buckley [9]), we have also become interested in this question. We would like to be able to quantify those characteristics which are possessed by problems suitable for parallel processing and use this as a means o f discriminating between 192 J . J . Bucldey et al. those problems which are suitable for parallel processing and those which are not. The motivation for such work is to us obvious. It has been argued that parallel processing will result in an increase in system performance. We have shown [9] that for a particular problem, that of echocardiogram image analysis, there is an overall increase in run-time performance by a factor o f 6 using a software emulation o f a parallel machine. Unfortunately, not all problems are ones that stand to benefit from use o f parallel computing techniques. In a broad sense we have grouped those problems which yield to inductive reasoning as being suitable for parallel processing, and those which yield to deductive reasoning as being suitable for sequential processing. This measure is a qualitative one and gives no indication o f the specific nature o f the parallelism within the problem. A problem may be one that does not fit this classification scheme well, having subproblems that are both inductive and deductive in nature. What is needed is a quantitative method for expressing the " a m o u n t " o f parallelism that a problem possesses and where that parallelism lies. Once this has been established, we may better apply existing techniques to solve the problem at hand. To this end we propose that the development o f an EFR or a set o f related EFRs is a technique whereby the parallel nature o f a problem can be demonstrated. In the preceding discussion we have shown that the evaluation o f an EFR is (minimally) equivalent to the processing o f several rules simultane- ously. On a suitably designed machine, we think that an EFR can be effectively evaluated in one step. What we must do is to describe such a machine and show where the parallelism lies. For such a machine, the input would be as described above, a vector o f data. In a preprocessing step, copies o f the data, one for each nonempty (ij) position in the EFR, would be produced and distributed to the processing elements, one processing element for each nonempty (ij) position. After this preprocessing, the evaluation o f each o f the inner products di * R 0 and the cij would take place. In a final post-processing step, the outputs o f the rn processors in each column can be aggregated to produce the resulting fuzzy output O. According to our definition o f a level g >_ 1 EFR, each Rij may be a vector o f Ki extended fuzzy relations. For the EFR to be evaluated as efficiently as possible, each o f the Ki relations Rijk must be processed simultaneously. This requires that there be Ki such machines at each o f the (ij) processing elements in (R. This results in a hierarchical view o f the parallelism that may exist in a problem. If we look at the echocardiogram analysis example presented earlier, we see that this is an EFR in which each of the relational components Rij can contain three EFRs and two binary relations. Clearly this could be represented as a problem with two levels o f parallelism, the first (lower level) being the processing o f area and centroid data to generate suitable fuzzy sets for the Extended Fuzzy Relations: Application 193 higher-level process, the generation o f the preliminary classifications (see Figure 2). In our production system, operating in parallel mode, we emulate the machine just described. The production s y s t e m ' s working m e m o r y acts as a central store for data that are accessible to all the R i f t c relations, and all those R i j k relations which have suitable data are made active at once. The m e m o r y management techniques (weakly monotonic) described in the section on the generalized m o d u s p o n e n s function as the post-processing step and produce a column output for the EFR. S U M M A R Y A N D C O N C L U S I O N S This article first introduced the idea o f an extended fuzzy relation 6t. The relation between two elements, say u and v, is u61v = (R1, " " , R x ) , where each Rk is a regular fuzzy relation or an extended fuzzy relation. Another type o f extended fuzzy relation has been considered by Bezdek, Pettus, Stephens, and Zhang [1] and Zhang, Bezdek, Pettus, and Stephens [17], where u61v is a fuzzy set representing a linguistic variable. Their application is knowledge representa- tion or information retrieval in an expert system. Our application is the use o f extended fuzzy relations to replace blocks o f rules in a fuzzy expert system with one rule. We have shown that our procedure contains the generalized m o d u s p o n e n s and have also shown how to construct extended fuzzy relations in two examples. W e have then argued that knowing that an extended fuzzy relation exists for a block o f rules may be the key to knowing when to process these rules in parallel instead o f sequentially. Firing rules in parallel, as opposed to sequentially, has two main advantages. First, a rule conflict algorithm, to determine which rule to fire when a group o f rules become fireable, is not needed. Second, there is no stacking o f unfired rules with subsequent backtracking. Parallel execution can result in a substantial reduction in system overhead and an increase in computational efficiency [9]. However, when operating in a parallel mode we need a m e m o r y conflict algorithm. When the system attempts to execute several rules all having the same conclusion, we need to decide on the final confidence we will place in this conclusion. Our system employs weakly monotonic logic for m e m o r y conflict resolution. The incorporation o f weakly monotonic logic into the extended fuzzy relation technique has been discussed in the section on the generalized m o d u s p o n e n s . Future research is needed to determine existence theorems for extended fuzzy relations. Results such as the following are needed for expert systems: I f your problem has characteristics ~,/3, .y, • • . , then theorem 3 says that there exists an extended fuzzy relation for this problem. Therefore, characteristics c~,/3, 3', " " " are sufficient for putting the problem on a parallel machine. 194 J . J . Buckley et al. References 1. Bezdek, J. C., Pettus, R. O., Stephens, L. M., and W.-R. Zhang, Knowledge representation using linguistic fuzzy similarity relations, Int. J. Man-Machine Stud. (to appear). 2. Buckley, J. J., and Siler, W., Echocardiogram analysis using fuzzy numbers and relations, Fuzzy Sets & Syst. (to appear). 3. Buckley, J. J., Siler, W., and Tucker, D., A fuzzy expert system, Fuzzy Sets & Syst. 20, 1-16, 1986. 4. Buckley, J. J., Siler, W., and Tucker, D., FLOPS, A fuzzy expert system: Applications and perspectives, in Fuzzy Logics in Knowledge Engineering (C. V. Negoita, and H. Prade, Eds.), Rheinland, Germany, Verlag TUV, 256-274, 1986. 5. Mizumoto, M., and Zimmermann, H.-J., Comparison of fuzzy reasoning methods, Fuzzy Sets & Syst. 8, 253-283, 1982. 6. Mizumoto, M., Fuzzy reasoning under new compositional rules of inference, Kybernetics 12, 107-117, 1985. 7. Siler, W., Tucker, D., Buckley, J. J., Hess, R. G., and Powell, V. G., Artificial intelligence in processing a sequence of time-varying images, Proceedings o f the International Society f o r Optical Engineering 548, 194-199, 1985. 8. Siler, W., and Tucker, D., FLOPS, A Fuzzy Logic Production System User's Manual, Kemp-Carraway Heart Institute, Birmingham, Ala. 1986. 9. Siler, W., Tucker, D., and Buckley, J. J., A parallel rule firing fuzzy production system with resolution of memory conflicts by weak fuzzy monotonicity, applied to the classification of multiple objects characterized by multiple uncertain features, Int. J. Man-Machine Studies (to appear). 10. Siler, W., Buckley, J. J., and Tucker, D., Functional requirements for a fuzzy expert system shell, in Artificial Intelligence: Applications o f Quantitative Reasoning (L. Zadeh and E. Sanchez, Eds.), Pergamon Press, New York, 21-31, 1987. 11. Tucker, D., Siler, W., Powell, V. G., and Stanley, A. W. H., FLOPS: A fuzzy expert system used in unsupervised enchocardiogram analysis, Computers in Cardiology, 341-344, 1985. 12. Uhr, L., Algorithm-Structured Computer Arrays and Networks, Academic Press, New York, 1984. 13. Whalen, T., and Schott, B., Alternative logics for approximate reasoning in expert systems: A comparative study, Int. J. Man-Machine Stud. 22, 327-346, 1985. 14. Yager, R. R., On the implication operator in fuzzy logic, Info, Sci. 31, 141-164, 1983. Extended Fuzzy Relations: Application 195 15. Zadeh, L. A., A theory of approximate reasoning, in Machine Intelligence 9 (J. E. Hayes, D. Michie, and L. I. Kulich, Eds.), John Wiley, New York, 149-194, 1979. 16. Zadeh, L. A., The role of fuzzy logic in the management of uncertainty in expert systems, F u z z y Sets & Syst. 11, 199-227, 1983. 17. Zhang, W. R., Bezdek, J. C., Pettus, R. O., and Stephens, L. M., Linguistic fuzzy relations in expert systems, presented at the Third Annual Computer Science Symposium on Knowledge Based Systems: Theory and Applications, Univ. South Carolina, Columbia, So. Carolina, 1986.