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 talk, I will discuss a marginal MAP solver that relaxes such structural constraints and instead performs inference by iteratively transforming the circuit. Central to this approach is a pruning algorithm that removes parts of the PC that are irrelevant to the marginal MAP query, shrinking the PC while maintaining the correct solution. Using this pruning technique, we are able to iteratively tighten the lower and upper bounds for the marginal MAP query and arrive at the exact solution without performing any search.