Subtractive Mixture Models via Squaring: Representation and Learning
Authors: Lorenzo Loconte
Aleksanteri Mikulus Sladek
Stefan Mengel
Martin Trapp
Arno Solin
Nicolas Gillis
Antonio Vergari
Venue: ICLR 2024 spotlight (2024)
Keywords: tractable inference
distribution estimation
probabilistic circuits
tensor networks
Primary area: probabilistic methods (Bayesian methods, variational inference, sampling, UQ, etc.)
TL;DR: We show how to effectively represent and learn a generic class of (deep) mixture models encoding subtractions of probability distributions, and theoretically prove they can be exponentially more expressive than addition-only mixture models.

Abstract: Mixture models are traditionally represented and learned by adding several distributions as components. Allowing mixtures to subtract probability mass or density can drastically reduce the number of components needed to model complex distributions. However, learning such subtractive mixtures while ensuring they still encode a non-negative function is challenging. We investigate how to learn and perform inference on deep subtractive mixtures by squaring them. We do this in the framework of probabilistic circuits, which enable us to represent tensorized mixtures and generalize several other subtractive models. We theoretically prove that the class of squared circuits allowing subtractions can be exponentially more expressive than traditional additive mixtures; and, we empirically show this increased expressiveness on a series of real-world distribution estimation tasks.

Published as a conference paper at ICLR 2024
SUBTRACTIVE MIXTURE MODELS VIA SQUARING: REPRESENTATION AND LEARNING
Lorenzo Loconte
Aleksanteri M. Sladek?
Stefan Mengel
Martin Trapp'
Arno Solin? Nicolas Gillis
Antonio Vergari'
School of Informatics, University of Edinburgh, UK
2 Department of Computer Science, Aalto University, Finland
3 University of Artois, CNRS, Centre de Recherche en Informatique de Lens (CRIL), France
4 Department of Mathematics and Operational Research, Université de Mons, Belgium
ABSTRACT
Mixture models are traditionally represented and learned by adding several distri- butions as components. Allowing mixtures to subtract probability mass density can drastically reduce the number of components needed to model complex dis- tributions. However, learning such subtractive mixtures while ensuring they still encode a non-negative function is challenging. We investigate how to learn and perform inference on deep subtractive mixtures by squaring them. We do this the framework of probabilistic circuits, which enable mixtures and generalize several other subtractive models. We theoretically prove that the class of squared circuits allowing subtractions can be exponentially more expressive than traditional additive mixtures; and, we empirically show this in- creased expressiveness on a series of real-world distribution estimation tasks.
represent tensorized
INTRODUCTION
Finite mixture models (MMs) are staple in probabilistic machine learning, as they offer a simple and elegant solution to model complex distributions by blending simpler ones in a linear combination (McLachlan et al., 2019). The classical recipe to design MMs is to compute a convex combination over input components. That is, MM representing a probability distribution over set of random variables X (X1, X2,..., XD) is usually defined as
(X)= ΣK K - (X):(X), with w. 2.0
Σ -=
where wi are the mixture parameters and each component p: is a mass or density function. This is the case for widely-used MMs such as Gaussian mixture models (GMMs) and hidden Markov models (HMMs) but also mixtures of generative models such as normalizing flows (Papamakarios et al., 2021) 1) and deep mixture models such as probabilistic circuits (PCs, Vergari et al., 2019b).
The convexity constraint in Eq. (1) is simplest sufficient condi- tion to ensure p is non-negative function integrating to 1, i... is valid probability distribution, and often assumed in practice. How- ever, this implies that the components p; can only be combined in additive manner, and thus it can greatly impact their ability to esti- mate distribution efficiently. For instance, consider approximating distributions having "holes" in their domain, such as the simple 2- dimensional ring distribution on the left (ground truth). A classical additive MM such GMM would ultimately recover it, as it is uni- versal approximator of density functions (Nguyen al., 2019), but only by using an unnecessarily high number of components (depicted as red ellipsoids). MM allowing negative mixture weights, i.e., wi < 0, would instead require
Ground Truth
GMM (K 2)
GMM 16)
NGMM (Km2)
Corresponding author, lloconte @ sms.ed.ac.uk Across the paper will abuse the integration also refer summation in of discrete variables.

---

Published as a conference paper at ICLR 2024
only two components, as it can subtract one inner Gaussian density from an outer one (NGMM, see dotted ellipsoid). We call these MMs subtractive or non non-monotonic MMs (NMMs), as opposed to their classical additive counterpart, called monotonic MMs (Shpilka & Ychudayoff, 2010).
The challenge with NMMs is ensuring that the modeled p(X) is a valid distribution, as the convex- ity constraint does not hold anymore. This problem has been investigated in the past in number of ways, in its simplest form by imposing ad-hoc constraints over the mixture parameters w/, de- rived for simple components such Gaussian and Weibull distributions (Zhang & Zhang, 2005; Rabusseau & Denis, 2014; Jiang et al., 1999). However, different families of components would require formulating different constraints, whose closed-form existence is not guaranteed.
In this paper, we study a more general principle to design NMMs that circumvents the aforemen- tioned limitation while ensuring non-negativity of the modeled function: squaring the encoded lin- ear combination. For example, the NGMM above is a squared combination of Gaussian densities with negative mixture parameters. We theoretically investigate the expressive efficiency of squared NMMs, i.e., their expressiveness w.r.t. their model size, and show how to effectively represent and learn them practice. Specifically, we do so the framework of PCs, tractable models general- izing classical shallow MMs into deep MMs represented as structured neural networks. Deep PCs are already more expressive efficient than shallow MMs as they compactly encode a mixture with an exponential number of components (Jaini et al., 2018; Vergari et al., 2019b). However, they are classically represented with non-negative parameters, hence being restricted to encode deep but ad- ditive MMs. Instead, PCs (NPC²s) can be exponentially more parameter-efficent than their monotonic counterparts.
main theoretical contribution prove that squared non-monotonic
Contributions. i) We introduce a general framework to represent NMMs via squaring (Sec. 2), within the language of tensorized PCs (Mari et al., 2023), and show how NPC*s can be effectively learned and used for tractable inference (Sec. 3). ii) We show how NPC*s generalize not only mono- tonic PCs but other apparently different models allowing negative parameters that have emerged in different literatures, such as square root of density models in signal processing (Pinheiro & Vi- dakovic, 1997), positive semi-definite (PSD) models in kernel methods (Rudi & Ciliberto, 2021), and Born machines from quantum mechanics (Orús, 2013; Glasser et al., 2019) (Sec. 4). This al- lows us to understand why they lead to tractable inference via the property-oriented framework of PCs. iil) We derive an exponential lower bound over the size of monotonic PCs to represent func- tions that can be compactly encoded by one NPC² (Sec. 4.1), hence showing that NPC's (and thus the aforementioned models) can be much more expressive for a given size. Finally, iv) we provide empirical evidence (Sec. 5) that NPC's can approximate distributions better than monotonic PCs for a variety of experimental settings involving learning from real-world data and distilling intractable models such large language models to unlock tractable inference (Zhang al., 2023).
2 SUBTRACTIVE MIXTURES VIA SQUARING
We start by formalizing how to represent shallow NMMs by squaring non-convex combinations of K simple functions. Like exponentiation in energy-based models (LeCun al., 2006), squaring ensures the non-negativity of our models, but differently from it, allows to tractably renormalize them. A squared NMM encodes (possibly unnormalized) distribution c² (x) over variables X as
(X) (ΣKn mxc((x))² = -K E (X)c
where are the learnable components and the mixture parameters w; E R are unconstrained, as opposed to Eq. (1). Squared NMMs can therefore represent (K+1) components within the same pa- rameter budget of K components of an additive MM. Each component of a squared NMM computes product of experts ca (x()ee (X) (Hinton, 2002) allowing negative parameters 2w;wy if i + j. and of (X) with wi otherwise. Fig. shows a concrete example of this construction, which constitutes the simplest 2PC² we can build (see Sec. 3), i.e., comprising a single layer and having depth one.
Tractable marginalization. Analogously to traditional MMs, squared NMMs support tractable marginalization and conditioning, if their component distributions do as well. The distribution en- coded by e² (X) can be normalized to compute a valid probability distribution p(X) = 2² (X)/2. by computing its partition function Z as
Z z= dx) dx EK EK wew, J (x)
(3)
2

---

Published as a conference paper at ICLR 2024
Figure Shallow MMs and squared NMMs represented as PCs, mapped to a computa- tional graph having input components and weighted sum unit output. Squaring mix- ture with = 3 components (left) can yield more components that share parameters (right).
XX)
003
2
C3
01
61
C2C3
Computing Z translates to evaluating 2x integrals over products of components C₁ (X) (X). More generally, marginalizing any subset of variables in X can be done in ( This how- ever implies that the components ej are chosen from a family of functions such that their product e, (x)e,, (X) can be tractably integrated, and Z is non-zero and finite. This is true for many para- metric families, including exponential families (Seeger, 2005). For instance, the product of two Gaussian or two categorical distributions is another Gaussian (Rasmussen & Williams, 2005) or categorical up to a multiplicative factor, which can be computed in polynomial time.
A wider choice of components. Note that we do not require each o to model a probability distri- bution, e.g., we might have (x) < O. This allows us to employ more expressive tractable functions as base components in squared NMMs such as splines (see App. E for details) potentially small neural networks (see discussion in App. G). However, if the components are already flexible enough there might not be an increase in expressiveness when mixing them in linear combination squar- ing them. E.g., a simple categorical distribution can already capture any discrete distribution with finite support and a (subtractive) mixture thereof might not yield additional benefits besides being easier to learn. An additive mixture of Binomials is instead more expressive than single Binomial, but expected to be less expressive than its subtractive version (as illustrated in Sec. 5).
Learning squared NMMs. The canonical way to learn traditional MMs (Eq. (I)) is by maximum- likelihood estimation (MLE), i.e., by maximizing Exep log p(x) where D is a set of independent and identically distributed (i.id.) samples. For squared NMMs, the MLE objective is
EXED log (x))x) = |D] log EXED log |c(x));
where c(x) -'K (x). Unlike other NMMs mentioned in Sec. 1, we do not need to derive additional closed-form constraints for the parameters to preserve non-negativity. Although mate- rializing the squared mixture having (* ( components is required to compute as in Eq. (3), evaluating log (o(x)] is linear in K. Hence, we can perform batched stochastic gradient-based opti- mization and compute Z just once per batch, which makes NMMs efficient to learn (see App. C).
3 SQUARING DEEP MIXTURE MODELS
So far, we dealt with mixtures that are shallow, i.e., that can be represented simple computational graphs with single weighted sum unit (e.g.. Fig. 1). We now generalize them in the framework of PCs (Vergari et al., 2019b; Choi et al., 2020; Darwiche, 2001) as they offer property- language to model structured neural networks which allow tractable inference. PCs enable us to encode an exponential number of mixture components in compact but deep computational graph.
PCs are usually defined terms of scalar computational units: sum, product and input (see App. A). Following Vergari al. (2019a); Mari et al. (2023), instead formalize them tensorized compu- tational graphs. That is, we group several computational units together in layers, whose advantage is twofold. First, we able to derive simplified tractable algorithm for squaring that requires only linear algebra operations and benefits from GPU acceleration (Alg. 1). Second, we can more easily generalize many recent PC architectures (Peharz et al., 2020b;a; Liu & Van den Broeck, 2021), as well as other tractable tensor representations (Sec. 4), Fig. A. illustrates how scalar computational units are mapped tensorized layers. We start by defining deep computational graphs that can model possibly negative functions, simply named circuits (Vergari et al., 2021).
Definition 1 (Tensorized circuit). A tensorized circuit is a parameterized computational graph encoding a function c(X) and comprising of three kinds of layers: input, product and sum. Each layer comprises computational units defined over the same set of variables, also called its scope, and every non-input layer receives input from one or more layers. The scope of each non-input layer is
3

---

Published as a conference paper at ICLR 2024
b))
X1. Xg. X1
W#
X
W.
+
Xs
X2
P
X
4 ... X
WioW,
(a)
circuits reduces to squaring layers, depicted as colored boxes of A (input), X (product), and + (sum). Connections to a sum layer labeled by the matrix parameterizing the layer, while connections to product layers are laheled by the Hadamard product sign (see also Fig. A. A tensorized structredddeccompsaabe circuit (b) over three variables defined from the RG (a) is squared in (c) by recursively squaring each layer via Alg. I. Squared layers contain a quadratic number of units, but still output vectors.
Figure 2: Squaring tensorized
the union of the scope of its inputs, and the scope of the output layer computing c(X) is X. Each input layer l has scope Y C X and computes a collection of K functions (Y) E R. i.e., outputs Hadamard (or element-wise) product over the N layers it receives as input, i..., L = 2 L. A sum layer with S sum units and receiving input from a previous layer L E R is parameterized by W E R and computes We.
K --dimennional vector. Each product layer l computes
Fig. 2b shows a deep cireuit in tensorized form. To model distribution via circuits we first require that the output of the computational graph is non-negative. We call such a circuit a PC. Similarly shallow additive MM (Eq. (I)), a sufficient condition ensure non-negativity of the output is make the PC monotonic, i.e., to parameterize all sum layers with non-negative matrices and to restrict input layers to encode non-negative functions (e.g., probability mass or density functions). So far, monotonic PCs have been the canonical way to represent and learn PCs (App. G). In Def. we presented product layers computing Hadamard products only, to simplify notation and as this implementation choice is commonly used in many existing PC architectures (Darwiche, 2009; Liu & Van den Broeck, 2021; Mari et al., 2023). We generalize our treatment of PCs in Def. A.6 to deal with another popular product layer implementation: Kronecker products (Peharz et al., 2020b;a; Mari et al., 2023). Our results still hold for both kinds of product layers, if not specified otherwise.
3.1 BUILDING TRACTABLE CIRCUITS FOR MARGINALIZATION
Deep PCs can be renormalized and marginalize out any subset of X in a single feed-forward pass if they are smooth and decomposable, i.c., each sum layer receives inputs from layers whose units are defined over the same scopes, and each product layer receives inputs from layers whose scopes are pairwise disjoint, respectively (Darwiche, 2001; Choi et al., 2020). See Prop. A.1 for more background. Sum layers in our Def. guarantee smoothness by design as they have exactly one input. A simple way to ensure decomposability is to create a circuit that follows a hierarchical scope partitioning of variables X, also called region graph, which is formalized next.
Definition 2 (Region graph (Dennis & Ventura, 2012)). Given set of variables X, region graph (RG) is a bipartite and rooted graph whose nodes are either regions, denoting subsets R. of X. or partitions specifying how a region is partitioned into other regions.
Fig. 2a shows an example of a RG. Given a RG, we can build a smooth and decomposable tensorized X that are not further partitioned with an
circuit as follows. First, we parameterize regions input layer encoding some functions over variables in R. Then, we parameterize each partitioning (R.) with a product layer having as inputs one layer for each R4, Each product layer is then followed by sum layer. Figs. 2a and 2b illustrate such a construction by color-coding regions and corresponding layers. As we will show in Sec. 3.2, this also provides us a clean recipe to efficiently square a deep circuit. The literature on PCs provides several ways to build RGs (Peharz et al., 2020b;a; Mari et al., 2023). In our experiments (Sec. 5), we recursively partition sets of variables randomly until no further partitioning possible (Peharz et al., 2020b). Moreover, we experiment with RGs that partitions variables one by one (c.g.. the one in Fig. 2a), as they are related to other classes of models (see Sec. 4). App. F further details how construct these RGs.
4

---

Published as a conference paper at ICLR 2024
3.2 SQUARING DEEP TENSORIZED CIRCUITS
(Squared negative) MMs as circuits. It is easy to see that traditional shallow MMs (Eq.. (1)) can be readily represented as tensorized smooth and decomposable PCs consisting of an input layer encoding K components p; followed by a sum layer, which is parameterized by non-negative row- vector W E R whose entries sum up one. Squared NMMs (Eq. (2)) can be represented in similar way, as they can be viewed as mixtures over an increased number of components (see Fig. and Fig. A.1), where the sum layer is parameterized by a vector with real entries, instead. Next, discuss how to square deep tensorized circuits as to retrieve our NPC model class.
Squaring (and renormalizing) tensorized circuits. The challenge of squaring tensorized non- monotonic circuit e (potentially encoding a negative function) is guaranteeing c² to be representable as smooth and decomposable PC with polynomial size, as these two properties are necessary conditions to being able to renormalize c² efficiently and in a single feed-forward pass (Choi et al., 2020). In general, even squaring decomposable circuit while preserving decomposability of the squared circuit is a #P-hard problem (Shen et al., 2016; Vergari et al., 2021). Fortunately, it is possible to obtain a decomposable representation of c² efficiently for circuits c that are structured- decomposable (Pipatsrisawat & Darwiche, 2008; Vergari et al., 2021). Intuitively. in tensorized dunetureddeccompsablee cireuit all product layers having the same scope Y C X decompose Y over their input layers in the exact same way. We formalize this property in the Appendix in Def. A.3.
Tensorized circuits satisfying this property by design can be easily constructed by stacking layers conforming to a RG, as discussed before, and requiring that such a RG is a free, i.e., in which there is a single way to partition each region, and whose input regions do not have overlapping scopes. E.g., the RG in Fig. 2a is tree RG. From here on, w.l.o.g. we assume our tree RGs to be binary trees, i.e.. they partition each region into two other regions only. Given a tensorized sructured-decompose circuit defined on such tree RG, Alg. efficiently constructs smooth and decomposable ten- sorized circuit c². Moreover, let T. be the number of layers and M the maximum time required to evaluate one layer in c, then the following proposition holds.
Proposition (Tractable marginalization of squared circuits). Let e be a tensorized structured- decomposable circuit where the products of functions computed by each input layer can be tractably integrated. Any marginalization of c² obtained via Alg. I requires time and space O(L 2
See App. B.2 for a proof. In a nutshell, this is possible because Alg. recursively squares each layer l in e such as e² = l. 69 l in c², where @ denotes the Kronecker product of two vectors. Our tensorized treatment of circuits allows for a much more compact version of the more general algo- rithm proposed in Vergari et al. (2021) which was defined in terms of squaring scalar computational units, At the same time, it lets us derive tighter worst-case upper-bound than the one usually re- ported for squaring
deccuureddeccompsabblle circuits (Pipatsrisawat & Darwiche, 2008; Choi et al., 2015; Vergari et al., 2021), which is the squared number of computations in the whole computational graph, or OL2 ) Note that materializing c² is needed when we want to efficiently compute the normalization constant Z of c² or marginalizing any subset of variables. As such, when learning by MLE (Eq. (4)) and by batched gradient descent, we need to evaluate e² only once per batch, thus greatly amortizing its cost. In App. C, we investigate the time and memory costs of learning NPC?s having different size and on different data set dimensionalities. Finally, tractable marginalization enables tractable sampling from the distribution modeled by NPC?s, as we discuss in App. A.2.
3.3 NUMERICALLY STABLE INFERENCE AND LEARNING
Renormalizing deep PCs can easily lead to underflows and/or overflows. In monotonic PCs, this is usually addressed by performing computations in log-space and utilizing the log-sum-exp trick (Blanchard et al., 2021). However, this is not applicable to non-monotonic PCs as intermediate layers can compute negative values. Therefore, we instead evaluate circuits by propagating the log- arithm of absolute values and the sign values of the outputs of each layer. Then, sum layers evaluated with a sign-aware version of the log-sum-exp trick. A similar idea has been already ap- plied to evaluate expectations of negative functions with monotonic PCs (Mauá et al., 2018; Correia & de Campos, 2019). App. D extends it to tensorized non-monotonic circuits.
"In Alg. B.1 we provide generalization of Alg. 1 square Kronecker product layers (Peharz et al., 2020b).
5

---

Published as a conference paper at ICLR 2024
Algorithm 1 square TensorizedCirouit(e. R)
Input: tensorized circuit having output layer l and defined on tree RG rooted by R.
Output: The tensorized squared circuit defined on the same tree RG having E² as output layer computing & L.
I: if l an input layer then computes K functions (R)
9:
return Ef @ L
2:
10:
else
D E is a sum layer
3: refurn An input layer & computing all K2
11:
{(e, R)} + getlnputs(e, R)
4:
product combinations (R)
12:
E squareTensorizedCCiruiii &, R)
5: else if l is a product layer then
13:
W
E
R _** <- getParameters(())
[(e, R2), (L,, R <- getinputs R)
14:
W' E R + W 2 W
7:
t { square Tenaarreennoiiiediiruutt//// Ri)
15:
return W
8: E SquareTensooizedCCicctt E,. Ra)
4 EXPRESSIVENESS OF NPC AND RELATIONSHIP TO OTHER MODELS
Circuits have been used as the "lingua franca" to represent apparently different tractable model representations (Darwiche Marquis, 2002; Shpilka & Yehudayoff, 2010), and to investigate their ability to exactly represent certain function families with only polynomial increase in model size also called the expressive efficiency (Martens & Medabalimi, 2014), or succinciness (de Colnet & Mengel, 2021) of a model class. This is because the size of circuits directly translates to the computational complexity of performing inference. As we extend the language of monotonic PCs to include negative parameters, here we provide polytime reductions from tractable probabilistic model classes emerging from different application fields that can encode subtractions, to (deep) non-monotonic PCs. By doing so, we not only shed light why they are tractable, by explicitly stating their structural properties as circuits, but also on why they can more expressive than classical additive MMs, as we prove that NPC?s can be exponentially more compact in Sec. 4.1.
Simple shallow NMMs have been investigated for a limited set of component families, as discussed in Sec. 1. Notably, this also be done by directly learning to approximate the square root of density function, as done in signal processing with wavelet functions as components (Daubechics, 1992; Pinheiro & Vidakovic, 1997) or RBF kernels, i.e., unnormalized Gaussians centered over data points (Schölkopf & Smola, 2001), as in Hong & Gao (2021). As discussed in Sec. 3, we can readily represent these NMMs as simple NPC's where kernel functions are computed by input layers.
Positive semi-definite (PSD) models (Rudi & Ciliberto, 2021; Marteau-Ferey et al., 2020) are recent class of models from the kernel and optimization literature. Given kernel function (e.g., RBF kernel in Rudi & Ciliberto (2021)) and set of d data points x(1), xx"),...,xx , x(()) with <(x) [x(x, (2)),.... ..... x(x, x (d)))] E Rd, and a real d x d PSD matrix A, they define unnor- (a(x)AAAe Ax(x). Although apparently malized distribution as the non-negative function [(x; A, k) = x(x) different, they can be translated to NPC²s in polynomial time.
Proposition 2 (Reduction from PSD models). PSD model with kernel function K, defined over d data points, and parameterized by PSD matrix A, can be represented as a mixture of squared NMMs (hence NPC²s) in time (dd))
We prove this in App. B.3. Note that while PSD models are shallow non-monotonic PCs, we can stack them into deeper NPC3s that support tractable marginalization via sruccuredddeccoppsabblii
Tensor networks and the Born rule Squaring a possibly negative function to retrieve an un- normalized distribution is related the Born rule in quantum mechanics (Dirac, 1930), used to characterize the distribution of partieles by squaring their wave function (Schollwoeck, 2010; Orús, 2013). These functions can be represented as large D-dimensional tensor 'T over discrete vari- ables X = {XI,..., XD) taking value (1...., m), compactly factorized in tensor network (TN) such as matrix-produet state (MPS) (Pérez-García al., 2007), also called tensor-train. Given an assignment (II,..., .D) to X, rank MPS compactly represents T as
Th Tpl Σ Σ, 11-1
E... E. -.
A [x1, A1] A2]22[2, in, iz] ... AD(TD, (5)
where AI, AD Rmxr, Ay E RX with 1 < D, for indices fii...., (d.....,ip-1,, and de- noting indexing with square brackets. To encode a distribution p(X), one can reparameterize ten- sors Aj to be non-negative (Glasser et al., 2019) or apply the Born rule and square T to model

---

Published as a conference paper at ICLR 2024
p(x) x [[.........]]...... Such TN is called Born machine (BM) (Glasser et al., 2019). Be- sides modeling complex quantum states, TNs such as BMs have also been explored as classical ML models to learn discrete distributions (Stoudenmire & Schwab, 2016; Han et al., 2018; Glasser et al., 2019; Cheng et al., 2019), in quantum MI. (Liu & Wang, 2018; Huggins et al., 2018), and more recently extended to continuous domains by introducing sets of basis functions, called TTDE (Novikov et al., 2021). Next, we show they are a special case of NPC²s.
Proposition (Reduction from BMs). BM encoding D-dimensional tensor with m states by squaring rank r MPS can be exactly represented as a structured-decompssabbe NPC² in (DD-)") time and space, with I min mr).
We prove this in App. B.4 by showing equivalent NPC² defined on linear tree RG (e.g., the one in Fig. 2a). This connection highlights how tractable marginalization in BMs is possible thanks to stnetured-decoompsabiiig (Proposition 1), a condition that to the best of our knowledge was not previously studied for TNs. Futhermore, as NPC we can now design more flexible tree RGs, e.g., randomized tree structures (Peharz et al., 2020b; Di Mauro et al., 2017; Di Mauro et al., 2021), densely tensorized structures heavily exploiting GPU parallelization (Peharz et al., 2020a; Mari et al., 2023) or heuristically learn them from data (Liu & Van den Broeck, 2021).
4.1 EXPONENTIAL SEPARATION OF NPC²s AND STRUCTURED MONOTONIC PCs
Squaring via Alg. I can already make a tensorized (monotonic) PC more expressive, but only by a polynomial factor, as we quadratically increase the size of each layer, while keeping the same num- ber of learnable parameters (similarly to the increased number of components of squared NMMs (Sec. 2)). On the other hand, allowing negative parameters can provide an exponential advantage, as proven for certain circuits (Valiant, 1979), but understanding if this advantage carries over to our squared circuits is not immediate. In fact, we observe there cannot be any expressiveness ad- vantage in squaring certain classes of non-monotonic diruttreedddecompsaabbl circuits. These are the circuits that support tractable maximum-a-posterinn additional property known as determinism (see Darwiche (2001), Def. A.5). Squaring these circuits outputs a PC of the same size and that is monotonic, as formalized next and proven in App. B.6.
inference (Choi et al., 2020) and satisfy an
Proposition 4 (Squaring deterministic circuits). Let be smooth, decomposable and deterministic circuit, possibly computing a negative function. Then, the squared circuit e? is monotonic and has the same structure (and hence size) of c.
The 2 we considered so far, as constructed in Sec. 3, are not deterministic. Here we prove that some non-negative functions (hence probability distributions up to renormalization) can be com- puted by NPC2s that are exponentially smaller than any
monotonic PC.
Theorem 1 (Expressive efficiency of NPC2s). There class of non-negative functions F over variables X that can be compactly represented as shallow squared NMM (hence NPC²s), but for which the smallest strictueeddeccoppoaube monotonic PC computing any F E F has size 201()) )
We prove this in App. B.5 by showing non-trivial lower bound on the size of structured- decomposable monotonic PCs for variant of the unique disjointness problem (Fiorini et al., 2015).
Intuitively, this tells us that, given fixed number of parameters, NPC's can potentially be much more expressive than structured- -ectuuueddddcoopsaabllle monotonic PCs (and hence shallow additive MMs). We conjecture that an analogous lower bound can be devised for decomposable monotonic PCs. Furthermore, as this result directly extends to PSD and BM models (Sec. 4), it opens up interesting theoretical connections in the research fields of kernel-based and tensor network models.
EXPERIMENTS
We aim to answer the following questions: (A) are NPC better distribution estimators than mono- tonic PCs? (B) how the increased model size given by squaring and the presence of negative pa- rameters independently influence the expressiveness of NPC (C) how does the choice of input layers and the RG affect the performance of NPC We perform several distribution estimation experiments on both synthetic and real- wolld data, and label the following paragraphs with letters denoting relevance to the above questions. Moreover, note that our comparisons between NPC and monotonic PCs are based on models having the same number of learnable parameters.
7

---

Published as a conference paper at ICLR 2024
CONTINUOUS
CATEGORICAL SPLINES
GT
DISCRETE
BINOMIAL
GT
MPC
MPC/
NPC²
MPC
MPC
NPC²
Figure 3: NPC are better estimators, especially with parameter-efficient input layers. Dis- tribution estimated by monotonic PCs (MPC), squared monotonic PCs (MPC?) and NPC on 2D continuous (above) and discrete (below) data. On continuous data input layers compute splines (Eq. (11)), while discrete data they compute either categoricals (for MPC and MPC²), embed- dings (for NPC²s) or Binomials, Apps. H.1 and H.2 shows log-likelihoods on also additional data.
Power
Gas
Hepmass
ONE
Power
Gas
Hepmass M.BooNE BSDS300
0.5
10.0
MADE
-3.08
3.56
-20.98
-15559
148.85
zzz-- I 52-
RealNVP
0.17
8.33
18.71
-13.84
153,28
0.25
0.0
MAF
10.08
-17.73
-12.24
154.93
NSF
0.66
13.09
-14.01
-9.22
157.31
Gaussian
-7.74
-3.58
-27.93
-37.24
96.67
MiniBooNE
BSDS300
FiNer-LRS
0.36
4.79
-22.46
-34.21
32
-21.34
-28.77
143.30
MPC (LT)
0.51
6.73
-22.06
-32.47
116.90
-3.00
110.0 120,0
128
NPC² (LT))
0.53
9.00
-20.66
-26,68
118.58
256
MPC (BT)
0.57
5.56
-22.45
-32.11
123.30
40.0
1024
NPC² (BT)
0.62
10.98
-20.41
-26.92
128.38
Figure 4: NPC²s can be more expressive than monotonic PCs (MPCs). Best average log- likelihoods achieved by monotonic PCs (+) and NPC²s (+²). built either from randomized lin- ear tree (LT) or binary tree (BT) RGs (see App. H.3). The scatter plots (left) pairs log-likelihoods based on the number of units per layer K (the higher the darker), differentiating PCs with Gaussian (G/blue) and splines (S/red) input layers. Both axes of each scatter plot are on the same scale, thus the results above the diagonal are NPC²s achieving higher log-likelihoods than MPCs at parity of model size. The table (right) shows models' best average test lig-likelshoods and puts them in context with intractable (above) and tractable (below) models w.r.t. variable marginalization.
(A, B) Synthetic continuous data. Following Wenliang et (2019), we evaluate monotonic PCs and NPC's 2D density estimation tasks, this allows gain insight the learned density functions. To disentangle the effect of squaring versus that of negative parameters, we also experiment with squared monotonic PCs. We build circuit structures from trivial tree RG (see App. H.1 for details). We experiment with splines as input layers for NPC²s, and enforce their non- negativity for monotonic PCs (see App. E). Fig. shows that, while squaring benefits monotonic PCs, negative parameters in NPC²s are needed to better capture complex target densities.
(C) Synthetic discrete data. We estimate the probability mass of the previous 2D data sets, now finitely-dise mhitely-discretizedd (see App. H.2), to better understand when negative parameters might bring little advantage if input layers are already expressive enough. First, we experiment with (squared) monotonic PCs (resp. NPC²s) having input layers computing categoricals (resp. real-valued em- beddings). Second, we employ the less flexible more parameter-efficien Binomials instead. App. H.2 reports the hyperparameters. Fig. 3 shows that, while there is no clear advantage for NPC²s equipped with embeddings instead MPC² with categoricals, in case of Binomials they can better capture the target distribution. This is because categoricals (and embeddings) already have enough parameters to capture "holes" in the probability mass function. However, Binomials introduce strong inductive bias that might hinder learning. We believe this is the reason why, cording to some preliminary results, we did not observe an improvement of NPC²s with respect to monotonic PCs estimating image distributions.
8

---

Published as a conference paper at ICLR 2024
Figure 5: NPC3s (+²) achieve higher log- likelihoods than monotonic PCs (+) on data sampled by GPT2. We report the median and the area including 90% of runs by varying the size of layers K and other hyperparameters (App. H.4). For comparison, the log-likelihood of GPT2 the same training data is about -52. The difference on the test data is significant for most values of K (see p-values in Table H.7).
LL
Training data
LL
Test data
70
75
-80
-80
85 102
K- 10a
10a
10a
(A, B, C) Multi-variate continuous data. Following Papamakarios et al. (2017), we evaluate deeper PCs for density estimation on five multivariate data sets (see Table H.1). We evaluate mono- tonic PCs and NPC²s in tensorized form built out of randomized linear tree RGs. That is, for some variable permutation, we construct a tree RG where each partition splits a region into a set of only one variable and recursively factorizes the rest. By doing so, we recover an architecture similar to a BM or TTDE (see Sec. 4). Following Peharz et al. (2020b), we also experiment with binary tree RGs whose regions are randomly split in half. App. H.3 details these RGs, as well as the hyperpa- rameters used. We compare against: a full covariance Gaussian, normalizing flows RealNVP (Dinh et al., 2017), MADE (Germain et al., 2015), MAF (Papamakarios et al., 2017) and NSF (Durkan et al., 2019), a monotonic PC with input layers encoding flows (EiNet-LRS) (Sidheekh et al., 2023), and TTDE (Novikov et al., 2021). Fig. shows that NPC with Gaussian input layers generally achieve higher log-likelihoods than monotonic PCs on four data sets. Fig. H.3 shows similar results when comparing to squared monotonic PCs, thus providing evidence that negative parameters other than squaring contribute to the expressiveness of NPC likelihoods than linear tree ones, especially on Gas, where NPC's using them outperform TTDE.
tree RGs generally deliver better
(A) Distilling intractable models. Monotonic PCs have been used to approximate intractable mod- els such as LLMs and perform exact inference in presence of logical constraints, such as for con- strained text generation (Zhang et al., 2023). As generation performance is correlated with how well the LLM is approximated by a tractable model, we are interested in how NPC can better be the distillation target of LLM such GPT2, rather than monotonic PCs. Following Zhang et al. (2023), we minimize the KL divergence between GPT2 and our PCs on a data set of sampled sentences (details App. H.4). Since sentences are sequences of token variables, the architecture of tensorized circuits is built from linear tree RG, thus corresponding to an inhomogencous HMM in case of monotonic PCs (see App. B.4.1) while resembling a BM for NPC²s. Fig. 5 shows that NPC?s can distill GPT2 and scale better than monotonic PCs, as they achieve log- ligliikelssoods closer to the ones computed by GPT2. We observe that NPC*s fit the training data much better than the test data, even though the results on test data are generally significant (see Table H.7). While this is further evidence of their increased expressiveness, reguuuirii NPC's deserves future investigation.
6 DISCUSSION & CONCLUSION
With this work, we hope to popularize subtractive MMs via squaring as a simple and effective model class in the toolkit of tractable probabilistic modeling and reasoning that can rival traditional additive MMs. By casting them in the framework of circuits, we presented how to effectively represent and learn deep subtractive MMs such as NPC²s (Sec. 3) while showing how they can generalize other model classes such as PSD and tensor network models (Sec. 4). Our main theoretical result (Sec. 4.1) applies also to these models and justifies the increased performance we found in practice (Sec. 5). This work is the first to rigorously address representing and learning non-monotonic PCs in general way, and opens up a number of future research directions. The first one is to retrieve a latent variable interpretation for NPC²s, as negative parameters in non-monotonic PC invalidate the probabilistic interpretation of its sub-circuits (Peharz et al., 2017), making it not possible to learn its structure and parameters in classical ways (see App. G). Better ways to learn NPC?s, in turn, can benefit all applications in which PCs are widely used - from causal discovery (Wang et al., 2022) to variational inference (Shih& & Ermon, 2020) and neuro-symbolic AI (Ahmed et al., 2022) by making more compact and expressive distributions accessible. Finally, by formally connecting circuits with tensor networks, community to the other, such as better learning schemes (Stoudenmire & Schwab, 2016; Novikov al., 2021), and more flexible ways factorize high-dimensional tensors (Mari et al., 2023).
hope to inspire works that carry over the advancements of one

---

Published as a conference paper at ICLR 2024
REPRODUCIBILITY STATEMENT
In App. we include all the details about the experiments we showed in Sec. 5. The source code, documentation, data sets and scripts needed to reproduce the results and figures, are available at https://githu: con/ hamm/pprl-tools.. http://pppooooolsaaaaaeeea---aaa squared-npcs.
ACKNOWLEDGMENTS
AV was supported by the "UNREAL: Unified Reasoning Layer for Trustworthy ML" project (EP/Y023838/1) selected by the ERC and funded by UKRI EPSRC. NG acknowledges the support by the European Union (ERC consolidator, eLinoR, no 101085607). AMS acknowledges funding from the Helsinki Institute for Information Technology. MT acknowledges funding from the Re- search Council of Finland (grant number 347279). AS acknowledges funding from the Research Council of Finland (grant number 339730). We acknowledge CSC- IT Center for Science, Fin- land, for awarding this project access to the LUMI supercomputer, owned by the EuroHPC Joint Undertaking, hosted by CSC (Finland) and the LUMI consortium through CSC. We acknowledge the computational resources provided by the Aalto Science-IT project.
REFERENCES
Kareem Ahmed, Stefano Teso, Kai-Wei Chang, Guy Van den Broeck, and Antonio Vergari. Seman- tic probabilistic layers for neuro-symbolic learning. In Advances in Neural Information Process- ing Systems 35 (NeurIPS), volume 35, pp. 29944-29959, Curran Associates, Inc., 2022.
Raphaël Bailly. Quadratic weighted automata: Spectral algorithm and likelihood maximization. In Asian Conference on Machine Learning, 2011.
Pierre Baldi, Kyle Cranmer, Taylor Faucett, Peter Sadowski, and Daniel Whiteson. Parameterized neural networks for high-energy physics. European Physical Journal C, 76(5):235, 2016. doi: 10.1 10.1140/epicss100022 016 016-4099-4.
Pierre Blanchard, Desmond Higham, and Nicholas Higham. Accurately computing the log-sum exp and softmax functions. Institute of Mathematics and its Applications Journal of Numerical Analysis (IMAJNA), ((4):2311-233))) 2021.
Oliver Broadrick, Honghua Zhang, and Guy Van den Broeck. Polynomial semantics of tractable probabilistic circuits. arXiv preprint arXiv:2402. 09085, 2024.
Song Cheng, Lei Wang, Tao Xiang, and Pan Zhang. Tree tensor networks for generative modeling. Physical Review B, 99(15):155131, 2019.
Arthur Choi, Guy Van den Broeck, Adnan Darwiche, Qiang Yang, and Michael Wooldridge. Tractable learning for structured probability spaces: A case study learning preference distribu- tions. In 24th International Joint Conference on Artificial Intelligence (IJCAI), volume 2015, pp. 2861-2868. IJCAI, 2015.
Myung Jin Choi, Vincent YF Tan, Animashree Anandkumar, and Alan S Willsky. Learning latent tree graphical models. Journal of Machine Learning Research, 12:1771-1812, 2011.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying frame- work for tractable probabilistic modeling. 2020.
Alvaro H. C. Correia and Cassio P. de Campos. Towards scalable and robust sum-product networks. In Scalable Uncertainty Management. 2019.
Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: A fast and accurate learner of sruuctured-decompoone probabilistic circuits. The International Journal of Approximate Rea- soning (IJAR), 140:92-115, 2021.
Adnan Darwiche. Decomposable negation normal form. Journal of the ACM (JACM), 48:608-647 2001.
10

---

Published as a conference paper at ICLR 2024
Adnan Darwiche. Modeling and Reasoning with Bayesian Networks. Cambridge University Press, 2009.
Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelli- gence Research (JAIR), 17:229 264, 2002.
Ingrid Daubechies. Ten lectures on wavelets. Computers in Physics, 6:697-697, 1992.
Carl de Boor. Subroutine package for calculating with B-splines. Technical report, Los Alamos National Lab. (LANL), 1971.
Alexis de Colnet and Stefan Mengel. compilation of succinetness results for arithmetic circuits. In 18th International Conference Principles of Knowledge Representation and Reasoning (KR), pp. 205-215, 2021.
Ronald De Wolf. Nondeterministic quantum query and communication complexities. SIAM Journal on Computing, 32(3):681-699, 2003.
Aaron W. Dennis. Algorithms for Learning the Structure of Monotone and Nonmonotone Sum- Product Networks. PhD thesis, Brigham Young University. 2016.
Aaron W. Dennis and Dan Ventura. Learning the architecture of sum- cum-product networks using clus- tering on variables. In Advances in Neural Information Processing Systems 25 (NeurIPS), pp- 2033-2041. Curran Associates, Inc., 2012.
Nicola Di Mauro, Antonio Vergari, Teresa M. Basile, and Floriana Esposito. Fast and aceu- rate density estimation with extremely randomized cutset networks. In Machine Learning and Knowledge Discovery in Databases: ECML PKDD, pp. 203-219. Springer, 2017.
Nicola Di Mauro, Gennaro Gala, Marco lannotta, and Teresa Maria Altomare Basile. Random probabilistic circuits. 37th Conference on Uncertainty in Artificial Intelligence (UAI), volume 161, pp. 1682-1691. PMLR, 2021.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using Real NVP. In 5th International Conference on Learning Representations (ICLR), 2017.
Paul Adrien Maurice Dirac. The Principles of Quantum Mechanics. Clarendon Press, Oxford, 1930.
Dheeru Dua and Casey Graff. UCI Machine Learning Repository, 2017.
Conor Durkan, Artur Bekasov, lain Murray, and George Papamakarios. Neural spline flows. In Advances in Neural Information Processing Systems 32 (NeurIPS), pp. 7511-7522. Curran Asso- ciates, Inc., 2019.
Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald De Wolf. Exponen- tial lower bounds for polytopes in combinatorial optimization. Journal of the ACM (JACM), 62 (2):1-23, 2015.
Jordi Fonollosa, Sadique Sheik, Ramón Huerta, and Santiago Marco. Reservoir computing compen- sates slow response of chemosensor arrays exposed to fast varying gas concentrations in continu- ous monitoring. Sensors and Actuators B: Chemical, 215:618-6299 2015.
Mathieu Germain, Karol Gregor, lain Murray, and Hugo Larochelle. MADE: Masked autoencoder for distribution estimation. In 32nd International Conference on Machine Learning (ICML), pp- 881 - 889, 2015.
Nicolas Gillis. Nonnegative Matrix Factorization. Society for Industrial and Applied Mathematics (SIAM), 2020.
Ivan Glasser, Ryan Sweke, Nicola Pancotti, Jens Fisert, and Ignacio Cirac. Expressive power of tensor-network factorizations for probabilistic modeling. Advances in Neural Information Pro- cessing Systems 32 (NeurIPS), pp. 1498-1510. Curran Associates, Inc., 2019.
Wolfgang Hackbusch. Tensor spaces and numerical lensor calculus, volume 42, Springer, 2012.

---

Published as a conference paper at ICLR 2024
Zhao-Yu Yu Han, Jun Wang, Heng Fan, Lei Wang. and Pan Zhang. Unsupervised generative modeling using matrix product states. Physical Review X, 8:031012, 2018.
Georges Hebrail and Alice Berard. Individual houschold electric power consumption. UCI Machine Learning Repository, 2012.
Geoffrey E. Hinton. Training products of experts by minimizing contrastive divergence. Neural Computation, 14:1771-1800, 2002.
Xia Hong and Junbin Gao. Estimating the square root of probability density function on Riemannian manifold. Expert Systems The Journal of Knowledge Engineering, 38(7). 2021.
Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the American Mathematical Society, 4334):439-561 2006.
William J. Huggins, Piyush Patil, Bradley K. Mitchell, K. Birgitta Whaley, and Edwin Miles Stoudenmire. Towards quantum machine learning with tensor networks. Quantum Science and Technology, 4, 2018.
Priyank Jaini, Pascal Poupart, and Yaoliang Yu. Deep homogeneous mixture models: Represen- tation, separation, and approximation. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianche and R. Garnett (eds.), Advances in Neural Information Processing Systems (NeurIPS), volume 31. Curran Associates, Inc., 2018.
Renyan Jiang, Ming J. Zuo, and Han-Xiong Li. Weibull and inverse weibull mixture models allowing negative weights. Reliability Engineering & System Safery, 66(3):227-23) 1999.
Diederik P. Kingma and Jimmy Ba. Adam: method for stochastic optimization. In 3rd Interna- tional Conference on Learning Representations (ICLR), 2015.
Tamara G. Kolda and Brett W. Bader. Tensor decompositions and applications. Society of Industrial and Applied Mathematics (SIAM) Review, 51(3):455-500, 2009.
Yann LeCun, Sumit Chopra, Raia Hadsell, Mare' Aurelio Ranzato, and Fujie Huang. A tutorial on energy- based learning. Predicting Structured Data, 2006.
Anji Liu and Guy Van den Broeck. Tractable regularization of probabilistic circuits. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 3558-3570. Curran Associates, Inc., 2021.
Anji Liu, Honghua Zhang, and Guy Van den Broeck. Scaling up probabilistic circuits by latent variable distillation. In 11th International Conference on Learning Representations (ICLR), 2023.
Jin-Guo Liu and Lei Wang. Differentiable learning of quantum circuit born machines. Physical Review A, 98(6):062324, 2018.
Lorenzo Loconte, Nicola Di Mauro, Robert Peharz, and Antonio Vergari. How turn your knowl- edge graph embeddings into generative models via probabilistic circuits. Advances in Neural Information Processing Systems 37 (NeurIPS). Curran Associates, Inc., 2023.
Antonio Mari, Gennaro Vessio, and Antonio Vergari. Unifying and understanding overparameter- ized circuit representations via low-rank tensor decompositions. 6th Workshop on Tractable Probabilistic Modeling. 2023.
Ulysse Marteau-Ferey, Francis Bach, and Alessandro Rudi. Non-paramctric models for non-negative functions. In Advances in Neural Information Processing Systems 33 (NeurIPS), pp. 12816- 12826, 2020.
James Martens and Venkatesh Medabalimi. On the expressive efficiency of sum product networks. arXiv preprint arXiv: 2014.
David Martin, Charless Fowlkes, Doron Tal, and Jitendra Malik. A database of human segmented natural images and its application to evaluating segmentation algorithms and measuring ecological statistics. In 8th International Conference on Computer Vision (ICCV), volume 2, pp. 416-423. IEEE, 2001.
12

---

Published as a conference paper at ICLR 2024
D. Mauá, Diarmaid Conaty, Fabio Gagliardi Cozman, Katja Poppenhaeger, and Cassio Polpo de Campos. Robustifying sum-prodie networks. International Journal of Approximate Rea- soning, 101:163-180, 2018.
Geoffrey J. McLachlan, Sharon X. Lee, and Suren I. Rathnayake. Finite mixture models. Anmual Review of Statistics and its Application, 6:355-378, 2019.
TrungTin Tin Nguyen, Hien Duy Nguyen, Faicel Chamroukhi, and Geoffrey J. McLachlan. Approxima- tion by finite mixtures of continuous density functions that vanish at infinity. Cogent Mathematics & Statistics, 7, 2019.
Georgii S. Novikov, Maxim E. Panov, and Ivan V. Oseledets. Tensor-train density estimation. In 37th Conference on Uncertainty in Artificial Intelligence (UAI), volume 161 Proceedings of Machine Learning Research, pp. 1321-1331. PMLR, 2021.
Román Orús. A practical introduction to tensor networks: Matrix product states and projected entangled pair states. Annals of Physics, 349:117-158, 2013.
George Papamakarios, Theo Pavlakou, and lain Murray. Masked autoregressive flow for density estimation. In Advances in Neural Information Processing Systems 30 (NeurIPS), pp. 2338-2347. Curran Associates, Inc., 2017.
George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lak- shminarayanan. Normalizing flows for probabilistic modeling and inference. The Journal of Machine Learning Research (JMLR), 22(1):2617-2680, 2021.
Robert Peharz, Robert Gens, Franz Pernkopf, and Pedro M. Domingos. On the latent variable interpretation in sum-product networks. IEEE Transactions on Pattern Analalysis and Machine Intelligence, 39(10)2003022)) 2044, 2017.
Robert Peharz, Steven Lang, Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp, Guy Van Den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In 37th International Conference on Machine Learning (ICML), volume 119 of Proceedings of Machine Learning Research, pp. 7563-7574. PMLR, 2020a.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp. Kristian Kersting, and Zoubin Ghahramani. Random sum-product networks: A simple and fective approach to probabilistic deep learning. In 35th Conference Uncertainty in Artificial Intelligence (UAI), volume 115 of Proceedings of Machine Learning Research, pp. 334-344. PMLR, 2020b.
David Pérez-Garcis F. Verstraete, Michael M. Wolf, and Juan Ignacio Cirac. Matrix product state representations. Quantum Information and Computing, 7(5):401-430) 2007. ISSN 1533-7146.
Les A. Piegl and Wayne Tiller. The NURBS book. In Monographs in Visual Communication, 1995.
Aluisio Pinheiro and Brani Vidakovic. Estimating the square root of density via compactly sup- ported wavelets. Computational Statistics and Data Analysis, 25(4): 415, 1997.
Knot Pipatsrisawat and Adnan Darwiche. New compilation languages based structured decom- posability. 23rd Conference on Artificial Intelligence (AAAl), volume 8, pp. 517-522, 2008
Hoifung Poon and Pedro Domingos. Sum- Sum-product networks: A new deep architecture. In IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Guillaume Rabusseau and François Denis. Learning negative mixture models by tensor decomposi- tions. arXiv preprint arXiv:/403.c0 2014.
Carl Edward Rasmussen and Christopher K. I. Williams. Gaussian Processes for Machine Learning. Adaptive Computation and Machine Learning. MIT Press, 2005.
13

---

Published as a conference paper at ICLR 2024
Byron P. Roe, Hai-Jun Yang. Ji Zhu, Yong Liu, Ion Stancu, and Gordon McGregor. Boosted decision trees as an alternative to artificial neural networks for particle identification. Nuclear Instruments & Methods in Physics Research Section A-accelerators Spectrometers Detectors and Associated Equipment, 543:577-584, 2004.
Tim Roughgarden. Communication complexity (for algorithm designers). Foundations and Trends@ in Theoretical Computer Science, 11(3-4)221-404,, 2016.
Alessandro Rudi and Carlo Ciliberto. PSD representations for effective probability models. In Advances Neural Information Processing Systems 34 (NeurIPS), pp. 19411-19422. Curran Associates, Inc., 2021.
Bernhard Schölkopf and Alex Smola. Learning with kernels: support vector machines, regulariza- tion, optimization, and beyond. In Adaptive Computation and Machine Learning Series. MIT Press, 2001.
Ulrich Schollwoeck. The density-matrin renormalization group in the age of matrix product states. Annals of Physics, 326:96-199 192, 2010.
Matthias Seeger. Expectation propagation for exponential families. 2005.
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of prob- abilistic models. In Advances in Neural Information Processing Systems 29 (NeurIPS). Curran Associates, Inc., 2016.
Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. In Advances in Neural Information Processing Systems 33 (NeurIPS). Curran Associates, Inc., 2020.
Amir Shpilka and Amir Yehudayoff. Arithmetic circuits: A survey of recent results and open ques- tions. Founddations and Trends in Theoretical Computer Science, 5:207-388, 2010.
Sahil Sidheekh, Kristian Kersting, and Sriraam Natarajan. Probabilistic flow circuits: Towards unified deep models for tractable probabilistic inference. In 39th Conference on Uncertainty in Artificial Intelligence (UAI), volume 216 of Proceedings of Machine Learning Research, pp- 1964-1973. PMLR, 2023.
Aleksanteri M Sladek, Martin Trapp, and Arno Solin. Encoding negative dependencies in proba- bilistic circuits. In 6th Workshop on Tractable Probabilistic Modeling, 2023.
Edwin Stoudenmire and David J Schwab. Supervised learning with tensor networks. In Advances in Neural Information Processing Systems 29 (NeurIPS), pp. 4799-4807. Curran Associates, Inc., 2016.
Russell Tsuchida, Cheng Soon Ong, and Dino Sejdinovic, Squared neural families: new class of tractable density models. arXiv preprint 1xXiv:2305./355:: 2023.
Leslie G. Valiant. Negation be exponentially powerful. In /th Annual ACM Symposium Theory of Computing, pp. 189-196, 1979.
Antonio Vergari, Nicola Di Mauro, and Floriana Esposito. Visualizing and understanding sum- product networks. Machine Learning, 108(4):551-573. 2019a.
Antonio Vergari, Nicola Di Mauro, and Guy Van den Broeck. Tractable probabilistic models: Repre- sentations, algorithms, learning, and applications. Tutorial the 35th Conference on Uncertainty in Artificial Intelligence (UAI), 2019b.
Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A compositional atlas of tractable circuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS), pp. 13189-1320 13201. Curran Associates, Inc., 2021.
Allan H. Vermeulen, Richard H. Bartels, and Glenn R. Heppler. Integrating products of B-splines. SIAM Journal on Scientific and Statistical Computing, 13:1025-1038, 1992.
14

---

Published as a conference paper at ICLR 2024
Benjie Wang, Matthew R. Wicker, and Marta Kwiatkowska. Tractable uncertainty for structure learning. In 39th International Conference on Machine Learning (ICML), pp. 23131-23150. PMLR. 2022.
Li Wenliang, Danica J. Sutherland, Heiko Strathmann, and Arthur Gretton. Learning deep kernels for exponential family densities. In 36th International Conference on Machine Learning (ICML), volume 97 of Proceedings of Machine Learning Research, pp. 6737-6746. PMLR, 2019.
Baibo Zhang and Changshui Zhang. Finite mixture models with negative components. In 4th In- ternational Conference on Machine Learning and Data Mining in Pattern Recognition (MLDM), pp. 31-41. Springer, 2005.
Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In International Conference Machine Learning, pp. 12447-12457. PMLR, 2021.
Honghua Zhang, Meihua Dang, Nanyun Peng, and Guy Van den Broeck. Tractable control for au- toregressive language generation. In 40th International Conference on Machine Learning (ICML), volume 202 of Proceedings of Machine Learning Research, pp. 40932 40945. PMLR, 2023.
15

---

Published as a conference paper at ICLR 2024
+++
W E R3x3
X
+++
Figure A.1: Computational units can be grouped into layers as to build a tensorized circuit. Sum units each parameterized by the rows of W R (left, in purple) form sum layer param- eterized by W (right). Product units (left, in red) form an Hadamard product layer (right). Input units (left, in yellow) form an input layer computing the same functions (right).
A CIRCUITS
In Sec. 3 we introduced circuits in a tensorized formalism. Here we instead present the definitions and properties of circuits as they are usually defined the literature, which will be used in App. B.
Definition A.1 (Circuit (Choi et al., 2020; Vergari et al., 2021)). circuit is a parameterized computational graph
variables X encoding function c(X) and comprising three kinds of computational units: input, product, and sum. Each product or sum unit n receives as inputs the outputs of other units, denoted with the set in(n). Each unit encodes function en defined as: (i) fa (sc())) if n is an input unit, where fa is a function over variables sc(n) S X, called its scope, (ii) [igin()) Ca (sc(n))) if a product unit, and (iii) Eiein(m) w;cr(sc(n;)) if n is sum unit, with wy E R denoting the weighted sum parameters. The scope of a product or sum unit n is the union of the scopes of its inputs, i.c., sc(n)) = Ulein(n) sc(i).
Note that tensorized circuits (Def. 1) are circuits where each input (resp. product and sum) layer consists of scalar input (resp. product and sum) units. For example, Fig. A.1 shows how compu- tational units are grouped into layers. A probabilistic circuit (PC) is defined a non-negative function. PCs that are smooth and decomposable (Def. A.2) enable computing the partition function and, more in general, performing variable marginalization efficiently (Prop. A.1).
circuit encoding
Definition A.2 (Smoothness and decomposability (Darwiche & Marquis. 2002)). A circuit is smooth if for every sum unit n. its input units depend all on the same variables, i.c. Vi,j E in(n): : sc(i) = sc(j). A circuit decomposable if the inputs of every product unit n depend on disjoint sets of variables, i.e, Vi,j E in(n) # j: sc(i) O sc(jj) 23
Proposition A.1 (Tractability (Choi et al., 2020)). Let c be smooth and decomposable circuit over variables X whose input units can integrated efficiently. Then for any S X and y an assignment to variables in X Z. the quantity f c(y, z) dz can be computed exactly in time and space O([c)), where |c| denotes the size of the circuit, i.e., the number of connections in the computational graph.
The size of circuits tensorized form is obtained by counting the number of connections between the scalar computational units (see App. A.I.I). Squaring circuits or their tensorized representation efficiently such that the resulting PC is smooth and decomposable (Def. A.2) requires the satisfaction of structuree-deccompsstie decomposabillty, as showed in (Pipatsrisawat & Darwiche, 2008; Vergari et al., 202
Definition A.3 (Structured- cccopooabbily (Pipatsrisawat& & Darwiche, 2008; Darwiche, 2009)). A circuit structured- detpereddddcoopsabbbllb if (1) it smooth and decomposable, and (2) any pair of product units n, having the same scope decompose their scope at their input units in the same way.
Note that shallow MMs are both decomposable and structured structureddeccompsssee decooposabb......... As anticipated in Sec. 3, the expressiveness of squared non-monotonic PCs that are also deterministic the same (MAP) infer-
as monotonic deterministic PCs, which are used for tractable maximum-a-posterie ence. We prove it formally in App. B.6 by leveraging the definition of determinism that we show in Def. A.5. Before that, introduce the definition of support of computational unit.
Definition A.4 (Support (Choi et al., 2020)). The support of computational unit over variables X is defined as the set of value assignments to variables in X such that the output of n is non-zero, i.e. (n)p(n) (x val(X) c, (x) # 0), where (X) denotes the domain of variables X.
16

---

Published as a conference paper at ICLR 2024
Definition A.5 (Determinism (Darwiche, 2001)), A circuit is deterministic if for any unit n E c its inputs have disjoint support (Def. A.4), Vi,j E in(n), 2 supp(t) n supp(j) = Ø.
A.1 TENSORIZED CIRCUITS
Def. 1 can be further generalized by introducing Kronecker product layers, which are the building blocks of other tensorized circuit architectures, such as randomized and tensorized sum- sum-product networks (RAT-SPNs) (Peharz et al., 2020b), einsum networks (FiNets) (Peharz et al., 2020a).
Definition A.6 (Tensorized circuit). tensorized circuit c is a parameterized computational graph encoding a function c(X) and comprising of three kinds of layers: input, product and sum. Each layer comprises computational units defined over the same set of variables, also called its scope, and every non-input layer receives input from
more layers. The scope of each non-input layer is the union of the scope of its inputs, and the scope of the output layer computing el e(X) is X. Each input layer l has scope Y X and computes collection of K functions f:(Y) R, i.e., & outputs a K -i-imensional vector. Each product layer & computes either an Hadamard (or element- wise) or Kronecker product over the layers receives as input, i.e., l = 3 L, or @ Li, respectively. A sum layer with S sum units and receiving input form a previous layer & T K is parameterized by W E Sx and computes We.
A.1.1 SIZE OF TENSORIZED CIRCUITS
The time and space complexity of evaluating a circuit is linear in its size. The size |c] of a circuit e (Def. A.1) is obtained by counting the number of input connections of each scalar product or sum unit. In other words, it is the number of edges in the computational graph.
If is a tensorized circuit, then its size is obtained by counting the number of connections in its non- tensorized form. Fig. A.1 shows part of tensorized circuit and its non-tensorized form. For sum layers, the number of scalar input connections is the size of its parameterization matrix, i.e., S K if it is parameterized by W E Sx If é is an Hadamard product layer computing L = - Li where each l outputs a K -idimensional vector, then the number of its scalar input connections is N K. In case of Kronecker product layers in the more general Def. A.6, i.e., l @i l, where each &, outputs K K-dimensional vector, then the number of its scalar input connections is K
A.2 TRACTABLE EXACT SAMPLING
Fach sum unit in monotonic PC can be interpreted as finitely discrete latent variable that can as- sume as many values as the number of input connections (Pcharz et al., 2017). As such, a monotonic PC can be by (1) recursively sampling latent variables until input units are reached, and (2) sampling observed variables from the distributions modeled by input units (Vergari et al., 2019a).
hierarchical MM. This allows to sample exactly from the modeled distribution
Such probabilistic interpretation of inner sum units for NPC is not possible, as they can output negative values. However, since NPC²s are smooth and decomposable (Def. A.2), they support efficient marginalization and hence conditioning (Proposition 1). This allows us to still sample exactly from the modeled distribution via inverse transform sampling. That is, we choose variable ordering X1,X2, X2,... XD and sample them in an autoregressive fashion, i.c., I1 p(X1), I2 ~ p(X2 æ1), .. DD ~ p(XD 21,..., ID-1), which is still linear in the number of variables.
B PROOFS
B. SQUARING TENSORIZED CIRCUITS
Proposition B.1 (Correctness of Alg. 1). Let be tensorized structueeddeccompssabbe circuit (Def. 1 or its generalization in Def. A.3), then Alg. I recursively constructs the layers of the squared tensorized PC e² such that e is also structured- decoureodddeommpaabeleee
Proof. The proof is by induction on the structure of c. Let be a sum layer having as input é; and computing We, with W E Sx and e; computing an output in IR.. If l is the last layer of e (i.e.,
17

---

if l Published as a conference paper at ICLR 2024
the output layer), then S = 1 since outputs scalar, and the squared layer E must compute
e² (W&) (W&) - (W @ () @ 6) - (W @ w)&.
which requires squaring the input layer 4. By inductive hypothesis the squared circuit having e output layer is structuredddecompsaabbe hence also the squared circuit having f² as output layer must be. l is a non-output sum layer, we still require computing the Kronecker product of its input layer. The squared layer L² is again a sum layer that outputs a 5 dimensional vector, i.e.,
t = t l (W&) & (WE) = (W & () & L) (W W)e?
via mixed-product property (L11-15 in Alg. 1). Let l be a binary' Hadamard product layer comput- ing Lü for input layers Li Eú each computing a K K-dimensional vector. Then, the squared layer L² computes the Hadamard product between K di-diinnsooaal vectors, i.e.,
e = (4 + Lnj &
(&
En) = (4, & 4j (La & Li) ff O
via mixed-product property with respect to the Hadamard product. By inductive hypothesis E and E are the output layers of structured- decrrre-dcccmpaablllee circuits depending on a disjoint sets of variables. As such, the circuit having e² as output layer maintains structured- -eeoouoodide (L6-9 in Alg. I). For the base case we consider the squaring of an input layer l that computes K functions over some variables Y C X. We replace l with its squaring Le which encodes the products Si( J(YY), 1 S i S K, by introducing K22 functions Pij such that Pij (Y) f((Y),,(Y) (L2-4 in Alg. 1).
Squaring Kronecker product layers. In the case of & being a binary Kronecker product layer instead as in the more general Def. A.6, then the squared layer l computes the Kronecker product between 2 -dimensional vectors up to permutation of the entries, i.e.,
e (c, Ln) (& & (n) R ((4 E,) (Cu 4n) R (e
by introducing K x Ka permutation matrix R whose rows are all zeros except for one entry set to 1. which reorders the entries of E @ c as to recover the equality in Eq. (6). Note that such permutation maintains decomposability (Def. A.2), and its application can be computed by a sum layer having R as fixed parameters. Moreover, by inductive hypothesis, the squaring circuit having e² as output layer is still structured -ei.ureedddcomppabblll Finally, Alg. B.1 generalizes Alg. as to support the squaring of Kronecker product layers as showed above (L10-11 in Alg. B.
Algorithm B.1 square TensorizedCircuitte R)
Input: A tensorized circuit (Def. A.6) having output layer and defined on a tree RG rooted by R.
Output: The tensorized squared circuit defined on the same tree RG having la as output layer computing ( l.
I: if é an input layer then
10:
else return R (ef @ L where R is
2: l. computes K functions (R)
11:
a permutation matrix (see proof of Prop. B.
3: return An input layer e computing all R²
12:
else
D> & is sum layer {(e, R)} + getlnputs( R)
4:
product combinations (R)
13:
5:
else é is a product layer then
14:
L? SquuareTensooiieddCiruiiitt R)
6:
[(e, R2), (&g, R < getinputs R)
15:
W E R $x x +- getParameters(()
7:
L <- square TensorizedCircuit( 4, Ri)
W' E sx + W & W
8:
E square TensorizedCirruitt.. En. R.) then return O
16:
17:
return W'e
B.2 TRACTABLE MARGINALIZATION OF NPC
Proposition 1. Let be a tensorized structured tions computed by each input layer can be tractably integrated. Any marginalization of c² obtained via Alg. requires time and space O(L M²), where L is the number of layers in and M is the maximum time required to evaluate one layer in e (as detailed in App. A.1.1).
circuit where the products of func-
Without loss of generality, we assume product layers have exactly two layers inputs.
18

---

Published as a conference paper at ICLR 2024
Proof. Given by hypothesis. Prop. B.1 ensures that the PC built via Alg. 1 computes c² and is defined on the same tree RG (Def. 2) of c. As such, c² is seancturedddecomposaadd argument about and c² in their
and hence also
smooth and decomposable (see Def. A.3). Now, make non-tensorized form (Def. A.1) as to leverage Prop. A. for tractable marginalization later. The size of is |c| E O M), where I. is the number of layers and M the maximum number of scalar input connections of each layer in с (see App. A.1.1 for details). The size of c² is therefore |oc| E OLL ) since Alg. I squares the output dimension of each layer well as the size of the parameterization matrix of each sum layer. Since c² is smooth and decomposable and the functions computed by its imput layers can be tractably integrated, then Prop. A.1 ensures we can marginalize any subset of variables in time and space |c OLL M²).
B.3 REPRESENTING PSD MODELS WITHIN THE LANGUAGE OF NPC²s
Proposition 2. A PSD model with kernel function K, defined over data points, and parameterized by PSD matrix A, can be represented as mixture of squared NMMs (hence NPC?s) in time (dd))
Proof. The PSD model computes non non-negative function f(x; A, k) = k(x) Ax(x), where n(x) = [x(x,
x(x, x())] E Fd with data points x .(.......'""" and A E Rddd is PSD. Let A Ei= N be the eigendecomposition of A with rank r. Then we can rewrite f(x; A, K.) as
f(x:A, xx))
i=1 Nun,, x(x) E A (uTx(x))
where X, 0 are positive eigenvalues. Therefore, such PSD model can be represented mono- tonic mixture of r I d squared NMMs (Eq. (2)), whose d components computing ks k(x) are shared. The cigendecomposition of A can be done in time Odd)) and materializing each squared NMMs (e.g., as in Fig. 1) requires time and space (dd). Note that if A = uu is a rank-1 matrix, then f(x; A, m)) = (u' x(x))² is exactly a squared NMM whose components compute xxx).
B.4 RELATIONSHIP WITH TENSOR NETWORKS
In this section, we detail the construction of a tensorized structured- decooooodddee circuit (Def. 1) that is equivalent to matrix product state (MPS) tensor network (Pérez-García et al., 2007), as we mention in Sec. 4. As such, the application of the Born rule to retrieve a probabilistic model called Born machine (BM) (Glasser et al., 2019) is equivalent to squaring the equivalent circuit (Sec. 3).
Proposition 3. A BM encoding D-dimensional tensor with m states by squaring rank r MPS can be exactly represented as a structured deoecuureddecompsaabele NPC² in O(D k*) time and space, with l < (in(rr,mr))
Proof. We prove it constructively, by using a similar transformation used by Glasser et al. (2019) to represent a non-negative MPS factorization as an hidden Markov model (HMM). Let (Xi.... }D} be a set of discrete variables each taking values in (l,..., m.. Let T be ten- sor with -i-dimensional indices. Given an assignment x = (II to X, we factorize T via rank MPS factorization, i.c.,
T FDl
Σ 1==
Σ fD-1=1
A / 12) AD(ED.iD-1
where AI, An E Raxr and A, E Rmxxxx with < j < D. for indices (i....., in- and denoting indexing with square brackets. To reduce T to being computed by tensorized structured- decomposable circuit c, i.c., such that c(x) = T[ xD] for any x, we perform the following construction. First, perform a canonical polyadic (CP) decomposition (Kolda & Bader, 2009) of each A, with < < D, iee.
Ay 2-11,
B
19

---

Published as a conference paper at ICLR 2024
where lo I minfr? mr) } is the maximum rank of the CP decomposition (Kolda & Bader, 2009), and V E mm By E I 1x* C3 E R Then, we "contract" each C2 with By+1 by computing
W Wylsi, E Bo 6=1
with W E Rix for <j < D -1 In addition, we "contract" CD-1 with Ad by computing
VDlED. Σ -o-Lib--sso-iAAlDo
1D-1=1
In addition, for notation clarity rename B2 with W and A with V1. By doing so, we can rewrite Eq. (7) as a sum with indices {11, Sp-,1 over products, i.e.,
&
T..,....,,
Vi h)
Wi [1, 82 (2,
4=1
8==1
W SD-3.
SD SD-2=1
Σ ap-1=1
W wo..basbo..Vb.loooo..bbbbbb...e
Fig. B.1 shows an example of such MPS factorization via CP decompositions. We see that we can encode the products over the same indices using Hadamard product layers, and summations over indices {i,, .............................. ; } with sum layers parameterized by the W j, with و precisely, the sum layers that sum over 82 and DD-1 are parameterized by matrices of ones. Each V with 1 S < D is instead encoded by an input layer depending on the variable X, and computing functions (X,) such that fi(z,) tensorized circuit constructed in this way is dirccporeddeecommpoabbll as it is defined on a linear tree RG (e.g., Fig. 2a) induced by the same variable ordering implicitly stated by the MPS factorization (from left to right in Eq. (7), see App. B.4 for details). Fig. B.2 shows the circuit representation corresponding to the MPS reported in Fig. B.lc.
1. More
V Vz, 4]. with < r if
and < < k: if > 1. The
Finally, note that the number of parameters of such tensorized circuit correspond to the size of all (W, ) and (V,) introduced above, i.e., overall O(D 1.2) with S min(r², mr). Moreover, the CP decompositions the beginning can be computed using iterative methods whose iterations require polynomial time (Kolda & Bader, 2009). To retrieve an equivalent BM, we can square the circuit constructed in this way using Alg. 1, which results in a circuit having size ((D-k)) (see Prop. B.1). A similar proof can be carried out for showing reduction of other tensor network structures that can be squared efficiently, such as tree-shaped networks (Cheng al., 2019).
B
C
B
C2
W
W
Ve
Aa
Aa
A
A
V
V
A
V
V
V
Xa
Xa
X4
X
X1
X
X
X1
Xi
(a)
(b)
(C)
Figure B.1: Further decomposing a matrix product state (MPS) via CP decompositions. Tensor networks are represented here using the Penrose graphical notation, where circles denote tensors and their connections denote summations over shared indices, and with variables X,, X2, Xa. Xa denoting input indices. Given MPS (a), we perform CP decomposition of A₂ and Ag (b). Red edges denote additional indices given by the CP decompositions. Then, we rename A with V1, B2 with W₁. 1. Finally, we contract C2 with B3, and C3 with A, resulting in tensors We and V4, respectively (c). Fig. B.2 shows the tensorized circuit corresponding to such tensor network, where V1, V2, Va, V. and W1, Wa parameterize input layers and sum layers, respectively.
20

---

squared structured- Published as a conference paper at ICLR 2024
V.Jri
N1.
Xa.
Valsal
Vi
X X
Vilei
X1
X3
(a)
(b)
Figure B.2: Matrix product states (MPS) as dtructured-decomposste circuits. The decom- posed MPS over three variables showed Fig. B. can be immediately represented as tensorized drruttreeddeccompsabbe circuit (a) defined on a linear tree RG (b, matching the colors of layers) having Hadamard product layers and sum layers parameterized by W1, W2 and row vector of ones 1 (for the output sum). Each input layer maps variable assignments 21, Z2, 23, to rows in VI, 22, V3, 44, respectively.
B.4.1 RELATIONSHIP WITH HIDDEN MARKOV MODELS
MPS tensor networks where each tensor A, is non-negative can be seen as inhomogeneous hidden Markov models (HMMs) as showed by Glasser et al. (2019), i.e., where latent state and emitting transitions do not necessarily share parameters. As such, the tensorized structured-dect deccuredddccomppsabbeee circuit c that is equivalent to MPS (see App. B.4) is also inhomogenous HMM if is monotonic.
In Sec. 5 we experiment with tensorized monotonic PC that is an inhomogenous HMM to distill large language model, to leverage the sequential structure of the sentences. We compare it against a NPC that the squaring of a MPS (also called Born machine (Glasser et al., 2019)) or, equivalently, the squaring of inhomogenous HMM-like whose parameters can be negative.
B.5 EXPONENTIAL SEPARATION
Theorem 1. There a class non-negative functions F over variables that can compactly represented shallow squared NMMs (and hence squared non-monotonic PCs) but for which the smallest strctured-deccompssbble monotonic PC computing any F E F has size (0(X))
Proof. For the proof of Theorem 1, we start by constructing F by introducing a variant of the unique disjointees (UDISJ) problem, which seems to have first been introduced by De Wolf (2003). The variant we consider here is defined over graphs, as detailed in the following definition.
Definition B.1 (Unique disjointness function). Consider an undirected graph = (V, where V denotes its vertices and E' its edges. To every vertex E V we associate Boolean variable X, and let Xv = {Xw, E V the set of these variables. The unique disjointness function of G defined as
Σ Xux.
UDISJ.(X.))
1
(8)
The UDISJ function as non-monotonic circuit. We will construct F as the class of functions UDISJG for graphs G E g, where 9 is family of graphs that we will choose later. Regardless of the way the class G is picked, we compactly represent UDISJe decomposable (Def. A.3) and non-monotonic circuit as follows. First, we represent the function c(Xv) = 1 X,, sum unit computing a((x))) (-1) -6(x)) where
a is a circuit gadget that realizes an unnormalized uniform distribution over the domain of variables in Xv. i.e a(Xy) [I 0} + 1(X, 1}) where 1 1(X, = 0} (resp. 1 1(X, = 1)) is indicator function that outputs when X,, is set 0 (resp. 1);
21

---

Published as a conference paper at ICLR 2024
b is another sum unit whose imputs are product units over the input units
1 1(x,, = 1]. 1xx, = 1} if there is an edge ue in G. ie.. b(Xv) = Ewdgg 1(X, 1} 1 1(x,11)
Note that b may not be smooth, but we can easily smooth it by adding to every product an additional input that is a circuit similar to a that outputs for any input X where X = Xv \ {Xw, ),), Since is grruttredddecooppssee
(Def. A.3), we can easily multiply it with itself to realize e that would be still a structured dec.urdodddooooabbllll circuit whose size is polynomially bounded as |e*| e ((cl)) (Vergari et al., 2021). Note that in this case have that |c) is polynomial in the number of variables (or vertices) [xy by the construction above. Furthermore, note that c² is non-monotonic as one of its sum unit has negative parameters (i.e.. 1) to encode the subtraction in Eq. (8).
The lower bound for monotonic circuits. To prove the exponential lower bound for monotonic circuits in Theorem 1, we will use an approach that has been used in several other works (Martens & Medabalimi, 2014; de Colner & Mengel, 2021). This approach is based on representing a decom- posable circuit (and hence are balanced products, as formalized next.
www.tuuredddccoooaabblll one) as a shallow mixture whose components
Definition B.2 (Balanced decomposable product). Let X be a set of variables. A balanced de- composable product over X is function from X to R that can be written as f(Y) x ((Z) where f and h are functions to E, is an alias for the product (when used to multiply functions from now on), and (Y, Z) is balanced partitioning of X, i.e. Y J X, Y Z Ø with |X|/3 Y|, |Z| S 2
Theorem B.1 (Martens & Medabalimi (2014)). Let F be non-negative function over Boolean variables X computed by a smooth and decomposable circuit c. Then, F can be written as a sum of N balanced decomposable products (Def. B.2) over X, with N < [c] in the form"
N
F(X)
Σ (a() x (z,)
where (Y,, Zạ) is balanced a partitioning of X for 1 S k I N. If c is structured-decompssabbeee the N partitions {(Y,, k, > are all identical. Moreover, if e is monotonic, then all fk. hg only compute non-negative values.
Intuitively, Thm. B.1 tells that to lower bound the size of e we can lower bound N. To this end, first encode the UDISJ function (Eq. (8)) as sum of N balanced products and show the exponential growth of N for particular family of graphs. We start with special case for a representation in the following proposition.
Proposition B.2. Let G, be a matching of size n, i.e., a graph consisting of n edges none of which share any vertices. Assume that the UDISJ function (Eq. (8)) for Gn, is written as sum of products of balanced partitions
(Y,
-
E fu(Y) (z),
where for every edge ur in G, we have that X,, E Y and X, Z. and fx. hy are non-negative functions. Then N 20(n)
To prove the above result, we will make an argument on the rank of the so-called communication matrix, also known as the value matrix, for function F and fixed partition (Y, Z).
Definition B.3 (Communication matrix, or value matrix (de Colnet & Mengel, 2021)). Let F be a function over (Y, Z), its communication matrix Mp is a 2| x 2 žl matrix whose rows (resp. columns) are uniquely indexed by assignments Y (resp. Z) such that for a pair of index (iv,jz). the entry at the row iy and column jz in M is Fi)..
'In Martens & Medahalimi (2014), Theorem 38, this result is stated with N s |c|2. The square materializes from the fact that they reduce their circuits to have all their inner units to have exactly two inputs, as we already assume, following de Colnct & Mengel (2021).
An index iy (resp. jz) is complete assignment to Boolean variables in Y (resp. Z). See Example 1.
22

---

Published as a conference paper at ICLR 2024
Example 1. Let consider simple matching 6 vertices, where Y correspond the first vertices, and Z to the last 3, and where there an edge between the first, second and third vertices of Y and Z. The matrix Mr is an 8-by-8 matrix, row and column for each assignment of the binary variables associated to each vertex; it is given by
Y
000
100
010
001
110
101
011
111
000
1
1
1
100
0
010
1
1
0
1
0
001
I
1
1
0
0
0
0
110
1
0
0
0
0
1
0
0
011
1
1
0
0
1
111
1
0
0
1
1
4
Note that the name UDISJ comes from the fact that Mr(i, if and only if Y and Z share single entry equal to 1. In the following, we will rely on the following quantity.
Definition B.4 (Non-negative rank). The non-negative rank of non-negative matrix A E R=*=" denoted rank+(A), is the smallest l such that there exist nonnegative rank-one matrices {A,) such that A = >m A.. Equivalently, it is the smallest k such that there exists two non-negative matrices B pT** and C x such that A BC.
Given function F written as sum over N decomposable products (see Thm. B.1) over a fixed par- tition (Y, Z), we now show that the non-negative rank of its communication matrix Mr (Def. B.3) a lower bound of N.
Lemma B.1. Let F(X)= = Em fx(Y) (Z) where f& and h& are non-negative functions and let Mp be the communication matrix (Def. B.3) F for the partition (Y, Z), then it holds that
rank+(Mp) N.
Proof. This proof is easy extension of the proof of Lemma 13 from de Colnet & Mengel (2021). Assume w.l.o.g. that (Y) x hy (Z) * 0 for any complete assignment to and Z. Let Mx denote the communication matrix of the function fY- h2 (Z). By construction, Mr = > Mg. Furthermore, since all values in Mr are non-ne non-negative by definition, rank, (M²) is defined for all & and by sub-additivity of the non-negative rank we have that rank (Mr) S
have that
Ek=1 rank (M+). To conclude the proof, is suffieient to show that Mj. are rank-1 matrices, i.e..
rank, = 1. To this end, consider an arbitrary k. Since / YY) ) x hy. (Z) of 0, there is row in
M2 that not row of zeros. Say it is indexed by iy. then its entries are of the form fa (ix) hy (iz)
for varying jz. In any other rows indexed by iy we have fiyy)) ) x hzziz) = (fx(() ff (ix)) X
fi( hz for varying jz. Consequently, all rows are non-negative multiples the iy row, and therefore rank, (M&) 1.
To complete the proof Prop. B.2, we leverage a known lower bound the non-negative rank of the communication matrix of the UDISJ problem. The interested reader find more information on this result in the books Roughgarden (2016), Gillis (2020) and the references therein.
Theorem B.2 (Fiorini et al. (2015)). Let UDISJ function defined in Prop. B.2, and MUDISJ be its communication matrix over partition (Y, 2), then it holds that
(3/2)² < rank4(MMDss
Using Thm. B.2 and Lem. B.I, we directly get Prop. B.2. So have shown that, for a fixed partition of variables (Y, Z), every monotonic circuit encoding the UDISJ function (Eq. (8)) of a matching of size n has size |c| 2 20(a) However, the smallest non-monotonic circuit encoding the same function has polynomial size in n (see the construction of the UDISJ function circuit above). Now, to complete the proof for the exponential lower bound in Theorem 1, we need to find
'If this were not the case could simply drop the term from the summation, which would clearly reduce the number of summands.
23

---

Published as a conference paper at ICLR 2024
function class F where this result holds for all possible partitions (Y, Z). Such function class consists of UDISJ functions over a family of graphs, as detailed the following proposition.
Proposition B.3. There is family of graphs & such that for every graph G, (V E,,) g we have |Vrl | (n). and any monotonic structured -ecpopooadddcoomoobablllle circuit representation of UDISJa, has size 20(())
Proof. We prove it by constructing class of so-called expander graphs, which we introduce next. We say that a graph G (V; E) has expansion there are at least e|V'| edges from V' to V V' in G. it well-known, see e.g. Hoory et al. (2006), that there are constants ε > 0 and d E N and a family (Gn) of graphs such that G, has at least n vertices, expansion & and maximal degree d. We fix such a family of graphs in the remainder and denote by Vn (resp. E,, the vertex set (resp. the edge set) of Gn.
for every subset V' of V of size at most [V//2,
Let be monotonic pectured-dccompssabbee circuit of size N computing UDISJG.. Then, by using Thm. B.I, we can write it as
UDISJ (Y Σ Jx(Y) x (Z)
where (Y, Z) is a balanced partition of Xy. Let V/y fu E Vn X, E YJ and V/2 = fo E V, X, E Z). Then (Vy, Vz) form a balanced partition of Vn. By the expansion of G.. it follows that there are Qnn) edges from vertices in Vy to vertices in Vz. By greedily choosing some of those edges and using the bounded degree of G,, matching between Y and Z, i.c., all edges in Ex, go from to Z and every vertex in Vn, is incident to only one edge in F. Let V. be the set of endpoints in P. and Xv; C Xy be the variables associated to them. We construct new circuit c' from by substituting all input units for variables X, that are not in Xv; by O. Clearly, |e'l S |c| and hence all the lower bounds for |c' are lower bounds for |cl. Let Y = Xy; n Y and Z = Xv: n Z. By construction c' computes the function
can construct an edge set E,, of size Mn)) that is
UDISJ (Y Z)
1 - Σ X
NIE
which corresponds to solving the UDISJ problem over the graph G²2 (V,, E,). From Eq. (9) recover that
UDISJo; (Y,S,,,YY,)) Σ Λ(Y x 14(2)
where f (resp. h() are obtained from fx (resp. hv) by setting all the variables not in Xv: to 0. Since monotonic by construction and Ex (n)) from Prop. B.2 it follows that N 20(n).
Prop. B.3 concludes the proof of Theorem 1, as showed the existence of family of graphs for which the smallest strueureeddeecompssbbe monotonic circuit computing the UDISJ function over variables has size 29(m)) However, the smallest dirutured-decooppsable non- mon-montoniic circuit has size polynomial in whose construction has been detailed at the beginning of our proof. Li
B.6 SQUARING DETERMINISTIC CIRCUITS
In Sec. 4.1 we argued that squaring any non-monotonie, smooth, decomposable (Def. A.2), and deterministic (Def. A.5) circuit yields a monotonic and deterministic PC. As a consequence, any function computed by NPC² that is deterministic can be computed by monotonic and deter- ministic PC. Therefore, we are interested in squaring structured-deccompssabb circuits that are not deterministie. Below we formally prove Proposition 4.
Proposition 4. Let c be smooth, decomposable and deterministic circuit variables X possibly computing a negative function. Then, the squared circuit c² is monotonic and has the same structure (hence size) of c.
24

---

Published as a conference paper at ICLR 2024
Proof. The proof is by induction. Let be product unit that computes Cy (Z)
IkEin(m) Cn (Z,), with Z - X and (Zi...., (nn()))) forming a partitioning of Z. Then its squaring computes c (Z)
[eii (Z,). Now consider a sum unit (Z) = Σ Eiein()) w.o (Z) with _ X and w, E R. Then its squaring computes e (Z) = Eiein(n) Σ ZzEin(n) Wa (z) (Z). Since is deterministic (Def. A.5), for any i.j with i o either c; (Z) or (Z) is zero for any assignment to Z. Therefore, have that
c that computes
C (Z)
Σ 2²et (Z).
(10)
(Ein(n)
This implies that in deterministic circuits, squaring does not introduce additional components that encode (possibly negative) cross-products. The base case is defined on input unit that models a function Sn. and hence its squaring is an input unit that models J By induction c² is constructed from by squaring the parameters of sum units wy and squaring the functions fn modeled by input units, Moreover, the number of inputs of each sum unit remains the same, as we observe in Eq. (10), and thus e² and e have the same size.
C EFFICIENT LEARNING OF NPC
GPU Memory (GiB)
5
1.0
c(x)
Time per batch
Z (xx]dx
0.5
0.0
20
10a
10at BS
10P
Figure C.I: Evaluating the squared circuit representation adds little overhead during training. By learning by MLE (Eq. (4)) and batched gradient descent, the time and space required to compute the partition function Z of c² is constant w.r.t. the batch size (BS) (left). By fixing the batch size to 512 and varying the output dimensionality (K) of each layer (right), the resources needed to compute 7 are similar the ones needed evaluate e (i.e., e(X)). For the left figure, fix K 256 and vary the BS, while for the right figure we fix BS = 512 and vary K. The plots share the y-axis.
In this section, we investigate the computational cost of learning NPC with series of benchmarks, showing that NPC²s add little computational overhead over traditional monotonic PCs (MPCs).
Efficient renormalization in practice. As suggested by the MLE objective (Eq. (4)), squaring the tensorized circuit with Alg. 1 is only required to compute the partition function Z = e²(x)) ]xx. In addition, need to compute Z only once per parameter update via gradient ascent, as Z does not depend on the training data. For these reasons, the increased computational burden of evaluating squared eircuit (see Proposition 1) as compute Z is negligible, and it is independent w.r.t. the batch size. Fig. C.1 illustrates this aspect by comparing the time needed to evaluate e on a batch of data and to compute the partition function Z. The results showed in Fig. C. are obtained by running benchmarks on NPC²s that are similar in size to the ones we experiment with in Sec. 5. That is, benchmark mixture of 32 NPC2s, each having an architecture built from a randomly-generated tree RG (see App. F for details) approximating the density function of BSDS300 (the data set with highest number of variables, see Table H.1). The input layers compute Gaussian distributions.
Training efficiency on UCI data sets. We benchmark the computational cost of learning NPC on UCI data sets (Table H.1). Fig. C.2 compares time and memory required to learn the best NPC and MPCs showed in Fig. 4, while Fig. C.3 compares time and memory required to learn them in a worse scenario for NPC where the batch size small and the layer dimensionality large, as NPC's benefit from using large batch sizes discussed above. NPC2s add very little overhead during training in most configurations when compared to MPCs, as computing the partition function Z is comparable to evaluating MPCs takes more time and memory to compute Z (times are 6ms and 121ms, while memory allocations 0.6GiB and 5.8GiB), but it is only slightly more than the cost of computing for MPCs (time
batch of samples. In particular, on Gas (x) 8). NPC
25

---

Published as a conference paper at ICLR 2024
144ms and memory 4.4GiB). Moreover, note that NPC's achieve about x2 improvement on the oog-likelihood on Gas. On the much higher dimensional data set BSDS300 ( 63) instead, we found that training NPC is even cheaper it requires fewer parameters while still achieving higher log-likelihood (128.38 rather than 123.3).
Hardware and significance of benchmarks. The benchmarks mentioned above and illustrated in Figs. C.1 to C.3 have been run on a single NVIDIA RTX A6000 with 48GiB of memory. The measured times are averaged over 50 independent circuit evaluations.
GPU Memory (GiB)
(9)
x
= /e(x]dx
10-1
(x]
@25.3
per
2 41
2692
10-2
20 40
60
X
20
40
60
[X
Figure C.2: NPC3s add little overhead during training on real-world data sets, while improving log-like oogllikeishoods. We evaluate time and memory required by monotonic PCs (MPCs) and NPC*s perform one optimization step on UCI data sets (Gas, Hepmass, MiniBooNE, BSDS300) with number of variables |X| and using the best hyperparameters found (see App. H.3). We benchmark computation of c(x) by MPCs and (x) by NPC²s on batch x of data (left), as well as the partition functions Z for both models (right), and label the data points with the final log-likelihoods achieved by the corresponding models (as also reported in Fig. 4). The plots share the y-axis. For NPC?s, computing the partition function Z is more expensive both in time and memory (right), but is still very similar to the cost of evaluating c(x) or c² (x) (left).
GPU Memory (GiB)
c(x)
Z [ /
10
e"(jddxx
per
10-2
40
X
40
X
Figure C.3: NPC3s add little overhead during training even with relatively small batch sizes. We evaluate time and memory required by monotonic PCs (MPCs) and NPC²s to perform one opti- mization step on UCI data sets (Gas, Hepmass, MiniBooNE, BSDS300) with respect to the number of variables X and using the same hyperparameters (512 batch size, 512 layer dimensionality, and Gaussian input layers). The plots share the y-axis. The cost of computing c²(xx on a batch x of data by NPC is only slightly higher than the cost of computing c(x) by MPCs (left), while the cost of computing Z for NPC²s is comparable to evaluating c² (x) or c(x) (right).
D THE SIGNED LOG-SUM-EXP TRICK
Scaling squared non-monotonic PCs to more than a few tens (resp. hundreds) of variables without performing computations in log-space is infeasible in 32-bit (resp. 64-bit) floating point arithmetic, as we illustrate in Fig. D. For this reason, we must perform computations in the log-space even in presence of negative values. The idea is to represent non-zero outputs in terms the element-wiss logarithm of their absolute value log ly and their element-wiss sign sign(y) 11, i.e., such that y sign(y) exp(log lyl)-
R of each layer
26

---

Published as a conference paper at ICLR 2024
+.00
1337
654
Figure D.I: Squared non-monotonie PCs cannot scale without performing computations in log-space. Parti- tion functions (and their natural logarithm) of squared non- monotonic PCs having Gaussian input units, with increasing number of variables V and having depth [logz V computed using 32-bit and 64-bit floating point arithmetic.
1063
10
240
10'00
Number of Variables
In practice we evaluate product and sum layers according to the following evaluation rules. Given an Hadamard product layer L, then it computes and propagates both log |4] Ei= log [&,] and sign(() i- sign(L;) for some inputs { Given sum layer & parameterized by W
R and having l' input layer, then it computes and propagates both log E a + log |s| and sign(e) = sign(s) where and s are defined as
1 max flog [e')
W (sign(e") @ exp(log [e') -e]=
by assuming + O, 1 denoting S-dimensional vector of ones, L']i denoting the j-th entry of the output of E,, and exp being applied element-wise. We call signed log- log-sum-exp trick the evaluation rule above for sum layers, which generalizes the log-sum-exp trick (Blanchard et al., 2021) that is used to evaluate tensorized monotonic PC architectures (Peharz et al., 2020a).
For the more general definition of tensorized circuits instead (Def. A.6), given Kronecker product layer L, then it computes both log | denotes an operator similar to the Kronecker product but computing sums rather than products.
+ N log [e,] and sign(E) X &/ sign(L.), where +
E SPLINES AS EXPRESSIVE INPUT COMPONENTS
Figure E.1: Splines represent class of flexible non-linear functions. A quadratic (k = spline (in black) over 4 knots chosen uniformly in (0, 1) (i.e, 0.2, 0.4, 0.6 and 0.8) is computed by linear combination of k + 7 distinct basis functions (each colored differently).
0.0
0.2
0.4
Polynomials defined on fixed intervals are candidate functions to modeled by components (resp. input layers) of squared NMMs (Sec. 2) (resp. NPC²s Sec. 3). This is because they can be negative function and their product can be tractably integrated. In particular, we experiment with piecewise polynomials, also called splines. An univariate spline function of order k is piecewise polynomial defined on a variable X, and the n values of where polynomials meet are called knots. B-splines of order l are basis functions for continuous spline functions of the same degree. In practice, represent any spline function f of order i defined over n knots inside an interval (a, b) as a linear combination of
basis functions, i.e.,
1 n+k+1
-(x==
(,Br((X)
(11)
where o; E IR are the parameters of the spline and (X) are polynomials of order k: (i.e., the basis of f), which are unequivocally determined by the choice of the n knots. In particular, each B (X) nog-neeative polynomial that recursively defined with the Cox-de-Boor formula (de Boor, 1971; Piegl & Tiller, 1995). Given two splines J.g of order & defined over knots and represented in terms of n + &e + basis functions in Eq. (11), we can write their product integral
1 (xx)xxx)xx Σ n+++1
n++++
0: 1
(x dx
(12)
1=
27

---

Published as a conference paper at ICLR 2024
where 0g R (resp. By E IR) denote the parameters of (resp. 9). Therefore, integrating product of splines requires integrating products of their basis functions. Among the various way of computing Eq. (12) exactly (Vermeulen et al., 1992),
do it in time On k2) by representing the product B (X) J,,x(( as the basis polynomial another B-spline of order 2k + 1, and finally integrating it in the interval of definition. Fig. E.1 shows example of spline.
Since each B is non-negative, we can use B-splines as components (resp. modeled by input layers) of traditional MMs (resp. monotonic PCs) by assuming each spline parameter os be non- negative. This is the case of monotonic PCs we experimented with in Sec. 5, where non-negativity guaranteed via exponentiation of the parameters.
F TREE REGION GRAPHS
X, X, X₁
X Xx.
X X3.
X
X₂.
X X
Xx
X
X
Figure F.1: Different ways to construct region graphs. The left figure illustrates linear (LTT) region graph (Def. 2) over four variables, which decomposes variables one by one. The right figure shows a possible binary tree (RT) region graph over five variables, which recursively splits them.
Since we require structured-decompossse decomposabilyy to square circuits (see Sec. 3.2), we construct their architecture based on tree RGs (Def. 2). We choose to experiment with two kinds of tree RGs: binury free (BT) and linear free (LT). Following Peharz et al. (2020b), the BT is built by recursively partitioning variables evenly and randomly until regions with only one variable are obtained. The LT is built by (1) shuffling the variables randomly and then (2) recursively partitioning variables one by one, i.e., a set of variables {X,.... Xp} } is partitioned in (X,) and ( (X++1.... ND) } for 1 S < D 1. Fig. F.1 shows examples of LT and BT RGs. Note that the LT is the same on which the circuit representation of matrix-produee states (MPS) (Pérez-Garefa et al., 2007) and TTDE (Novikov al., 2021) depend (see also Sec. 4 and App. B.4).
G ADDITIONAL RELATED WORKS
Squared neural family (SNEFY) (Tsuchida et al., 2023) have been concurrently proposed as a class of models squaring the 2-norm of the output of single-hidden-layer neural network. Under certain parametric conditions, SNEFYs can be re-normalized as to model a density function, but they do not guarantee tractable marginalization of any subset of variables as our NPC²s do, unless they encode a fully-factorized distribution, which would limit their expressiveness. Hence, SNEFYs can be employed in our NPC*s to model multivariate units in input layers with bounded scopes.
The rich literature of PCs provides several algorithms to learn both the structure and the parameters of circuits (Poon & Domingos, 2011: 1; Peharz al., 2017: Di Mauro et al., 2021: Dang et al., 2021; Liu & Van den Broeck, 2021; Liu et al., 2023). However, in these works circuits are always assumed to be monotonic. A first work considering subtractions is Dennis (2016) which generalizes the ad- hoc constraints over Gaussian NMMs (Zhang & Zhang, 2005) to deep PCs over Gaussian inputs by constraining their structure and reparameterizing their sum weights. Shallow NMM represented as squared circuits have been investigated for low-dimensional categorical distributions in Loconte et al. (2023). Concurrently, Sladek et al. (2023) investigated interleaving PSD models and PCs to represent deep NMMs in low-dimensional settings. The resulting model can be interpreted sum of squared circuits. Circuit representations encoding probability generating functions allow negative coefficients in symbolic computational graphs (Zhang et al., 2021), differently from them
28

---

Published as a conference paper at ICLR 2024
encode probability densities and masses. Non-monotonic PCs have been recently proven to be able to compactly represent determinantal point processes, for which no compact monotonic circuit representation exists (Broadrick al., 2024).
The relationship with tensor networks and PCs has been hinted (Glasser et al., 2019) and (Novikov et al., 2021) for matrix-product states. However, they did neither provide formal duction nor a highlighted the structural properties needed to tractably perform the squaring and marginalize variables. Glasser et al. (2019) showed number of bounds over ranks of matrix-product states and Born machines, however they do not provide a separation between NPC²s and monotonic PCs as we do, nor their results generalize any region graph, including tree-shaped networks as our Theorem does for structured decomposable monotonic PCs. Born machines and squared tree- shaped tensor networks have been explored for distribution estimation (Han et al., 2018; Cheng al., 2019) but, differently from our NPC they were not equipped with non-linearithe at the inputs and their evaluation was limited to small scale binary data. Bailly (2011) proposed squared probabilistic automata that are similar to Born machines but supporting inputs of any length by sharing the same parameter tensors across steps. By applying the construction used to show Proposition 3, we can represent such models as NPC²s where the parameters of sum and input layers shared. Jaini et al. (2018) draw a connection between monotonic PCs, latent tree models (Choi et al., 201 1) and hierarchical tensor mixture models (Hackbusch, 2012) with non-negative parameters, showing exponential separation between shallow and deep monotonic circuits.
29

---

Published as a conference paper at ICLR 2024
GT
MPC
MPC²
NPC²
GT Funnel
MPC
MPC
NPC²
Rings
Cosine
Banana
Average LL
MPC
2.00
2.35
2.400
MPC
-2.
2.25
2.40
2.425
NPC
K
10
10
Figure H.1: Negative parameters increases the expressiveness of NPC's. From left to right (above) and for each bivariate density, we show the ground truth (GT) and estimation by mono- tonic PC (MPC), squared monotonic PC (MPC),, and NPC² having input layers computing quadratic splines (App. E) and with the same number of parameters. Moreover, (below) we show the average log-likelihoods (and one standard deviation with 10 independent runs) unseen data achieved by monotonic MPC, a squared monotonic MPC?, and a NPC by increasing the dimen- sionality of imput layers K.
H EXPERIMENTAL SETTINGS AND COMPLEMENTARY RESULTS
H.1 CONTINUOUS SYNTHETIC DATA
Following (Wenliang et al., 2019) experiment with monotonic PCs, their squaring and NPC?s on synthetic continuous 2D data sets, named rings, cosine, funnel and banana. We generate each synthetic data set by sampling 10 10_0000111000 000 training/validatiionness samples. In these periments, we are interested in studying whether NPC²s can be more expressive in practice, with- making assumptions
the data distribution and therefore choosing parametric distributions as components. For this reason, we choose components computing the product of univariate spline functions (see App. E) over 32 knots that are uniformly chosen in the data domain. In particular, for monotonic mixtures we restrict the spline coefficients to be non-negative.
Learning and hyperparameters. Since the data is bivariate, the tree on which PCs are defined on consists of just one region that is split in half. All models are learned by batched stochastic gradient descent using the Adam optimizer with default learning rate (Kingma & Ba, 2015) and batch size of 256. The parameters of all mixtures are initialized by sampling uniformly between 0 and 1. Furthermore, monotonicity in (squared) PCs ensured by exponentiating the parameters.
Fig. 3 shows the density functions estimated from data sets rings and cosine, when using 8 and 12 components, respectively. Moreover, Fig. H.1 report the log-likelihoods and other density functions learned from data sets funnel and banana, when using components.
H.2 DISCRETE SYNTHETIC DATA
For our experiments investigating the flexibility of input layers of NPC²s (Sec. 2) in of discrete data (Sec. 5), we quantize the bivariate continuous synthetic data sets reported in App. H.1. That is, we discretize both continuous variables using 32 uniform bins each. The resulting target distribution is therefore probability mass function over two finitely discrete variables.
We experiment with monotonic PCs, their squaring and NPC's with two families of input layers. First, we investigate very flexible input layers for finitely discrete data: categoricals for monotonic PCs and embeddings for NPC*s. Second, we experiment with the less flexible but more parameter- efficient Binomials. The learning and hyperparameters setting are the same used for the continuous data (see App. H.1). Fig. H.2 shows that there is little advantage in subtracting probability mass with respect monotonic PCss having categorical components. However, in case of the less flex- ible Binomial components, NPC's capture the target distribution significantly better. This is also confirmed by the ligeliiesssoods unseen data, which show in Fig. H.2.
30

---

Published as a conference paper at ICLR 2024
CATEGORICAL CATEGORICAL
BINOMIAL
BINOMIAL
CATBGORICAL
BINOMIAL
GT
MPC
MPC²
NPC
MPC
MPC²
NPC²
Rings
Cosine
Funnel
Banana
Average LL
-6.1
5.50
5.225
4.950
MPC
6.2
5.250
2PC
6.3
5.75
5.275
4.975
NPC²
K-
5
10
5
10
10
(a) Mixtures with categorical or embedding components.
Rings
Cosine
Funnel
Banana
Average LL
6.25
5.3
4.95
MPC
5.00
MPC²
-6.50
-5.4
NPC
6.00
5.05
K 50
100
50
100
50
100
50
100
(b) Mixtures with Binomial components.
Figure H.2: Negative parameters increases the expressiveness NPC From left right (above) and for each bivariate distribution, we show the ground truth (GT) and its estimation by monotonie PC (MPC), squared monotonic PC (MPC*), and NPC having input layers comput- ing categoricals (embeddings for NPC²s) and with the same number of parameters. Moreover, we show the average log-likelihoode (and one standard deviation with 10 independent runs) on unseen data achieved by monotonic MPC, a squared monotonic MPC², and a NPC with either categori- cal (a) or Binomial (b) components and by increasing the dimensionality of input layers K.
H.3 UCI CONTINUOUS DATA
Data sets. In Sec. we evaluate NPC for density estimation on five multivariate UCI data sets (Dua & Graff, 2017): Power (Hebrail & Berard, 2012), Gas (Fonollosa et al., 2015), Hepmass (Baldi et al., 2016), MiniBooNE (Roe et al., 2004) and BSDS300 patches (Martin et al., 2001) by following the pre-processing by Papamakarios et al. (2017). Table H. reports their statistics.
Number of samples
Table H.l: 1: UCI data statistics. Di- mensionality D and number of samples of each data set split after the prepro- cessing by Papamakarios et al. (2017).
D
train
validation
test
Power
1.659,917
184,435
204,928
Gas
8
852,174
94,685
105.206
Hepmass
21
315,123
35,013
174,987
MiniBooNE
43
29,556
3,284
3,648
BSDS300
1,000,000
50,000
250.000
Models. We compare monotonic PCs and NPC²s s in tensorized form (Def. 1) for density estimation.
The tensorized architecture for both is constructed based on either the binary tree (BT) or linear tree (L.T) RGs (see App. F). In addition, since both RGs randomly-conssruated, instantiate
31

---

Published as a conference paper at ICLR 2024
eight of them by changing the random seed. By doing so, monotonic PCs consist of mixture of tensorized monotonic PCs each defined on a different RG. Conversely, our NPC's consist of a mixture (with non-negative parameters) of tensorized NPC2s, each constructed by squaring circuit defined on a different RG. To ensure a fair comparison, monotonic PCs and NPC have the exact same structure, but NPC allow for negative parameters via the squaring mechanism (see Sec. 3).
Hyperparameters. We search for hyperparameters by running a grid search with both monotonic PCs and NPC For each UCI data set, Tables H.2 and H.3 report the possible value of each hyperparameter, depending on the chosen RG. In case of input layers modeling spline functions (see App. E), we use quadratic splines and select 512 uniformly the domain space.
Parameters initialization. We found NPC to be more sensible to the choice of the initialization method for parameters than monotonic PCs. The effect of initialization in monotonic PCs is not well explored in the literature, and it is even more unclear for NPC²s as parameters are allowed to be negative. In these experiments, we investigated initializing NPC²s by independently sampling the parameters from a normal distribution. However, we found NPC²s to achieve higher log- logllioels they are initialized with non-negative parameters only, i.e. by sampling uniformly between 0 and 1. However, in App. H.5 we show they still learn negative parameters when converging. Note that our work is a first attempt to learn non monooonot PCs at scale, thus it opens interesting future directions how initialize and learn NPC?s, well as how to regularize them.
Table H.2: Hyperparameter grid search space for each UCI data set (for BT experiments). Each data set is associated to lists of hyperparameters: learning rate, the dimensionality of layers in tensorized PCs (K), batch size, and whether input layers compute Gaussian likelihoods or spline functions (see App. E).
Data
Learning rate
K
Batch size
Input layer
Power
[32..... 512]
[512, 1024, 2048)
Gas
1024
[512, 1024, 2048, 4096]
Hepmass MiniBooNE
[0.01, 0.005]
32,
512)
[512, 1024, 2048
[Gaussian, splines]
32, 512
512, 1024, 2048
BSDS300
32. 256
512, 1024, 2048)
Table H.3: Hyperparameter grid search space for each UCI data set (for LT experiments). Each data set is associated to lists hyperparameters: learning rate, the dimensionality of layers in tensorized PCs (K), ) batch size, and whether input layers compute Gaussian likelihoods spline functions (see App. E).
Data I Learning
K
Batch size
Input layer
Power
Gas
Ilepmass MiniBooNE BSD$300
[0.005,0 0.001]
(32.... 512]
[512, 1024, 2048]
[Gaussian, splines]
Power
Gas
Hepmass
MiniBooNE
BSDS300
32
64
128
256
2
512
1024
0.25 0.50
0
-22.5-200 -35-
25 110 120
Figure H.3: Negative parameters make squared non-monotonic PCs more expressive than squared monotonic PCs. NPC's (+2, vertical) generally achieve higher log-likelihoods than squared monotonic PCs (+2, horizontal) when paired with the same number of units per layer K. as shown by the presence of more points in the upper triangle than the lower triangle for most data sets. Blue circles and red diamonds refer to runs with Gaussian (G) and spline (S) input layers respectively, and darker hues indicate larger K. The dashed grey line represents the points of cqual likeliiel for both the NPC and the squared monotonic PC.
32

---

Published as a conference paper at ICLR 2024
Table H.4: Squared non-monotonic PCs can be more expressive than monotonic PCs. Best average test loglliilsssooss and two standard errors achieved by monotonic PCs (MPC) and NPC's built either from randomized linear tree RGs (LT) or from randomized binary tree RGs (BT) (see App. H.3), when compared to baselines. MPC, MPC and NPC² were experimented with both Gaussian (G) and spline (S) node input layers. means no values were originally provided.
Power
Gas
Hepmass
MiniBooNF:
RSDS300
MADE
.3008 +0.03
3.56 40.04
20.9% +0.02
15.59 44.50
148.85 #0.28
RealNVP
0.17 #0.01
8.33 +0.
-18.71 +0.02
-1384 +0.52
153.28 +1.78
MAF
NSF
0.66 =0.01
13.09 +0.02
.1400 #0.03
99.2 +0.48
157.31 +0.28
Gaussian
-7.74 =0.02
-3.58 40.75
-27.93 10.02
37.24
96.67 40.25
EiNet-LRS
0.36
4.79 +f
-22 =f
-34.21 =1
TTDE
0.46
8.93 #
-21 24.34
-28.77 =f
143. 14.300.0
(LT) 0.51 2.01
0.24 1:01
6.73 1.03
-2.55
a.02
-2.07
a.02
23.09
0.02
-3248
4.44
-37.33
a.46
123.15 1.28
116.90 2:28
MPC² (LT) 0.49
NPC (IT)
0.01
0.43
9.00
4:02
3.03 +.02
20.66
+.02
21.53
26.68
4.42
-29.36
112.99
+.29
120.11
4:29
MPC (BT) 0.57 2.01 0.322.01
5.56 1.03
-2.55
a.02
22.45
a.02
24.09
2.02
-3.111
2.43
-37.56
2.46
121.92
2:29
123.30
2:29
MPC² (BT) 0.57 2:01 0.36
8.24 4.03
0.32
#.02
-1 4.02
23.38
4.02
29.46
a.43
.33.4
125.56
126.85 4.29
NPC² (BT)
114.47
Table H.5: Average test log-likelihoods and standard deviation over five independent runs with random initialization, using the same hyperparameters that brought the results showed in Table H.4.
Power
Gas
Hepmass
MiniBooNE
BSDS300
MPC (I.T)
0.46 #0.03
7.03 +0.18
-2.07
+0.02
-31.79
+0.39
126.66
+5.46
MPC (BT)
0.53 #0.03
6.16 +0.56
-22.42
+0.45
43.30
+0.98
122.77
#0.71
NPC² (LT)
0.42 #0.11
8.97
+0.08
-20677
+0.05
29.58
+0.29
127.58
+4.66
NPC (BT)
0.62 #0.01
10.55 +0.39
-20488
10.11
-7.64
#0.44
128.45
+0.52
Best hyperparameters found via grid search, which were used for achieving results showed in Table H.4. For input layers, G and S respectively denote Gaussian and spline.
Table H.6:
Model
Data set
K
Batch size
Learning rate
Input layer
Power
512
512
0.01
1024
4096
0.01
MPC (BT)
Hepmass
128
512
0.01
MiniBooNE
32
512
0.01
BSDS300
512
512
0.01
Power
512
512
Gas
512
1024
0.001
MPC (L.T)
Hepmass
512
512
0.005
MiniBooNE
512
1024
0.005
BSDS300
64
512
0.005
Power
512
512
0.01
1024
512
0.01
2PC² (BT)
Hepmass
256
512
0.01
MiniBooNE
32
512
0.01
BSDS300
128
512
0.01
Power
512
512
Gas
512
512
0.001
NPC² (LT)
Hepmass
256
512
0.001
MiniBooNE
128
2048
0.005
3SDS300
32
1024
0.001
H.4 LARGE LANGUAGE MODEL DISTILLATION
Data set. Given (x) the distribution modeled by GPT2 over sentences = [I F TD) maximum length D. we aim to minimize the bullback-Leible divergence KL[p" pl. where is modeled by PC. Minimizing such divergence is equivalent to learn the PC by on data sampled by GPT2. Therefore, following the experimental setting by Zhang et al. (2023) sample data of 8M sentences using GPT2 having bounded length / = 32, i.e., with
having
33

---

Published as a conference paper at ICLR 2024
maximum of D 32 tokens. Then, we split such sentences into training, validation and test set having proportions 0.85/0.05/0.10, respectively.
Models. Then, we learn monotonic PC and a NPC as tensorized circuits whose architecture is determined by a linear tree RG (Def. 2), i.c., a region graph that recursively partitions each set of finitely-discret variables (X,,.... XD) into {X;) and [Xi-1.--- XD} for 1 i D (e.g., see Fig. 2a). This is because we are interested in exploiting the sequential dependencies between words in a sentence. By enforcing monotonicity, we recover that the monotonie PC is equivalent to an inhomogenous hidden Markov model (HMM), and that that NPC* corresponds to a Born machine (see App. 1.4.1 for details).
Hyperparameters. All PCs are learned by batched stochastic gradient descent using Adam (Kingma & Ba, 2015) as optimizer with batch size 4096, and we continue optimizing until ei- ther the validation loss does not improve after three consecutive epochs or the maximum budget of 200 epochs has been reached. We perform multiple runs by exploring combinations of learn- ing rates and initialization. For monotonic PCs, we run experiments by choosing learning rates in (5- 10-10-3, 20- 1 and initializing parameters by sampling uniformly in (0, 1), by sampling from standard log-normal distribution, and from a Dirichlet distribution with concentration values set to 1. Similarly for NPC we run experiments by choosing the same learning rates for mono- tonic PCs, but using different initialization methods. Since squaring results in much larger outputs when compared to monotonic PCs, we initialize NPC²s such that the magnitude of parameters is relatively small. That is, in addition to sampling uniformly in (0, 10-1), also initialize the param- eters by sampling from a normal distribution having mean O and standard deviation 10-1, By doing so, we initialize an approximately even number of positive and negative parameters. Moreover, we also experiment by initializing parameters by sampling from a normal distribution with mean 10" and standard deviation 10 which initializes more parameters to be positive.
Results. For increasing layer dimensionality, we group runs having different learning rate and ini- tialization method together and show the achieved log- ligeliicls in Fig. Moreover, for layer dimensionalities K < 256, we report the double of log-likelihood points by repeating the runs with a different seed. Then, we perform statistical tests to assess the significance of NPC2s achieving higher -igliikei than monotonic PCs on the test data, and show the p-values in Table H.7.
= 32
64
128
256
512
1024
valuee = 1.0000
0.1071
0.0019
0.0020
0.0001
< 0.0001
Table H.7: Statistical significance of NPC's achieving higher likelihoods on LLM distillation. We perform one-sided Mann-Whitnes U test between the log-likelihoods achieved by NPC*s and monotonic PCs on the test data (see also Fig. 5), using a total of 36 runs for layer dimensionalities K < 256 and 18 runs for K > 256. We highlight the p-values that are consistent with 99% confidence interval in bold.
H.5 HISTOGRAMS OF LEARNED PARAMETERS
In Fig. H.4, we show the parameters of both monotonic PCs and NPC learned our experiments (Sec. 5), i.e., distribution estimation UCI data sets (Table H.1) and sentences sampled from GPT2. Even though we initialize the parameters of NPC to be non-negative in our experiments (i.e., by sampling from uniform distribution located on the non-negative side), they still end up learning negative parameters. In particular, Fig. H.4 shows the histograms of sum layers parameters of monotonic PC and NPC²s learned on UCI data sets having the same model size, i.e., with layer dimensionality K = 512 for Power and Gas, K = 128 for Hepmass and MiniBooNE, and K = 64 for BSDS300. For the rest hyperparameters, we choose batch size 512, learning rate 10-2, quadratic splines as input layers, and build a mixture of tree-shaped circuits (as described in App. H.3). For the models learned on GPT2 sentences, we use learning rate 10 - and uniform initialization with non-negative values (see also App. H.4). Note that for NPC we report the parameters of the circuit after being squared with Alg. 1, thus resulting in a quadratic increase the number of parameters.
34

---

Published as a conference paper at ICLR 2024
10a
10a
105
10a
10a
10a
10
107
104
10
0
10
25
25
(a) Power
(b) Gas
10
10a
10a
10a
10
104
107
10
10s
10
10a
105
-10
(c) Hepmass
(d) MiniBooNE
10a
107
10
107
10a
10
108
10
10
102
102
10a
0
10
500
-20
20
(e) BSDS300
(f) GPT2 sentences
Figure H.4: NPC²s learn negative parameters with non-negative initializations. Histograms containing the 99% interquartile range the sum layers parameters of monotonic PCs (+, blue) and ' after being squared (+2, orange) that are learned on UCI data sets (a-e) (App. H.3) and on sentences sampled from GPT2 (f) (App. H.4). Even if the chosen NPC are initialized with non- negative parameters (see App. H.5), they converge a model instance with negative parameters.
35


Reviews:
[{"review_id": "p2Ns2qzZtW", "reviewer": "Reviewer_nUGh", "summary": "The authors consider the problem of learning a mixture model where the separate components do not have to be positive.\n\nThis can be naively done by squaring the additive MM but this is computationally inefficient.\n\nThe authors develop a method based on probabilistic circuits allowing to square different model structures without excessive computational cost.", "questions": "See the weaknesses section.", "limitations": "", "rating": 6, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "The paper is reasonably clear and proposes simple yet interesting idea which appears to work well on selected synthetic/small scale experiments.\n\nThe authors provide the code for the experiments (which I did not reviewed).\n\nThe figure in page 1 nicely summarises the benefit of relaxing the requirement of positive components. Overall the figures in the paper help to understand the introduced concepts.\n\nI think the paper is an interesting read.", "weaknesses": "The clarity of the paper in pages 4,5,6 could be improved, the presentation is very dense and discusses multiple threads. The paper would benefit from focusing on core ideas and describing them in more detail while the less important parts could be moved to the appendix.\n\nI have concerns that a few points in the paper are overselling the method (i.e the result in Fig 5. on test data appears very small if statistically significant at all but using ^2 introduces additional computational cost). I would welcome the balanced discussion describing advantages and disadvantages of the method.\n\nThe authors do not discuss in detail how much additional computational cost is needed to achieve these results (a plot log-likelihood improvement vs CPU time would make the paper stronger). \n\nError bars in Figure 2 would help to understand the significance of empirical results.\n\nIn my eyes, the empirical improvements warranted by the proposed method are rather small and mostly shown on synthetic data.\n\nThe authors somewhat addressed three different questions in the empirical section but I feel it would be nicer to provide strong evidence for just one question: Does NPC^2 provide strong gains in performance without substantial increase in computational cost?\n\nIn Figure 4 the authors show that while NPC^2 outperforms MPC for LT and BT separately, for the cross comparison NPC^2(LT) vs MPC(BT) the latter can be better (similarly in table F5). This begs the question: is the RG doing the heavy lifting? If so, more empirical analysis would be helpful.\n\nThe authors should also elaborate on the selection of RG for improved clarity.\n\nWhy the differences reported in F2(a) are so small?\n\nCan the authors elaborate on the statement 105-106 regarding batching? I appears not fully clear to me. I cannot see how one can perform batching in (4) without introducing the bias to the gradient due to the presence of $\\nabla log Z$. Normally calculating  $\\nabla log Z$ requires sampling from the mode with every update of the parameters; it would be useful to provide exact update rule for clarity. Is the learning rule unbiased?\n\nSince $\\log c(x)^2 = 2 \\log c(x)$ the majority of the difference between maximising MM and MM^2 comes from the difference in the gradients of $\\log Z$ for MM and MM^2, I think this requires more clarity/explanation.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "FTIfTkmaP3", "reviewer": "Reviewer_uVYn", "summary": "Motivated by mixture models, the paper investigates a class of functions that is a squared mixture of arbitrary functions with potentially negative weights and functions that do not necessarily represent a density function. After motivating this in the \"shallow\" regime, the authors propose extensions to deep mixtures based on tensorized circuits.", "questions": "- See [W1]\n- Do authors have additional insights on [W2]?", "limitations": "", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "- [S1]: Originality -- as far as I can judge it's a novel and very interesting \n- [S2]: Significance -- seems to often work better than mixture models and other alternatives such as flows\n- [S3]: Clarity -- While the part related to tensor computations is a bit dense and could benefit from a more higher-level treatise, the paper is clearly written", "weaknesses": "- [W1]: Missing discussion / limitations: Maybe I overlooked this, but I could not find an actual discussion about the restriction of the approach, e.g., \n    + what are the limitations of the approach?\n    + how restrictive is the induced functional form by using squared functions?\n    + how expressive is the approach in the shallow or small-K setting? (Fig. 5 e.g. indicates that $\\pm$ is worse for small $K$)\n    + is it possible to extend the approach to a conditional setup?\n- [W2]: Experiments: The paper addresses the computational costs of the approach from a theoretical point of view and even provides some empirical evidence for the computation of the normalization constant, but empirically investigating a couple of scaling aspects such as \n    + the scaling in $D$ or \n    + a comparison with other appraoches such as the MAFs in terms of runtime \n\n    would provide further valuable insights (e.g. related to \"fairness\" when tuning different methods). \n- [W3]: Presentation (minor): Some of the graphics are rather hard to read:\n    + relatively small and dense (Fig. 4)\n    + the x or y-axis labels are sometimes missing (Fig. 4) or hard to find (not centered; Fig. 5, C1)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "asB673EIn0", "reviewer": "Reviewer_5G72", "summary": "Mixture models traditionally are represented as convex combinations of simpler probability distributions. This paper proposes loosening this constraint to any linear combination, and squaring the result at the end to ensure non-negativity. This modification is then applied to probabilistic circuits (by allowing negative weights in sums, and then squaring). Theoretical and empirical analysis confirm:\n\n1. Better distribution approximations for a given number of parameters (with a theoretical example showing exponential separation)\n2. Preservation of smoothness and decomposability when converting a PC to a squared NPC.", "questions": "Questions/Suggestions:\n- GPT2 distillation experiment should compare other tractable models\n- Exponential separation is established theoretically for a restricted class of functions (unique disjointness). Is it possible to establish that for a more general class of distributions?\n- Definition A.1 in Appendix A seems to have a typo. The sum nodes should use sc(n_i), instead of sc(c_i)?", "limitations": "", "rating": 6, "confidence": 3, "soundness": 3, "presentation": 2, "contribution": 2, "strengths": "- Simple and effective idea\n- Empirical results show better performance than baseline on some tasks", "weaknesses": "- Paper's motivation can be stronger. e.g. add a real world motivating example. It would be interesting to see how the better density estimation can be used for an improved downstream task as well.\n- The NPCs use fewer parameters but in a more complex way. What is the impact of this on training cost. This question is not explored empirically.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "IeKXhl5Qbx", "reviewer": "Reviewer_Lqff", "summary": "Mixture models (herein called MPC) are probability density functions over a domain $X$ that are composed by adding together multiple simpler probability density functions. The authors propose a more general framework, (called NPC), where any functions over the domain $X$ (or specific dimensions of $X$) may be multiplied, added, subtracted together and finally squared to return a non-negative scalar which, under the right conditions the authors prove, can also be normalised yielding a probability density. Given the same number of parameters, the proposed NPC models have far more expressive capability than traditional MPCs, in fact proven exponentially more capacity.\n\nThe authors describe a range of concepts, rooted graphs, tensor circuits, to lead to the conditions for a given NPC to be marginalizable. Theoretical relationships with related work is described and finally experiments demonstrate the efficacy of the propoosed approach.", "questions": "- In Figure 2,b,. the sum layer must output dimension $S=K$ in order to be accepted by the following product layer?\n- how does one find the rooted graph/division partition or variables? Try a handful of graphs and choose the maximum likelihood graph?\n- there is much discussion on tensored circuits which have a tensor output, I presume the final layer is a sum to scalar layer?\n- the authors justify the naming of \"tensorized circuits\" as a way to encompass and simplify other methods. If I understand correctly, these  are standard computational graphs, the bread and butter of all pytorch or tensorflow users, is a new name really required?", "limitations": "", "rating": 8, "confidence": 2, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "- extensive theoretical evaluation\n  - proof of conditions for normalization which significantly affects model design\n  - proof of exponential expresivity\n  - proofs of connections to related methods\n\n- simplicity\n  - take some functions over the space $X$, functions over disjoint subsets of dimensions\n  - multiply them (across disjoint groups)\n  - add them together (functions within a disjoint group)\n  - sum the output and square it to get a single non-negative scalar value\n  - if we followed the rules, we can find the partition function/normalising constant in one forward pass of the function\n  - I feel this is very intuitive and surprisingly simple, and most importantly  avoids difficult normalisation (e.g. MCMC) while yielding a big improvement in expressiveness over standard mixture models. Analytic normalisation also enables conditioning. Sampling is briefly mentioned in the Appendix and appears to be one point to be harder than MPCs.", "weaknesses": "While I feel confident I understood the method paper and the paper, I am not familiar with the surrounding literature hence my comments are mainly on the general practicalities and the paper presentation.\n\n## Major Comments\n\nThe main four big questions I have mostly relate to practical considerations  \n- How do I normalise $c(X)$? Much of section 3 is building foundations to finally reach proposition 1 which successfully solves the issue of normalization (which is a significant strength of the paper in my view)\n- For a given dataset, how do I find the rooted graph? The issue is not so carefully discussed, and presumably there is no theoretical or provable result and in practice one must simply employ some sort of architecture search. If not already, this should be clarified in the main paper as I feel it may be an obstacle for practitioners.\n- Given the exponentially more expressiveness, could this easily lead to overfitting? A quick word search in the document doesn't yield results, this is not mentioned once?\n- How do I generate samples? This is described in the appendix and appears to be not as easy compared to MPCs, \n\nI understand if the authors would like to argue this is a more theoretical paper and such practicalities are beyond scope.\n\n## Minor Comments (Presentation)\n\n### Content Density\nUpon first reading, I was exhausted by section 5, however upon second reading the paper made much more sense.\n  - Sections 1, 2 were simple and easy to follow\n  - section 3 was hard work on first reading but very clear on second reading (see details below)\n  - section 4 contains multiple short sharp deep dives into a range of related fields.\n  - section 5 was very short and I personally didn't truly understand the benchmarks nor get a feel for implementing the method or its practicalities or failure modes, (e.g. overfitting, sensitivity to rooted graph, sampling)\n\nGiven the main paper introduces a range of concepts, then proposes a new method, provides proven results and proves connections to related fields and then benchmarks, I feel like this is a (very nice) journal paper that was heavily compressed into 9 pages and all of the overflow was placed in the appendix. \n\nThe theoretical treatment is extensive. The authors may consider moving some of the less significant content regarding other works in Section 4 to the appendix in order to extend section 5 with more \"hands on\" details about the using NPCs, e.g. a worked illustrative example or failure modes or sensitivity to the rooted graph.\n\n### Section 3 detailed comments\nI understand computational graphs have nodes that are operations and the links are tensors, \n- Definition 1 was very hard to follow, the ambiguous notation that $\\ell$ represent a layer as well as a numerical output tensor from a layer. \n- Figure 2 b, c, blur the boundary of \"nodes\" and \"edges\", there are rectangles with operations, and there are volumes between them also with operations (hadamard product and $W$). Even now I struggle to parse these diagrams.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "BViIIZKINN", "reviewer": "Reviewer_Bp5w", "summary": "The paper proposes a way to learn and represent mixture models with negative weights by squaring the linear combination defined by these models. The resulting model is cast into the Probabilistic Circuits (PCs) framework and thus further extended to deep mixture models, resulting in the main contribution of the paper, squared non-monotonic PCs (or NPC$^2$s). NPC$^2$s are theoretically proven to be more expressive efficient than regular (or monotonic) PCs, which translates to strong empirical results in a number of benchmarks.", "questions": "1. Unless I missed it, there is no mention of how the number of parameters of the MPCs used in the experiments compare to that of MPC$^2$ and NPC$^2$. I assume the authors used the same number of parameters for all models, which is probably the most natural comparison, but it would be interesting to compare the squared models with an MPC of size equal to that of the unrolled model (e.g. as in the right hand side of Figure 1). I imagine MPC$^2$ and NPC$^2$ would still perform better because, despite being less flexible than the unrolled MPC, they effectively share weights among components, which probably facilitates learning. Would the authors share the same opinion? Weight sharing might be important in practice, and the paper could benefit from exploring this aspect a bit further in the text or experiments.\n2. How does the optimization of NPC$^2$ with SGD compare to that of regular MPCs? Some would argue that optimization is one of the main bottlenecks holding PCs back, since they tend to converge relatively fast, probably quickly getting stuck in local minima. Have the authors observed any notable differences in convergence or stability of the optimization process of NPC$^2$s as compared to MPCs? Even though NPC$^2$s are provenly more expressive than regular MPCs, their utility is heavily tied to how easy they are to learn, and it would be useful to have more insights in that sense.\n\nSmall remarks:\n- I believe the signed logsumexp trick, or a very similar solution, was already used in previous works to compute expectations of arbitrary functions using PCs [1, 2]. The PCs used there did not have negative weights, of course, but the signed logsumexp trick was needed to propagate negative values through the networks since the functions one would compute the expectation of could take negative values. I am not sure the trick is actually mentioned in the papers, but it is certainly used in their respective implementations.\n- Line 227: “they” is repeated.\n- Line 303: The “to” after “answer” is not necessary.", "limitations": "", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "The work is novel and certainly relevant for the Tractable Probabilistic Models community, since it adds a new and provenly more expressive model to the class of Probabilistic Circuits. More importantly, the main ideas are well developed in the text and thoroughly analyzed both theoretically and empirically, allowing for a well-rounded understanding of this new class of models. The text itself is well written and easy to follow, and the related work develops important connections to other methods and models in the literature of Probabilistic Circuits and beyond.", "weaknesses": "The paper is very well executed, and honestly I cannot think of any major flaws or possible improvements besides the couple of questions I outline below.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Decision: Accept (spotlight)