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