Abstract
Scaling probabilistic models to large realistic problems and datasets is a key challenge in machine learning. Central to this effort is the development of tractable probabilistic models (TPMs): models where exact inference can be performed efficiently. This paper explores the theoretical boundaries between two major families of TPMs: Probabilistic Circuits (PCs) and Determinantal Point Processes (DPPs). We establish that while both are tractable, they are fundamentally distinct in their expressive power, with most DPPs requiring exponential size to be represented as PCs.
Introduction: The Expressivity-Tractability Trade-off
In probabilistic machine learning, there is a constant tension between expressivity (how complex a distribution a model can represent) and tractability (how fast we can compute answers to queries like marginals or MAP inference).
Two popular frameworks have emerged to address this:
- Probabilistic Circuits (PCs): These represent distributions as computational graphs (like Sum-Product Networks). They are flexible and excel at modeling positive dependencies.
- Determinantal Point Processes (DPPs): These use the machinery of linear algebra (determinants) to model "negative dependence"—situations where items in a set repulse each other to ensure diversity (e.g., in search results).
Until this work, it was unclear if these two families could be unified. Could a DPP be efficiently simulated by a PC to leverage the strengths of both? This paper tackles this unification problem through theoretical proofs and empirical study.
The Expressivity Gap
The authors prove that DPPs and PCs occupy largely different niches in the landscape of machine learning. A primary reason is the nature of the dependencies they model. PCs are naturally suited for positive dependence, whereas DPPs are the gold standard for negative dependence.
The Exponential Wall
The paper establishes rigorous lower bounds on the size of a PC required to represent a DPP. For "almost all" DPPs, any attempt to represent them as a Deterministic PC or a Probabilistic Sentential Decision Diagram (PSDD) results in a circuit of exponential size ($2^{n-1}$). This means they are not just slightly inefficient; they are fundamentally incompatible for large-scale problems.
Negative Parameter Necessity
A key insight is that representing a determinant—the heart of a DPP—within a circuit structure requires the use of negative parameters. This immediately disqualifies standard Sum-Product Networks (SPNs), which are typically restricted to non-negative weights to maintain probabilistic validity.
Bridging the Gap: Rank-1 Perturbations
Despite the general incompatibility, the authors identified a "sweet spot." They found that a specific subclass of DPPs—Rank-1 Perturbations (R1P) of diagonal matrices—can indeed be represented by polynomial-size PCs.
This discovery suggests a path forward for hybrid modeling. While we cannot unify the entire families, we can build tractable models that approximate complex DPPs using mixtures of these R1P-based circuits. In small-scale empirical tests, these mixtures significantly outperformed fully-factorized baselines in approximating general DPPs.
Conclusion
This research clarifies the landscape of tractable probabilistic modeling by proving that PCs and DPPs are fundamentally distinct. While the "exponential wall" prevents a total unification, the identification of the R1P bridge provides a new tool for researchers looking to incorporate diversity modeling into circuit-based frameworks. Future work remains to determine if decomposable PCs that allow negative parameters could potentially bridge this gap further.
Summary updated