Probabilistic Generating Circuits - Demystified

Zhang et al. (ICML 2021, PLMR 139, pp. 12447-1245) introduced probabilistic generating circuits (PGCs) as a probabilistic model to unify probabilistic circuits (PCs) and determinantal point processes (DPPs). At a first glance, PGCs store a distribution in a very different way, they compute the probability generating polynomial instead of the probability mass function and it seems that this is the main reason why PGCs are more powerful than PCs or DPPs. However, PGCs also allow for negative weights, whereas classical PCs assume that all weights are nonnegative. One of the main insights of our paper is that the negative weights are responsible for the power of PGCs and not the different representation. PGCs are PCs in disguise, in particular, we show how to transform any PGC into a PC with negative weights with only polynomial blowup. PGCs were defined by Zhang et al. only for binary random variables. As our second main result, we show that there is a good reason for this: we prove that PGCs for categorial variables with larger image size do not support tractable marginalization unless NP = P. On the other hand, we show that we can model categorial variables with larger image size as PC with negative weights computing setmultilinear polynomials. These allow for tractable marginalization. In this sense, PCs with negative weights strictly subsume PGCs. * Broadrick et al. [2024] independently obtain some of the results presented in this paper. In particular, they prove that probabilistic circuits and probabilistic generating circuits for binary variables are equivalent (our Theorem 8.1) as well as the hardness of marginalization for probabilistic generating circuits with at least four categories (our Theorem 7.1). These results were obtained independently of ours and were submitted to a conference around the same time as ours.