ML Anthology

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

Denis Deratani Mauá, Cassio P. de Campos, Fábio Gagliardi Cozman
IJCAI 2015 pp. 889-895
/ijcai/2015/maua2015ijcai-complexity/

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

PDF IJCAI Semantic Scholar

Cite

Text

Mauá et al. "The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages." International Joint Conference on Artificial Intelligence, 2015.

Markdown

[Mauá et al. "The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages." International Joint Conference on Artificial Intelligence, 2015.](https://mlanthology.org/ijcai/2015/maua2015ijcai-complexity/)

BibTeX

@inproceedings{maua2015ijcai-complexity,
  title     = {{The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages}},
  author    = {Mauá, Denis Deratani and de Campos, Cassio P. and Cozman, Fábio Gagliardi},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year      = {2015},
  pages     = {889-895},
  url       = {https://mlanthology.org/ijcai/2015/maua2015ijcai-complexity/}
}