The use of conflicts in searching Bayesian networks
  This paper discusses how conflicts (as used by the consistency-based
diagnosis community) can be adapted to be used in a search-based algorithm for
computing prior and posterior probabilities in discrete Bayesian Networks. This
is an "anytime" algorithm, that at any stage can estimate the probabilities and
give an error bound. Whereas the most popular Bayesian net algorithms exploit
the structure of the network for efficiency, we exploit probability
distributions for efficiency; this algorithm is most suited to the case with
extreme probabilities. This paper presents a solution to the inefficiencies
found in naive algorithms, and shows how the tools of the consistency-based
diagnosis community (namely conflicts) can be used effectively to improve the
efficiency. Empirical results with networks having tens of thousands of nodes
are presented.
