An optimal approximation algorithm for Bayesian inference

摘要

Approximating the inference probability Pr[X = x | E = e] in any sense, even for a single evidence node E, is NP-hard. This result holds for belief networks that are allowed to contain extreme conditional probabilities—that is, conditional probabilities arbitrarily close to 0. Nevertheless, all previous approximation algorithms have failed to approximate efficiently many inferences, even for belief networks without extreme conditional probabilities.