Almost No News on the Complexity of MAP in Bayesian Networks

Cassio P. de Campos
Proceedings of the 10th International Conference on Probabilistic Graphical Models, PMLR 138:149-160, 2020.

Abstract

This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.

Cite this Paper

BibTeX
@InProceedings{pmlr-v138-campos20a, title = {Almost No News on the Complexity of {MAP} in {B}ayesian Networks}, author = {de Campos, Cassio P.}, booktitle = {Proceedings of the 10th International Conference on Probabilistic Graphical Models}, pages = {149--160}, year = {2020}, editor = {Jaeger, Manfred and Nielsen, Thomas Dyhre}, volume = {138}, series = {Proceedings of Machine Learning Research}, month = {23--25 Sep}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v138/campos20a/campos20a.pdf}, url = {https://proceedings.mlr.press/v138/campos20a.html}, abstract = {This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.} }
Endnote
%0 Conference Paper %T Almost No News on the Complexity of MAP in Bayesian Networks %A Cassio P. de Campos %B Proceedings of the 10th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2020 %E Manfred Jaeger %E Thomas Dyhre Nielsen %F pmlr-v138-campos20a %I PMLR %P 149--160 %U https://proceedings.mlr.press/v138/campos20a.html %V 138 %X This article discusses the current state of the art in terms of computational complexity for the problem of finding the most probable configuration of a subset of variables in a multivariate domain modelled by probabilistic graphical models such as Markov networks (random fields) or Bayesian networks. It contains complexity proofs and an algorithm for the problem and shows empirical results for Boolean trees which may suggest tractability of the task in some special cases.
APA
de Campos, C.P.. (2020). Almost No News on the Complexity of MAP in Bayesian Networks. Proceedings of the 10th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 138:149-160 Available from https://proceedings.mlr.press/v138/campos20a.html.

Related Material