Sum of Squares Circuits

• URL: http://arxiv.org/abs/2408.11778v1
• Date: Wed, 21 Aug 2024 17:08:05 GMT
• Title: Sum of Squares Circuits
• Authors: Lorenzo Loconte, Stefan Mengel, Antonio Vergari,
• Abstract summary: Probabilistic circuits (PCs) offer a framework where this tractability-vs-expressiveness trade-off can be analyzed theoretically. We show that squared PCs encoding subtractive mixtures via negative parameters can be exponentially more expressive than monotonic PCs. We formalize a novel class of PCs -- sum of squares PCs -- that can be exponentially more expressive than both squared and monotonic PCs.
• Score: 8.323409122604893
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Designing expressive generative models that support exact and efficient inference is a core question in probabilistic ML. Probabilistic circuits (PCs) offer a framework where this tractability-vs-expressiveness trade-off can be analyzed theoretically. Recently, squared PCs encoding subtractive mixtures via negative parameters have emerged as tractable models that can be exponentially more expressive than monotonic PCs, i.e., PCs with positive parameters only. In this paper, we provide a more precise theoretical characterization of the expressiveness relationships among these models. First, we prove that squared PCs can be less expressive than monotonic ones. Second, we formalize a novel class of PCs -- sum of squares PCs -- that can be exponentially more expressive than both squared and monotonic PCs. Around sum of squares PCs, we build an expressiveness hierarchy that allows us to precisely unify and separate different tractable model classes such as Born Machines and PSD models, and other recently introduced tractable probabilistic models by using complex parameters. Finally, we empirically show the effectiveness of sum of squares circuits in performing distribution estimation.

Related papers

• Efficient Fairness-Performance Pareto Front Computation [51.558848491038916]
  We show that optimal fair representations possess several useful structural properties. We then show that these approxing problems can be solved efficiently via concave programming methods.
  arXiv  Detail & Related papers  (2024-09-26T08:46:48Z)
• Probabilistic Circuits with Constraints via Convex Optimization [2.6436521007616114]
  The proposed approach takes both a PC and constraints as inputs, and outputs a new PC that satisfies the constraints. Empirical evaluations indicate that the combination of constraints and PCs can have multiple use cases.
  arXiv  Detail & Related papers  (2024-03-19T19:55:38Z)
• Probabilistic Integral Circuits [11.112802758446344]
  We introduce a new language of computational graphs that extends PCs with integral units representing continuous LVs. In practice, we parameterise PICs with light-weight neural nets delivering an intractable hierarchical continuous mixture. We show that such PIC-approximating PCs systematically outperform PCs commonly learned via expectation-maximization or SGD.
  arXiv  Detail & Related papers  (2023-10-25T20:38:18Z)
• Continuous Mixtures of Tractable Probabilistic Models [10.667104977730304]
  Probabilistic models based on continuous latent spaces, such as variational autoencoders, can be understood as uncountable mixture models. Probabilistic circuits (PCs) can be understood as hierarchical discrete mixture models. In this paper, we investigate a hybrid approach, namely continuous mixtures of tractable models with a small latent dimension.
  arXiv  Detail & Related papers  (2022-09-21T18:18:32Z)
• Low-Rank Constraints for Fast Inference in Structured Models [110.38427965904266]
  This work demonstrates a simple approach to reduce the computational and memory complexity of a large class of structured models. Experiments with neural parameterized structured models for language modeling, polyphonic music modeling, unsupervised grammar induction, and video modeling show that our approach matches the accuracy of standard models at large state spaces.
  arXiv  Detail & Related papers  (2022-01-08T00:47:50Z)
• HyperSPNs: Compact and Expressive Probabilistic Circuits [89.897635970366]
  HyperSPNs is a new paradigm of generating the mixture weights of large PCs using a small-scale neural network. We show the merits of our regularization strategy on two state-of-the-art PC families introduced in recent literature.
  arXiv  Detail & Related papers  (2021-12-02T01:24:43Z)
• PSD Representations for Effective Probability Models [117.35298398434628]
  We show that a recently proposed class of positive semi-definite (PSD) models for non-negative functions is particularly suited to this end. We characterize both approximation and generalization capabilities of PSD models, showing that they enjoy strong theoretical guarantees. Our results open the way to applications of PSD models to density estimation, decision theory and inference.
  arXiv  Detail & Related papers  (2021-06-30T15:13:39Z)
• Probabilistic Generating Circuits [50.98473654244851]
  We propose probabilistic generating circuits (PGCs) for their efficient representation. PGCs are not just a theoretical framework that unifies vastly different existing models, but also show huge potential in modeling realistic data. We exhibit a simple class of PGCs that are not trivially subsumed by simple combinations of PCs and DPPs, and obtain competitive performance on a suite of density estimation benchmarks.
  arXiv  Detail & Related papers  (2021-02-19T07:06:53Z)
• Probabilistic Circuits for Variational Inference in Discrete Graphical Models [101.28528515775842]
  Inference in discrete graphical models with variational methods is difficult. Many sampling-based methods have been proposed for estimating Evidence Lower Bound (ELBO) We propose a new approach that leverages the tractability of probabilistic circuit models, such as Sum Product Networks (SPN) We show that selective-SPNs are suitable as an expressive variational distribution, and prove that when the log-density of the target model is aweighted the corresponding ELBO can be computed analytically.
  arXiv  Detail & Related papers  (2020-10-22T05:04:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.