Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

Yoojung Choi, Tal Friedman, Guy Van Den Broeck
Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, PMLR 151:10196-10208, 2022.

Abstract

Probabilistic circuits (PCs) are a class of tractable probabilistic models that allow efficient, often linear-time, inference of queries such as marginals and most probable explanations (MPE). However, marginal MAP, which is central to many decision-making problems, remains a hard query for PCs unless they satisfy highly restrictive structural constraints. In this paper, we develop a pruning algorithm that removes parts of the PC that are irrelevant to a marginal MAP query, shrinking the PC while maintaining the correct solution. This pruning technique is so effective that we are able to build a marginal MAP solver based solely on iteratively transforming the circuit—no search is required. We empirically demonstrate the efficacy of our approach on real-world datasets.

Cite this Paper

BibTeX
@InProceedings{pmlr-v151-choi22b, title = { Solving Marginal MAP Exactly by Probabilistic Circuit Transformations }, author = {Choi, Yoojung and Friedman, Tal and Van Den Broeck, Guy}, booktitle = {Proceedings of The 25th International Conference on Artificial Intelligence and Statistics}, pages = {10196--10208}, year = {2022}, editor = {Camps-Valls, Gustau and Ruiz, Francisco J. R. and Valera, Isabel}, volume = {151}, series = {Proceedings of Machine Learning Research}, month = {28--30 Mar}, publisher = {PMLR}, pdf = {https://proceedings.mlr.press/v151/choi22b/choi22b.pdf}, url = {https://proceedings.mlr.press/v151/choi22b.html}, abstract = { Probabilistic circuits (PCs) are a class of tractable probabilistic models that allow efficient, often linear-time, inference of queries such as marginals and most probable explanations (MPE). However, marginal MAP, which is central to many decision-making problems, remains a hard query for PCs unless they satisfy highly restrictive structural constraints. In this paper, we develop a pruning algorithm that removes parts of the PC that are irrelevant to a marginal MAP query, shrinking the PC while maintaining the correct solution. This pruning technique is so effective that we are able to build a marginal MAP solver based solely on iteratively transforming the circuit—no search is required. We empirically demonstrate the efficacy of our approach on real-world datasets. } }
Endnote
%0 Conference Paper %T Solving Marginal MAP Exactly by Probabilistic Circuit Transformations %A Yoojung Choi %A Tal Friedman %A Guy Van Den Broeck %B Proceedings of The 25th International Conference on Artificial Intelligence and Statistics %C Proceedings of Machine Learning Research %D 2022 %E Gustau Camps-Valls %E Francisco J. R. Ruiz %E Isabel Valera %F pmlr-v151-choi22b %I PMLR %P 10196--10208 %U https://proceedings.mlr.press/v151/choi22b.html %V 151 %X Probabilistic circuits (PCs) are a class of tractable probabilistic models that allow efficient, often linear-time, inference of queries such as marginals and most probable explanations (MPE). However, marginal MAP, which is central to many decision-making problems, remains a hard query for PCs unless they satisfy highly restrictive structural constraints. In this paper, we develop a pruning algorithm that removes parts of the PC that are irrelevant to a marginal MAP query, shrinking the PC while maintaining the correct solution. This pruning technique is so effective that we are able to build a marginal MAP solver based solely on iteratively transforming the circuit—no search is required. We empirically demonstrate the efficacy of our approach on real-world datasets.
APA
Choi, Y., Friedman, T. & Van Den Broeck, G.. (2022). Solving Marginal MAP Exactly by Probabilistic Circuit Transformations . Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, in Proceedings of Machine Learning Research 151:10196-10208 Available from https://proceedings.mlr.press/v151/choi22b.html.

Related Material