New Complexity Results for MAP in Bayesian Networks
Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence. Pages 2100-2105.
Abstract
This paper presents new results for the (partial) maximum a posteriori (MAP) problem in Bayesian networks, which is the problem of querying the most probable state configuration of some of the network variables given evidence. It is demonstrated that the problem remains hard even in networks with very simple topology, such as binary polytrees and simple trees (including the Naive Bayes structure), which extends previous complexity results. Furthermore, a Fully Polynomial Time Approximation Scheme for MAP in networks with bounded treewidth and bounded number of states per variable is developed. Approximation schemes were thought to be impossible, but here it is shown otherwise under the assumptions just mentioned, which are adopted in most applications.
@inproceedings{ijcai2011p351,
title = {New Complexity Results for MAP in Bayesian Networks},
author = {de Campos, Cassio Polpo},
booktitle = {Proceedings of the Twenty-Second International Joint Conference on
Artificial Intelligence, {IJCAI-11}},
publisher = {AAAI Press/International Joint Conferences on Artificial Intelligence},
editor = {Toby Walsh},
pages = {2100--2105},
year = {2011},
month = {7},
doi = {10.5591/978-1-57735-516-8/IJCAI11-351},
url = {https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351},
}
TY - CPAPER TI - New Complexity Results for MAP in Bayesian Networks AU - de Campos, Cassio Polpo T2 - Proceedings of the Twenty-Second International Joint Conference on Artificial Intelligence, IJCAI-11 PB - AAAI Press/International Joint Conferences on Artificial Intelligence PY - 2011 SP - 2100 EP - 2105 DO - 10.5591/978-1-57735-516-8/IJCAI11-351 UR - https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351 ER -Copied
Machine-readable versions of this paper, for tools and AI agents:
