The use of conflicts in searching Bayesian networks
This work addresses inefficiencies in Bayesian network inference for applications requiring extreme probabilities, offering an incremental improvement over naive algorithms.
The paper tackles the problem of computing prior and posterior probabilities in discrete Bayesian Networks by adapting conflicts from consistency-based diagnosis into a search-based algorithm, which is an anytime method providing error bounds and is most efficient with extreme probabilities. Empirical results demonstrate its effectiveness on networks with tens of thousands of nodes.
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.