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

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

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

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

School of Electronics, Electrical Engineering and Computer Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

9 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 language	English
Title of host publication	Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)
Publisher	International Joint Conferences on Artificial Intelligence
Pages	889-895
Number of pages	7
ISBN (Print)	9781577357384
Publication status	Published - 2015
Event	24th International Joint Conference on Artificial Intelligence - Buenos Aires, Argentina Duration: 25 Jul 2015 → 31 Jul 2015

Conference

Conference	24th International Joint Conference on Artificial Intelligence
Country/Territory	Argentina
City	Buenos Aires
Period	25/07/2015 → 31/07/2015

Bibliographical note

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

Access to Document

http://ijcai.org/papers15/Abstracts/IJCAI15-130.html

Cite this

Maua, D. D., de Campos, C. P., & Cozman, F. G. (2015). The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages. In Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI) (pp. 889-895). International Joint Conferences on Artificial Intelligence . http://ijcai.org/papers15/Abstracts/IJCAI15-130.html

@inproceedings{fee5c92bb8254b12af90660d21de13b7,

title = "The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages",

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.",

author = "Maua, {Denis Deratani} and {de Campos}, {Cassio Polpo} and Cozman, {Fabio Gagliardi}",

note = "Double blind peer-reviewed by multiple reviewers. Acc. rate 28%; 24th International Joint Conference on Artificial Intelligence ; Conference date: 25-07-2015 Through 31-07-2015",

year = "2015",

language = "English",

isbn = "9781577357384",

pages = "889--895",

booktitle = "Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)",

publisher = "International Joint Conferences on Artificial Intelligence ",

}

Maua, DD, de Campos, CP & Cozman, FG 2015, The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages. in Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI). International Joint Conferences on Artificial Intelligence , pp. 889-895, 24th International Joint Conference on Artificial Intelligence, Buenos Aires, Argentina, 25/07/2015. <http://ijcai.org/papers15/Abstracts/IJCAI15-130.html>

The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages. / Maua, Denis Deratani; de Campos, Cassio Polpo; Cozman, Fabio Gagliardi.
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI). International Joint Conferences on Artificial Intelligence , 2015. p. 889-895.

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

TY - GEN

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

AU - Maua, Denis Deratani

AU - de Campos, Cassio Polpo

AU - Cozman, Fabio Gagliardi

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

PY - 2015

Y1 - 2015

N2 - 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.

AB - 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.

M3 - Conference contribution

SN - 9781577357384

SP - 889

EP - 895

BT - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence (IJCAI)

PB - International Joint Conferences on Artificial Intelligence

T2 - 24th International Joint Conference on Artificial Intelligence

Y2 - 25 July 2015 through 31 July 2015

ER -

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

Abstract

Conference

Bibliographical note

Access to Document

Fingerprint

Cite this