The Inferential Complexity of Bayesian and Credal Networks

Cassio Polpo de Campos, Fábio Gagliardi CozmanIJCAI 2005 · OpenReview

Abstract

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).

Introduction

Probabilistic graphical models like Bayesian Networks (BNs) are powerful tools for reasoning under uncertainty, but they require precise numerical probabilities. In many real-world scenarios—such as group decision-making or vague expert knowledge—we only have intervals or sets of possible probabilities. Credal Networks (CNs) generalize BNs to handle this imprecision. While the complexity of BNs is well-documented, the computational cost of reasoning with CNs remained a "patchwork" of results. This paper addresses the gap by providing a comprehensive complexity analysis for various inference tasks across different network topologies.

Methodology

The authors employ theoretical complexity analysis, primarily using polynomial-time reductions from known hard problems in logic and set theory (such as MAX-3-SAT and versions of the Quantified Satisfiability problem, QSAT₂).

Graphical representation of a network structure used in the complexity proofs.

Key methodological contributions include:

  • Redefining Bounded Induced-Width (BIW): The authors allow the width to grow logarithmically with the network size, creating a more flexible class of tractable networks.
  • Defining New Problems: They introduce BN-MmAP (maximin a posteriori), a decision problem relevant to game theory where one seeks an instantiation that maximizes a minimum probability.
  • Distinguishing MPE vs. MPEe: They highlight a critical distinction in Credal networks between the Most Probable Explanation (MPE) without evidence and MPE with evidence (MPEe), showing they belong to entirely different complexity classes.

Results and Discussion

A recurring theme in the findings is the "One Step Up" Rule: moving from BNs to CNs typically increases complexity by one level in the polynomial hierarchy. For example, a problem that is NP-complete in a BN often becomes $\Sigma^P_2$-complete in a CN.

Complexity results for various inference problems in Bayesian and Credal networks across different topologies.

Key results from the analysis include:

  • The Evidence Gap: In standard Bayesian networks, finding the MPE is computationally similar whether or not you have observed evidence. In Credal networks, finding the MPE without evidence is polynomial in simple graphs, but adding evidence (MPEe) makes the problem $\Sigma^P_2$-complete.
  • Correcting the Record: The authors provide a new, rigorous proof that updating beliefs in a polytree Credal network (PT-CN-Pr) is NP-complete, correcting previously flawed arguments in the literature.
  • MmAP as a Bridge: The newly defined MmAP problem in Bayesian networks is shown to be as hard as MAP problems in Credal networks, strengthening the theoretical link between the two models.

Conclusion and Future Work

This work provides a definitive map of the computational landscape for Bayesian and Credal networks. While it establishes hardness results for many configurations, some completeness results for multiply-connected networks remain open. Future research will explore whether restricting networks to binary variables reduces complexity and focus on developing efficient approximation schemes for $\Sigma^P_2$-hard problems, which are currently intractable for exact inference in large-scale applications.

Summary updated

Abstract

This paper presents new results on the complexity of graph-theoretical models that represent probabilities (Bayesian networks) and that represent interval and set valued probabilities (credal networks). We define a new class of networks with bounded width, and introduce a new decision problem for Bayesian networks, the maximin a posteriori. We present new links between the Bayesian and credal networks, and present new results both for Bayesian networks (most probable explanation with observations, maximin a posteriori) and for credal networks (bounds on probabilities a posteriori, most probable explanation with and without observations, maximum a posteriori).
BibTeX
@inproceedings{campos2005inferential,
  author = {Cassio Polpo de Campos and Fábio Gagliardi Cozman},
  title = {{The Inferential Complexity of Bayesian and Credal Networks}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2005},
  url = {https://openreview.net/forum?id=HyPiQz_-B},
}
Figure