On the Hardness of Probabilistic Inference Relaxations

Supratik Chakraborty, Kuldeep S. Meel, Moshe Y. Vardi

Abstract

Probabilistic inference is a fundamental task in artificial intelligence, yet its exact computation is known to be #P-hard. To circumvent this complexity, researchers frequently employ relaxations—approximations that trade exactness for perceived computational efficiency. This paper rigorously examines the theoretical foundations of these relaxations, challenging the assumption that they are inherently easier to compute. Through computational complexity analysis, the authors demonstrate that many common additive and threshold relaxations remain as difficult as the original problem. However, they identify a "sweet spot" in multiplicative approximations and introduce $\alpha$-PMT, a new relaxation that is provably efficient, providing a theoretical bridge between hard inference problems and practical SAT-based solvers.

Introduction

Calculating the likelihood of an event given evidence—probabilistic inference—underpins applications ranging from medical diagnostics to autonomous navigation. Because exact inference is #P-hard, the field has largely pivoted toward "relaxations." These methods aim to find an answer that is "close enough," such as a value within a certain error bound or a binary decision based on a probability threshold.

While these approximations are often assumed to be more tractable than exact counting, this paper asks a critical question: Do these relaxations actually reduce the computational complexity of the problem, or are we merely benefiting from specific benchmark structures? By applying the tools of complexity theory, the authors analyze the hardness of three primary relaxation categories: additive, multiplicative, and thresholding.

The Complexity of Common Relaxations

1. Additive Relaxations (AAMC)

Additive-Approximate Model Counting (AAMC) seeks to find a count within a fixed range (e.g., $\pm \epsilon$). A common intuition suggests that as the error tolerance $\epsilon$ increases, the problem should become easier. The authors debunk this premise, proving that AAMC remains #P-complete even when the error bound is exponentially large (specifically, for any error $\epsilon \le 2^{n/2 - 2}$). This suggests that simply allowing for a large margin of error does not provide a computational shortcut in the worst case.

2. Threshold Relaxations (PMT)

Probabilistic Model Thresholding (PMT) involves determining whether a probability exceeds a specific threshold. This is a common task in decision-making and hypothesis testing. Surprisingly, the paper proves that PMT is even harder than exact counting in some respects, showing that the entire Polynomial Hierarchy ($PH$) is contained within $BPP^{PMT}$. In simpler terms, if one could solve threshold relaxations efficiently, they could solve every problem in the $PH$, a scenario considered highly unlikely in complexity theory. This places PMT beyond the reach of standard efficient algorithms.

3. Multiplicative Relaxations (PACMC)

Probably Approximately Correct Model Counting (PACMC) uses a multiplicative error (e.g., $1 \pm \rho$) and a confidence bound. The authors identify this as a rare "sweet spot." Unlike additive or threshold relaxations, PACMC can be solved using a polynomial number of calls to an NP-oracle (such as a SAT solver), placing it in the complexity class $BPP^{NP}$. This explains why multiplicative approximations have seen more success in developing rigorous, scalable algorithms.

Introducing $\alpha$-PMT: The Power of the Gap

Recognizing the hardness of sharp thresholding, the authors propose a new relaxation called $\alpha$-Probabilistic Model Thresholding ($\alpha$-PMT). The core innovation is the introduction of a "gap" between high and low thresholds. Instead of a single point of failure, the algorithm is allowed to be uncertain if the true probability falls within a specific range defined by $\alpha$.

For $\alpha < 1/4$, the authors prove that $\alpha$-PMT is in $BPP^{NP}$. They provide an algorithm that solves this problem using only $O(\log(1/\delta))$ calls to an NP-oracle. This effectively moves the problem from being "impossibly hard" to being solvable with modern SAT-solving technology, making it a viable candidate for real-world decision-making tasks.

Conclusion and Future Directions

This research highlights a significant discrepancy between empirical heuristics and theoretical reality. Many relaxations used in practice do not actually simplify the underlying computational problem in a worst-case sense. The authors argue that the community should shift its focus toward relaxations like PACMC and $\alpha$-PMT, which are grounded in rigorous complexity-theoretic arguments.

While these results focus on worst-case bounds, the authors acknowledge that real-world data often possesses hidden structures that allow heuristics to perform well. Future work is needed to reconcile these theoretical limits with observed performance, potentially by investigating the specific properties of datasets that allow "hard" problems to be solved in practice. For now, $\alpha$-PMT stands as a provably efficient alternative for those seeking reliable probabilistic inference.

Summary updated

Abstract

A promising approach to probabilistic inference that has attracted recent attention exploits its reduction to a set of model counting queries. Since probabilistic inference and model counting are #P-hard, various relaxations are used in practice, with the hope that these relaxations allow efficient computation while also providing rigorous approximation guarantees. In this paper, we show that contrary to common belief, several relaxations used for model counting and its applications (including probablistic inference) do not really lead to computational efficiency in a complexity theoretic sense. Our arguments proceed by showing the corresponding relaxed notions of counting to be computationally hard. We argue that approximate counting with multiplicative tolerance and probabilistic guarantees of correctness is the only class of relaxations that provably simplifies the problem, given access to an NP-oracle. Finally, we show that for applications that compare probability estimates with a threshold, a new notion of relaxation with gaps between low and high thresholds can be used. This new relaxation allows efficient decision making in practice, given access to an NP-oracle, while also bounding the approximation error. Erratum: This research is supported in part by the National Research Foundation Singapore under its AI Singapore Programme (Award Number: [AISG-RP-2018-005])
BibTeX
@inproceedings{chakraborty2019hardness,
  author = {Supratik Chakraborty and Kuldeep S. Meel and Moshe Y. Vardi},
  title = {{On the Hardness of Probabilistic Inference Relaxations}},
  booktitle = {AAAI Conference on Artificial Intelligence},
  year = {2019},
  doi = {10.1609/aaai.v33i01.33017785},
}
Figure