This paper has been concerned with how to exploit causal independence in exact BN inference. Previous approaches [26,15] use causal independencies to transform BNs. Efficiency is gained because inference is easier in the transformed BNs than in the original BNs.
A new method has been proposed in this paper. Here is the basic idea. A Bayesian network can be viewed as representing a factorization of a joint probability into the multiplication of a list of conditional probabilities. We have studied a notion of causal independence that enables one to further factorize the conditional probabilities into a combination of even smaller factors and consequently obtain a finer-grain factorization of the joint probability.
We propose to extend inference algorithms to make use of this finer-grain factorization. This paper has extended an algorithm called VE . Experiments have shown that the extended VE algorithm, VE1 , is significantly more efficient than if one first performs Olesen et al.'s or Heckerman's transformation and then apply VE .
The choice of VE instead of the more widely known CTP algorithm is due to its ability to work in networks that CTP cannot deal with. As a matter of fact, CTP was not able to deal with the networks used in our experiments, even after Olesen et al.'s or Heckerman's transformation. On the other hand, VE1 was able to answer almost all randomly generated queries with and a majority of the queries were answered in little time. It would be interesting to extend CTP to make use of the finer-grain factorization mentioned above.
As we have seen in the previous section, there are queries, especially in the 422-node network, that took VE1 a long time to answer. There are also queries that VE1 was not able to answer. For those queries, approximation is a must. We employed an approximation technique when comparing algorithms in the 422-node network. The technique captures, to some extent, the heuristic of ignoring minor distinctions. In future work, we are developing a way to bound the error of the technique and an anytime algorithm based on the technique.