The computational complexity of probabilistic inference using bayesian belief networks

TLDR

Bayesian belief networks offer an efficient representation of probabilistic dependencies, yet while efficient inference exists for special classes, general belief networks remain computationally challenging. The study argues that research should shift from pursuing a universal efficient inference algorithm toward designing efficient special‑case, average‑case, and approximation methods. Probabilistic inference using belief networks is NP‑hard, implying that an exact efficient algorithm for all classes is unlikely.

Abstract

Bayesian belief networks provide a natural, efficient method for representing probabilistic dependencies among a set of variables. For these reasons, numerous researchers are exploring the use of belief networks as a knowledge representation in artificial intelligence. Algorithms have been developed previously for efficient probabilistic inference using special classes of belief networks. More general classes of belief networks, however, have eluded efforts to develop efficient inference algorithms. We show that probabilistic inference using belief networks is NP-hard. Therefore, it seems unlikely that an exact algorithm can be developed to perform probabilistic inference efficiently over all classes of belief networks. This result suggests that research should be directed away from the search for a general, efficient probabilistic inference algorithm, and toward the design of efficient special-case, average-case, and approximation algorithms.