  As real-world Bayesian networks continue to grow larger and more complex, it
is important to investigate the possibilities for improving the performance of
existing algorithms of probabilistic inference. Motivated by examples, we
investigate the dependency of the performance of Lazy propagation on the
message computation algorithm. We show how Symbolic Probabilistic Inference
(SPI) and Arc-Reversal (AR) can be used for computation of clique to clique
messages in the addition to the traditional use of Variable Elimination (VE).
In addition, the paper resents the results of an empirical evaluation of the
performance of Lazy propagation using VE, SPI, and AR as the message
computation algorithm. The results of the empirical evaluation show that for
most networks, the performance of inference did not depend on the choice of
message computation algorithm, but for some randomly generated networks the
choice had an impact on both space and time performance. In the cases where the
choice had an impact, AR produced the best results.

Artificial Intelligence