Venue: NeurIPS 2021 Conference

Reviews:

final_score: rating: 7: Good paper, accept
review_content: summary: This is a paper about regularizing probabilistic circuits (PCs), a rich class of tractable probabilistic models. The authors propose two new methods: data softening and entropy regularization. Data softening aims to put a non-zero mass on each possible assignment with a higher emphasis on observed assignments in the given data. Training the PC on this soften data implicitly regularizes its parameters. Entropy regularization aims to avoid learning low-entropy distributions which are prone to overfitting. To achieve this the authors introduce an entropy regularizer into the log-likelihood objective function. Both techniques are computationally intractable to implement even for simple machine learning models. The authors leverage the tractability and structural properties of PCs and propose how the techniques can be practically applied to learn regularized parameters. On a number of benchmark datasets for density estimation, the proposed methods achieved improved generalization accuracy compared to other widely used regularization techniques.  
main_review: Laplace smoothing has been the most widely used technique for regularizing the parameters of both deterministic and non-deterministic PCs. The authors give an example of how this simple technique can fail to produce reasonable non-uniform priors for sum units in PCs that are imbalanced (have drastically different support sizes). The authors make two contributions to address this issue. The first contribution is softening the data which implicitly regularizes the parameters of the PC by adding noise in closed form. The authors have theoretically analyzed the non-trivial challenge of training machine learning models using such softened data and proved that PCs are an exception to this: One can train a PC using softened data (exponentially many) in time that is linear in its size as well as the original data. The second contribution is proposing an entropy regularization objective function that essentially adds the entropy of the model (with a hyperparameter) to the log-likelihood objective function to be maximized, essentially discouraging learning models with lower entropy. This was also proven to be a computationally hard task when the model is not a PC. The authors have presented an EM-style algorithm to find a stationary point of the non-concave objective function. Both of the proposed techniques were applied to two PCs types: deterministic and non-deterministic. Experimental results showed that both approaches significantly improved the test set log-likelihood scores on several problems compared to Laplace smoothing. 
 
Overall, the paper makes useful practical contributions for regularizing PCs. The motivation was well-expressed, challenges of the proposed approach were described and solutions for both types of PCs were presented. Empirical results were promising. I am writing some comments/suggestions that might improve the readability of the paper.

Comments:
1. Figure 5 shows summary results of regularizing several PC structures using both data softening and entropy regularization. Since it’s a summary result its hard to get a picture of how these methods worked for higher dimensional problems and what were there structural complexities. I would suggest to present a table similar to Table 1.
2. Proof of theorem 3 was quite involved. It would help if a high-level sketch is given first and then details are presented. 
3. Table 1 only reports one set of hyperparameters. It was unclear whether any tuning was performed here. Also, the \beta hyperparameter is shown to be very small (<0.5) compared to the ones used for deterministic PCs. Were the two techniques combined for HCLTs?  
limitations_and_societal_impact: yes
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: The paper deal with the problem of regularization of Probabilistic Circuits (PCs).
main_review: Two approaches have been proposed, one based on softening the training samples and the other one based on controlling the entropy of the learned distribution. They show that both the proposed approaches improve the test set likelihood over standard density estimation datasets.

Some theorems are presented in order to prove the tractability of the learning algorithms.

Table 1 is not referenced in the paper.

As regards the Laplace smoothing, the problem of uniform prior has been addressed in [1], where the authors introduced a Bayesian Parameter Smoothing for deterministic PCs. 

It is not clear why a simple CLT has been used for non-deterministic PCs instead of learning a more complex one.

The experimental evaluation proves the validity of the proposed approaches.

Concluding, the paper is well written, the idea is novel for PCs, and the results, both theoretical and empirical, are good.

[1] Learning accurate cutset networks by exploiting decomposability, 2015 

limitations_and_societal_impact: Sec. 4.2 discusses the limitation489of Thm. 4; Sec. 4.3 discusses the limitation of applying entropy regularization to490non-deterministic PCs
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: This paper tackles a common issue with probabilistic circuits (PCs) in practice: overfitting. The work suggests two novel methods for principled regularization. The first method, called data softening, injects noise into the dataset. The second method, called entropy regularization, directly regularizes the entropy of the distribution encoded by the PC. Both methods are global and model-agnostic, meaning they can be applied to any arbitrary distribution, regardless of the model.
main_review: This work is original in the PC context. Both regularization techniques are not novel ideas on their own. Indeed, data softening is related to data augmentation, a procedure wildly used in machine learning. Similarly, entropy as an overfitting measurement is also not innovative. However, bringing these intuitive methods to PC regularization is a clever move. PCs allow for (mostly) tractable inference, and the two regularization techniques benefit from that tractability. Therefore, the methods proposed in the manuscript are new and of relevance.

This paper has a good technical quality. The main ideas in Section 2 are introduced with proper formalism. Similarly, the work's main theoretical contributions in Section 4 are formally demonstrated and proved. Specifically, Theorem 4 shows the monotonical convergence of Algorithm 3, a result of practical interest. All derived results solidify their principled proposed methods.

The manuscript is well-written and clear. I also enjoyed the presentation, which favours the logical flow of explanation. For example, empirical results are given right after the method's description, as in Sections 4.2 and 4.3

The experiment results demonstrate the work's relevance. While reaching state-of-the-art in some datasets, the experiment results section can be strengthened with tasks evaluation. At times, log-likelihood will not reflect performance in specific probabilistic tasks, such as classification or regression. Thus, it would be interesting to see the influence of the proposed regularization techniques in such tasks.
limitations_and_societal_impact: This paper does not explicitly discuss the limitations of the method's proposed. Given the theoretical results presented here, a formal analysis of possible assumptions or requirements for the method's application would be welcome.
review_title: null

final_score: rating: 7: Good paper, accept
review_content: summary: In the context of Probabilistic Circuits (PCs), recent developments of large-scale models point to the increasing need of regularization. 
Having large models with millions of parameters is inherently a challenge, but more so for models with structural restrictions that favor tractability.
In this paper, the authors present regularization techniques for probabilistic circuits including non-deterministic models.
The regularization is based on data softening and on regularization via entropy, and the authors show that this is possible for PCs while intractable for other models.
And demonstrate empirically that the approach is beneficial.
main_review: The authors present a regularization approach based on a modified loss that includes an entropy component. Furthermore, updates based on a softened dataset are computed in time linear w.r.t. to the model size and the training dataset size.

The paper is well-written and technically sound, and very relevant and significant for the tractable probabilistic models community.
The authors give a proper introduction to the models and the different characterizations based on determinism. Moreover, they also show how this regularization approach would not be tractable for other ML approaches. In short, this approach is uniquely tailored to the capabilities of probabilistic circuits.

There are minor clarifications that I believe could help readers better understand the paper:
- In lines 48/49 (and later), you mention that MLE parameters can be obtained in linear time wrt to sizes. But you present an iterative approach in Eq. 4. This would introduce another factor in the time needed for the MLE estimation. I believe the distinction is based on determinism, and this could be mentioned earlier (e.g., in lines 48/49).
- In line 141, maybe you want to add the word “exact”, as you can compute approximates for the non-deterministic variant.

A more important question is the comparison to other regularization approaches, and the most significant here is dropout as introduced in RAT-SPNs. In your paper you mention that you compared to this approach (RAT), but you do not mention whether dropout was enabled nor what hyper-parameters were used for that.
A comparison here would help the reader better understand the impact of your approach, even if they are orthogonal.
limitations_and_societal_impact: The authors have not mentioned societal impact, but I believe there are no conflicts or points to raise.
review_title: null

Meta-review: Thanks for submitting your work to NeurIPS. Getting probabilistic circuits (PCs) to scale well is important Here, the paper makes two important contributions to regularization of PCs, namely, data softening and entropy regularization. While both methods are infeasible for many machine learning models, the paper proves that  they can be efficiently implemented for PCs. All reviewers agree that this is a very solid and important contribution. And I fully agree with this sentiment. 
Decision: Accept (Spotlight)