next up previous
Next: Experiments Up: Exploiting Causal Independence in Previous: Comparing VE and

Previous Methods

 

Two methods have been proposed previously for exploiting causal independence to speed up inference in general BNs [26,15]. They both use causal independence to transform the topology of a BN. After the transformation, conventional algorithms such as CTP or VE are used for inference.

We shall illustrate those methods by using the BN in Figure 3(1). Let be the base combination operator of e, let denote the contribution of to e, and let be the contributing factor of to e.

The parent-divorcing method [26] transforms the BN into the one in Figure 3(3). After the transformation, all variables are regular and the new variables and have the same possible values as e. The conditional probabilities of and are given by

The conditional probability of e is given by

for any value of e, of , and of . We shall use PD to refer to the algorithm that first performs the parent-divorcing transformation and then uses VE for inference.

The temporal transformation by Heckerman [15] converts the BN into the one in Figure 3(4). Again all variables are regular after the transformation and the newly introduced variables have the same possible values as e. The conditional probability of is given by

for each value of . For i=2, 3, 4, the conditional probability of ( stands for e) is given by

for each possible value of and of . We shall use TT to refer to the algorithm that first performs the temporal transformation and then uses VE for inference.

The factorization represented by the original BN includes a factor that contain five variables, while factors in the transformed BNs contain no more than three variables. In general, the transformations lead to finer-grain factorizations of joint probabilities. This is why PD and TT can be more efficient than VE .

However, PD and TT are not as efficient as VE1 . We shall provide empirical evidence in support of this claim in the next section. Here we illustrate it by considering calculating . Doing this in Figure 3(3) by VE using the elimination ordering , , , , , and would require numerical multiplications and 18 numerical additions.gif Doing the same in Figure 3(4) using the elimination ordering , , , , , , would require numerical multiplications and 20 numerical additions. In both cases, more numerical multiplications and additions are performed than VE1 . The differences are more drastic in complex networks, as will be shown in the next section.

  
Figure: The result of Applying Oleson's method to the BN of Figure 1.

The saving for this example may seem marginal. It may be reasonable to conjecture that, as Oleson's method produces families with three elements, this marginal saving is all that we can hope for; producing factors of two elements rather than cliques of three elements. However, interacting causal variables can make the difference more extreme. For example, if we were to use Oleson's method for the BN of Figure 1, we producegif the network of Figure 4. Any triangulation for this network has at least one clique with four or more elements, yet VE1 does not produce a factor with more than two elements.

Note that as far as computing in the networks shown in Figure 3 is concerned, VE1 is more efficient than PD, PD is more efficient than TT, and TT is more efficient than VE . Our experiments show that this is true in general.



next up previous
Next: Experiments Up: Exploiting Causal Independence in Previous: Comparing VE and



David Poole
Fri Dec 6 15:09:32 PST 1996