New complexity results for MAP in Bayesian networks

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

28 Citaties (Scopus)

Uittreksel

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.

Originele taal-2Engels
TitelIJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence
UitgeverijAAAI Press
Pagina's2100-2106
Aantal pagina's7
ISBN van geprinte versie9781577355120
DOI's
StatusGepubliceerd - 1 dec 2011
Extern gepubliceerdJa
Evenement22nd International Joint Conference on Artificial Intelligence, IJCAI 2011 - Barcelona, Catalonia, Spanje
Duur: 16 jul 201122 jul 2011

Congres

Congres22nd International Joint Conference on Artificial Intelligence, IJCAI 2011
LandSpanje
StadBarcelona, Catalonia
Periode16/07/1122/07/11

Vingerafdruk

Bayesian networks
Topology
Polynomials

Bibliografische nota

(oral presentation, double-blind peer reviewed by >3 reviewers)

Citeer dit

de Campos, C. P. (2011). New complexity results for MAP in Bayesian networks. In IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence (blz. 2100-2106). AAAI Press. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351
de Campos, Cassio P. / New complexity results for MAP in Bayesian networks. IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence. AAAI Press, 2011. blz. 2100-2106
@inproceedings{1605f6e30a6f46e9bc698e3e727282e4,
title = "New complexity results for MAP in Bayesian networks",
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.",
author = "{de Campos}, {Cassio P.}",
note = "(oral presentation, double-blind peer reviewed by >3 reviewers)",
year = "2011",
month = "12",
day = "1",
doi = "10.5591/978-1-57735-516-8/IJCAI11-351",
language = "English",
isbn = "9781577355120",
pages = "2100--2106",
booktitle = "IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence",
publisher = "AAAI Press",

}

de Campos, CP 2011, New complexity results for MAP in Bayesian networks. in IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence. AAAI Press, blz. 2100-2106, Barcelona, Catalonia, Spanje, 16/07/11. https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351

New complexity results for MAP in Bayesian networks. / de Campos, Cassio P.

IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence. AAAI Press, 2011. blz. 2100-2106.

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

TY - GEN

T1 - New complexity results for MAP in Bayesian networks

AU - de Campos, Cassio P.

N1 - (oral presentation, double-blind peer reviewed by >3 reviewers)

PY - 2011/12/1

Y1 - 2011/12/1

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

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

UR - http://www.scopus.com/inward/record.url?scp=84867132452&partnerID=8YFLogxK

U2 - 10.5591/978-1-57735-516-8/IJCAI11-351

DO - 10.5591/978-1-57735-516-8/IJCAI11-351

M3 - Conference contribution

SN - 9781577355120

SP - 2100

EP - 2106

BT - IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence

PB - AAAI Press

ER -

de Campos CP. New complexity results for MAP in Bayesian networks. In IJCAI 2011 - 22nd International Joint Conference on Artificial Intelligence. AAAI Press. 2011. blz. 2100-2106 https://doi.org/10.5591/978-1-57735-516-8/IJCAI11-351