This paper extends VE to exploit this finer-grain factorization. We will compute the answer to a query by summing out variables one by one from the factorization just as we did in VE .
The correctness of VE is guaranteed by the fact that factors in a homogeneous factorization can be combined (by multiplication) in any order and by the distributivity of multiplication over summations (see the proof of Theorem 1).
According to Proposition 3, the operator 
is
distributive over summations. However, factors in a heterogeneous factorization
cannot be combined in arbitrary order. For example, consider the
heterogeneous factorization (6). While it is correct
to combine 
and 
using 
, and
to combine 
and 
using 
,
it is not correct to combine 
and 
with 
. We want to combine these latter two by multiplication,
but only after each has been combined with its sibling heterogeneous
factors.
To overcome this difficulty, a transformation called deputation will be performed on our BN. The transformation does not change the answers to queries. And the heterogeneous factorization represented by the transformed BN is flexible in the following sense:
A heterogeneous factorization of a joint probability is flexible if:
This property allows us to carry out multiplication of homogeneous
factors in arbitrary order, and since 
is associative and commutative,
combination of heterogeneous factors in arbitrary order.
If the conditions of Proposition 4 are satisfied, we can also
exchange a multiplication with a combination by 
.
To guarantee the conditions of Proposition 4, the elimination ordering
needs to be constrained (Sections 7 and 8).
The heterogeneous factorization of
given at the end of the previous section is
not flexible. Consider combining all the heterogeneous factors.
Since the operator 
is commutative and associative, one can first
combine, for each i, all the 
's, obtaining
the conditional probability of 
, and then combine the resulting
conditional probabilities. The combination
is not the same as the multiplication
because the
convergent variables 
and 
appear in more than one factor.
Consequently, equation (7) does not hold and
the factorization is not flexible.
This problem arises when a convergent variable
is shared between two factors that are not siblings. For example, we
do not want to combine 
and 
using
. In order to tackle this problem we introduce a new
`deputation' variable so that each heterogeneous factor contains a
single convergent variable.
Deputation is a transformation that one can apply to a BN to make
the heterogeneous factorization represented by the BN flexible.
Let e be a convergent variable.
To depute e is to
make a copy 
of e, make
the parents of e be parents of 
,
replace e with 
in the contributing factors of e,
make 
the only parent of
e, and set the conditional probability 
as follows:
We shall call 
the deputy of e.
The deputy variable 
is a
convergent variable by definition. The variable e, which is convergent
before deputation,
becomes a regular variable after deputation.
We shall refer to it as a new regular variable.
In contrast, we shall refer to the variables that are regular
before deputation as old regular variables.
The conditional probability 
is
a homogeneous factor by definition.
It will sometimes be called the deputing function and written
as 
since it ensures that 
and e always take the same value.
Figure 2: The BN in Figure 1 after the deputation of convergent variables.
A deputation BN is obtained from a BN by deputing all the convergent variables. In a deputation BN, deputy variables are convergent variables and only deputy variables are convergent variables.
Figure 2 shows the deputation of the BN in Figure 1. It factorizes the joint probability
into homogeneous factors
and heterogeneous factors
This factorization has three important properties.
's are
no longer convergent variables and their deputies are.)
appears
in one and only one homogeneous factor, namely the deputing function
.
Proof: Consider the
combination, by 
, of all the heterogeneous
factors in the deputation BN.
Since the combination operator 
is commutative
and associative, we can carry out the combination in
following two steps. First for each convergent (deputy) variable 
,
combine all the heterogeneous factors that contain 
,
yielding the conditional probability 
of 
.
Then combine
those resulting conditional probabilities.
It follows from the first property mentioned above that
for different convergent variables 
and 
, 
and 
do not share convergent variables. Hence the combination
of the 
's is just the multiplication of them.
Consequently, the combination, by 
,
of all heterogeneous factors in a deputation BN
is just the multiplication of the conditional probabilities of
all convergent variables. Therefore, we have
The proposition is hence proved. 
Deputation does not change the answer to a query. More precisely, we have
Proof: Let R, E, and 
be the lists
of old regular, new regular, and deputy variables in the
deputation BN respectively. It suffices to show that
is the same in the original BN as in the deputation
BN. For any new regular variable e, let 
be its deputy.
It is easy to see that the quantity
in the deputation BN is the
same as 
in the original BN. Hence,
The proposition is proved. 
