Positive Semi-Definite Probabilistic Circuits

Abstract

The computation of probabilistic inference operations with models estimating probability distributions is crucial for applications requiring well-calibrated estimates of uncertainty, such as safety critical decision-making, but often becomes computationally intractable due to the model's formulation. Probabilistic circuits (PCs) are models that can guarantee tractability of these operations by virtue of their formulation as structurally constrained computational graphs. PCs encode complex probability distributions as a hierarchical set of non-negatively weighted summations and products of simpler tractable probability distributions. The non-negative weight constraint on summations ensures non-negativity of the probability distribution represented, however, is also known to hinder the expressiveness of PCs. This work proposes loosening this non-negativity constraint to a positive semi-definite (PSD) constraint, yielding a positive semi-definite parameterized PC (PSD-PC). This model can have negative weights and is hypothesized to be more expressive than PCs. PSD-PCs are shown to represent valid probability distributions and proven to retain tractability for probabilistic inference operations. A density estimation experiment conducted on simulated and toy data sets showed empirical evidence for PSD-PCs being more expressive-efficient than PCs, possibly due to increased capability to model negative dependencies. PSD-PCs are, however, also subject to a stricter constraint on their graphical structure than PCs and are more challenging to optimize.