Speeding up approximate MAP by applying domain knowledge about relevant variables

Johan Kwisthout
Proceedings of The 11th International Conference on Probabilistic Graphical Models, PMLR 186:229-240, 2022.

Abstract

The MAP problem in Bayesian networks is notoriously intractable, even when approximated. In an earlier paper we introduced the Most Frugal Explanation heuristic approach to solving MAP, by partitioning the set of intermediate variables (neither observed nor part of the MAP variables) into a set of relevant variables, which are marginalized out, and irrelevant variables, which will be assigned a sampled value from their domain. In this study we explore whether knowledge about which variables are relevant for a particular query (i.e., domain knowledge) speeds up computation sufficiently to beat both exact MAP as well as approximate MAP while giving reasonably accurate results. Our results are inconclusive, but also show that this probably depends on the specifics of the MAP query, most prominently the number of MAP variables.

Cite this Paper

BibTeX
@InProceedings{pmlr-v186-kwisthout22a, title = {Speeding up approximate {MAP} by applying domain knowledge about relevant variables}, author = {Kwisthout, Johan}, booktitle = {Proceedings of The 11th International Conference on Probabilistic Graphical Models}, pages = {229--240}, year = {2022}, editor = {Salmerón, Antonio and Rumı́, Rafael}, volume = {186}, series = {Proceedings of Machine Learning Research}, month = {05--07 Oct}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v186/kwisthout22a/kwisthout22a.pdf}, url = {https://proceedings.mlr.press/v186/kwisthout22a.html}, abstract = {The MAP problem in Bayesian networks is notoriously intractable, even when approximated. In an earlier paper we introduced the Most Frugal Explanation heuristic approach to solving MAP, by partitioning the set of intermediate variables (neither observed nor part of the MAP variables) into a set of relevant variables, which are marginalized out, and irrelevant variables, which will be assigned a sampled value from their domain. In this study we explore whether knowledge about which variables are relevant for a particular query (i.e., domain knowledge) speeds up computation sufficiently to beat both exact MAP as well as approximate MAP while giving reasonably accurate results. Our results are inconclusive, but also show that this probably depends on the specifics of the MAP query, most prominently the number of MAP variables.} }
Endnote
%0 Conference Paper %T Speeding up approximate MAP by applying domain knowledge about relevant variables %A Johan Kwisthout %B Proceedings of The 11th International Conference on Probabilistic Graphical Models %C Proceedings of Machine Learning Research %D 2022 %E Antonio Salmerón %E Rafael Rumı́ %F pmlr-v186-kwisthout22a %I PMLR %P 229--240 %U https://proceedings.mlr.press/v186/kwisthout22a.html %V 186 %X The MAP problem in Bayesian networks is notoriously intractable, even when approximated. In an earlier paper we introduced the Most Frugal Explanation heuristic approach to solving MAP, by partitioning the set of intermediate variables (neither observed nor part of the MAP variables) into a set of relevant variables, which are marginalized out, and irrelevant variables, which will be assigned a sampled value from their domain. In this study we explore whether knowledge about which variables are relevant for a particular query (i.e., domain knowledge) speeds up computation sufficiently to beat both exact MAP as well as approximate MAP while giving reasonably accurate results. Our results are inconclusive, but also show that this probably depends on the specifics of the MAP query, most prominently the number of MAP variables.
APA
Kwisthout, J.. (2022). Speeding up approximate MAP by applying domain knowledge about relevant variables. Proceedings of The 11th International Conference on Probabilistic Graphical Models, in Proceedings of Machine Learning Research 186:229-240 Available from https://proceedings.mlr.press/v186/kwisthout22a.html.

Related Material