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

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

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 Polpo 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},
}

Loading related content...

Figure