A Constraint Propagation Approach to Probabilistic Reasoning

The paper demonstrates that strict adherence to probability theory does not preclude the use of concurrent, self-activated constraint-propagation mechanisms for managing uncertainty. Maintaining local records of sources-of-belief allows both predictive and diagnostic inferences to be activated simultaneously and propagate harmoniously towards a stable equilibrium.


INTRODUCTION: BAYES NEIWORKS AND CONSTRAINTS PROPAGATION
Scholarly textbooks on probability theory often create the impression that to construct an adequate representation of probabilistic knowledge we must first define a joint distribution function on all propositions and their combinations, i.e., on the so-called universe of discern ment. The computational difficulties involved in articulating, validating, storing and manipu lating such distributions seem insurmountable and have discouraged many AI researchers from openly using probabilistic formalisms in expert systems. In truth, however, these difficulties are merely mathematical fiction, and do not plague common-sensical approaches to probabilistic reasoning. In a sparsely connected world like ours, it is fairly clear that probabilistic knowledge, in both man and machine, should not be represented by entries of a giant joint distribution table, but rather by a network of low-order probabilistic relationships between small clusters of semantically related propositions. One effective representation of such rela tionships is provided by Bayesian Networb: a class of networks typified by the use of "influence diagrams" in decision analysis [Howard and Matheson, 1984] and "inference networks" in expert systems [Duda, Hart, and Nilsson, 1976]. (The alternative network representation using Mar kov fields [Pearl, 1985] will not be discussed here.) Bayes Networks are directed acyclic graphs in which the nodes represent propositions (or variables), the arcs signify the existence of direct causal influences between the linked pro positi�ns, and the strengths of these influences are quantified by conditional probabilities (Fig   ure 1 ). Thus, if the graph contains the variables .r1, •.. ,Xn, and S, is the set of parents for vari able .r1, then a complete and consistent quantification can be attained by specifying, for each node x1, an assessment of P(x1 I S1). The product of all these assessments, constitutes a joint-probability model which supports the assessed quantities. That is, if we compute the conditional probabilities P(x, IS,) dictated by P(.r1, . . . ,.rn)• the original assess ments are recovered. For example, the distribution corresponding to the graph of Figure 1  An important feature of Bayes network i:'l that it provides a clear visual representation for many independence relationships embedded in the underlying probabilistic model. The cri terion for detecting these independencies is based on graph eeparation: namely, if all paths between x1 and x1 are "blocked" by a a subset S of variables, then Xt ie independent of XJ given the values of the variables in S. Thus, each variable Xt is independent of both its siblings and its grandparents, gh�en the values of the variables in its parent set s,. For this "blocking• cri terion to hold in general, we must provide a special interpretation of separation for nodes that share common children. \Ve say that the pathway along arrows meeting head-to-head at node xk. is normally "blocked", unless Xt: or any of its descendants is in S. In Figure 1, for example, x2 and X3 are independent given S1 = {xl} Or S2 = {X1p%4}, because the two paths between X2 and X] are blocked by either one of these sets. However, x2 and X3 may not be independent given S3 = {x1p%J, because .%6, as a descendant of xs , "unhlocks• the head-to-head connection at xs, thus opening a pathway between x2 and x3.
Once a Bayes network is established, it can he used to represent the deep causal knowledge of a domain expert and can provide probabilistic answers to all queries regarding the interpretation of evidential information in that domain. Ideally, however, we would also like to treat such a network as a computational architecture that facilitates the interpretation of data at th� knowl� d ge level its�lf: we want to view the links not merely as codes for storing factual knowledge but also as pathways and activation centers which both direct and propel the flow of data in the process of querying and updating that knowledge.
The process of self-activated interpretation is conveniently described in terms of constraint-propagation or relaxation paradigm. Each link in the network represents constraints on the possible values that the belief parameters can take at the two nodes connected by the link. Updating is accomplished by successiYely finding unsatisfied constraints and satisfying them by modifying the belief parameters, thus bringing ·out of kilter" constraints hack to re laxed status. Relaxing one constraint usually perturbs its neighbors, so relaxation results in a multi-directional propagation process which reaches a static equilibrium when all constraints are satisfied.
The relaxation paradigm has several advantages over other mechanisms of uncertainty management. It permits knowledge to be specified declaratively without regard for the specific control method used. It is readily implementable by pattern-oriented rule-based languages as well as by object-oriented languages. In the former, the antecedents of the rules alert to viola tions of constraints and their consequent parts specify corrective actions. In the latter, each node is an object of the same generic type and the constraints are the messages by which neighboring objects communicate. Moreover, relaxation can be executed in parallel by a large array of simple autonomous processes, thus providing a reasonable model of human cognitive behavior.
While constraint-propagation mechanisms have found several applications in AI, such as vtston [Rosenfeld, Hummel and Zucker,  1 980], their use in evidential reasoning has been limited to non-Bayesian formalisms [e.g. Lowrance, 1982]. The reason has been several-fold.
First, the conditional probabilities characterir:ing the links in the network do not seem to impose definitive constraints on the probabilities that can be assigned to the nodes. The quantifier P(A IB) only restricts the belief accorded to A in a very special set of circumstances: namely, when B is known to be true with absolute certainty, and when no other evidential data is available. Under normal circumstances, all internal nodes in the network will be subject to some uncertainty and, more seriously, after observing evidence � the conditional belief in A is no longer governed by P(AIB) but by P(AIB, �), which may be totally different. The result is that any assignment of beliefs, P(A) and P(B), to propositions A and B can be consistent with the value of P(AIB) initially assigned to the link connecting them; therefore, no violation of constraint can be detected locally.
Next, the difference between P(AIB, 6) and P(A!B) seems to suggest that the weights on the links should not remain fixed but should undergo constant adjustment as new evidence ar rives. This, in turn, would require an enormous computational work and would wipe out the advantages normally associated with propagation through fixed constraints.
Finally, the fact that evidential reasoning involves both top-down (predictive) and bottom-up (diagnostic) inferences has caused apprehensions that, once we allow the propaga tion process to run its course unsupervised, pathological cases of instability, deadlock, and cir cular reasoning will develop. Indeed, if a stronger belief in a given hypothesis means a greater expectation for the occurrence of its various manifestations and if, in tum, a greater certainty in the occurrence of these manifestations adds further credence to the hypothesis, how can one avoid infinite updating loops when the processors responsible for these propositions begin to communicate with one another! Likewise, Lowrance [1 982] expresses concern that if proposi tion B influences the belief in A via P(A!B) and proposition A influences the belief in B via P(BjA), then the "feedback between A and B would eventually drive the two beliefs to the mar ginals," thus preventing any further updating from occurring. This paper shows that coherent and stable probabilistic reasoning can be accomplished by local propagation mechanisms while keeping the weights on the links constant throughout the process. This is made possible by characterizing the belief in each proposition by a vector of parameters, one for each port. Each component in the vector stands for the degree of sup port that the host proposition obtains from one of its neighbors. We show that, in certain net works, maintaining such a breakdown record of the sources of belief facilitates efficient updat- The relaxation paradigm has several advantages over other mechanisms of uncertainty management. It permits knowledge to be specified dedaratively without regard for the specific control method used. It ill readily implementable by pattern-oriented rule-balled languages as well as by object-oriented languages. In the former, the antecedent!! of the rules alert to viola tions o( c onstraints and their consequent parts specify corrective actions. In the latter, each noc.le is an object of the same generic type and the constraints are the messages by which neighboring objects communicate. Moreover, relaxation can be executed in parallel by a large array of simple autonomous proce!lses, thus providing a reasonable model of human cognitive behavior.
While constraint-propagation mechanisms have found several applications in AI, such as vision {Rosenfeld, Hummel and Zucker, 1976; Waltz, H/72] and truth maintenance [McAllester, 1980], their use in evidential reasoning has been limited to non-Bayesian formalisms (e.g. Lowrance, 1982]. The reason has been several-fold. First, the conditional probabilities characterizing the links in the network do not seem to impose definitive constraints on the probabilities that can be assigned to the nodes. The quantifier P(A jB) only restricts the belief accorded to A in a very special set of circumstances: namely, when B is known to be true with absolute certainty, and when no ether evidential data is available. Under normal circumstances, all internal nodes in the network will be subject to some uncertainty and, more seriously, after observing evidence t the conditional belief in A is no longer go>erned by P(AjB) but by P(AIEJ, t), which may be totally different. The result is that any assignment of beliefs, P(A) and P(B), to propositions A and B can be consistent with the value of P(AIB) initially assigned to the link connecting them; therefore, no violation of constraint can be detected locally.
Next, the difference between P(A \B, t) and P(A\B) 11eems to suggest that the weights on the links should not remain fixed but should undergo constant adjustment as new evidence ar rives. This, in turn, would require an enormous computational work and would wipe out the advantages normally associated with propagation through fixed constraints.
Finally, the fact that evidential reasoning involves both top-down (predictive) and bottom-up (diagnostic) inferences has caused apprehensions that, once we allow the propaga tion process to run its course unsupervised, pathological cases of instability, deadlock, and cir cular reasoning will develop. Indeed, if a stronger belief in a given hypothesis means a greater expectation for the occurrence of its various manifestations and if, in turn, a greater certainty in the occurrence of these manifestations adds further credence to the hypothesis, how can one avoid infi nite updating loops when the processors responsible for these propositions begin to communicate with one another! Likewise, Lowrance (1982] expresses concern that if proposi tion B influences the belief in A via P(A IB) and proposition A influences the belief in B via P(BjA), then the "feedback between A and B would eventually drive the two beliefs to the mar ginals," thus preventing any further updating from occurring. This paper shows that coherent and stable probabilistic reasoning can he accomplished by local propagation mechanisms while keeping the weights on the links constant throughout the process. This is made possible by characterizing the belief in each proposition by a vector of parameters, one for each port. Each component in the vector stands for the degree of sup port that the host proposition obtains from one of its neighbors. We show that, in certain net works, maintaining such a breakdown record of the sources of belief facilitates efficient updat- ing of parameters by constraint-propagation, and that the network relaxes to a stable equilibri um consistent with the axioms of probability theory, in time proportional to the network diam eter. This record of parameters is also postulated as the mechanism which permits people to trace hack the sources of beliefs for the purpose of constructing explanatory arguments.

2.
PROPAGATION IN SINGLY -CONNECJ'ED NEIWORKS \Vc shall first consider Bayes networks which are singly connected, that is, there is at most one underlying path between any pair of nodes. Propagation algorithms for such networks were developed by Pearl [1982], for the special case of trees, and were later generalized by Kim and Pearl [1983] to admit nodes with multiple parents. To establish the notation necessary for treating more general networks, we shall reiterate here the results of Kim and Pearl and cast them in the context of constraint propagation.
Let each node in the network represent a multivalued variable which might stand for a collection of mutually exclusive hypotheses (e.g., identity of organism: ORG1, ORG2, ... ) or a col lection of possible ohserntions (e.g. patient's temperature: high, medium, low). Let a variable be labeled by a capital letter, e.g., A, B, C, ... , and its possible values subscripted, e.g., A1o A2, ... , A,. Each group of arrows pointing at a given node is quantified by a fixed condition al probability matrix. For example, the arrows B .. A and C .. A in Figure 2, will be quantified by a matrix M, with entries: Mu�c = P(AIIBJ,Ck)· These matrices quantify the strength of influence between causes and their conse quences. Additionally, they contain the information for deciding how the belief in one cause is affected by evidence bearing on another, once their common manifestation is observed. This in teraction, colloquially termed "explaining away," is a prevailing pattern of human reasoning, and occurs even when the causal variables are marginally independent. For example, when a physician discovers evidence in favor of one disease, it reduces the credibility of other diseases, although the patient could be suffering from two or more disorders simultaneously.
Instantiated variables, constituting the incoming evidence or data will be denoted by D.
For the sake of clarity we will distinguish between the fixed conditional probabilities that label the links, e.g. P(A 18), and the dynamic values of the updated node probabilities. The latter will be denoted by BEL(A1), which reflects the overall belief accorded to proposition A1 by all data so far received. Thus, where D is the value combination of all instantiated variables.

Fusion Equations
Consider a fragment of a singly connected network, as depicted in Figure 2. The link B .. A partitions the graph into two parts: an upper. subgraph G,t1., and a lower subgraph G&, the complement of G�. These two graphs contain two sets of data which we shall call D� and DB,.. , respectively. Likewise, the links C .. A, A .. X, and A .. Y define the subgraphs G�, G_.\K, and GA"r which contain the data sets D�, Dix, and DA"r, respectively. Since A is a common child of B and C, it does not separate G,t1. and Gt;. apart. However, it does separate the following three subgraphs: G1.t U GC,., GA"f, and G.,U., and we can write and (3) the fixed conditional probability matrix, P(AjB, C), which relates the variable A to its immediate causes. Accordingly, we let each link carry two dynamic parametent, 'If and �. and let each node store the information contained in P( AjB , C).
With these parameten at hand, the fusion equation (5) Assume that the vectors 'If and � are stored with each link, "' at the tail of the arrow and � at its head. Our task is now to prescribe how the values of 'If and � at a given link are constrained by the corresponding parameters at neighboring links.
Upda.ting k Starting from the definition of �A ( B, ) ,.. P(D &\B , }, we partition the data DiA into its components: A, DAi, DA;r, D't_, and summing over all values of A and C we get (10) Eq.(lO) shows that only three parameters (in addition to the conditional probabilities P( AjB , C ) ) need to he involved in updating the diagnostic parameter vector �A (B) : 'lfA ( C), �x(A ) , and �r(A ) . This is expected since DiA is completely summarized by X, Y, and C.
The boundary conditions are established as follows: Data-no d es: If the J .,;, state of B is known to be true, we add to B a dummy son Z, and set �z(B) = (0, ... ,0,1,0, ... ,0) with 1 at the l' position.

Root-no d es:
If B is a node with no parents, we add to B a dummy father Z instantiated to Z=TRUE, and set the link matrix P(Bjz=1RUE) equal to the prior P(B).

Constraints Propagation
So far we have viewed the links of the network as message-carrying devices through which the node processors communicate. They can also be viewed as constraint-maintaining agents. Imagine that each node is characterized by several parameter vectors, one for each of its ports. The 1r's are placed on the outgoing ports :1nd the �·s on the incoming ports. In node A of Figure 2, for example, the parameters 1rx(A) and 1ry{A) will be placed on the lower two ports (facing the children X and Y) while �A(B) and �A(C) will be placed on the upper ports (facing the parents). Imagine also that a node is permitted to compare its own set of parame ters with those of its neighbors. Equations (10) and (11) then dictate how the link matrices P(A 1B ,C) impose equality constraints between the parameters of one node and those of its neighbors. If these equalities are satisfied (within some reasonable tolerance), no actiYity takes place. However, if any of these equalities is violated, the responsible node is activated to revise its violating parameter and set it straight. This, of course, will activate similar revisions at neighboring nodes and will set up a multidirectional propagation process.
Eqs. (10) and (11 ) demonstrate that a perturbation of the causal parameter, '1'1, will not affect the diagnostic parameter, �. on the same link, and vice vena. The two are orthogonal to each other since they depend on two disjoint sets of data. Therefore, no feedback or "circular reasoning" can take place --any perturbation of beliefs due to new evidence propagates through the network and is absorbed at the boundary without reflection, resulting in a new equilibrium state compatible with the newly observed eviden . ce.
In summary, we see that the architectural objectives of propagating beliefs coherently, through an active network of primitive, identical, and autonomous processors can be fully real ized in singly-connected graphs. Instabilities due to cyclic inferences are· avoided by. using mul tiple, source-identified belief parameters, and equilibrium is guaranteed to be reached in time . proportional to the network diameter.
The primitive processors are simple, repetitive, and require no working memory except that used in matrix multiplications. Thus, this architecture lends itself naturally to hardware implementation, capable of real-time interpretation of rapidly changing data. It also provides a reasonable model of neural nets involved in cognitive tasks such as visual recognition, reading comprehension (Rumelhart, 1976], and associative retrieval (Anderson, 1983), where unsuper vised concurrent processing is an uncontested mechanism.

PROPAGATION IN MULTIPLY-CONNECTED NEIWORKS
The efficacy of singly-connected networks in supporting autonomous propagation raises the question of whether similar propagation mechanisms exist in less restrictive networks (like the one in Figure 1), where multiple parents of common children also possess common ances tors, thus forming loops in the underlying network. If we ignore the existence of loops and per mit the nodes to continue communicating with each other as if the network was singly connected, it will set up messages circulating indefinitely around the loops and the process most probably will not converge to a coherent equilibrium.
A straightforward way of handling the network of Figure 1 would be to appoint a local interpreter for the loop .l'lf x2, x3, %.5 that will pass messages directly between x1 and x.s, account ing for the interactions between x2 and %3. This amounts basically to collapsing nodes x2 and x3.
into a single node, representing the compound variable (xlt xv. This method works well on small loops, but as soon as the number of variables exceeds 3 or 4, collapsing requires handling huge matrices and washes away the natural conceptual structure embedded in the original net work. A second method of propagation is based on "stochastic relaxation" (Gem an and Ge m an, 1984). Each processor interrogates the states of the variables within its influencing neigh borhood, computes a belief distribution for the values of its host variable, then randomly selects one of these values with probability given by the computed distribution. The value chosen will subsequently be interrogated by the neighbors upon computing their beliefs, and so on. This scheme is guaranteed convergence, but usually requires very long relaxation times to reach a steady state. The method that we found most promising iB 'baBed on the ability to change the connec tivity of a network, and render it singly connectecl by instantiating a selected group of vari ables. In Figure 1, for example, instantiating z1·to some value would block the pathway z2, zlt z3 and would render the rest of the network singly connected, where the propagation techniques of the preceding section are applicable. Thus, if we wish to propagate the impact of an observed data, say at xt,, to the entire network, we first assume .x1 = 0, propagate the impact of Zts to the variables z2, ... ,z5, repeat the propagaltion under the assumption z1 = 1 and, final ly, linearly combine the two results weighed by the prior probability P ( .xl)· The legitimacy of this method is clearly seen from the ever-so-faithful conditioning rule of probability: P(x2, · · · xtJ = l: P(z2, . .. ,.fn I z 1) P(zl) .r1 The novelty here is that while in the ordinary use of the rule we seek a conditioning nriable that renders some other variables independent (separating the network into unconnect. ed frag ments), we now settle for more modest goals, requiring only that the resulting conditional pro bability P (.x2, •••• Ztslx1) have a singly-connected network representation. Note that the choice of .x2 as a conditioning variable would be equally adequate, but z5 is a bad choice, since instan tiating this variable would not disconnect the pathway .x2, .x5, .1'3.
The tool of conditioning is not foreign to human reasoning. The terms "hypothetical" or "assumption-ba!led" reasoning, "reasoning by cases," and "envisioning" all refer to the same basic mechanism of selecting a key variable, binding it to some of its values, deriving the conse quences of each binding separately, and integrating those consequences together. Reasoning by cases is very frequently used in explanation and argumentation -showing that diametrically opposed assumptions impart equal credence to a given proposition constitutes a convincing ar gument for assigning that credence to the proposition. Likewise, showing that different sets of circumstances would require the same type of action constitutes a strong argument for recom mending that action.
Although conditioning was introduced here as a sequential process, it can easily be im plemented in parallel, to comply with our propagation paradigm. Instead of a single set of 1T -� parameters, each node should maintain Beveral Buch sets, one for each value of the condition ing variable. The constraint equations (Eqs. (10) and (11)) are checked for each of these sets individually, and the appropriate parameters updated. Additionally, the prior probability of the conditioning variable can also pass along from node to node so that when the overall belief in a given proposition is required, the proper weightB will be available to perl'orm the averag mg.
By contrast, under conditioning routines, node x2 (as well as x3) will prepare for x.s, not a single parameter 1T .r 5 (xv, but two: together with the prior probability P(x1) (see Figure 3). Receiving these two forces x.s to follow suit and compute two sets of parameters as well: 1T�, (x.s) = � P(x.s�2.x3)1T;,(xv1T;.(x3) 1'2.1'3-0,1 Now imagine that some evidence is obtained, say X6 = 1. Node X6 will provide x5 with the diagnostic parameters: )..r,(x .s) = P(X6 = 1� s) x.s = 0,1 and subsequently, X5 will deliver to X2 two sets of ).1'5(XV parameters: A similar set will be computed for X3. To calculate the overall belief in a proposition, say X2, we make use of the prior probability P(x1) and compute the average BEL (xv = po 1T;, (xv >.;s (xv P(x 1 = O) + P 1 1Ti, (xv >.is (xv P(x 1 -1) It is essential to note that the conditioned parameters must propagate as separate quan tities and only be averaged when the final belief measures are to be calculated. The reason is that the conditioning variable influences the other variables in the loop along two separate paths, clockwise and counterclockwise. If we were to pass along the averaged quantities, in stead of the individual constituents, it would amount to counting the prior information twice, instead or once.

CONCLUSIONS
The architectural objectives of propagating beliefs coherently by self-activated and con current mechanisms are fully realizable in singly-connected graphs. In multiply-connected