Stable local computation with conditional Gaussian distributions.
This article describes a propagation scheme for Bayesian networks with conditional Gaussian distributions that does not have the numerical weaknesses of the scheme derived in Lauritzen (Journal of the American Statistical Association 87: 10981108, 1992).The propagation architecture is that of Lauritzen and Spiegelhalter (Journal of the Royal Statistical Society, Series B 50: 157 224, 1988).In addition to the means and variances provided by the previous algorithm, the new propagation scheme yields full local marginal distributions. The new scheme also handles linear deterministic relationships between continuous variables in the network specification.The computations involved in the new propagation scheme are simpler than those in the previous scheme and the method has been implemented in the most recent version of the HUGIN software.
Introduction
Bayesian networks have developed into an important tool for building systems
for decision support in environments characterized by uncertainty (Pearl
1988; Jensen 1996; Cowell et al. 1999).
The exact computational algorithms that are most developed are concerned
with networks involving discrete variables only.
This is Research Report R-99-2014, Department of Mathematical Sciences, Aalborg
University.
Lauritzen (1992) developed a computational scheme for exact local computation
of means and variances in networks with conditional Gaussian dis-
tributions. Unfortunately the scheme turned out to have fatal numerical
difficulties, basically due to a computationally unstable transformation between
two different representations of these distributions.
The motivation for the present work is to remedy this numerical insta-
bility. The fundamental idea behind the developments below is at all times
to keep the interesting quantities represented in units that have a direct
meaning such as probabilities, means, regression coefficients, and variances.
These must necessarily be of a reasonable order of magnitude.
The computational scheme to be developed is rather remote from the
computational architecture used to deal with the discrete variables in the
HUGIN software and similar schemes as represented, for example, in abstract
form in Shenoy and Shafer (1990) and Lauritzen and Jensen (1997).
The difference is partly related to the fundamental operations of combination
and marginalization being only partially defined, but also the handling
of evidence is quite different. The scheme is closest to the original scheme
developed in Lauritzen and Spiegelhalter (1988), but abstract considerations
such as those in Shafer (1991) seem necessary to embed the scheme in
a unifying framework.
Additional benefits of the present scheme includes that deterministic linear
relationships between the continuous variables can be represented without
difficulty, and we show how to calculate full local marginals of continuous
variables without much computational effort. Both of these represent major
improvements over the original scheme of Lauritzen (1992).
distributions and regressions
The Bayesian networks to be considered have distributions that are conditionally
Gaussian, a family of distributions introduced by Lauritzen and
Wermuth (1984, 1989). We shall briefly review some standard notation but
otherwise refer the reader to Lauritzen (1996) for further details.
The set of variables V is partitioned as into variables of
discrete (\Delta) and continuous (\Gamma) type and the joint distribution of the continuous
variables given the discrete is assumed to be multivariate Gaussian,
i.e.
where Y denotes the continuous variables, I the discrete, j\Gammaj denotes the
cardinality of \Gamma, and \Sigma(i) is positive semidefinite. We then say that
I [ Y follows a CG distribution.
The symbol N j\Gammaj (; \Sigma) denotes the multivariate Gaussian distribution
with mean  and covariance matrix \Sigma. In the case where \Sigma is positive
definite, this distribution has density
(2) j\Gammaj det \Sigma
exp
If \Sigma is singular, the multivariate Gaussian distribution has no density
but is implicitly determined through the property that for any vector v, the
linear combination v ? Y has a univariate Gaussian distribution:
is to be interpreted as the distribution degenerate at .
See for example Rao (1973), Chapter 8, for a description of the Gaussian
distribution at this level of generality.
Note: there is a slight difference between the terminology used here and
in Lauritzen (1996) in that we allow p(i) to be equal to 0 for some entries
i. We also avoid using the so-called canonical characteristics of the CG
distribution as the numerical instability of the scheme in Lauritzen (1992)
is associated with switching between these and the moment characteristics
As an additional benefit, we can then allow singular covariance
matrices \Sigma.
Occasionally it is of interest to describe how a CG distribution depends
on additional variables. If the dependence on a set of discrete variables j
and a vector of continuous variables z is determined as
we refer to this dependence as a (simple) CG regression. Note that neither
the covariance matrix nor the discrete part depends on the continuous variables
z and the conditional expectation of the continuous variables depends
linearly on the continuous variables for fixed values of the discrete variables
(i; j). In a general CG regression, p is also permitted to depend on z in a
specific way (Lauritzen 1996), but this is not relevant here.
3 Mixed Bayesian networks
We consider probabilistic networks over a directed acyclic graph (DAG),
known as Bayesian networks (Pearl 1986). A mixed Bayesian network with
conditional Gaussian distributions is specified over a set of nodes or variables
discrete and continuous variables as
above. The DAG associated with the network must satisfy the restriction
that discrete nodes have no continuous parents. The conditional distributions
of discrete variables given their (discrete) parent variables are specified
as usual, whereas the conditional distribution of continuous variables are
given by CG regressions
Note that as Y is one-dimensional, fl(i) is just a nonnegative real number.
If distribution specifies a linear and deterministic
dependence of Y on Z.
The assumptions above imply that the joint distribution of all variables
in the Bayesian network is a CG distribution.
The computational task to be addressed is that of computing the joint
distribution of interesting subsets of these variables - in particular of a single
variable - possibly given specific evidence, i.e. given known values of
arbitrary subsets of other variables in the network. This distribution will in
general be a mixture of conditional Gaussian distributions.
The propagation scheme to be described involves the usual steps: Construction
of a junction tree with strong root, initialization of the junction
tree, incorporation of evidence, and local computation of marginals
to cliques.
4 Potentials and their operations
4.1 CG potentials
The basic computational object is that of a CG potential. A CG potential is
represented as a partitioning of
the continuous variables in the domain D of OE into head and tail :
H [T . We denote the variables in the head by Y and those in the tail by Z
and assume these to be r and s-dimensional. An arbitrary configuration of
the discrete variables in the domain is denoted by i. Thus, every potential
has a domain with discrete nodes, head nodes and tail nodes, some of which
could be absent. In the expression above
is a table of nonnegative numbers, i.e. a 'usual' potential
as in the discrete case;
is a table of r \Theta 1 vectors;
fB(i)g is a table of r \Theta s matrices;
is a table of r \Theta r positive semidefinite symmetric matrices.
The potential represented by [p; A; B; C](H specifies the CG regression
The abstract notion of potentials with head and tail is due to Shafer
(1991). In many ways it would be more natural also to partition the discrete
variables into head and tail variables, then reflecting that the potentials
always represent a conditional distribution of head variables given their tail.
But as the partitioning of discrete variables is not exploited in our propagation
scheme, we have chosen not to do so. A propagation scheme of the
type (Madsen and Jensen 1998) could exploit such a partitioning.
The initial conditional distribution for a continuous variable v with parent
nodes pa(v) in a mixed Bayesian network corresponds to the CG potential
of the domain equal to pa(v) " \Delta. Similarly, the specification of the conditional
distribution of a discrete variable given its parents corresponds to the
CG potential [p; \Gamma; \Gamma; \Gamma](\Gamma j \Gamma), where p is determined by the conditional
probability tables. The discrete part of the domain is equal to the family
hyphens indicate that the corresponding parts of the
potential are void.
4.2 Extension and reduction
A CG potential can be extended by adding discrete variables to its domain
or continuous variables to its tail. When adding discrete variables to its
domain, the parts of OE are extended as p   (i; adding
continuous variables to its tail, the B matrices are extended by adding zero
columns for each of the new tail variables:
Similarly, if B has columns that are identically zero for all values of i, the
corresponding variables can be removed from the tail of the potential, and
we say that the tail is reduced. If no columns of B are identically zero, the
tail of the potential is said to be minimal.
4.3 Marginals
As in the propagation scheme of Lauritzen (1992), marginals of a CG potential
are only defined under certain conditions and when marginals over
groups of discrete and continuous variables are calculated, the marginals
over continuous variables are calculated first.
Marginals over continuous variables can only be calculated over head
variables. If [p; A; B; C](H
corresponding to a partitioning of the head variables as
marginal of OE to D
We say that these marginals are strong as they correspond to calculating
ordinary marginals of the relevant conditional Gaussian distributions.
When all head variables have been removed by marginalization, the tail
can be reduced to become empty so that a discrete potential emerges. This
leads indirectly to marginalization of tail variables.
Marginals over discrete variables are defined only when the tail of the
potential is empty, i.e. when there are no continuous conditioning variables
and therefore no B matrix. Then the marginal of the CG potential
\Gamma) with discrete domain partitioned as U [ W over W is
where
~
~
~
ae
oe
This marginalization is said to be weak when it does
not correspond to calculating the full marginal distribution.
In general the full marginal distribution will be a discrete mixture of CG
distributions, and the distribution represented by the weakly marginalized
potential will be the CG distribution closest in Kullback-Leibler distance to
the true marginal, see Lauritzen (1996), Lemma 6.4.
4.4 Direct combination
The combination operation for CG potentials will not be defined for an
arbitrary pair of potentials and as such the scheme is quite different from
most other propagation schemes.
The direct combination of two CG potentials
and defined only if the head of / is disjoint from
the domain of OE, i.e. satisfies that
Here we always assume that the potentials have first been reduced so that
the tails are minimal.
If (1) is fulfilled for the reduced potentials, these are subsequently extended
such that the extensions have This is done by extending
Next, let
corresponding to (H We then define the direct combination as the
(apparently non-commutative) product
where
and
This combination operation corresponds to ordinary composition of conditional
distributions. Note that if both of OE
\Omega / and /
\Omega OE exist, they are
equal. The direct combination also satisfies
\Omega /)
\Omega (/
\Omega
in the sense that if the combinations on one side are well defined, so are those
on the other side and the resulting potentials are the same. Shafer (1991)
has called this type of algebraic structure a partial commutative semigroup.
The notation above reflects that the operation of direct combination in
some sense is similar to that of forming disjoint union of sets.
Unfortunately, direct combination of CG potentials is not sufficient for
our propagation scheme to work for an arbitrary mixed Bayesian network.
But before we can define a more general combination, we need to introduce
the notion of complement.
4.5 Complements
If the head of a CG potential partitioned as
and [p   ; A is the strong marginal of OE, then we define its
complement OE jH1[T as the CG potential [q; E; F; G](H
Here denotes an arbitrary generalized inverse of the matrix M (Penrose
1955), i.e. an arbitrary matrix M \Gamma satisfying
see also Rao (1973), pp. 24-27, and Rao and Mitra (1971). Then
which is easily checked by using the formulae for combination together
with (2) and the fact that for any generalized inverse
11 of C 11 it also
holds that
see e.g. Rao (1973), formula (8a.2.12).
Note that in the above expressions we either have p  ;. The
decomposition of a potential into its strong marginal and its complement
corresponds exactly to the decomposition of a probability distribution into
its marginal and conditional.
4.6 Recursive combination
We next define a more general combination of CG potentials. This is required
for the initialization process described in the section below. Consider
again two potentials
with minimal tails. If H the combination will remain undefined.
If the heads of the potentials are disjoint, we let
\Omega / or
\Omega OE
if at least one of the right-hand-side expressions are defined. As we have
OE
\Omega OE if both are defined, there is no ambiguity in this definition.
If neither of the direct combinations are defined, we must have that
Let D If both of these are empty, the
combination will not be defined. Else we decompose one of the factors, say OE
(assuming D 12 6= ;), as
\Omega OE 00
and attempt to combine OE and / as
This equation is to be understood recursively in the sense that the procedure
described is to be repeated for the product OE
0\Omega /, whereas the direct
combination in the expression is well defined by construction.
The recursion terminates unsuccessfully if two potentials with minimal
tails satisfy (3) and also
Then the combination of OE and / remains undefined.
Initialization
Setting up the computational structure involves several steps: forming a
strong junction tree with strong root, assigning potentials to cliques, transforming
these to potentials of a specific form by sending messages first towards
the root, then away from the root.
A junction tree with strong root is constructed in the usual way, see
for example Cowell et al. (1999), Chapter 7. Thus, we assume to begin
our computational scheme at the point where we have specified a mixed
Bayesian network and an associated junction tree with cliques C and a root
such that for all neighbouring cliques C and D with C closer to the
root than D, we have that
i.e. if the 'residual' D n C contains a discrete variable, then the separator S
consists of discrete variables only. Also, it holds for all variables v that fa(v)
is contained in some clique of the junction tree.
5.1 Assignment of potentials to cliques
Every CG potential corresponding to a specification of the conditional distribution
of a node given its parents is assigned to an arbitrary clique of the
junction tree that contains its family. The potentials assigned to a given
clique are subsequently combined in some order. This can always be done
using direct combination as the DAG is acyclic and each continuous node is
head of exactly one potential.
5.2 Collecting messages at the root
The next step in the initialization process involves sending messages from
the leaves of the junction tree towards the root in a way similar to the
process known as CollectEvidence in the standard HUGIN architecture
(Jensen et al. 1990), although the messages sent are slightly different. Thus,
a clique is allowed to send a message if it is a leaf of the junction tree, or
if it has received messages from all of its neighbours further away from the
root. The process stops when the root has received messages from all of its
neighbours. We use the term Collect for this operation.
When a Collect-message is sent from a clique C to its neighbour D
towards the root with separator D, the potentials OE C on C and OE D
on D are modified to become OE
C and OE
OE
D\Omega OE #S
i.e. OE
C is the complement of OE C after marginalization to the separator and
OE
D is obtained by combining the original potential with the marginal of OE C .
It remains to be argued that the combination in (6) is indeed well defined.
To see this we first realize that the heads of any two potentials to be
combined must necessarily be disjoint as a variable occurs only once as head.
Further, for any of the potentials involved in (6), it holds that tail variables
have no parents in the DAG induced by the conditional specifications
that have been combined and possibly marginalized to form the potential.
Thus, if the potential is reduced to have minimal tail, there must be a directed
path from every variable present in the tail of the potential to some
variable in the head of the potential. Because then it holds for any tail
variable u that it is not conditionally independent of the head given the
remaining tail variables. Thus there must be a trail which d-connects u to
some variable in the head. As tail variables have no parents, this trail must
initially be directed away from u and leave the tail immediately. As only tail
variables are in the conditioning set, there can be no head-to-head nodes on
this active trail, which then must form a directed path from u to the head.
Assume that (4) is satisfied and H 1 and H 2 are both nonempty. This
implies . From this we deduce that there must be a
directed path from every variable u (implying
and from v there must be a directed path to some
variable w . Thus, from every u there is a directed path to some
nonempty and finite, this would contradict the
acyclicity of the DAG.
To illustrate that recursive combination is necessary for the initialization
process, we consider two simple examples.
Example 1 Consider the DAG in Figure 1. When potentials are assigned
to cliques, the nodes c and e must be assigned to fb; c; eg and the remaining
nodes to fa; b; c; dg.
Combining the potentials in the two cliques leads to potentials with head
and tail (fc; eg j fbg) in fb; c; eg and (fb; dg j fcg) in fa; b; c; dg.
When the first of these is marginalized to the separator fb; cg, the result
has head and tail (fcg j fbg), which cannot be directly combined with the
potential on the root clique fa; b; c; dg.
e

Figure

1: A mixed Bayesian network with associated junction tree. The
variable a is the only discrete variable and the strong root is fa; b; c; dg.
The root clique potential is then decomposed into potentials with head
and tail (fdg j fb; cg) and (fbg j fcg). But the latter can be reduced to (fbg j \Gamma)
as the dependence on c is spurious. The potentials can now be combined
directly. 2
In the example above, it was the potential in the receiving clique that
was decomposed. And had we not combined the potentials in the receiving
clique before combining with the incoming message, the combination could
have been performed directly. The next example illustrates that it may be
the incoming message which needs to be decomposed and there is no way
to avoid computation during the decomposition.
Example 2 Consider the DAG in Figure 2. When potentials are assigned to
cliques, the nodes d, e and f must be assigned to fc; d; e; fg, c to fa; c; d; eg,
and b to fa; b; dg. There are two choices for the node a and we choose to
assign it to the clique fa; b; dg, which is also chosen as root.
When Collecting towards the root, the first message is the fc; d; eg-
marginal of the potential in fc; d; e; fg. This must be calculated by combining
the assigned potentials to one with head and tail (fd; e; fg j fcg) and
then marginalizing to (fd; eg j fcg).
Again this cannot be directly combined with the potential on the neighbouring
clique which has head and tail (fcg j feg).
The incoming potential is then decomposed into potentials with head and
tail (fdg j fc; eg) and (feg j fcg). But the latter can be reduced to (feg j \Gamma)
as the dependence on c is spurious. The potentials can now be combined
directly. 2
After the root has received messages from all its neighbours, the root
potential contains the correct root marginal and its tail is then empty. If
evidence has been incorporated, a normalization of the discrete part of the
root potential may be necessary, see Section 7.
e
f

Figure

2: A mixed Bayesian network with associated junction tree. The
variable a is the only discrete variable and the strong root could be chosen
to be either fa; b; dg or fa; c; d; eg.
Also, the potential OE representing the joint distribution of all the variables
is now equal to the combination of all the clique potentials OE C
O
In fact, as all marginals computed during the Collect phase have been
strong, it holds for any subset C 0 ' C which contains the root R and forms
a connected subtree of the junction tree that
O
As the complements are stored in the cliques during
Collect and the separators are not playing a specific role during this
process, the computation is similar to the process of forming a set chain in
Lauritzen and Spiegelhalter (1988). Thus the inward computation is of the
type called Lauritzen-Spiegelhalter architecture in Shafer (1996), see also
Lauritzen and Jensen (1997).
5.3 Distributing messages from the root
The first step in the calculation of marginals involves sending messages away
from the root, similar to DistributeEvidence in the standard HUGIN
architecture. The root begins by sending messages to all its neighbours, and
a clique is allowed to send a message as soon as it has received one from its
neighbour closer to the root. We use the term Distribute for this process
which again has slightly different messages than in the standard HUGIN
architecture.
When a Distribute-message is sent from a clique C to its neighbour D
further away from the root with separator them, C has
just received a message from its neighbour towards the root. We make the
inductive assumption that the separator S 0 towards the root then contains
the weak clique marginal of the joint potential
When sending a message, a new potential OE S is created on S as follows.
First the weak clique marginal at C is calculated as
That this formula is correct is seen exactly as in Lauritzen (1992). Next this
potential is further marginalized to the separator
The combination is well defined because after the collect operation, complements
were stored in the cliques so the head of OE C is disjoint from S 0 and
the (weak) marginal is well defined as the tail of OE C is contained in the head
of OE S 0 implying that the combination in (9) has empty tail.
After Distribute the separators all contain weak marginals to the separator
nodes.
Note that we have chosen not to store the weak clique marginals calculated
under Distribute, but preferred to keep the original complement
potentials. This is a minor variation of the Lauritzen-Spiegelhalter architecture

The initialization process is now completed. The cliques of the junction
tree contain complement potentials, the separators contain weak marginals
of the joint potential, and this joint potential can be recovered by (7).
6 Computation of marginals
When the junction tree has been initialized as described in the previous
section, various types of marginals can easily be calculated.
6.1 Marginals of variables in a single clique
If not stored separately, weak clique marginals can always be recalculated
as in (9) when needed, and further marginalized to subsets of cliques, in
particular to single nodes.
Under some circumstances, these weak marginals happen to be strong
and give the correct, full marginal distribution of the variables involved.
This is clearly true if the desired marginal involves discrete variables only.
But there are other cases of interest when this is true.
As already mentioned, the root clique contains the correct full marginal
distribution of its variables. Thus, for example, the true marginal of the set
of continuous variables Y in the root clique can be easily calculated as a
Gaussian discrete mixture with weights p(i), i.e.
where the root potential is [p; A; \Gamma; Further marginalization
can then easily be performed.
But the same holds for a clique C that satisfies the slightly less restrictive
condition that the tail of its potential is empty. For example, this is the case
if the separator of the clique C towards the root contains discrete variables
only.
To see this we argue as follows. From (8) we have that the true marginal
to the union of cliques on the path from the root to C is given by combination
of the relevant potentials
O
where
and the cliques on the path are C. The continuous variables
in C are conditionally independent of the remaining discrete variables
on this path, given the separator variables; as the tail of the potential on C
is assumed empty, this also holds given just the discrete separator variables.
Proposition 6.3 of Lauritzen (1996) then yields that the weak marginal to C
is also equal to the full marginal and we can proceed as with the root clique.
6.2 Rearranging the junction tree
To obtain the marginal of a set of variables that is not a subset of some clique
of the junction tree or to obtain strong marginals of a group of variables or
a single variable that is not in a clique having a potential with an empty
tail, the junction tree must be rearranged. Fortunately there is a simple
operation that can be used to achieve the necessary rearrangement which
we denote by Push. It acts on a group of variables M which are contained in
a clique W with neighbour U towards the root and corresponding separator
. The operation Push appplied to the variables M does the
1. The potential OE W is decomposed as
\Omega
2. The clique U is extended to U
3. The potentials are changed as
\Omega
\Omega
After the Push operation the variables in M have come closer to the strong
root, but the extended junction tree still represents the joint potential as
after the initialization. The price that has been paid is that the clique U
has increased to U   .
Example 3 We illustrate the Push operation using the mixed Bayesian
network in Figure 2, assuming that we have chosen fa; b; dg as root.
After initialization the clique fa; c; d; eg contains the potential representing
the conditional distribution of variables fc; eg given fa; dg having head
and tail (fc; eg j fdg).
If we use Push on fcg, this potential is decomposed into its marginal with
head and tail (fcg j fdg) and complement with head and tail (feg j fc; dg).
The root clique is now extended with the variable c and the marginal is
combined with the root potential, whereas the complement is kept in the
clique fa; c; d; eg. 2
6.3 Marginals of variables in different cliques
If a (weak) marginal is desired of a set of variables that is not a subset of
some clique of the original junction tree, we first form the smallest connected
subtree of the original junction tree that contains all the variables. Let C
be the clique of the subtree that is closest to the strong root of the original
junction tree. By repeated use of the Push operation we eventually achieve
that the variables in question all become members of C. The desired weak
marginal can then be computed directly using (9).
6.4 Strong marginals
If the strong marginal of a group of variables is desired, the Push operation
again yields the appropriate rearrangement of the junction tree.
As in the computation of weak marginals, we first form the smallest
connected subtree of the original junction tree that contains all the variables.
Let C be the clique of this subtree that is closest to the strong root R of
the original junction tree. Again, we use the Push operation to make the
variables in question become members of C. If C, after performing the Push
operations, has a potential with an empty tail, we can compute the desired
strong marginal from the potential of C as in (10). Otherwise, we need to
Push the variables in question closer to R until we eventually have all the
variables contained in a clique having a potential with an empty tail; from
the potential of this clique we can compute the desired potential as in (10).
If necessary, we may need to Push the variables all the way to R.
The calculation of the strong marginal for a single continuous variable
is an important special case, and from the above discussion it follows that
such a marginal can be calculated with limited additional effort, since no
potential of the junction tree will be extended with more than a single
continuous variable as part of this calculation.
7 Incorporating evidence
At this point we assume that the initialization process has been completed so
that the cliques of the junction tree contain complements and the separators
contain weak marginals.
Discrete evidence is incorporated as usual, it does not matter where, and
it is not necessary to insert discrete evidence in more than one clique.
To describe how to incorporate continuous evidence we first realize that
every continuous node necessarily appears as head in exactly one clique,
which is the clique where it appears closest to the strong root. In all other
clique potentials where it appears, it must be a tail node.
Also, if U and W are neighbouring cliques with U closest to the root,
the continuous variables in the separator constitute a superset
of the tail of the potential (complement) that is stored in W .
It is most convenient to incorporate evidence about continuous nodes a
single node at a time. Evidence that Y must be entered in all cliques
appears. We assume that the clique where Y 2 appears as head
has a potential with an empty tail. If this is not the case, we use the Push
operation described above in Subsection 6.2 until we achieve this. We then
proceed as follows:
1. In cliques where Y 2 is a tail node, the tail of the clique potential
is decreased by Y 2 , p and C are unchanged, and B is changed by
removing the column B 2 corresponding to Y 2 . A is modified to become
A
2. In the clique where Y 2 is a head node we partition the head nodes as
under marginalization into The potential after inserted
evidence is denoted OE
obtained from H by removing Y 2 . The tail T   (and thus B   ) is empty.
We then distinguish two cases:
(a) If there is a j with C 22 (j), we let for all i
ae
and for all i with p   (i) ? 0 we let
A
(b) Else we let
2C22 (i)
and for all i with p   (i) ? 0 we let
A
Intuitively the operation reflects that any deterministic explanation of the
evidence (with C 22 infinitely more likely than a non-deterministic
one, if it is available. The calculation for case (2a) is simply based upon the
fact that
whereas a standard density calculation is appropriate in case (2b), where
The correctness of the operation can be formally proved by a small calculation
in (not so elementary) probability. For simplicity we only give this
argument in the case where Y 1 is void, so that Y
Let q(i j y) denote the kernel obtained by normalizing p   above, but where
we have let the dependence on y be explicit, i.e.
We need to show that for any interval D on the real line, q satisfies the
relation
Z
where  is the marginal distribution of Y , i.e.
and  j denoting the normal distribution NfA(j); C(j)g, degenerate at A(j)
For C 22
Z
ae
Thus we get
Z
ae P
ae
If C 22 (i) ? 0 we similarly get
Z
Z
Z
When a piece of continuous evidence has been inserted, the representation
is still a 'complement' representation, and the insertion of the next
F

Figure

3: Bayesian network and strong junction tree for the waste incinerator
example. The variables are W (type of waste), F (filter state), B (burn-
ing regimen), M i (metals in waste), E (filter efficiency), C (CO 2 emission),
D (emission of dust), M o (emission of metals), and L (light penetrability).
The variables W , F and B are discrete.
piece of evidence can take place. When all evidence has been inserted, we
Collect towards the root as during initialization. This collection will only
involve proper computations in the discrete part of the potentials. And
the normalizer at the root clique will be equal to the joint density of the
evidence.
Example 4 Our final example is the Waste example described in Lauritzen
(1992) and Cowell et al. (1999), Section 7.7, and we refer to either
of these for the details of the numerical specifications. The example is
concerned with the control of the emission of heavy metals from a waste
incinerator:
The emission from a waste incinerator differs because of compositional
differences in incoming waste. Another important factor
is the waste burning regimen which can be monitored by measuring
the concentration of CO 2 in the emission. The filter efficiency
depends on the technical state of the electrofilter and the amount
and composition of waste. The emission of heavy metals depends
both on the concentration of metals in the incoming waste and
the emission of dust particulates in general. The emission of dust
is monitored through measuring the penetrability of light.
The essence of this description is represented in the Bayesian network of

Figure

3, which also shows a junction tree. The strong root can be chosen
either as fB; Cg or fB; F; W;Eg. There is only one way to assign (the potentials
corresponding to) the continuous variables to cliques of the junction
tree: C is assigned to fB; Cg, D to fB; W;E;Dg, E to fB; F; W;Eg, L to
g. So, there is exactly
one potential involving continuous variables assigned to each clique, and the
continuous components of these potentials become the corresponding continuous
components of the clique potentials of the initialized strong junction
tree. This is because the Collect operation - for this particular junction
tree - does not change the continuous components of the clique potentials
during the initialization process.
Incorporation of evidence on C or E can be done without invoking the
Push operation, since these variables appear either as head in the root or
in a clique with discrete separator towards the root. Incorporating evidence
on D requires D to be Pushed to fB; F; W;Eg (unless evidence on E has
already been incorporated). Similarly, incorporation of evidence on L will
require Pushing L to fB; F; W;Eg unless some separator along the path
from fL; Dg to fB; F; W;Eg has been made empty or fully discrete by incorporation
of evidence on D and/or E.
Before incorporation of evidence on M i and M o the clique fW; D;M i g has
a potential with head fM i g and an empty tail. Incorporating evidence on M i
at this point can therefore be done without invoking the Push operation. If,
on the other hand, evidence on M o (but not on D) has been incorporated,
the potential on the clique fW; D;M i g will have head and tail (fM i g j fDg)
and incorporating evidence on M i at this point will require Pushing M i
closer to fB; F; W;Eg.
Incorporation of evidence on M Pushing M o to fW; D;M i g
unless evidence have been incorporated on both D and M i .
Similar considerations apply to finding full mixture distributions for individual
continuous variables.

Figures

4 and 5 display full mixture distributions of all the continuous
variables before and after incorporation of the information that the waste
has been of industrial type, L has been measured to 1:1, and C to \Gamma0:9. 2

Figure

4: Screendumps from the HUGIN software displaying full marginals
of all continuous variables from the waste incinerator example before any
evidence has been incorporated.

Figure

5: Screendumps from the HUGIN software displaying full marginals
of the remaining continuous variables from the waste incinerator example
after inserting the evidence that the waste has been of industrial type, L has
been measured to 1:1, and C to \Gamma0:9.

Acknowledgements

The first author has benefited from conversations with Glenn Shafer concerning
the development of an abstract theory of local computation. The
research has been partly supported by the Danish Research Councils through
the PIFT programme.
Anders L. Madsen provided helpful comments on a draft version of this
paper, and Lars M. Nielsen prepared the HUGIN screendumps shown in

Figures

4 and 5.



--R


Probabilistic Networks and Expert Systems.
An Introduction to Bayesian Networks.
Bayesian updating in causal probabilistic networks by local computation.
Propagation of probabilities
Graphical Models.
Local computation with valuations from a commutative semigroup.
Local computations with probabilities on graphical structures and their application to expert systems (with discussion).
Mixed interaction models.
Graphical models for associations between variables
Annals of Statistics
Lazy propagation in junction trees.



Probabilistic Reasoning in Intelligent Systems.
A generalized inverse for matrices.
Linear Statistical Inference and Its Applications
John Wiley and Sons

An axiomatic study of computation in hypertrees.
Probabilistic Expert Systems.
Axioms for probability and belief- function propagation

The Netherlands.
--TR

--CTR
Anders L. Madsen, An empirical evaluation of possible variations of lazy propagation, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.366-373, July 07-11, 2004, Banff, Canada
Thiesson , David Maxwell Chickering , David Heckerman , Christopher Meek, ARMA time-series modeling with graphical models, Proceedings of the 20th conference on Uncertainty in artificial intelligence, p.552-560, July 07-11, 2004, Banff, Canada
Robert G. Cowell, Local Propagation in Conditional Gaussian Bayesian Networks, The Journal of Machine Learning Research, 6, p.1517-1550, 12/1/2005
David Barber, Expectation Correction for Smoothed Inference in Switching Linear Dynamical Systems, The Journal of Machine Learning Research, 7, p.2515-2540, 12/1/2006
Martin Neil , Manesh Tailor , David Marquez, Inference in hybrid Bayesian networks using dynamic discretization, Statistics and Computing, v.17 n.3, p.219-233, September 2007
propagation of evidence;bayesian networks;gaussian mixtures;artificial intelligence;probabilistic expert systems;CG distributions