A formal comparison of variable elimination and arc reversal in Bayesian network inference

Abstract

We present a comparative study of 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. These two characteristics are supported by experimental results on six large BNs, which indicate that VE is never slower than AR and can perform inference significantly faster than AR.