On the Relationship Between Probabilistic Circuits and Determinantal Point Processes

Honghua Zhang, Steven Holtzen, Guy Van den Broeck

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 whose structure guarantees efficient probabilistic inference algorithms. The current landscape of TPMs is fragmented: there exist various kinds of TPMs with different strengths and weaknesses. Two of the most prominent classes of TPMs are determinantal point processes (DPPs) and probabilistic circuits (PCs). This paper provides the first systematic study of their relationship. We propose a unified analysis and shared language for discussing DPPs and PCs. Then we establish theoretical barriers for the unification of these two families, and prove that there are cases where DPPs have no compact representation as a class of PCs. We close with a perspective on the central problem of unifying these tractable models.

Introduction

In the field of machine learning, researchers often navigate a fundamental trade-off between model expressivity and computational tractability. Tractable Probabilistic Models (TPMs) are designed to bypass this trade-off by guaranteeing efficient inference for tasks such as marginalization or maximum a posteriori (MAP) estimation. However, the TPM landscape remains fragmented between two dominant paradigms: Determinantal Point Processes (DPPs), which excel at modeling diversity and negative dependence, and Probabilistic Circuits (PCs), which represent distributions as computational graphs of sums and products.

This paper, presented at UAI 2020, investigates whether these two popular frameworks can be unified. Through rigorous theoretical analysis, the authors establish "no-go" theorems demonstrating that PCs and DPPs are fundamentally distinct in their expressive power, with most DPPs lacking compact representations within standard PC classes.

The Fragmented Landscape of TPMs

Until this study, it was unclear if the mathematical elegance of DPPs (defined via kernels and determinants) could be fully captured by the structural flexibility of PCs. While both are considered "tractable," they occupy different niches in probabilistic modeling.

The fragmented landscape of Tractable Probabilistic Models (TPMs), showing the distinct domains of Probabilistic Circuits (PCs) and Determinantal Point Processes (DPPs).

DPPs are particularly effective at ensuring subsets of items are non-redundant, a property known as negative dependence. Conversely, standard PCs are often built on principles of positive dependence or factorization. The authors' systematic study aims to bridge this gap by translating DPPs into the language of random variables used in the PC community.

Methodology and Theoretical Barriers

The authors employ several rigorous techniques to establish lower bounds on circuit size:

  1. Algebraic Independence: Using the concept of algebraically independent numbers, they prove that the conditional distributions of a DPP are often too numerous and distinct to be captured by a small Probabilistic Sentential Decision Diagram (PSDD).
  2. Combinatorial Proofs: By analyzing the uniform distribution over spanning trees—a classic DPP—they demonstrate that any Sum-Product Network (SPN) representing it must be exponentially large.
  3. Symbolic Kernels: The introduction of symbolic kernels reveals that computing a determinant (the core of a DPP) inherently requires negative parameters, which violates the non-negativity constraints of many standard PC types.

Key Insights: The Necessity of Negative Parameters

A critical finding of the research is the "Negative Parameter Necessity." Standard PCs, such as SPNs, typically use non-negative weights to ensure valid probability distributions. However, a determinant is a sum of products that includes subtractions. Consequently, any PC attempting to represent a DPP must utilize negative parameters, which can compromise the tractability of certain circuit operations.

A Probabilistic Circuit (PC) with negative weights representing a Determinantal Point Process (DPP) defined by kernel L.

Despite these barriers, the authors identified a specific subclass called Rank-1 Perturbation (R1P) L-ensembles. These models can be represented by polynomial-size decomposable circuits, suggesting that while a total unification is impossible, there are specific "islands" of overlap where the two families meet.

Key Results and "No-Go" Theorems

The paper establishes three major negative results that define the limits of unification:

  • Exponential Lower Bounds: For a general DPP over $n$ variables, a deterministic PC requires at least $2^{n-2}$ parameters, making exact representation infeasible for even moderately sized problems.
  • PSDD Limitations: The authors prove that with probability 1, a randomly sampled DPP cannot be represented by a polynomial-size PSDD.
  • Approximation Potential: While exact representation is difficult, small-scale experiments showed that mixtures of R1P circuits approximated general DPPs significantly better than standard fully-factorized models.

Conclusion

This work concludes that Probabilistic Circuits and Determinantal Point Processes are fundamentally different tools. The "no-go" theorems established here suggest that rather than forcing one model into the structure of the other, future research should focus on developing entirely new hybrid models. While exact unification is theoretically barred, the exploration of approximate representations and the further development of R1P mixtures remain promising avenues for the field of tractable probabilistic modeling.

Summary updated

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 whose structure guarantees efficient probabilistic inference algorithms. The current landscape of TPMs is fragmented: there exist various kinds of TPMs with different strengths and weaknesses. Two of the most prominent classes of TPMs are determinantal point processes (DPPs) and probabilistic circuits (PCs). This paper provides the first systematic study of their relationship. We propose a unified analysis and shared language for discussing DPPs and PCs. Then we establish theoretical barriers for the unification of these two families, and prove that there are cases where DPPs have no compact representation as a class of PCs. We close with a perspective on the central problem of unifying these tractable models.
BibTeX
@inproceedings{zhang2020relationship,
  author = {Honghua Zhang and Steven Holtzen and Guy Van den Broeck},
  title = {{On the Relationship Between Probabilistic Circuits and Determinantal Point Processes}},
  booktitle = {Conference on Uncertainty in Artificial Intelligence},
  year = {2020},
  url = {https://openreview.net/forum?id=oEyqbOaOL4N},
}

Loading related content...

Figure