We propose Simple Propagation (SP) as a new join tree propagation algorithm for exact inference in discrete Bayesian networks. We establish the correctness of SP. The striking feature of SP is that its message construction exploits the factorization of potentials at a sending node, but without the overhead of building and examining graphs as done in Lazy Propagation (LP). Experimental results on numerous benchmark Bayesian networks show that SP is often faster than LP.

Identifying tractable subclasses and designing efficient algorithms for these tractable classes are important topics in the study of constraint satisfaction and Bayesian network inference problems. In this paper we investigate the asymptotic average behavior of a typical tractable subclass characterized by the treewidth of the problems. We show that the property of having a bounded treewidth in the constraint satisfaction problem and Bayesian network inference problem has a phase transition that occurs while the underlying structures of problems are still sparse. This implies that algorithms making use of treewidth based structural knowledge only work efficiently in a limited range of random instances. INTRODUCTION It is well known that many NP complete problems have tractable subclasses characterized by certain structural parameters.

We compare two approaches to Bayesian network inference, called variable elimination (VE) and arc reversal (AR). It is established that VE never requires more space than AR, and never requires more computation (multiplications and additions) than AR.