So far, we have only encountered heterogeneous factorizations that correspond to Bayesian networks. In the following algorithm, the intermediate heterogeneous factorizations do not necessarily correspond by BNs. They do have the property that they combine to form the appropriate marginal probabilities. The general intuition is that the heterogeneous factors must combine with their sibling heterogeneous factors before being multiplied by factors containing the original convergent variable.
In the previous section, we mentioned three properties of the heterogeneous factorization represented by a deputation BN, and we used the first property to show that the factorization is flexible. The other two properties qualify the factorization as a tidy heterogeneous factorization, which is defined below.
Let 
, 
, ..., 
be a list of
variables in a deputation BN such that
if a convergent (deputy) variable 
is in 
, so
is the corresponding new regular variable e.
A flexible heterogeneous factorization of 
is said to be tidy If
,
the factorization contains
the deputing function 
and it is the only homogeneous factor
that involves 
.
Under certain conditions, to be given in Theorem 3, one can obtain a tidy factorization
of 
by summing out 
from a tidy factorization
of 
using the the following procedure.
Proceduresum-out1
- Inputs:
--- A list of homogeneous factors,
--- A list of heterogeneous factors,
z --- A variable.- Output: A list of heterogeneous factors and a list of homogeneous factors.
- Remove from
all the factors that contain z, multiply them resulting in, say, f. If there are no such factors, set
.
- Remove from
all the factors that contain z, combine them by using
resulting in, say, g. If there are no such factors, set
.
- If
, add the new (homogeneous) factor
to
.
- Else add the new (heterogeneous) factor
to
.
- Return
.
The proof of this theorem is quite long and hence is given in the appendix.
