Solving Marginal MAP Exactly by Probabilistic Circuit Transformations
This addresses a bottleneck in decision-making problems for users of probabilistic models, though it is incremental as it builds on existing circuit methods.
The paper tackled the problem of marginal MAP inference in probabilistic circuits, which is computationally hard, by developing a pruning algorithm that removes irrelevant parts of the circuit to shrink it while preserving the correct solution, enabling an exact solver without search and demonstrating efficacy on real-world datasets.
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.