Fast Arc-Reversal

Abstract

Fast arc-reversal (FAR) is proposed as a new exact inference algorithm in discrete Bayesian networks (BNs), merging favourable features of Arc-reversal (AR) and Variable elimination (VE). AR constantly maintains a sub-BN structure when rendering a variable barren via arc reversals, requiring more computational effort than VE, which sacrifices a sub-BN structure by directly eliminating a variable. We formally establish that FAR can recover a unique and sound sub-BN structure after consecutive variable eliminations. Experimental results on real-world benchmark networks empirically show a substantial improvement in the average run-time and variance of FAR compared to AR. We also suggest a novel method, called d-contraction, for graphically understanding FAR since FAR is not always the same as a sequence of arc reversals.