Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

YooJung Choi, Tal Friedman, and Guy Van den Broeck.
In Proceedings of the 25th International Conference on Artificial Intelligence and Statistics (AISTATS), 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.

Citation

@inproceedings{ChoiAISTATS22,
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}
month     = {Mar},
year      = {2022},
}