Almost No News on the Complexity of MAP in Bayesian Networks

Cassio P. de CamposPGM 2020 · OpenReview

Abstract

This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.

Introduction

In probabilistic graphical models, identifying the most likely state of variables is a fundamental task. Two primary variants exist: Most Probable Explanation (MPE), which seeks the most likely assignment for all unknown variables, and Maximum a Posteriori (MAP), which focuses on a specific subset. MAP is significantly more complex because it requires marginalizing (summing out) nuisance variables before maximizing. While MAP is known to be hard in general, its complexity in highly restricted structures like trees has remained a subject of debate.

Theoretical Landscape and Corrections

Cassio P. de Campos’s work tightens the complexity bounds for MAP, particularly in simple graph structures. A major contribution is the correction of previous literature regarding MPE with evidence (MPEE). The paper reclassifies MPEE as belonging to $PP^{NP[b]}$, a class involving probabilistic polynomial-time machines with limited NP oracle access.

Furthermore, the paper introduces MINAP, the problem of finding the least probable configuration. While maximizing probability in Boolean trees remains an open question, the author proves that minimizing it is definitively NP-complete.

Methodology: Reductions and Algorithms

To establish hardness, the author utilizes theoretical reductions from the Partition Problem. By constructing specific Bayesian network structures where the joint probability peaks only upon a valid partition, the math problem is mapped onto BN inference.

A Bayesian network structure used in complexity reductions.

The paper also introduces MAPinTree, an algorithm designed for tree structures. It leverages variable elimination combined with geometric techniques like Pareto-pruning and convex hulls to manage the candidate solution space during tree traversal.

Key Results

The research provides several definitive complexity classifications for MAP and its variants under different constraints.

Summary of complexity results for MAP and related problems.

Significant findings include:

  • Theorem 7: Decision-MAP is NP-hard even in trees with a maximum of 3 states per variable ($z=3$) and treewidth 1 ($w=1$).
  • Theorem 9: Decision-MINAP is NP-complete in Boolean trees ($z=2, w=1$).
  • Empirical Observations: In practice, the MAP algorithm demonstrated stability as tree size increased, whereas MINAP exhibited exponential growth. This suggests that while formal proof is lacking, MAP in Boolean trees may be more tractable than its minimization counterpart.

Conclusion

Despite these advancements, the "Boolean MAP" problem—determining if MAP in trees with two-state variables is NP-hard or polynomial—remains the field's "unreachable" goal. The empirical success of MAPinTree on Boolean structures provides a promising direction for future algorithmic development.

Summary updated

Abstract

This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.
BibTeX
@inproceedings{campos2020almost,
  author = {Cassio P. de Campos},
  title = {{Almost No News on the Complexity of MAP in Bayesian Networks}},
  booktitle = {PGM},
  year = {2020},
  url = {https://openreview.net/forum?id=tro2AwrvCR},
}
Figure