In comparing VE and VE1 , we notice that when summing out a variable, they both combine only those factors that contain the variable. However, the factorization that the latter works with is of finer grain than the factorization used by the former. In our running example, the latter works with a factorization which initially consists of factors that contain only two variables; while the factorization the former uses initially include factors that contain five variables. On the other hand, the latter uses the operator which is more expensive than multiplication. Consider, for instance, calculating . Suppose e is a convergent variable and all variables are binary. Then the operation requires numerical multiplications and numerical summations. On the other hand, multiplying and only requires numerical multiplications.
Despite the expensiveness of the operator , VE1 is more efficient than VE . We shall provide empirical evidence in support of this claim in Section 10. To see a simple example where this is true, consider the BN in Figure 3(1), where e is a convergent variable. Suppose all variables are binary. Then, computing by VE using the elimination ordering , , , and requires numerical multiplications and numerical additions. On the other hand, computing in the deputation BN shown in Figure 3(2) by VE1 using the elimination ordering , , , , and requires only numerical multiplications and numerical additions. Note that summing out requires numerical multiplications because after summing out 's, there are four heterogeneous factors, each containing the only argument . Combining them pairwise requires multiplications. The resultant factor needs to be multiplied with the deputing factor , which requires numerical multiplications.
Figure 3: A BN, its deputation and transformations.