conflicts in a search algorithm for estimating posterior probabilities
in Bayesian networks
In Artificial Intelligence, Volume 88,
pages 69-100, 1996.
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.
You can get the
paper and get the code distribution
Last updated 11 Sept 98 - David Poole