Also check out the awesome paper "Sum of Squares Circuits" (arxiv.org/pdf/2408.11778) by @loreloc_, Stefan Mengel, and @tetraduzione, which concurrently showed the separation between monotone and squared circuits. Also at AAAI 2025 today poster #840!

Inception PCs strictly subsume monotone and squared PCs, and are strictly more expressive than both. We show this leads to improved downstream modeling performance when normalizing for FLOPS:

To overcome these limitations, we propose Inception PCs, a novel tractable probabilistic model representing a deep *sum-of-square-of-sums*.

Inception PCs explicitly introduce two types of latent variables into the circuit for the mixtures encoded at sum nodes.

We show that the reverse also holds (!!) - some tractable distributions expressed as monotone circuits cannot be compactly expressed as a square.

On the other hand, squared circuits (arxiv.org/abs/2310.00724) allow use of arbitrary real parameters by *squaring* the circuit output. It was previously proven that squared circuits can be exponentially more expressive than monotone circuits!

Probabilistic circuits are deep *tractable* probabilistic models that allow efficient and exact computation of marginals.

Traditionally, monotone circuits enforce non-negativity by using non-negative weights.

Paper: arxiv.org/abs/2408.00876

Thanks Devendra!

Thanks to my amazing co-authors Denis Mauá, @yjchoi1.bsky.social, @guyvdb.bsky.social. Hope to see you at the poster session!

Along the way we also show a bunch of other cool results, like:
- More efficient algorithms for causal inference on circuits
- New circuit properties
- Separation/hardness results

Building upon the prior PC atlas (proceedings.neurips.cc/paper_files/... ), our algebraic atlas provides a comprehensive approach for deriving **efficient algorithms** and **tractability conditions** for arbitrary compositional queries.

Try our atlas the next time you come across a new query!

Just as circuits serve as a unifying representation of models, we show how you can express many queries as compositions of just a few basic operations: aggregation (marginalization, max, etc.), product, and elementwise mappings.

Circuits are a unifying representation of probability distributions as a computation graph of sums and products. Here we consider the more general algebraic circuits, where sum/product is replaced with a semiring operation (think e.g. OR and AND for Boolean circuits).

Hi! I work on prob ML & tractable models.