Subtractive Mixture Models via Squaring: Representation and Learning

We thank the reviewer for appreciating the novelty of our work and the theoretical connections with other tractable probabilistic models. We are also keen on citing the additional work (but references seem missing!)

There is no mention of how the number of parameters of the MPCs used in the experiments compare to that of MPC^2s and NPC.

In the experiments we always compare MPCs and NPC^2s having the same number of learnable parameters. We added a sentence in the latest version of the paper in order to make this explicit. We also compare NPC^2 against squared MPCs (MPC^2s) in order to disentangle the effects given by squaring and the negative parameters.

I imagine MPC and NPC^2 would still perform better because [...] they effectively share weights among components, which probably facilitates learning. Would the authors share the same opinion?

We perform experiments with squared MPCs (MPC^2s) as well, therefore taking into account parameter sharing for monotonic circuits. Table H.4 (in the latest revision) brings evidence that the parameters sharing given by squaring is beneficial for density estimation even in monotonic circuits (e.g., see results of MPC^2s against MPCs on Gas, Hepmass, Miniboone). And it also supports our claim around negative parameters being the key factor in boosting performance, as NPC^2s outperform MPC^2s. Theoretically investigating if parameter sharing creates an expressive efficiency advantage or how its influence on learning is interesting future work.

How does the optimization of NPC with SGD compare to that of regular MPCs? Have the authors observed any notable differences in convergence or stability of the optimization process of NPCs as compared to MPCs?

The fast convergence to some local minimum with MPCs that the reviewer mentioned has been observed on UCI data sets. By contrast, NPC^2s generally require more epochs to converge than MPCs, but they achieve higher log-likelihoods on both training and test data.

Regarding the stability of optimization, we found NPC^2s to be more sensible to the parameters initialization method than MPCs. In general, choosing initialization is already tricky for MPCs, and it is even more difficult for NPC^2 as parameters are allowed to be negative. In our experiments we investigated initializing NPC^2s by sampling the parameters from a normal distribution independently. However, we found NPC^2s to achieve higher log-likelihoods if they are initialized with non-negative parameters only (i.e., by sampling uniformly between 0 and 1). Our paper is a first attempt to learn non-monotonic circuits in a principled way and at scale. We believe it can open up plenty of interesting future directions on how to initialize, regularize and learn NPC^2s.

I believe the signed logsumexp trick [...] was already used in previous works to compute expectations of arbitrary functions using PCs [1, 2].

Can you please provide the references [1, 2] ? We will definitely cite them in our work.

Typos

Thank you! We fixed the typos in the latest version of the paper.

We thank the reviewer for appreciating the theoretical contributions of our work, as well as its simplicity. Our paper is not merely theoretical, but its theoretical contribution is definitely a major strength. Indeed, we present one of few lowerbounds for non-monotonic circuits, as well as important connections to PSD models and tensor networks. Bridging these previously disconnected literatures can greatly propel future research in PCs (and viceversa). Concerning presentation, we agree with the reviewer and we moved Section 4.2 to Appendix G, and better describe how we build region graphs in the main text and in Appendix F and Figure F.1. We answer the posed questions below, and we are happy to further clarify any additional point.

How do I normalise c(X)?

We assume you are referring to normalising $c^2(X)$. Computing its partition function Z is done by recursively decomposing the integral and by exploiting the structure of $c^2$. E.g., in Eq. 3 Z can be computed by i) computing integrals over products of components, and then ii) a linear combination thereof. This method applies to deep squared NPCs, where the integral is recursively decomposed until it is first applied on products of functions at the input layers (for example see input layer labelled with $f_i(X_3)f_j(X_3)$ in Figure 2c). Then, these computations are propagated to the inner layers, which are evaluated only once. Finally, the scalar output will be exactly Z of $c^2(X)$.

[...] could this easily lead to overfitting?

An increased expressiveness does not imply that the model will overfit more easily. As many other machine learning models overfitting is possible, but the risk can be reduced by limiting the number of parameters.

How do I generate samples?

Sampling can be done in an autoregressive fashion. We choose an ordering of variables and sample one at a time in that order. To sample the i-th variable $X_i$, we fix all the previous i - 1 variables that have been already sampled and sample from the conditional $p(X_i \mid X_1,\ldots X_{i-1})$. This requires evaluating the tensorized circuit as many times as the number of variables and not only once as for MPCs. However, since we are actually evaluating the same tensorized circuit, many inner computations can be cached and reused. This speeds-up sampling, but requires engineering effort that is out of the scope of this work.

[...] what is a worked illustrative example or failure modes?

In Section 5 we already discuss some failure scenarios of NPC^2s. E.g., we show that there is little advantage in having negative parameters in NPC^2s if the input components are already flexible enough such as Categoricals. We illustrate this aspect in Figure 3. Also, we did not find any significant improvement with respect to monotonic PCs on image data, as we mention in L326-328.

[...] the sum layer must output dimension S=K?

Sum layers can output a vector (of size S) that is smaller or bigger than their input (of size K). Since the inputs of element-wise product layers must be of the same dimensionality, it means that when a sum layer feeds a product layer (like in Fig 2b) then its output has the same size as the product layer. However, for example, in Fig 2b we can have input layers that are smaller than the sum layers, hence some sum layers will necessarily have S > K.

How to find the region graph?

There are various ways coming from the PCs literature. For example, one can recursively split sets of variables randomly until no further splitting is possible [A]. Alternatively, it can be learned from data by performing independence tests to split variables [B]. In case of image data one can split patches of pixels [C].

Is the final layer a sum to scalar layer?

Yes, the output is a scalar. However, one can also have tensorized circuits with a tensor output. In fact, our Algorithm 1 operates on such tensorized circuits after the first recursive step.

[...], is a new name really required?

Circuits are computational graphs, with special structural constraints. Therefore sometimes they are referred to structured neural networks [D]. We call our circuits “tensorized” as we define them in a layer-wise fashion via tensor operations, as opposed to the classical way to define circuits that is unit-wise [E]. For example, Figure A.1 shows how scalar units in circuits can be tensorized to form layers. Modern circuit architectures are indeed tensorized [A] [F]

[A] Peharz, Random Sum-Product Networks: A Simple and Effective Approach to Probabilistic Deep Learning, 2019

[B] Gens Learning the Structure of Sum-Product Networks, 2013

[C] Poon, Sum-product networks: A new deep architecture, 2011

[D] Vergari, Tractable probabilistic models: Representations, algorithms, learning, and applications, 2019

[E] Choi, Probabilistic Circuits: A Unifying Framework for Tractable Probabilistic Models, 2020

[F] Peharz, Einsum Networks: Fast and Scalable Learning of Tractable Probabilistic Circuits, 2020

We thank the reviewer for appreciating the simplicity and effectiveness of our idea and the empirical evidence that shows an improved distribution estimation task. We believe our answers below can address all the raised concerns. We are happy to clarify further points and to run further experiments if the reviewer points us to specific cases.

It would be interesting to see how the better density estimation can be used for an improved downstream task as well.

Our experiment on distilling GPT2 already shows the potential of NPC^2 for a downstream task. That is, [A] proposes how models such as PCs (and hence also NPC^2) can be used in combination with large language models (LLMs) for the downstream task of constrained text generation. In particular, Figure 3 in [A] shows that the log-likelihood highly correlates with the text generation quality (measured as BLEU-4 scores). Therefore, higher log-likelihoods would directly translate to better performances on the mentioned downstream task.

[...] What is the impact of this on training cost?

The increased complexity of NPC^2 during training arises only from the computation of the partition function Z, which however can be greatly amortised over large batches as we show in Appendix C and Figure C.1. There, one can see that for NPC^2 the cost of computing Z is similar to the cost of evaluating the circuit once on a batch of data. This is because the complexity of Z does not depend on the batch size and therefore its cost can be greatly amortised.

In the rebuttal revision we added Figures C.2 and C.3, which compare the actual computational cost of training the monotonic PCs and NPC^2 on UCI data sets. In these figures, we show that NPC^2 adds little overhead during training in most configurations, as computing the partition function Z is comparable to evaluating $c(x)$ or $c^2(x)$ on a batch of data. Concerning the likelihoods gains the overhead for training on Gas results in a NPC^2 achieving a x2 improvement on the final test log-likelihood. Moreover, on high-dimensional data such as BSDS300, NPC^2s are actually faster as they require fewer parameters and achieve higher log-likelihoods. We also report an analysis for the largest possible models (worst-case) in Figure C.3, and confirm that the cost of computing Z is still comparable to evaluating $c(x)$.

GPT2 distillation experiment should compare other tractable models

If the reviewer can specify other tractable models or an available implementation of flows for text data, we will gladly run the additional experiments. Note that the normalising flows we have in the table of Figure 4 operate on continuous variables and therefore cannot be applied on discrete data such as text in our GPT2 distillation experiment.

Exponential separation is established theoretically for a restricted class of functions. Is it possible to establish that for a more general class of distributions?

Exponential separations as in our result are often very tricky. First, it is often hard to find candidates for separations: many functions turn out to be too easy or too hard, in the sense that they are either easy to compute in both models one wants to separate or hard in both. And even when a candidate function for being a separating example is found, it also has to be amenable to theoretical analysis. This often requires very regular, structured characteristics of the function that allow a good understanding. Furthermore, note that we never have access to the real distribution that has generated the data. And even if we had access to it, it would require the above regularity conditions to make a theoretical claim. The combination of these effects often makes the functions for which one can actually show separations very specific!

We remark that in [D] there are quite a number of open questions about exponential separations between non-monotonic circuits. We hope our new lower bound can help build other results that close these open questions. So while we would of course be delighted to show separation results for more classes of functions, we are very happy with the result we can show.

Definition A.1 in Appendix A seems to have a typo

Yes, thank you! We fixed it in the updated revision.

[A] Zhang et al.,Tractable Control for Autoregressive Language Generation, 2023

[B] Hoogeboom et al., Integer Discrete Flows and Lossless Compression, 2019

[C] Tran et al., Discrete flows: Invertible generative models of discrete data. 2019

[D] de Colnet, Mengel, A Compilation of Succinctness Results for Arithmetic Circuits, 2021

We hope all your concerns have been addressed by our answers and the new figures we added in the latest paper version. We are willing to run more experiments if the reviewer specifies which model to evaluate. In any case, we remain open to solve any other pending issue to achieve a full acceptance.

We thank the reviewer for pointing out the novelty of our approach and the significance of our empirical results. We answer below to the comments raised.

What are the limitations of the approach?

We already show two limitations about NPC^2s in our paper. First, we show that negative parameters are not really useful if we use flexible yet expensive components, such as Categoricals (see L309-320 and log-likelihoods shown in F.2 (a) (in the rebuttal revision they are now shown in H.2)). Second, we highlight the aspect that NPC^2 cannot support tractable MAP inference without losing the benefits given by negative parameters (see discussion in Section 4.2 and Proposition 4).

Finally, to complement our time and memory benchmarks shown in Figure C.1, we added Figures C.2 and C.3 in the latest paper version. We show that training NPC^2s might require slightly more time and memory in some cases (see also our answers to reviewers 5G72 and nUGh).

How restrictive is the induced functional form by using squared functions?

We already know that Gaussian mixture models (GMMs) and monotonic PCs are universal approximators. Moreover, we showed that NPC^2s can require fewer parameters than monotonic PCs (Theorem 1), i.e. they are more expressive efficient. Showing whether other models can be more expressive efficient than NPC^2 is an open problem. Nevertheless, our empirical analysis suggests squaring is not restrictive for density estimation on real world data sets (see Figure 4).

How expressive is the approach in the shallow or small-K setting? (Fig. 5 e.g. indicates that +- is worse for small K)

We experiment with NPC^2s on 2D artificial data sets with small K values, which results in shallow models that are more expressive than the monotonic PCs (MPCs) that are equivalent in size.

In Figure 5, the worse results on the test data for very small $K$ (such as $K=32$) indeed requires further investigation. We believe it is because smaller models are much more sensitive to initialization, and we believe initialization is an important aspect in NPC^2 that definitely deserves future work. See also our answers to Reviewers nUGh (about our results showed in Figure 5) and Bp5w (about difficulties in training NPC^2s).

Is it possible to extend the approach to a conditional setup?

Yes, e.g., one can construct a NPC^2 modelling a conditional distribution $p(Y\mid X)$ for some labels $Y$. To do so, you can learn a neural network that takes the features $X$ as inputs and outputs the real-valued parameters of a NPC^2 modelling a probability distribution over $Y$. This idea has already been investigated for monotonic PCs, see [A].

[...] empirically investigating a couple of scaling aspects such as the scaling in D [...]

In the rebuttal revision we added Figures C.2 and C.3, showing how training monotonic PCs and NPC^2s scale when increasing the data set dimensionality. The results show that squaring in NPC^2s adds little overhead in terms of time and memory in most configurations. See also our responses to Reviewers 5G72 and nUGh.

Presentation (minor): Some of the graphics are rather hard to read [...]

We want to clarify that the scatter plots in Figure 4 lack labels on the x-axis because they would be exactly the one of the y-axis. In fact, each grey diagonal separates the graph into two even trapezoids. Furthermore, the y-axes of the two plots in Figure C.1 are shared. In the latest revision, we updated the captions of these Figures to make this explicit.

[A] Shao, Conditional Sum-Product Networks: Imposing Structure on Deep Probabilistic Architectures, 2019

a plot log-likelihood improvement vs CPU time would make the paper stronger

In the latest revision we added Figure C.2 which exactly compares the actual computational cost of training the monotonic PCs and NPC^2 on UCI data sets and contrasts it with the gained likelihood. We show that NPC^2 adds little overhead during training in most configurations. In particular, Figure C.2 shows that the overhead for training on Gas results in NPC^2 achieving a x2 improvement on the final test log-likelihood. Moreover, on high-dimensional data such as BSDS300, NPC^2s are actually faster as they require fewer parameters and achieve higher log-likelihoods. We further analyze the “worst case” behavior on the largest circuits possible in Figure C.3 and confirm that the computation of Z for NPC^2 can match the cost of computing c(x) for MPC when amortized in batches. See also our response to Reviewer 5G72.

Error bars in Figure 2 would help to understand the significance of empirical results.

We assume you are referring to the table in Figure 4, let us know if not. We have already reported some of the standard deviations with multiple random repetitions in Table F.5 (which is now H.5 in the rebuttal revision). Apart from the results on Power, the standard deviations are quite small when compared to the average log-likelihoods and therefore support the significance of our empirical results.

the empirical improvements warranted by the proposed method are rather small and mostly shown on synthetic data.

The experiments shown in Figure 4 are actually on real-world data sets. These data sets have been extensively used to evaluate deep generative models such as normalising flows in the past. To the best of our knowledge, our NPC^2 on these data sets score the current state-of-the-art for tractable probabilistic models supporting exact marginalization.

Furthermore, the improvements on these data sets are actually significant. For example, we got a x2 improvement in terms of log-likelihoods on Gas (see table in Figure 4). Moreover, on MiniBooNE we went from -32.11 by monotonic PCs (MPC (BT)) to -26.92 by NPC^2 (BT), which is definitely much better if we also look at the multivariate Gaussian baseline that achieves -37.24.

Why the differences reported in F2(a) are so small?

The log-likelihoods shown in F.2 (a) (in the rebuttal revision they are now shown in H.2) refer to mixture models having Categoricals as components. The small differences confirm our claim that negative parameters are not really useful if we use flexible yet expensive components, such as Categoricals (L309-320). We believe our empirical analysis is therefore balanced as it also provides failure cases for NPC^2s.

Can the authors elaborate on the statement 105-106 regarding batching?

We want to remark that computing $Z$ and $\nabla \log Z$ can be done exactly in the proposed models (e.g., see Proposition 1), and therefore it does not require sampling. In our answer to Reviewer Lqff, we further discuss how the exact computation of $Z$ is performed in NPC^2s. Therefore, learning is performed by updating the parameters using exact gradients given by differentiating the negative log-likelihood on a batch of data. However, note that we need to differentiate $\log Z$ only once per batch, as it does not depend on the input, and therefore adds little overhead during training (see our response to Reviewer 5G72). Furthermore, note that gradients on MPCs and NPC^2s are different because NPC^2s allow for negative parameters.

We thank the reviewer for appreciating our ideas and its potential. We believe our answers below can address all the raised concerns. Let us know if not, we are very keen to engage in a discussion.

[...] the presentation is very dense. The authors should also elaborate on the selection of RG for improved clarity.

We agree with the reviewer and improved the presentation. In the updated revision we have moved Section 4.2 to Appendix G, and better described how we build region graphs in the main text. We also provided more details in Appendix F and Figure F.1. Moreover, we splitted Section 3 in three parts to improve readability. If the reviewer has some additional reasonable suggestions, we will incorporate them in a new revision.

[...] for the cross comparison NPC^2(LT) vs MPC(BT) the latter can be better. This begs the question: is the RG doing the heavy lifting? If so, more empirical analysis would be helpful.

Note that we already take into account the region graph (RG) construction as a latent confounder in Figure 4. And in all datasets, fixed a RG, NPC^2 is better than MPC. The case in which MPC (BT) is better than NPC^2 (LT) has been observed on Power only. If the reviewer can specify which particular aspect requires to be analysed empirically, we will gladly investigate it.

the result in Fig 5. on test data appears very small if statistically significant at all

We agree with the reviewer, and believe our NPC^2s are overfitting in that experiment. Therefore, we updated the caption of Figure 5 and discussed this aspect in the text of the rebuttal revision. In general, we believe training NPC^2s can be more challenging (e.g., due to an observed higher sensitivity in parameters initialization), and we cannot rely on existing works investigating training as they assume non-negative parameters (such as [A]). See also our answer to Reviewer Bp5w.

However, note that our experiments follow the same settings in [B], which is based on training a tractable probabilistic model (in our case a NPC^2) on sentences sampled from GPT2, with the aim of evaluating the expressiveness of our models on a more challenging scenario. So a higher train likelihood still brings enough evidence that NPC^2 are more expressive than MPCs. Furthermore note that, compared to [B], we use only half their number of sentences for temporal resource constraints (i.e. 4 millions instead of 8). In the limit and by sampling enough sentences from GPT2, one can definitely reduce the risk of overfitting. Lastly, we believe our work will also motivate future work on regularising NPC^2s as it is the first one to learn non-monotonic PCs on a large scale.

[A] Liu et al., Scaling Up Probabilistic Circuits by Latent Variable Distillation, 2023

[B] Zhang et al.,Tractable Control for Autoregressive Language Generation, 2023

We hope we addressed all your concerns in our two comments above. If not, we are very keen to solve any additional issue that holds our submission back from a full acceptance.