Propagation of Preference Relations in Qualitative Inference Networks

1 Introduction

Many intelligent systems employ the numeric degrees of belief to make decisions. One of the difficulties often en­ countered in using a quantitative theory of partial belief is the estimation of the required numeric input . In creat­ ing the knowledge base, the human expert may not be fa­ miliar with expressing his belief in terms of numeric val­ ues. Thus, the problem of obtaining the numeric degrees of belief from the expert is a major concern in the design of a decision support system. On the other hand, there are qualitative methods for uncertain reasoning such as those using qualitative probability, qualitative belief or relative plausibility, which are all based on the concept of preference relations. In these approaches, the experts are not required to provide numeric values for the indi­ vidual propositions, but are asked instead to specify the qualitative relationships between the propositions. In many applications, the qualitative approaches seem to be more realistic, as it may not be feasible to represent the available information numerically. Besides, people are usually more confident in supplying qualitative re­ lationships such as proposition A is more probable than proposition B.

In addition to the representation of uncertain informa­ tion, another important issue is to propagate such infor­ mation. Many researchers have studied the possibility of using networks for inference. Heckerman (1986), Pearl (1986), Shenoy and Shafer (1986) studied the propaga­ tion of quantitative information such as certainty factors, probability and belief functions in quantitative networks. Wellman (1990) extended Pearl's framework to quali­ tative networks by classifying the influence of different sources of evidence on a proposition into four classes +,

- , 0, and ?. If the class is+, then the proposition has become more probable due to the presence of the new evidence. On the other hand if the class is -, then the proposition has become less probable due to the pres­ ence of the new evidence. Class 0 indicates that the new evidence has no influence on the probability of the proposition, while class ? indicates that the influence of the evidence on the proposition is unknown. One can also define different operators for the manipulation of these influences. It is clear that qualitative networks can be useful for suggesting potential actions, eliminat­ ing inferior plans, identifying important tradeoffs, and explaining probability models (Wellman, 1990) . How­ ever, Wellman's study is restricted to frames with only two elements (a proposition and its negation) , and the suggested classification of influence lacks a theoretical basis.

This study outlines a qualitative inference network whose nodes are frames of discernment consisting of mutually exclusive and exhaustive propositions, and whose edges represent the relationships between differ­ ent frames. In such a network, the two basic rules are the sequential and parallel combinations of propagat ions (Heckerman, 1986). The former deals with propagat ing information from a frame S to another frame T, from T to e, and so on, in a sequential manner . The lat­ ter considers the propagation of information from two or more frames, T1 , T2 , ... , to another frame e foll owed by a parallel combination of the propagated information (Lingras and Wong, 1990a).

The main objective of this paper is to analyze the fundamental elements of a qualitative inference network based on preference relations, namely, the sequential and parallel combinations of qualitative information . We be­ lieve that the results of this analysis provide a basis for the development of a network useful for qualitative rea­ soning.

2 Qualitative Preference Structures

Suppose e = {lh, ... , Om} is a finite set of all possible answers to a given question according to one's knowl­ edge, and only one of these answers is correct. This set e is referred to as the frame of discernment or simply the frame defined by the question (Shafer, 1976). Any subset A~ e is regarded as a proposition, which reprcsenls the assertion that the correct answer to the ques­ tion lies in A. The power set 2° of e denotes the set of all propositions discerned by the frame e. In a situation with incomplete or vague information, it is not possible to say with certainty which proposition contains the cor­ rect answer. However, based on the evidence at hand it may be possible to express one's judgement on a given proposition either quantitatively or qualitatively. In the quantitative representation, a real number is used to in­ dicate the degree of belief in a proposition. Alternatively, one can also characterize the uncertain knowledge qual­ itatively in terms of a preference relation. We assume that one can define the preference or indifference rela­ tionship between any two propositions A, B E 2°. The assertion, A is preferred to B, is denoted by A >- B. In the absence of strict preference, i.e., -,(A >- B) and -,(B >- A), we say that A and B are indifferent, written A ....., B. That is, the preference relation >- represents the qualitative information or one's knowledge about a particular situation. The precise meaning of the pref­ erence relation depends of course on the context of the application. For example, in the exposition of qualita­ tive probability, A >- B represents the assertion that A is more probable than B.

The notion of preference relations enables us to spec­ ify whether a given proposition is more probable than another proposition. Such a notion can be useful for a number of reasons. For example, if it is not possible to provide a reliable estimation of the required quantitative probabilities, a preference relation can provide a more re­ alistic model of random phenomena. Obviously, qualita­ tive preference relations provide a wider class of models to represent a given situation than quantitative probabil­ ities. Preference relations also facilitate the study of the structures of quantitative probabilities and belief func­ tions (Fine, 1973). To illustrate this point, consider the following axioms that impose certain restrictions on the class of preference relations that can be used for repre­ senting uncertain information:

• (i) Asymmetry: A >- B ==::} -,(B >- A)
• ( ii) Negative Transitivity: .,(A>- B) & .,(B >- C) ==::} -,(A >- C)
• (iii) Dominance: For all A, B E 2°, A :::> B ==::} A >- B or A ....., B
• (iv) Pa-;.tial monotonicity: For all A, B, C E 2°, if A :::> B & An C ::f 0, then A >- B ==::} (AU C) >- (B U C)
• ( v) N ontriviality: e >- 0

Wong et al. (1990) have shown that there exists a belief function consistent with >-, i.e.,

if and only if the preference relation >- satisfies axioms (i) - (v) . The belief function obeys the following three axioms (Shafer, 1976; Smets, 1988):

1. Be/(0) = 0 ,
2. Bel(e) = 1 ,
3. For every positive integer n and every collection A1, ... , An of subsets of e,

Thus, belief functions can be used to represent the class of preference relations which obey axioms (i)-(v) . A preference relation satisfying axioms (i)-(v) is called a qualitative belief or a belief relation (Yao and Wong, 1990). For a given belief function, one can define a plau­ sibility function PI as follows : for A E 2°,

where Ac represents the complement of A, i.e., Ac = 0 - A. Similarly, we can also define a qualitative counterpart of a plausibility function . Let >-Bel be a belief relation , the corresponding plausibility relation >-PI is defined as:

which is consistent with the definition of plausibility functions.

Based on the notion of preference relations, in the fol­ lowing section we consider a qualitative inference net­ work, and analyze the fundamental elements of such a. network.

3 A Qualitative Inference Network

In making decisions, we are often interested in a number of related questions. We can formulate a frame of dis­ cernment for each question, and build a qualitative in­ ference network based on the relationships (represented by compatibility relations) between these frames . If we want to evaluate the beliefs in a particular frame, we may have to propagate and combine the beliefs from dif­ ferent sources of evidence to the frame of interest . Thus , we have to consider the propagation of information from one frame to another (Yao and Wong, 1990), and the sequential and parallel combination rules (Lingras and Wong, 1990a).

We assume that the information about a frame T is represented by a preference relation >-, and that the re­ lationship between frame T and the frame of interest 0 is described by a compatibility relation. We consider the propagation of the preference relation >- on frame T to frame e.

Definition 1: Consider two frames T and e. An element t E Tis compatible with an element 8 E e, written t C 0, if the proposition {t} does not contradict the proposition {8}.

Compatibility is symmetric: t is compatible with 8 if and only if 8 is compatible with t. A compatibility relation C between two frames T and e is a subset of pairs (t , 0) in the Cartesian product T X e such that t c 0. The compatibility relation provides a qualitative description of the relationships between the elements of two frames .

Definition 2: A compatibility relation C between two frames T and 8 is complete if for any t E T there exists a 8 E e such that t C 8, and vice versa.

Without loss of generality, we may assume that the com­ patibility relation between any two frames is complete, because one can always obtain a reduced frame by delet­ ing those elements in one of the frames which are not compatible with any element in the other frame, and vtce versa.

Definition 3: Given a compatibility relation C between two frames T and e, we can define a mapping r which assigns a subset f(t) ~ e for every t E T by:

For any subset A ~ e, the lower and upper preimages of A, written ~(A) and w(A), are defined as:

and

The set ~(A) consists of the elements in T which are compatible with only the elements in A, and the set w(A) consists of the elements in T which are compatible with at least one element in A. Upper and lower preimages are similar to the inner and outer reductions discussed by Shafer (1976). For any X E 2T, we use f(X) to denote the following subset of e:

Note that we have adopted the notation, f({t}) = f(t).

If the information regarding the propositions in 2T is described by a preference relation, one can propagate this relation to another frame using the upper and lower preimages.

Definition 4: Let T and e be two frames, and let C be a compatibility relation between T and e. For a given preference relation >- on 2T, the lower and upper preference relations, · >- and · >-, on 2° are defined as: for A,B E 2 9 ,

and

The mapping~ : 2 9 - 2T can be considered as a pes­ simistic way in which the (comparative or quantitative) belief in the propositions discerned by T can be trans­ ferred to the propositions discerned by e (Lingras and Wong, 1990b) . Hence, we will refer to the propagation from >- on 2T to .>- on 2 9 as the pessimistic propagation of >-. Similarly, we will refer to the propagation from >­ on 2T to *>- on 2° as the optimistic propagation of >­ defined by the mapping w : 2 9 - 2T. In a qualitative inference network, we can either use the pessimistic or the optimistic propagation depending upon the applica­ tion. It is also possible to use a combination of both the pessimistic and optimistic propagations.

Example 1: Consider a question regarding a chemical solution: Is it acidic, alkaline or neutral? Let e = { ac, al, ne} be the frame consisting of all possible an­ swers to this question.

(i) Suppose we have a reading 6.5 ± 0.5 from a pH­ meter for the solution. If we use this pH value as a measure of acidity of the solution, we will have to con­ sider the question of reliability of the pH-meter. The frame corresponding to this question is defined by T1 = {reliable, unreliable}. Based on our knowledge of the pH-meter, we can specify the following weak order (Fish­ burn, 1972):

Here a proposition is preferred over another proposi­ tion if it appears on the left hand side and is separated by at least one >-1 symbol. Thus, T1 is preferred over {reliable}, {unreliable} and 0, and so on.

(ii) Suppose we receive another evidence from a lit­ mus test conducted by a student. He observed that the change in color of the litmus paper was so slight that it was hard to say whether the solution was acidic, al­ kaline or neutral. Nevertheless, he specified his degrees of belief by the following preference relation on a frame T2 = {change, no-change}:

Although, the frames T1 and T2 are not directly related totheframeofinterest, e = {ac,al,ne}, we can transfer the available information to obtain a preference relation on e. We may use the pessimistic propagation scheme to propagate the preference relations >- 1 on frame T1 and >-2 on frame T2 to frame e, respectively.

(iii) We know that if the pH value is less than 7, the solution is acidic; equal to 7, the solution is neutral; greater than 7, the solution is alkaline. Therefore, based on the pH-meter reading and our knowledge of chemistry, the compatibility relationships between the elements of T1 = {reliable, unreliable} and e = {ac, al, ne} can be expressed as:

The above compatibility relationships enable us to com­ pute the lower preimages of the propositions in e, namely:

From these lower preimages, we obtain the relation .>- 1 on 2 9 as a result of the propagation of the relation >- 1 on 2T 1 :

(iv) We know that if the color of the litmus paper does not change, the solution is neutral; otherwise it is ac or al . Thus, the compatibility relationships be­ tween the elements of 12 = {change, no- change} and e = {ac, a/,ne} are given by:

These compatibility relationships lead to the following lower preimages of the propositions in e :

Similarly, we can use these lower preimages to define the pessimistic propagation of >-2 on frame T2 to frame e. We obtain:

Yao and Wong (1990) showed that the result of quali­ tative propagation is consistent with that of quantitative propagation (Dempster, 1967). The following theorem demonstrates that the pessimistic propagation of a be­ lief relation on a frame results in a belief relation on an­ other frame. The same can be said about the optimistic propagation of a plausibility relation.

Theorem 1: Consider two frames T and e , and a com­ patibility relation C between T and e. Let >-Bel be a belief relation on 2T, and >-PI the corresponding plau­ sibility relation. The relation .>-Bel propagated from >-Bel is a belief relation on 2°, and the relation *>-PI propagated from >-PI is a plausibility relation of .>-Bel , namely, A *>-PI B-¢::=:} Be .>-Bd Ac .

It is clear that we can easily apply the pessimistic or optimistic propagation scheme described above to prop­ agate a preference relation from one frame to another. In a complex inference network, the propagation of un­ certain information is accomplished by combining two el­ ementary sequential and parallel networks (Beckerman, 1986) . In an elmentary sequential network, the propa­ gation from S to T, and the propagation from T to e are combined to obtain a propagation from S to e. In an elementary parallel network, we have a set of eviden­ tial frames T1 , . . . , Tn which are connected to the same hypothesis frame e. The propagations from T; toe are combined in parallel in frame e. In the subsequent dis­ cussion, we will analyze these two combination schemes.

(I) Sequential Combination

Let >- be a preference relation on frame S, C1 a com­ patibility relation between S and T, and C2 between T and e. We are interested in the propagation of the preference relation >- to e based on the compatibility rel ations C1 and C2.

Recall that one can use the pessimistic propagation to construct a preference relation .>- on 2T from the prefer­ ence relation >- on 2 5 . By using the same procedure, one can construct a preference relation · >- on 2° from · >­ on 2T . Similarly, one can use the optimistic propagation scheme to obtain a preference relation *>- on 2° from >on 2 5 . The preference relations · >- and · >- on 2° are the results of the sequential combination of the two-step propagations from S to T , and from T to e . In fact , the sequential combination can be expressed directly in terms of the composition of the compatibility relations cl and c2.

Definition 5: Let S, T, e be three frames , C1 a com­ patibility relation between S and T, and C2 a compat­ ibility relation between T and e. A composite relation c = cl 0 c2 between sand e can be defined as follows: for s E S and 8 E e, s C1 o C2 8 if and only if there exists t E T such that s C1 t and t C2 8.

One may argue that an element s E S may not be compatible with an element 8 E e even if there is an element t E T such that s C1 t and t C2 8. However, it is reasonable to assume that s is not compatible with 8 if there is no t satisfying s C1 t and t C2 8. Thus, in the absence of any direct relationship between the two frames s and e, the composite relation as defined by definition 5 may be an acceptable solution.

Based on the composite relation C1 o C2 , one may directly propagate the relation >- from frame S to frame 8 in just one step instead of two. The following theorem shows that the results of these two combination schemes are the same.

Theorem 2: Let S , T, e be three frames , C1 a compati­ bility relation between S and T, and C2 a compatibili ty relation between T and e. For a given preference re­ lation >- on frame S, the results of propagating >- first from S to T by C1 and then from T to e by C2 are the same as that of propagating >- directly from T to e by the composite relation cl 0 c2.

Proof. Let rl(s) = {t E TIs cl t} for every s E S , and r2(t) = {8 E e It c2 8} for every t E T . Given the com­ posite relation cl 0 c2, we can define a composite mapping from s toe by r2orl(s) = r2(rl(s)) = u r2(t) ter, (· )

for every s E S. Therefore, for any subset A ~ e , we have:

The set ~,oc,(A) represents the lower preimage of A by a one-step propagation, and the set ~.(~,(A)) is the lower preimage of A by a two-step propagation. Sim­ ilarly, the set wc,oc,(A) represents the upper preimage of A by a one-step propagation, and the set w c 1 (w c, (A)) is the upper preimage of A by a two-step propaga­ tion. Here, we only need to prove that ~.oc,(A ) = ~. (~,(A)) and wc,oc,(A) = we, (wc, (A)) for every subset A~ e .

Suppose s E ~.(~,(A)). It follows that f 1(s) ~ ~,(A) . Hence, for every t E f 1 (s) , t E ~c, (A) . This implies that f2(t) ~ A . Therefore, we can immediately conclude that f2(f1(s)) ~ A. That is, s E ~,oc, (A) . Thus, ~~(~,(A)) ~ ~c,oc,(A) . Now assume that s E ~,oc (A) . This is equivalent to f 2(ft(s)) ~ A, which implies that for every t E f 1(s) , we must have f2(t) ~ A. Hence, t E ~, (A) . In other words, we obtain f 1(s) ~ ~c~(A) . Thus, s E ~~(~~(A)) . This means that ~c,oc~(A) ~ ~. (~c~(A)). We can there­ fore conclude that ~,oc~(A) = ~c, (~~(A)) . Similarly, one can prove that wc,oc~(A) =we, (wc,(A)) D.

Theorem 2 provides a possibility of reducing a two­ step propagation to a one-step propagation . Since both the one-step and two-step propagations produce the same results, the sequential propagation from S to T to e can be replaced by a propagation directly from s to e using the composite relation. Such a simplification can result in an efficient method for sequential propagation.

(II) Parallel Combination

Suppose T1 , · ·· , Tn serve as evidential frames for e. Let >-; be the preference relation on 2T;, i = 1, ... , n. We first propagate the individual preference relation >-; on 2T; to >-'; on 2° using either the pessimistic or optimistic propagation scheme. Our objective is to determine the preference relation >- on 2° based on the combined ev­ idence. Such a combination is referred to as the paral­ lel combination. Obviously, the combined preference re­ lation should preserve as many preference relationships from the individual preference relations>-';, i = 1, ... , n as possible. If we assume for the time being that the preference relations involved are not restricted by any axioms , we can use the following combination rule: for A,B E 2°,

This simple combination scheme preserves all the rela­ tionships from the individual preference relations. How­ ever, in this process, we may also have inadvertently ac­ cumulated many contradictory preference relationships such as:

In order to avoid such contradictions, we may have to impose restrictions on the preference relations >- and >-'; by introducing various axioms (Fishburn, 1972; Savage, 1972; Yao and Wong, 1990). In that case, we will have to construct appropriate combination rules accordingly.

If the preference relation >- is to obey a given set of axioms L, then certain relationships are not allowed. For example, if >- is asymmetric, then we cannot have both A >- B and B >- A in the combined relation. A se­ lection scheme can be explicitly defined by specifying priorities among the relationships from the preference relations >-';, i = 1, ... , n , as follows :

• (a) In general, the preference relationships>-'; are more important in decision making than the indifference re­ lationships -';. Hence, we may want to assign higher priority to the preference relationships >-'; than the in­ difference relationships -';.
• (b) We arrange the same type ofrelationships in an order according to the priority( i) assigned to each preference relation>-';, i = 1, ... , n.

(c) If two relationships cannot be arranged in the order according to (a) and (b), then, we may have to introduce some other predefined order .

We have just described one of the many possible pri­ ority schemes. Depending upon the application and the nature of the evidence, a system designer can choose an appropriate priority scheme for ordering the preference relations.

Once we have assigned priorities to the individual pref­ erence relations >-';, i = 1, ... , n, we can apply combina­ tion rule (10) to the individual preference relationships. Let U be the set of relationships in the combined prefer­ ence relation >-. Initially, U = 0. For every relationship A >-'; B, we add the relationship A >- B to the set U, provided that based on the set of axioms L, the relation­ ships in U do not infer the contradictory relationship ...,(A >- B). Similarly, for every relationship A "'i B we add the relationship A "' B to the set U if the relation­ ships in U do not infer the contradictory relationship -,(A"' B). Thus, combination rule (10) can be modified as: for A, B E 2°,

The expression U ~L ...,(A "' B) denotes the fact that the relationships in U do not logically infer ...,(A '"" B) with the set of axioms L. The combination rule (12) can be implemented using standard logic programming techniques. In practice, the.expert may be able to specify only a few relationships in a given preference relation. In that case, the execution of the qualitative combination rule will be reasonably fast .

If the individual relations >-'1, .. . , >-' n completely de­ scribe the relationship between all the pairs in 2° x 2° (i.e., either A >- B, B >- A or A "' B holds for all A, B E 2°), it can be easily seen that the combined re­ lation >- will also completely describe the relationship between all the pairs in 2° x 2°. Moreover, since we do not add to U either A >- B or A "' B if it violates the axioms in L, the combined relation >- will also obey the axioms in L . Thus, similar to Theorem 1, we can state the following result .

Theorem 3: If >-'1 , ... , >-' n defined on 2° are belief re­ lations, the combined relation >- obtained by using rule (12) is also a belief relation, provided that Lis equivalent to axioms (i)-(v).

The proof of Theorem 3 follows immediately from the preceding discussions.

Based on Theorems 1 and 3, we can say that if the input preference relations obey axioms (i)-(v), then the preference relations resulting from sequential and paral­ lel combinations will also obey axioms (i)-(v) . Moreover, the parallel combination rule discussed here is related to quantitative combination rules such as the Dempster rule. A detailed discussion on such a relationship can be found in (Lingras and Wong, 1990a). Hence, the sequen­ tial and parallel combinations discussed here can be used to propagate uncertain information that can be modeled by a subset of axioms (i)-(v) in any qualitative inference network.

Example 2. Consider the two preference relations .>- 1 and .>-2 from Example 1. Our objective is to construct the combined preference relation >- to reflect the accu­ mulated evidence from the pH-meter reading and the litmus test. Suppose .>-1 , .>-2 , and >- obey the set of axioms L = {asymmetry, negative transitivity} for a weak order .

We can order the preference relationships from .>-1 and .>-2 , for example, according to the priority scheme de­ scribed earlier. The following priority scheme is used in this example.

Initially, U = 0. Since U ~L ...,(0 >- {ac,ne}), we add the relationship 0 >- {ac, ne} to U based on rule (12) . Using the same argument, we can check if we can add all the preference relationships from .>-1 and · >- 2 . We obtain the following weak order:

Note that we did not add the relationships such as {ac, a/} .>-t{ac,ne} (i.e., no. 22 in the priority scheme) to U, because

after adding the first 21 relationships. 0

4 Summary and Conclusion

Preference relations, which specify whether a given proposition is more probable than another proposition, provide a more realistic model to represent uncertain information than quantitative probability or belief func­ tions. In order to use preference relations for reason­ ing under uncertainty, it may be necessary to organize and propagate the available information in a qualita­ tive network. Sequential and parallel combinations of propagated information are two of the fundamental el­ ements in such a system. This paper suggests rules for sequential and parallel combinations using the notion of compatibility relationships. It is also shown that if the input preference relations obey certain properties, the combined relations will also obey these properties.

The qualitative inference networks discussed here are different from Wellman's qualitative probabilistic net­ works. The ·qualitative probabilistic relations used by Wellman correspond to the compatibility relations in this study. The use of qualitative probabilistic relations in­ stead of compatibility relations may lead to a more gen­ eralized qualitative inference network.