Solving Marginal MAP Exactly by Probabilistic Circuit Transformations

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},
}