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

Article type: Research Article

Authors: Butz, C.J.^{a; *} | Chen, J.^a | Konkel, K.^a | Lingras, P.^b

Affiliations: [a] Department of Computer Science, University of Regina, Regina, SK, S4S 0A2, Canada | [b] Department of Mathematics and Computing Science, Saint Mary's University, Halifax, NS, B3H 3C3, Canada

Correspondence: [*] Corresponding author. E-mail: [email protected]

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.

DOI: 10.3233/IDT-2009-0064

Journal: Intelligent Decision Technologies, vol. 3, no. 3, pp. 173-180, 2009