Probabilistic Conflicts in a Search Algorithm for Estimating Posterior Probabilities in Bayesian Networks

This paper presents a search algorithm for estimating prior and posterior probabilities in discrete Bayesian networks. It shows how conflicts (as used by the consistency-based diagnosis community) can be adapted to speed up the search. This is an 'anytime' algorithm, that at any stage can estimate probabilities and give an error bound. This algorithm is especially suited to the case where there are skewed distributions, although nothing about the algorithm or the definitions depends on skewness of conditional distributions. Empirical results with Bayesian networks having tens of thousands of nodes are presented.