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
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.
- 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.