On the Relationship Between Monotone and Squared Probabilistic Circuits

• URL: http://arxiv.org/abs/2408.00876v1
• Date: Thu, 1 Aug 2024 18:56:08 GMT
• Title: On the Relationship Between Monotone and Squared Probabilistic Circuits
• Authors: Benjie Wang, Guy Van den Broeck,
• Abstract summary: InceptionPCs is a novel type of circuit that naturally encompasses both monotone circuits and squared circuits as special cases. Empirically, we validate that InceptionPCs can outperform both monotone and squared circuits on image datasets.
• Score: 32.42702089668762
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Probabilistic circuits are a unifying representation of functions as computation graphs of weighted sums and products. Their primary application is in probabilistic modeling, where circuits with non-negative weights (monotone circuits) can be used to represent and learn density/mass functions, with tractable marginal inference. Recently, it was proposed to instead represent densities as the square of the circuit function (squared circuits); this allows the use of negative weights while retaining tractability, and can be exponentially more compact than monotone circuits. Unfortunately, we show the reverse also holds, meaning that monotone circuits and squared circuits are incomparable in general. This raises the question of whether we can reconcile, and indeed improve upon the two modeling approaches. We answer in the positive by proposing InceptionPCs, a novel type of circuit that naturally encompasses both monotone circuits and squared circuits as special cases, and employs complex parameters. Empirically, we validate that InceptionPCs can outperform both monotone and squared circuits on image datasets.

Related papers

• Position-aware Automatic Circuit Discovery [59.64762573617173]
  We identify a gap in existing circuit discovery methods, treating model components as equally relevant across input positions. We propose two improvements to incorporate positionality into circuits, even on tasks containing variable-length examples. Our approach enables fully automated discovery of position-sensitive circuits, yielding better trade-offs between circuit size and faithfulness compared to prior work.
  arXiv  Detail & Related papers  (2025-02-07T00:18:20Z)
• On Faster Marginalization with Squared Circuits via Orthonormalization [5.211074429497916]
  We show how to parameterize squared circuits to ensure they encode already normalized distributions. We then use this parameterization to devise an algorithm to compute any marginal of squared circuits that is more efficient than a previously known one.
  arXiv  Detail & Related papers  (2024-12-10T19:37:03Z)
• Sum of Squares Circuits [8.323409122604893]
  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.
  arXiv  Detail & Related papers  (2024-08-21T17:08:05Z)
• Finding Transformer Circuits with Edge Pruning [71.12127707678961]
  We propose Edge Pruning as an effective and scalable solution to automated circuit discovery. Our method finds circuits in GPT-2 that use less than half the number of edges compared to circuits found by previous methods. Thanks to its efficiency, we scale Edge Pruning to CodeLlama-13B, a model over 100x the scale that prior methods operate on.
  arXiv  Detail & Related papers  (2024-06-24T16:40:54Z)
• A Circuit Complexity Formulation of Algorithmic Information Theory [1.5483078145498086]
  Inspired by Solomonoffs theory of inductive inference, we propose a prior based on circuit complexity. We argue that an inductive bias towards simple explanations as measured by circuit complexity is appropriate for this problem.
  arXiv  Detail & Related papers  (2023-06-25T01:30:37Z)
• Dual unitary circuits in random geometries [0.0]
  We show that regularity of the lattice circuit is not crucial for exact solvability. We consider a circuit where random 2-qubit dual unitary gates sit at intersections of random arrangements straight lines in two dimensions.
  arXiv  Detail & Related papers  (2022-06-20T09:11:43Z)
• Random quantum circuits anti-concentrate in log depth [118.18170052022323]
  We study the number of gates needed for the distribution over measurement outcomes for typical circuit instances to be anti-concentrated. Our definition of anti-concentration is that the expected collision probability is only a constant factor larger than if the distribution were uniform. In both the case where the gates are nearest-neighbor on a 1D ring and the case where gates are long-range, we show $O(n log(n)) gates are also sufficient.
  arXiv  Detail & Related papers  (2020-11-24T18:44:57Z)
• Free Mode Removal and Mode Decoupling for Simulating General Superconducting Quantum Circuits [4.568911586155097]
  We consider and solve two issues involved in simulating general superconducting circuits. One is the handling of free modes in the circuit, that is, circuit modes with no potential term in the Hamiltonian. The other is the challenge of simulating strongly coupled multimode circuits.
  arXiv  Detail & Related papers  (2020-11-20T18:59:29Z)
• Hardware-Encoding Grid States in a Non-Reciprocal Superconducting Circuit [62.997667081978825]
  We present a circuit design composed of a non-reciprocal device and Josephson junctions whose ground space is doubly degenerate and the ground states are approximate codewords of the Gottesman-Kitaev-Preskill (GKP) code. We find that the circuit is naturally protected against the common noise channels in superconducting circuits, such as charge and flux noise, implying that it can be used for passive quantum error correction.
  arXiv  Detail & Related papers  (2020-02-18T16:45:09Z)
• Efficient classical simulation of random shallow 2D quantum circuits [104.50546079040298]
  Random quantum circuits are commonly viewed as hard to simulate classically. We show that approximate simulation of typical instances is almost as hard as exact simulation. We also conjecture that sufficiently shallow random circuits are efficiently simulable more generally.
  arXiv  Detail & Related papers  (2019-12-31T19:00:00Z)

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.