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

Denis Deratani Maua, Cassio Polpo de Campos, Fabio Gagliardi Cozman

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Citations (Scopus)

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.
Original languageEnglish
Title of host publicationProceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)
PublisherInternational Joint Conferences on Artificial Intelligence
Pages889-895
Number of pages7
ISBN (Print)9781577357384
Publication statusPublished - 2015
Event24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina
Duration: 25 Jul 201531 Jul 2015

Conference

Conference24th International Joint Conference on Artificial Intelligence
CountryArgentina
CityBuenos Aires
Period25/07/201531/07/2015

Bibliographical note

Double blind peer-reviewed by multiple reviewers. Acc. rate 28%

Fingerprint

Dive into the research topics of 'The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages'. Together they form a unique fingerprint.

Cite this