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.
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.
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