A Comparison of Different Marginalization Operations in Simple Propagation

Simple Propagation is a message passing algorithm for exact inference in Bayesian networks. Simple Propagation is like Lazy Propagation but uses the one in, one out-principle when computing inter-clique messages passed between cliques of the junction tree. Here Lazy propagation performs a more in-depth graphical analysis of the set of potentials. Originally, Simple Propagation used Variable Elimination as the marginalization operation algorithm. In this paper, we describe how Symbolic Probabilistic Inference (SPI) can be used as the marginalization operation algorithm in Simple Propagation. We report on the results of an empirical evaluation where the time performance of Simple Propagation with SPI is compared to the time performance of Simple Propagation with Variable Elimination and Simple Propagation with Arc-Reversal. The experimental results are interesting and show that in some cases Simple Propagation with SPI has the best time performance.