| Variable elimination (VE) and arc reversal (AR) are two methods for performing inference in Bayesian networks (BNs). VE eliminates a set of variables by multiplying all of the probability distributions involving each variable into one distribution and then summing the variable out of the obtained product. AR, on the other hand, eliminates a set of variables by recursively modifying the BN under consideration and then building the CPTs to match the structure of the BN. In probabilistic reasoning literature, however, it is often the case that only one of these two methods is described. Moreover, no study has ever compared the efficiency and space requirements of ME against those of AR.In this thesis, we present the first study to theoretically compare VE and AR. We first simplify AR by defining its workings with respect to the original BN rather than a modified version of the original BN. Our main result is 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. |
