The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages
Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence. Main Track. Pages 889-894.
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.
Denis Deratani Mauá, Cassio Polpo de Campos, and Fabio Gagliardi Cozman. 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-15. IJCAI, 889–894. https://ijcai.org/proceedings/2015/130
Mauá, 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-15 (pp. 889–894). IJCAI. https://ijcai.org/proceedings/2015/130
@inproceedings{ijcai2015p130,
title = {The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages},
author = {Mauá, Denis Deratani and de Campos, Cassio Polpo and Cozman, Fabio Gagliardi},
booktitle = {Proceedings of the Twenty-Fourth International Joint Conference on
Artificial Intelligence, {IJCAI-15}},
publisher = {International Joint Conferences on Artificial Intelligence},
editor = {Qiang Yang and Michael Wooldridge},
pages = {889--894},
year = {2015},
month = {7},
note = {Main Track},
url = {https://ijcai.org/proceedings/2015/130},
}
TY - CPAPER TI - The Complexity of MAP Inference in Bayesian Networks Specified Through Logical Languages AU - Mauá, Denis Deratani AU - de Campos, Cassio Polpo AU - Cozman, Fabio Gagliardi T2 - Proceedings of the Twenty-Fourth International Joint Conference on Artificial Intelligence, IJCAI-15 PB - International Joint Conferences on Artificial Intelligence PY - 2015 SP - 889 EP - 894 UR - https://ijcai.org/proceedings/2015/130 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
