Probabilistic conflicts in a search algorithm for estimating posterior probabilities in Bayesian networks

摘要

This paper presents a search algorithm for estimating posterior probabilities in discrete Bayesian networks. It shows how conflicts (as used in consistency-based diagnosis) can be adapted to speed up the search. 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 distributions. The general idea is to forward simulate the network, based on the “normal” values for each variable (the value with high probability given its parents). When a predicted value is at odds with the observations, we analyse which variables were responsible for the expectation failure—these form a conflict—and continue forward simulation considering different values for these variables. This results in a set of possible worlds from which posterior probabilities—together with error bounds—can be derived. Empirical results with Bayesian networks having tens of thousands of nodes are presented.