An Axiomatic Framework for Propagating Uncertainty in Directed Acyclic Networks

An Axiomatic Framework for Propagating Uncertainty in Directed Acyclic Networks Jos6 Cano, Miguel Delgado, and Serafin Moral Universidad de Granada, Granada, Spain ABSTRACT This paper presents an axiomatic system for propagating uncertainty in Pearl's causal networks, (Probabilistic Reasoning in Intelligent Systems: Networks of Plausible Inference, 1988 [7]). The main objective is to study all aspects of knowledge representation and reasoning in causal networks from an abstract point of view, independent of the particular theory being used to represent information (probabilities, belief functions or upper and lower probabilities). This is achieved by expressing concepts and algorithms in terms of valuations, an abstract mathematical concept representing a piece of information, introduced by Shenoy and Sharer [1, 2]. Three new axioms are added to Shenoy and Shafer's axiomatic framework [1, 2], for the propagation of general valuations in hypertrees. These axioms allow us to address from an abstract point of view concepts such as conditional information (a generalization of conditional probabilities) and give rules relating the decomposition of global information with the concept of independence (a generalization of probability rules allowing the decomposition of a bidimensional distribution with independent marginals in the product of its two marginals). Finally, Pearl's propagation algorithms are also developed and expressed in terms of operations with valuations. KEYWORDS: causal network, uncertainty, hypertrees, PULCINELLA system, marginalization, combination, conditional information 1. INTRODUCTION Shenoy and Shafer [1, 2] have given an axiomatic framework for the propagation of uncertainty in hypergraphs. In this work the propagation Address correspondence to Serafin Moral, Department of Artificial Intelligence, Campus de Fuente Nueca, University of Granada 18071, Granada, Spain. Received January 1, 1992; accepted September 9, 1992. International Journal of Approximate Reasoning 1993; 8:253-280 © 1993 Elsevier Science Publishing Co., Inc. 655 Avenue of the Americas, New York, NY 10010 0888-613X/93/$6.00 253 254 Jos6 Cano, Miguel Delgado, and Serafin Moral algorithms are abstracted from the particular theory being used to represent information. They introduce the primitive concept of valuation, which can be considered as the mathematical representation of a piece of information. A valuation may be particularized to a possibility distribution, a probability distribution, a belief function, etc. Then they develop and express propagation algorithms in terms of operations with valuations. These algorithms may be particularized to any concrete theory by translating valuations and operations to their special interpretation in this theory. These general algorithms have been implemented in the PULCINELLA system [3]. The notation used in this paper, and examples of what is a valuation in Probability Theory and Theory of Belief Functions, are as follows: NOTATION Assume that we have an n-dimensional variable, (X~ ..... Xn), each dimension, X i, taking values on a finite set U~. The following conventions will be followed: • If I ___ {1 .... , n}, we shall denote by X I the I/L-dimensional variable (lI[ is the number of elements of set I), (Xi)i~ 1, and by UI the cartesian product l--[ i E 1 Ui, that is the set in which X i takes its values. • If u ~ U~, then we shall denote by u i the ith coordinate of u, that is the element from U/. • If u ~ U 1 and J ___ I, we shall denote by u + g the element from Uj obtained from u by dropping the extra coordinates; that is, the element given by u) J = u j, Vj ~ J. • If A ___ U 1 and J __. I, we shall denote by A + J the subset of Uj, given by A *J = (rE UjIv= u +J,u cal. EXAMPLE 1 In Probability Theory a valuation is the representation of a probabilistic piece of information about some of the variables, X 1, I {1,..., n}. More concretely, if we have three variables (X1, X2, X 3) taking values on U 1 × U 2, x U3, where U/= {uil, ui2}, i = 1, 2, 3, then a valuation may be a probability distribution about X1, p(u11 ) = 0.8 p(u12 ) = 0.2. It may also be a conditional probability distribution about X3 given 2(2, p(U31[U21 ) = 0.9 P(U32]U21 ) = 0.1 p(U31[U22 ) = 0.6 P(U32[U22 ) = 0.4. Directed Acyclic Networks 255 From a mathematical point of view, a probabilistic valuation about variables X~ is a non-negative mapping, p : Ul --, ,~¢ ~, where ~ denotes the non-negative reals. These mappings are not considered normalized, but are considered equivalent upon multiplication by a positive constant; that is, two valuations pl, P2 defined on the same frame /3/ are considered equivalent if there exists a constant a > 0, such that Vu ~ U~, p~(u) = ,~.p2(u). From strict mathematical point of view, a valuation should be considered an equivalence class on the set of non-negative mappings from U I on ,~ 0-, under the above equivalence relation; however, to simplify the language and notation, we shall consider that a valuation is a mapping, but that two mappings are considered identical if they are equivalent. EXAMPLE 2 For Belief Functions [4-6], a valuation about X t is a nonnecessarily normalized mass assignment on U~, that is, a mapping m: 9(Ut) ~ ,~c~, where ~(U I) is the set of all the subsets of U1, and m(Q) = 0. Two basic operations are assumed to be defined among valuations: combination and marginalization. Combination is an operation to summarize in a single valuation the information of two valuations. If the two valuations to be combined are V 1 and V 2 defined on U t and Uj, respectively, their combination will be denoted V t ® V2 and will be defined on UIuj" Marginalization is an operation to calculate the information induced by a valuation defined on a frame U/, on a less fine frame: Uj, where J c I. If V is the valuation defined on U~, its marginalization to Uj is denoted by V +g EXAMPLE 3 In the particular case of probabilistic valuations, combination is defined by point-wise multiplication. If p~ and P2 are non-negative functions defined on U I and Uj, respectively, then p~ ® P2 is a mapping defined on U/g g to ~- given by, Pl @P2(u) =Pl(us')'p2(ulg), Vu E UIu J. This operation is used in probability to combine a marginal distribution with a conditional one to produce a bidimensional distribution, or used to 256 Jos6 Cano, Miguel Delgado, and Serafin Moral calculate conditional information. Remember that as we are not concerned about normalization, conditioning to a set A may be considered as the multiplication with the likelihood associated to A (its characteristic function: lA(u) -- 1, if u ~ A; lA(u) = 0, otherwise). Manginalization is defined in the usual way: If p is a valuation defined on U t and J c_ I, then p J(v) = Y'. p(u), v,,c u~J=l) EXAMPLE 4 In Belief Functions [4, 5] combination is carried out by means of Dempster's rule: m I ® m2(A ) = y' ml(B1) "m2(B2). BIOB2=A We do not normalize because two valuations are considered as equivalent if one is obtained from the other by multiplying by a positive constant. If m is defined on U t and J c_ I, then the marginalization of m to Uj is given by, m~J(A) = • m(B) B~J=A Shenoy and Shafer [1, 2] show that if these two operations verify a system of three axioms, then the calculus with valuations may be done by means of propagation algorithms. More specifically, they show that if we have n valuations, V~,..., V n, and we want to calculate (V 1 ® V 2 ® -.. ® Vn) ~ oil for each variable Xi, then we can do so without explicitly calculating the global valuation V 1 ® V 2 ... ® V~, but by doing local computations among the initial valuations, arranged in an appropriate way. The advantage of avoiding the calculation of V~ ® V 2 -.. ® V, is that, in general, this calculation is very inefficient. For example, in the case of probabilities, if each variable X i appears at least on a valuation ~ and we have m variables, then I/1 ® V 2 ... ® V~ will be defined on U 1 × ... × U m. If each U~ has k i elements, we will need l-I m,=~ k i values to specify this valuation. In the best case (all the k i equal to 2) this number is 2 m. Although Shenoy and Sharer, [1, 2], focus their work on the problem of calculus, there are other important aspects in the process of problem modeling and resolution that have not been considered. If we have two pieces of information represented by valuations V 1 and V2, then their combination, V a ® V 2 does not always give rise to a meaningful or valid information for the problem. Consider, for example, two probabilistic valuations about variables X 1 and X2: p, a bidimensional probability about (X1, X2), and Pl, a probability about X 1. The combination p ® p~ Directed Acyclic Networks 257 makes no sense from a probabilistic viewpoint. It is not a valid probability for the two variables; however, if p is a conditional probability about X 2 given X 1, then Pl ® P is valid probability distribution about (X 1, )(2). It is a bidimensional probability. The concept of independence plays an important role in this kind of rules: If Pl and P2 are probability distributions for X 1 and X2, respectively, and these variables are independent, then, Pl ® P2 is a valid probability for (X~, X2). If X I and X 2 are not independent, then this is not true. Pearl [7] uses these rules in Probability Theory to show that in a causal network (directed acyclic graph), giving a conditional probability for each node given its parents determines one and only one global probability distribution for all the variables. In other words, the initial pieces of information are complete and coherent. These important issues are the main topics of the present paper. Shenoy, [8], also studies conditional independence for valuations in terms of factors of the joint valuation. In this paper, it is not assumed the existency of a joint valuation. We give rules to build more complex valuations from elemental ones using the given independence relationships. We also give conditions to determine one and only one joint valuation. The graphical structures used to represent relationships among variables in our work are Pearl's causal networks, not Shenoy and Shafer's hypergraphs, because the former are more appropriate to represent independence relationships among variables in a direct way. In the second section we introduce three new axioms for operations with valuations, and define, in an abstract way, the concepts of conditional valuation, obser~'ation, and 'a posteriori' information. We then introduce rules to build new valuations from initial ones. In the third section we show that in a directed acyclic graph, having a valuation for each node, given its parents, determines one and only one global valuation valid for all the variables. In the fourth section, we obtain general propagation algorithms in directed acyclic graphs. These are a generalization of Pearl's algorithms, [7], but now are expressed in terms of operations with valuations, and, therefore, applicable to different uncertainty theories. Finally, in the last section we relate propagation algorithms with the independence relationships associated with the graph. 2. VALUATION-BASED SYSTEMS In this section we describe how to represent information with valuations and how to do calculations with them, giving a method analogous to Bayes Theorem. Let X = (X1,..., X n) be an n-dimensional variable such that each X i 258 Jos6 Cano, Miguel Delgado, and Serafin Moral takes its values on a finite set U v A valuation is a primitive concept meaning the mathematical representation for a piece of information in a given uncertainty theory. We will assume that for each I ___ {1 ..... n} there is a set V/of valuations defined on the cartesian product, U 1. V will be the set of all valuations V = U i c{l ...... }VI. Two basic operations are necessary (see Zadeh [9]; Shenoy, Shafer [1, 2]): • Marginalization. If J c_ I and V 1 e VI, then the marginalization of V l to J is a valuation Vl + 1 in Vj. • Combination. If V 1 ~ V/ and V 2 ~ Vj, then their combination is a valuation V l ® V 2 in V l u ]- Shenoy and Shafer [1, 2], consider the following three axioms for these operations on valuations: Axiom l Vl ® V2 = V2 ® V1, (VI ~ V2) ~ V3 = VI ~ (V2 ~ V3). Axiom 2 lf l c J c K, and V ~ VK , then ( V + g ) +1= V ~ I Axiom 3 If V 1 ~ V/, V 2 ~ Vj, then (V 1 ® 1/2) ;1= V l ® V2 "L(J•I). We assume three more axioms, Axiom 4 Neutral Element. There exists one and only one valuation V 0 defined on U 1 x ... x U, such that VV ~ V~, ~¢J c_ I, Vo ~ ] ® V=V. Axiom 5 Contradiction. There exists one and only one valuation, V c, defined on U 1 x -.. x U n, such that VV E V, V~ ® V -- V~. Axiom 6 VV E Vo, if V ~ Vc ;¢, then V = V0 ~°. The three first axioms provide the necessary conditions to deduce propagation algorithms. The third axiom is of particular importance to the development of propagation algorithms, as it allows us to calculate (V 1 ® 1/'2) ~1 without explicitly calculating (V 1 ® V2), a valuation defined on Ut u ]. This can be done by calculating I/2 ~ (g n 1) and combining the result with V 1. In this last case we need only handle valuations on Uj, U I n ], and UI, which is much more efficient. Remember that, in general it is inefficient to handle valuations defined for a large number of variables. The fourth axiom deals with the existence of the neutral element. This neutral element is considered by Shafer and Shenoy [1], but its existence is not postulated by an axiom. This axiom is essential in the present study to define the concept of conditional information in an abstract way. In the case of Probability Theory, the neutral element is a constant (non-zero) valuation: po(U) = 1, Vu ~ U1 X "" x U, The constant value is not important because probabilistic valuations are equivalent upon multiplication by a positive constant. In the case of Belief Functions, the neutral element is the so-called vacuous belief, [5, 6], given Directed Acyclic Networks 259 by ifA =U~ ×..'× Un. otherwise In the Axiom 4, the existence of the neutral element is postulated on the flame corresponding to all the variables, U t × ... × U n. In smaller frames, the neutral element is obtained by marginalization. Therefore, V~j ~K will be called the neutral element of V~, and when there is no chance of confusion, it will be denoted simply by V 0. The contradiction is characterized in Axiom 5 as a valuation such that if it is combined with any other valuation, it produces the contradiction. In Probability Theory it is given by the zero-valued function p,(u) = O, Vu ~ U~ x ... × U,, In Belief Functions Theory, the contradiction is the zero valued mass assignment, m~,(A) = O, VA c U~ x ... x U,, These valuations are obtained by combining two contradictory valuations. For example, in the case of Belief Functions, it can result from combining the masses, m~ and m 2, defined on (uE, u2, u d and given by rnl({ul} ) = 1; ml(A ) = 0, otherwise rnz({U2} ) = 0.5; m2((u2,u3} ) = 0.5; m2(A ) = 0, otherwise. In Shenoy and Shafer [2], the contradiction is considered from a different standpoint: They define a subset of the set of valuations called the family of proper ualuations. The elements of this set are the valuations different from the contradiction. As in the case of the neutral element, Vc ~ ~ will be called the contradiction of V K, and will sometimes be denoted by V,.. According to Axiom 6, in the frame corresponding to the empty set of variables, U~, all valuations are the contradiction or the neutral element. To better appreciate this, let us show its meaning in Probability Theory. The cartesian product U~ has one element: {e}. A valuation, p, in this set ~, + is, therefore, a mapping from {e} on ,R0, that is, a number, p(e). If this number is zero, then we have the contradiction; if it is different from zero, then we have the neutral element: combination with this valuation produces an equivalent valuation. Its meaning and consequences will be discussed below when we consider the relationships of the calculus with valuations and the concept of independence. 260 Jos6 Cano, Miguel Delgado, and Serafln Moral The following propositions illustrate some additional properties of valuations. We assume that Axioms 1-6 are verified. PROPOSITION 1 VV E VK, V ® Vc ~ K = Vc~ K Proof On the basis of Axioms 5 and 3, v~. ~K = (V~ ® V) ~ = v® Vc *K Q.E.D. • PROPOSITION 2 VV ~ V / being I _ K, we have V ® Vc+ K = V+ Proof On the basis of Axioms 4, 1, and Proposition 1, v® v~ ~K = v® (K. ~K ® v~ ~K) = (v ® Vc ~) ® V~ ~ = V~ ~ Proposition 1 has been applied in the last equality. • The following proposition is quite natural: if a valuation is marginalized on the variables in which it is defined, we obtain the same valuation; however, proof of this requires invocations of Axiom 4. PROPOSITION 3 VV ~ V/, V ~ l = V Proof By applying Axioms 4, 3, 2, and 4, V ~1 = (V® Vo~) ~I = V® (Vo~) ~ = V® V0 ~= V. The following is a technical proposition that will be used in later propagation algorithms. PROPOSITION 4 If 1/1,V 2~V,I_{1,2 ..... n}, VI E V],V z ~ V K with I__c_J u K, J n K c_ I, then (1/1 ~ v~) ~' = v, .1~] ~ v2 ~'n~ Proof On the basis of Axiom 2, (V, ® V2) $' = ((V 1 ® V2)$Ju') j'l As (V 1 ® V 2) is a valuation on J u K and we know that I c J u K, then by using Axiom 4, we obtain (V 1 ® V2) +1 = (((V, ~ V2) ® Vo$1)$JUl) $1 On the basis of Axioms 1 and 3, (V 1 ® g2) $I = ((V 1 ® V 2 ~ Vo$l)J'Jul) $1 = (((V1 ® goJ, I) ® V2)J'Jt)l) j'' = ((V 1 * Vo ,[,I) ® V2J~(jUl)nK) $1 = (1/1 ® v® +I * V~+'~K) z~ Directed Acyclic Networks 261 The last equality is derived from the fact that if (J n K)_ I, then (JUI) AK=IAK. Now, using Axioms 1, 3, and 4 we get, (V 1 ~ re) "LI = ((Vo ,L1 ~ V2 "LINK) ~ Vi) ~'I ~__ (Vo ,~1 (~ V2 SINK ~ Vl"~lnJ). As the valuation I/2 *tnK® V1 ~l~J is defined on (I N K) U (I N J) = I n (K U J), which--because I ___ J u K--is equal to I, this valuation is defined on I. Therefore, applying Axiom 4 we get (V 1 ~ V2) "tl = (V2 $1oK ~ Vl"/oJ), Q.E.D. [] Note that in this proof, multiplication by the neutral valuation on Vt, V0 ~* is used, in general, to extend a valuation V ~ V~ to the set V K u I. This method will be used several times throughout the article. An immediate consequence of above proposition is the following one, which we give without proof. PROPOSITION 5 If V 1,V 2 ~ V,I___{1,2 ..... n},V 1 ~ Vj, V 2 ~ V K J n K = I, then (7 I ~ V2) *l = pl $1 ~ V2 $1 The following proposition can be deduced using Axiom 6. with PROPOSITION 6 If V 1, V 2 ~ 1,1, V 1 ~ V~, V 2 ~ V K with J • K = • and V2 ~ 4= V~ +e then (V 1 ~ V2) SJ ~- Vl " According to this proposition, if we have two valuations, V 1 and V 2, given for disjoint sets of variables, J and K, and we combine them-- obtaining a valuation for the set J u K--and if we then marginalize on the first set, then we obtain the same valuation V]. This is not necessarily verified if Axiom 6 is not postulated as true. In that case, the combination of a valuation with a disjoint valuation, followed by marginalization, may affect this valuation. This may produce some incoherence between the concept of independence and the calculus with valuations to be given below. We shall consider this problem in more detail in section 5. The main definitions relative to the calculus with valuations are given below. DEFINITION 1 A valuation V ~ V/ is said to be absorbent if and only if it is not the contradiction in V/ and (VV' ~ VIX(V ® V' = V) or (V ® v' = v~)). 268 Jos6 Cano, Miguel Delgado, and Serafin Moral Then the following facts are verified. a. (H', h') is actually a system of information. b. V~ ~ H', Vi ~ {1 .... , n}, with h'(V i) = (i, e(i)). c. If for a system of information (H", h") with the same dependence structure, (b) is verified, then M t, R1, i, SI. ] belong to H". d. The only global valuation, V, in H' with h(V) = ({1, 2 ..... n}, O) is Vl® v2 ® ... ® v.. If these points are proved, then from (a) and (b) we conclude that H _c H', H being the system of information generated by valuations {V/}i~tl,2 ..... n~. Taking into account (c), we have the equality H = H', because H is a system of information that verifies (b). According to (d), there is one and only one global valuation defined for all the variables, {1,..., n}: V 1 ® V 2 ® ... ® V~. Now all we need is to prove these points. To show (a), we need to prove the four properties of systems of information: 1. It is immediate by the way valuations MI, R z, S/, ] are defined. 2. Property 2 may be applied only to valuations Rl, i, S~,] combined with valuations M t. It is verified because the combination R~, i ® M t u e~0 = MI u P(i) u {i}, and the combination St, ] ® M] = M 1 u ], that is, elements from H'. 3. The combination of a valuation M/with V0 ~ ], with D(I, O, J) = 0, is precisely S/, ]. Applying this rule to valuations in the form of Rt, ~ and St, ] yields elements of the same type. 4. Marginalization of elements Mt and St,] produces elements of the same type. The only proper marginalization operations applicable to elements Rt, i are to marginalize to U/v e~n and to U~ u e(i)u {i}. In the first case, as RI, i is a valuation conditioned on variables (Xj)j ~ i u e~o, yields the neutral valuation on U/u e(i) which is equal to S~, e<0" The second is not really a marginalization. We get the same valuation Rl, i. The proof of (b), (c), and (d) is straightforward and will not be described in detail. • 4. PROPAGATION OF VALUATIONS IN POLYTREES Assume that (X1,... , gn) is an n-dimensional variable and (H, h) is a system of information defined on the graph (T, E) and given by valuations {V~}i ~ tl ..... n~. Under these conditions, the only possible global valuation for all the variables is V 1 ® V z ® .-. ® V~. Consider also a family of observations {Oi}i~i, and that our objective is to calculate the 'a posteriori' valuations for each single variable, that is, to calculate the following Directed Acyclic Networks 269 valuations: PSi = ® 0 i ~ V ieI for each j e {1 ..... n}, where V = 1/1 ® .-" ® Vn __ is the only existing global information. The main problem, as indicated in the introduction, is to calculate, 1/1 ®... ® V~. Propagation algorithms proposed by Pearl, [7], avoid the calculation of V] ® .-- ® V n if the graph does not have undirected cycles (also called loops). These graphs are called polytrees, [7]. In this section we generalize these algorithms to the uncertainty expressed by means of valuations. The notation will be based on the following valuations, Hk = Vk,if k ~ I Hk = V~ ® Ok,if k ~ l 0~= V o~ V{j.},ifj~I O; = Oj, if j ~ l and the following sets for each j c {1 ..... n}, • If, the set of indexes i such that X i is a descendent of Xj (there is a directed path from Xj to Xi). • I[ = {1,...,n} - (17 U {j}). • P(j) is the set of parents of node Xj. • For each k ~ P(j), I~ is the set of indexes of nodes X i such that there is an undirected path from X i to X k or from X~ to X i not containing Xj. • C(j), is the set of children of node Xj. • For each k ~ C(j), Ij~, the set of indexes of nodes connected with X k via an undirected path not containing )(i.. • I~ is the set of indexes of nodes not connected with node Xj. The following propositions form the basis of propagation algorithms. In all of them, it is assumed that the graph has no loops. PROPOSITION 8 Vje {1 ..... n}, PSi Proof = 7rj ® ;ti, where ] '~ {j} ,~ (j} Taking into account the expression of PSi and the definition of PSi = (H, ® H 2 ® "'" ® Hn) ~{j} 270 Joss Can®, Miguel Delgado, and Serafin Moral Taking into account Axioms 1 and 2, PSj = ( H 1 ® H 2 ® ''' ® H~) ~ {j) = ((iE~lj+Hi) ® Hj ® (iE~llj Hi)) J'{j} On the basis of Proposition 5, and taking into account that (I S u {j}) n (I~ u {j}) = {j}, ® ) ~ {j) ,' '[ {j} ) Q.E.D. • PROPOSITION 9 If (H 1 ® H 2 ® ... ®/4,) ~° is different from the contradiction, then Vj~ {1 ..... n}, zr) = Vj® ( @ 7rf' ; A i = ~ h~ ®q \k~P(j) "/ I I k~C(j) where Proof = l~j = (iE~iijkHi) i ljk The expression for 7rj is Taking into account that the graph has no loops, we can show that Directed Acyclic Networks If = LI~ ~ p(j) I)~ with Ij~, n I)] 2 = ~ if k, 4: k 2. Therefore, and on the basis of Axiom 3, ® ~] ~ ({Jlueff))] klj} o k~P(j) i~ljk 271 Now, by a repeated application of Proposition 4, Taking into account the expression for ~r[, we obtain the desired equality for 7rj, k~P(j) The valuation Aj was defined as As the graph has no loops, I~ = U k ~ c(j)u (01 I~, with Ijk ' n I~ = Q, if k I 4= k 2. Therefore, Aj = ® ® ® o~. By a repeated application of Proposition 5, ~= ® /4, ® ®o~. • kGC(j) l Ilk \i~ljo Taking into account the expression of A~, k~C(j) i o 272 Jos6 Cano, Miguel Delgado, and Serafin Moral As (H 1 ® ..-® H,) t~ is different from the contradiction then (®i~ 6o Hi)~° is also different from the contradiction, and taking into account Axiom 6, Thus, a t= ® a: ®o:= ® aj ®o:. k~C(j) k~C(j) Q.E.D. • We now have the valuations we want to calculate, PSi, in terms of k and valuations 7rj and A:, which are expressed in terms of valuations h: • ff. In the next proposition, we show how we calculate these valuations in a node, assuming that the corresponding valuations in all the neighboring nodes are known. PROPOSITION 10 If j ~ {1,..., n}, then Vk ~ P(j), i~C(k), i¢j And Vk~ C(j), k Ak® ' ®V~® ® ~- Aj = O k i~P(k), icj Proof If k ~ P(j), then [ ~{k} i ®/-/,/ i~ C(k), iej [ ( .)] = %®0~,® ® ,~}, . i~ C(k), i=/=j Directed Acyclic Networks 273 Analogously, if k ~ C(j), • lj~ = h k ® O k ® V k ® ® 7rk icP(k), i4-j Q.E.D. • The contradiction raises the following problem. If we have a graph with two disconnected parts, for example one with vertices {1, 2,..., i} and other with vertices {i + 1 .... , n} (that is, there is no arc from vertices of one set to vertices of the other set), then if H l ® ... ® H i is the contradiction in U~I ..... i~, it can be shown that H 1 ® ... ® H n is the global contradiction and PSi is the contradiction for each variable Xj, j ~ {1,2 ..... n}. However, if we use the above formulas, then the contradiction is not propagated between non-connected parts of the graph and what we obtain for PSi, j ~ {i + 1 ..... n} is (Hi+ 1 ® ... ® [In) ~{j}, which is not PSi if there is no contradiction in variables Xi+ 1 .... , X n. What to do from a practical point of view? The answer is simple. If the graph is connected, then the propagation formulas are correct. We have used the lack of contradiction to show that and in this case Ij0 is empty. If the graph is not connected, then for a global contradiction to exist, some of the connected parts have to be contradictory. In such a case, from a mathematical point of view all values of PSi will be contradictory. But there is an alternative: not to consider the information from variables giving rise to the contradiction, removing such contradictory information from the system and keeping only non-contradictory valuations. Shenoy [12] describes an efficient way to isolate a maximal consistent set of valuations. With this restricted system, the formulas of propagation can be used. Our objective is now to calculate the values ~j, hi, 7r~ k (k E C(j)), h~ (k ~ P(j)), for each j E {1 ..... n}. If the set of observations, {Oi}i~ 1 is empty (I = ~3), then this can be done very easily. First, we shall prove that all valuations h i are the neutral valuation. 274 Jos6 Cano, Miguel Delgado, and Serafin Moral PROPOSITION 11 If I = Q and V c ~ (V 1 ® ... ® Vn) *e then Aj = V o KU}, Vj ~ {1 .... , n}. Proof For every leaf variable in (T, E), we have Aj = (®k~c(j) A~) ® O~=V o. If Xj is a leaf (a node with no children) then C(j)=Q, therefore, O~ = V o. Now let us prove that if A k = Vo ~tk} ~ Vtk ~ for every k ~ C(j) then Aj = Vo ~j~ + v+. k~C(j) k~C(j) and ,~= ,~,®o~®v, ® ~ i~P(k), i.,~j i~P(k), i#:j [< t ]"J' = ® -,,-~ ® v/p<k) i~P(k), i~j Now, taking into account that V k ~ V~k}le(k), [ < ,)1 A~ = Vo ~'<') ® ® ~-~ i~P(k), iV:j By a repeated application of Proposition 4 we get k VoCJ}® ( @ -a'~'t~) = Vo cj} Aj= i~P(k), imj That is, ;t~ = V0 * u} ~ Vtm hence a.j=( ® a.~)=Vo~U}~vu,. k~C(j) Q.E.D. • Under these conditions, if I = 0, we can find ~rj for every j ~ {1 ..... n} with the following algorithm, where it is assumed that if ] > i, then Xj is Directed Acyclic Networks 275 not a parent of X i (that is, the rrj value of a node will be calculated when corresponding 7r~, j ~ P(k) are known). The steps are as follows: • For every j = 1 .... , n calculate aj I~,, ~j PS i= rrj ® Aj. Vk ~ C(j), 7r~ = rr k Vi ~ P(j), aj = Vo+ ~1 Assume now that we want to calculate PSi with a set I 4= 0. We shall give, like Pearl, [7], an algorithm that calculates these values (PSi, 7rj, Aj, A~, ~-~) for a set I' = 1 U {@}, assuming that we know these values for the set of observations I; that is, the algorithm updates the values of valulations in the light of a new observation. For k ~ P(j), the 7rf values are said to be messages from the parents of Xj to it, or incoming messages from its parents. Analogously, for k ~ C(j), the A~ values are the messages that this node receives from its children. On introducing a new observation, O t, all incoming messages to a node do not change, unless there is an undirected path between this node and X t. In this case, only the message arriving from this path changes; that is, A~ or 71"j k change only when there is an undirected path between Xj and X t via X k. As the graphs we are working with do not have loops, there is, at most, only one undirected path from each node to X t. All incoming valuations for Xj with the set of observations I' are, therefore, the same as the valuations for set of observations I, except perhaps for the message coming from one of its children or parents. The outgoing message from Xj to this node does not change, but all the other outgoing messages are different (Figure 1). For node X l, the variable for which we have introduced the new observation, the situation is as follows: all incoming messages are the same and all outgoing messages are new (Figure 1). In the light of these considerations we can design an algorithm to perform the updating. The algorithm is based on the fact that when we arrive at a node, all the incoming messages are calculated, and we then calculate 7r/, A/, PS/, and the outgoing messages. Let J be the set of pairs (Jl, J2) where Jl is a node to be updated and J2 the incoming node. Then the algorithm is as follows: • J = {(1, -1)} • While J =~ Q Choose (Jl,J2) ~ J, J "- J - {(JJ,J2)} calculate • rrj~ *- [~ ® (®~ ~rk) l~u'} e.g(j~) jl ] k t • Ajl ~ (®*¢<c<j,) Ajl) ® O;I • PSjj ,-- rrjl ® Ajl 276 Jos6 Cano, Miguel Delgado, and Serafin Moral Figure 1. Changing messages with a new observation 09. For every k e C(jl) , k 4:j2 calculate jl * 77 k ~ [77jl ~ O~l ~ (~i~:C(jl)i.k /~'1 )] , J ~ J u {(k, Jl)} For every k E P(Jl), k 4= Jl calculate * A~ 1 ~ [~jl ~ Oil * Vii ~ (®iEP(j,),.krr;1)] "~(k} * J (- J U ((k, jx)} It is immediately clear that this algorithm updates all the messages, and the values of PSi corresponding to I'. 5. PROPAGATION ALGORITHMS AND CONDITIONAL INDEPENDENCE In this section we prove that if all the axioms hold, then the propagation algorithms are coherent with the initial dependence structure associated with a graph. To prove this coherence, we need Axiom 6. In a theory of uncertainty representation in which this axiom does not hold, we could resort to use propagation formulas, but then we would have to admit that we are violating the coherence with the dependence structure associated with the graph. PROPOSITION 12 Let (T, E) be a DAG without loops associated with n-dimensional variable (X 1 ..... X,), (H, h) a system of information defined on it, and I,J,K_c{1 ..... n} in such a way that D(I,J,K)=O. Under Directed Acyclic Networks 277 these conditions, if we know the values of variables X j, that is, if we have the observations {Oj}j ~ j and the contradiction is never obtained, then the introduction of a new observation of a variable in {Xi} i ~ ~ does not change the 'a posteriori' valuation in any of the variables in {X~} k ~ s.. Proof Assume that we introduce a new observation, Oi~ ,, where i~b E 1, and assume a node Xk, where k ~ K. As the graph has no loops there is only one undirected path going from Xi,, to X k. Along this undirected path travel the messages with the influence of Oi,, on Xk. If at a given moment, one of these messages does not change after introducing observation O~,, then this observation does not have any effect on X k. As we assume that D(1, J, K) = 0, then by the d-separation criterion (see Definition 13) we have that for this path one of the two following conditions holds • There exists a node with converging arrows in the path that does not belong to {Xj}j ~j and its descendents do not belong to {Xj}j~ j. • There exists a node without converging arrows in the path that belongs to {Xj}j~ j. In the first case, let this node be X I. None of its descendents is in {X~}j~ j. By applying a proof similar to that in Proposition 11, it can be shown that before and after introducing observation Oi,,, all messages that this node sends to its parents are the neutral valuation. As the chain of messages carrying the effect of Oi, ' to X k goes through X 1 from one of its parents to a different parent, the outgoing message does not change. It is the neutral element, with no effect on X k. In the second case, we have a node, Xj, j ~ J, without converging arrows in the path from Xi, ' to X k. As j is in the set of observations, we have an observation Oj for this node, which is an absorbent valuation. The messages this node sends to its children. X m, m ~ C(j) are i~ C(j) i ~ m As Oj is absorbent and the contradiction is never obtained, rr~ = O i . Thus, the messages from Xj to its children never change, and if the path from Xi, ' to X k passes through Xj from a parent to a child, or from a child to a different child, then it does not change in X k and has no effect on S k .