The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages

Denis Deratani Mauá, Cassio P. de Campos, Fábio Gagliardi Cozman

Abstract

This paper investigates the computational complexity of Maximum A Posteriori (MAP) and Most Probable Explanation (MPE) inference in Bayesian Networks (BNs) where local conditional probabilities are defined via logical languages. Contrary to the traditional view that graph treewidth is the primary driver of complexity, the authors demonstrate that the choice of logical operators and the nature of evidence can significantly shift the tractability of inference. By analyzing deterministic logical formulas, the research shows that inference can remain tractable even in high-treewidth networks or become intractable in simple ones depending on the logical specification.

Introduction

In Bayesian Network (BN) theory, the "conventional wisdom" suggests that the difficulty of finding the most likely explanation for data depends primarily on the graph's treewidth—a measure of its "tree-likeness." Low treewidth typically implies polynomial-time inference, while high treewidth suggests intractability. However, many real-world models, such as the QMR-DT medical diagnostic tool, possess massive treewidths yet remain computationally solvable. This discrepancy arises from "local structure"—specific functional interactions (like Noisy-OR gates) that define how variables interact. This paper formalizes this phenomenon by shifting the focus from graph topology to the logical language used to specify local probability distributions.

Methods

The authors analyze two primary inference tasks: Most Probable Explanation (MPE), which finds the most likely state for all variables, and Maximum A Posteriori (MAP), which finds the most likely state for a subset of variables by marginalizing (summing out) the others. They define BNs where conditional probabilities are specified as deterministic logical formulas (e.g., $X \Leftrightarrow A \wedge B$).

To categorize the difficulty of these problems, the authors employ tools from computational complexity theory, specifically reductions from known hard problems. For instance, reductions from Vertex Cover are used to prove NP-completeness for MPE, while variants of the Satisfiability problem like EMAJ(3)SAT are used to establish $NP^{PP}$-completeness for MAP.

Figure 5: Reduction from a graph problem (left) to a Bayesian Network structure (right) to analyze complexity.

Key Insights and Ideas

The research reveals that the choice of logical operators is a catalyst for complexity jumps. While networks using only conjunction ($\wedge$) and positive evidence can be tractable, the introduction of disjunction ($\vee$) or negative evidence often pushes the problem into NP-complete territory. This is partly because negative evidence combined with conjunction can simulate disjunction via De Morgan's laws.

Figure 1: A Bayesian Network example where local distributions are specified through logical formulas, illustrating the interplay between graph structure and logic.

Furthermore, MAP inference is shown to be significantly harder than MPE. Because MAP requires marginalization, it frequently lands in the complexity class $NP^{PP}$, which is substantially higher than the NP-completeness typically associated with MPE.

Key Results

  • MPE Complexity: MPE is NP-complete when using only conjunction or only disjunction. However, it is tractable (in P) when restricted to conjunction with positive evidence or when using the exclusive-OR ($\oplus$) operator.
  • MAP Complexity: MAP is $NP^{PP}$-complete even when using only disjunction with positive evidence. It remains PP-hard even with no evidence in very simple languages.
  • Relational Models: In relational BNs, "Data Complexity" (fixed model, growing domain) is tractable for simple description logics but becomes NP-complete for more expressive ones.

Discussion and Future Work

This work proves that restricting the logical language can bypass the treewidth barrier, achieving tractable inference in complex networks. However, several areas remain open for exploration. The interplay between domain size and logical expressivity in relational models is still poorly understood. Additionally, while MAP with no evidence is proven PP-hard, its exact complexity class ($NP^{PP}$ vs. lower) is not yet pinned down. Future research should focus on developing practical algorithms and solvers that exploit these logical restrictions to enhance inference performance in real-world applications.

Summary updated

Abstract

We study the computational complexity of finding maximum a posteriori configurations in Bayesian networks whose probabilities are specified by logical formulas. This approach leads to a fine grained study in which local information such as contextsensitive independence and determinism can be considered. It also allows us to characterize more precisely the jump from tractability to NP-hardness and beyond, and to consider the complexity introduced by evidence alone.
BibTeX
@inproceedings{maua2015complexity,
  author = {Denis Deratani Mauá and Cassio P. de Campos and Fábio Gagliardi Cozman},
  title = {{The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2015},
}
Figure