Tractable Regularization of Probabilistic Circuits
Authors: Anji Liu
Guy Van den Broeck
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Probabilistic Circuits
Tractable Probabilistic Models
Parameter Regularization
Overfitting

Abstract: Probabilistic Circuits (PCs) are a promising avenue for probabilistic modeling. They combine advantages of probabilistic graphical models (PGMs) with those of neural networks (NNs). Crucially, however, they are tractable probabilistic models, supporting efficient and exact computation of many probabilistic inference queries, such as marginals and MAP. Further, since PCs are structured computation graphs, they can take advantage of deep-learning-style parameter updates, which greatly improves their scalability. However, this innovation also makes PCs prone to overfitting, which has been observed in many standard benchmarks. Despite the existence of abundant regularization techniques for both PGMs and NNs, they are not effective enough when applied to PCs. Instead, we re-think regularization for PCs and propose two intuitive techniques, data softening and entropy regularization, that both take advantage of PCs' tractability and still have an efficient implementation as a computation graph. Specifically, data softening provides a principled way to add uncertainty in datasets in closed form, which implicitly regularizes PC parameters. To learn parameters from a softened dataset, PCs only need linear time by virtue of their tractability. In entropy regularization, the exact entropy of the distribution encoded by a PC can be regularized directly, which is again infeasible for most other density estimation models. We show that both methods consistently improve the generalization performance of a wide variety of PCs. Moreover, when paired with a simple PC structure, we achieved state-of-the-art results on 10 out of 20 standard discrete density estimation benchmarks. Open-source code and experiments are available at https://github.com/UCLA-StarAI/Tractable-PC-Regularization.

Tractable Regularization of Probabilistic Circuits
Anji Liu Department of Computer Science UCLA Los Angeles, CA 90095 liuanji@cos ucla. edu
Guy Van den Broeck Department Computer Science UCLA Los Angeles, CA 90095 guyvdbêcs ucla. adu
Abstract
Probabilistic Circuits (PCs) are promising avenue for probabilistic modeling. They combine advantages probabilistic graphical models (PGMs) with those of neural networks (NNs). Crucially, however, they are tractable probabilistic models, supporting efficient and exact computation of many probabilistic inference queries, such marginals and MAP. Further, since PCs are structured compu- tation graphs, they can take advantage of deep-learming-style parameter updates, which greatly improves their scalability. However, this innovation also makes PCs prone to overfitting, which has been observed in many standard benchmarks. Despite the existence of abundant regularization techniques for both PGMs and NNs, they are not effective enough when applied to PCs. Instead, we re-think regularization for PCs and propose entropy regularization, that both take advantage of PCs' tractability and still have efficient implementation as computation graph. Specifically, data soften- ing provides a principled way to add uncertainty in datasets in closed form, which implicitly regularizes PC parameters. To learn parameters from soft- ened dataset, PCs only need linear time by virtue of their tractability. In en- tropy regularization, the exact entropy of the distribution encoded by PC can be regularized directly, which is again infeasible for most other density estima- tion models. We show that both methods consistently improve the generalization performance of wide variety of PCs. Moreover, when paired with simple PC structure, we achieved state-of-the-an results on 10 out of 20 standard discrete density estimation benchmarks. Open-source code and experiments available at htttps://github: com/UCLA- UCLA StarAA/Tractablee PC- Regularizatio
intuitive techniques, data softening and
Introduction
Probabilistic Circuits (PCs) 212 are considered be the lingua franca for Tractable Probabilistic Models (TPMs) as they offer unified framework to abstract from a wide variety of TPM circuit representations, such as arithmetic circuits (ACs) (3), sum-product networks (SPNs) 4 and prob- abilistic sentential decision diagrams (PSDDs) [5]. PCs are a successful combination of classic probabilistic graphical models (PGMs) and neural networks (NNs). Moreover, by enforcing various structural properties, PCs permit efficient and exact computation of a large family of probabilistic inference queries 6 g The ability to answer these queries leads successful applications in areas such as model compression [9] and model bias detection [10 I1 At the same time, PCs are analogous NNs since their evaluation also carried out using computation graphs. By exploiting the parallel computation power of GPUs, dedicated implementations [ 12] can train complex PC with millions of parameters in minutes. These innovations have made PCs much more expressive and scalable to richer datasets that are beyond the reach of "older" TPMs [3]
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

However, such advances make PCs more prone to overfitting, Although parameter regularization has been extensively studied in both the PGM and NN communities [5], we find that existing regularization techniques for PGMs and NNs are either not suitable or not effective enough when applied to PCs. For example, parameter priors or Laplace smoothing typically used PGMs, and often used in PC learning as well [16] 17 18. incur unwanted bias when learning PC parameters we will illustrate this point in Sec. 3) Classic NN methods such as LI and L2 regularization are not always suitable since PCs often use either closed-form or EM-based parameter updates.
This paper designs parameter regularization methods that are directly tailored for PCs. We propose two regularization techniques, data softening and entropy regularization. Both formulate the regularization objective in terms of distributions, regardless of their representation and parameterization. Yet, both leverage the tractability and structural properties of PCs. Specifically, data softening injects noise into the dataset by turning hard evidence in the samples into soft evidence 19 20 While learning with such softened datasets is infeasible even for simple machine learning models, with their tractability, a estimation (MLE) parameters given softened dataset in ([pl (P)) time, where |p| is the size of the PC and [D] is the size of the (original) dataset. For PCs that are not deterministic, every parameter update step can be done in ([p) (DI) time, still allowing efficient parameter learning. Additionally, the entropy of the distribution encoded by a PC can be tractably regularized. Although the entropy regularization objective for PC is molti- and global optimum cannot be found in general, we propose an algorithm that is guaranteed to converge monotonically towards a stationary point.
class of PCs (i.e., deterministic PCs) can learn the maximum-likeliben
We show that both proposed approaches consistently improve the test set performance over standard density estimation benchmarks. Furthermore, we observe that when data softening and entropy regularization are properly combined, even better generalization performance can be achieved. Specifically, when paired with a simple PC structure, this combined regularization method achieves state-of-the-art results on 10 out of 20 standard discrete density estimation benchmarks.
Notation We denote random variables by uppercase letters (e.g., X) and their assignments by lowercase letters (e.g,, z). Analogously, we use bold uppercase letters (e.g.. X) and bold lowercase letters (e.g., 2) for sets of variables and their joint assignments, respectively.
2 Two Intuitive Ideas for Regularizing Distributions
common way to prevent overfitting in machine learning models to regularize the syntactic representation of the distribution. For example, LI and L2 losses add mutually independent priors to all parameters of a model; other approaches such as Dropout [4], Bayesian Neural Networks (BNNs) 211. and Bayesian parameter smoothing [22] incorporate more complex and structured priors into the model 223. In this section, we ask the question: how would we regularize an arbitrary distribution, regardless of the model at hand, and the way it is parameterized? Such global, model-agnostic regularizers appear to be under-explored. Next, we introduce two intuitive ideas for regularizing distributions, and study how they can be practically realized in the context of probabilistic circuits in the remainder of this paper.
Data softening Data augmentation is a common technique to improve the generalization perfor- mance of machine learning models 24 25). A simple yet effective type of data augmentation is to inject noise into the samples, for example by randomly corrupting bits or pixels (26). This can greatly improve generalization as it renders the model more robust to such noise. While current noise injection methods are implemented as sequence of sampled transformations, we stress that some noise injection can be done in closed form: we will be considering all possible corruptions, each with their own probability, a function of how similar they are to a training data point.
Consider boolean variables"]ar as an example: after noise injection, a sample X=1 is represented as a distribution over all possible assignments (i.e., X= and X =0), where the instance X =1, which "similar" to the original sample, gets a higher probability: P(X 1) 3. Here 8 (0.5, 1] is a hyperparameter that specifies the regularization strength if 1, no regularization is added; if 8 approaches 0.5, the regularized sample represents an (almost) uniform distribution. For a sample x with K variables X = [X where the kth variable takes value Tk. we can similarly 'soften' x
We postpone the discussion on regularizing samples with non- boolean variables in Appendix B.1

---

by independently injecting noise into each variable, resulting in softened distribution Pa.s:
K
K
Va' Eva,(X), Pa.a(X = Pa - ( (1-
For full softened dataset D3. Its empirical distribution is the average softened distribution of its data. It is weighted dataset, where weight(D;; x) denotes the weight of sample æ in Dzz:
dataset D fxx (1) 1 this softening of the data can also be represented through a new, (x)())))))))))
D3 = (= and weight(Dg, N Pa
Σ
0 e X x))
(I)
This softened dataset ensures that each possible assignment has small but non-zero weight in the training data. Consequently, any distribution learned on the softened data must assign a small probability everywhere as well. Of course, materializing this dataset, which contains all possible training example, is not practical. Regardless, we will think of data softening as implicitly operating on this softened dataset. We remark that data softening is related soft evidence [27] and virtual which both define a framework to incorporate uncertain evidence into a distribution.
evidence 288
Entropy regularization Shannon entropy is an effective indicator for overfitting. For dataset D with N' distinct samples, a perfectly overfitting model that learns the exact empirical distribution has entropy log(N), A distribution that generalizes well should have much larger entropy, since it assigns positive probability to exponentially more assignments near the training samples. Concretely, for the protein sequence density estimation task (9) that we will experiment with in [Sec. 4.3) the perfectly overfitting empirical distribution has entropy 3, a severely overfitting learned model has entropy 92, yet a model that generalizes well has entropy 177. Therefore, directly controlling the entropy of the learned distribution will help mitigate overfitting. Given a model Pe parametrized by and a dataset D: (0) N we define the following entropy regularization objective:
LLent (0;D,T) = N Σ log (x) (.NTTEEN)))
where (PTT PP)
log (xx denotes the entropy of distribution Po. and r is a hyperparameter that controls the regularization strength. Various forms of entropy regularization have been used in the training process of deep learning models. Different from [q. (2) these methods
Emev=l))))))) Po (x)
regularize the entropy of a parametric [30 or non-parametric (32) output space of the model.
Although both ideas for regularizing distributions rather intuitive, it is surprisingly hard to implement them in practice since they are intractable even for the simplest machine learning models.
Theorem 1. Computing the likelihood of a distribution represented as a exponentiated logistic regression (or equivalently, single neuron) given softened data is #hrdd
Theorem 2. Computing the Shannon entropy of a normalized logistic regression model is #P-hard.
2 are provided in Appendices A.3 and A.4 Although data softening and entropy regularization infeasible for many models, will show in the following sections that they tractable to use when applied to Probabilistic Circuits (PCs) [I] class of expressive TPMs.
Proof of Thm. and
3 Background and Motivation
Probabilistic Circuits (PCs) are a collective term for wide variety of TPMs. They present a unified set of notations that provides succinet representations for TPMs such as Probabilistic Sentential Decision Diagrams (PSDDs) [5], Sum-Product Networks (SPNs) 4. and Arithmetic Circuits (ACs)
We proceed by introducing the syntax and semantics of a PCC
Definition (Probabilistic Cireuits). A PC p that represents a probability distribution over variables X is defined by parametrized directed acyclic graph (DAG) with a single root node, denoted nl. The DAG comprises three kinds of units: input, sum, and product. Each leaf node n in the DAG corresponds to input unit; each inner node n (i.c., sum and product units) receives inputs from its
3

---

0.23
0.17
0.12
0.058
supplrs)
supplc]
10
10
Imhalanceness
10' 10
(a) A PC with imbulanced sum unit Ri,
(b) Imbalanceness of the PCs Iearned by Strudel.
Figure 1: A Problem of Laplace smoothing. (a) Laplace smoothing cannot properly regularize this PC the sum unit n is imbalanced, i.e., its two children have drastically different support sizes. (b) A large fraction of sum units learned by a PC structure learning algorithm 17 are imbalanced.
children, denoted in(n). Each unit n encodes a probability distribution Pr, defined follows:
(x)
if is an input unit,
Pr (a:) = Eccin(s) On Pc(ax) [oEin(a) (x))
if is sum unit,
if v a product unit,
where Jn univariate input distribution (e.g., boolean, categorical Gaussian), and On.c repre- sents the parameter corresponds to edge (n, c). Intuitively, a sum unit models a weighted mixture distribution over its children, and product unit encodes factored distribution over its children. We assume w.l.o.g. that all parameters are positive and the parameters associated with any sum unit n sum up to 1 (i.e., Eecin(x) On. = 1). We further assume w.l.o.g. that PC alternates between sum and product layers
The size of a PC denoted [p). the number of edges in its DAG.
This paper focuses on two classes of PCs that support different types of queries: (i) PCs that allow linear-time computation of marginal (MAR) and maximum-a-poster
(MAP) inferences (c.g.. PSDDs [5], selective SPNs (34); (ii) PCs that only permit linear-time computation of MAR queries (c.g., SPNs (4). The borders between these two types of PCs are defined by their structural properties, i.e. constraints imposed on PC. First, in order to compute MAR queries in linear time, both classes of PCs should be decomposable (Def. 2) and smooth (Def. 3) [ These are properties of the (variable) scope (n) of PC units n, that is, the collection of variables defined by all its descendent input nodes.
Definition (Decomposability).
PC is decomposable if for every product unit n, its children have disjoint scopes: Ve,, C2 E in(n) (c1 # c2), ((c)) n Φ(c2) = Ø.
Definition (Smoothness). A PC smooth for every sum unit n, its children have the same scope: Ve1,22 02 in(n), ((c)) = ((02).
Next, determinism is required to guarantee efficient computation of MAP inference
35
Definition 4 (Determinism). Define the support supp(n) of a PC unit as the set of complete variable assignments E val(X) for which (a:) has non-zero probability (density): supp(n) {æ x Evval(X), Pm (x) > 0}. A PC is deterministic if for every sum unit n, its children have disjoint support: Ve, C2 E in(n) (c1 * c2), supp(c1) ssupp(c2) Ø.
Since the only difference in the structural properties of both PCs classes is determinism, we denote members in the first PC class as deterministic PCs, and members the second PC class as non- deterministic PCs. Interestingly. both PC classes not only differ in their tractability, which is characterized by the set of queries that can be computed within poly((p)) time (6] they also exhibit drastically different expressive efficiency. Specifically, abundant empirical [17 [33 and thcoretical 36) evidences suggest that non-deterministic PCs are more expressive than their deterministic counterparts. Due to their differences in terms of tractability and expressive efficiency, this paper studies parameter regularization on deterministic and non-deterministic PCs separately.
Laplace smoothing is widely adopted as a PC regularizer [6 I7]. Since it is also the default regularizer classical probabilistic models such as Bayesian Networks (BNs) 37 and Hierarchical Bayesian Models (HBMs) (38) this naturally raises the following question: are there differences between a good regularizer for classical probabilistic models such as BNs and HBMs and effective regularizers for PCs? The question can be answered affirmatively while Laplace
Motivation

---

Algorithm Forward pass
Algorithm Backward pass
1: Input: A deterministic PC p. sample æ
1: Input: A deterministic PC Vn, value(ni
2: Output: value m/:=(x (upp(n)) for each unit n
2: Output: flow[n, :==- (x E (% (7+)) for each pair (n, where n is a sum unit and inin(n)
3: foreach n traversed in postorder do
4: i isa input unit then value [n] fx)
3: Vn. context [r] < 00 context [aaxxx][]]]] <- value m4.]
elif isa product unit then
4: foreach sum unit n traversed in preorder do
6: L Vvalueee [ooggnn()) value(c]
5: forcach m pa(n) do (denote g pa(m)
7: else //n is sum unit
6: f valuela context[g]
value[m]
8:
Lavaluel [n] Ceein()) value(c]
7: contextinn += f;
flow g. m)
smoothing provides good priors to BNs and HBMs, its uniform prior could add unwanted bias to PCs. Specifically, for every sum unit Laplace smoothing assigns the same prior to all its child parameters (i.e.. (0 CE in(n)), while in many practical PCs, these parameters should be given drastically different priors. For example, consider the PC shown in Fig. Ia). Since 02 has an exponentially larger support than C₁, it should assumed as prior that 012 will be much larger than Oy..
We highlight the significance of the above issue by examining the fraction of sum units with imbal- anced child support sizes in PCs learned by Strudel, a ofate-of-the-rr structure learning algorithm for deterministic PCs [5). We examine 20 PCs learned from the 20 density estimation benchmarks 39 respectively. All sum units with 2 children and with support size 2 128 are recorded. We measure "imbalanceness" of a sum unit n by the fraction of the maximum and minimum support size of children (i.e., maxe Cin(so [supp(c)]] Ein(s) [supp[es]]
). As demonstrated Fig. (b), more than 20% of the sum units have imbalanceness 2 102, which suggests that the inability of Laplace smoothing to properly regularize PCs with imbalanced sum units could lead to severe performance degradation in practice.
4 How Is This Tractable And Practical?
In this section, we first provide additional background about the parameter learning algorithms for deterministic and non-deterministic PCs (Sec. 4.1). We then demonstrate how the two intuitive ideas for regularizing distributions (Sec. 2}. i.e., data softening and entropy regularization, can be efficiently implemented for deterministic Secc. 4.2p and non-deterministic (Sec. 4.3) PCs.
4.1 Learning the Parameters of PCs
Deterministic PCs Given deterministic PC p defined on variables X and dataset D = (1)
Ji=l
N the maximum likelihood estimation (MLE) parameters 0y: argmax Σi= log (0) (9; 0) can be learned in closed-form. To formalize the MLE solution, we need a few extra definitions.
Definition (Context). The context Yn of every unit n in a PC is defined in a top-down manner: for the base case, context of the root node n, is defined as its support: "n- supp(n,)) For every other node n, its context is the intersection of its support and the union of its parents' (pa(n)) contexts:
U 7m suppp(n).
Yn =
mppa(()
Intuitively, if an assignment a is in the context of unit n, then there exists path on the PC's DAG from n to the root unit n, such that for any unit m the path, we have x E supp(mm). Circuit flow extends the notation of context to indicate whether sample is in the context of an edge (n, c).
Definition 6 (Flows). The flow F (z) of any edge (n, c) in a PC given variable assignments x E Ex) defined as 1 [ (n.e.. where 1[1] is the indicator function. The flow Fn,c(D) w.r.t. N dataset D= (x(() Ji=1 is the sum of the flows of all its samples: F Fn.c(D): : (z))
The flow (xr) for all edges (n, c) in a PC p w.r.t. sample æ can be computed through forward and backward path that both take O(pl)) time. The forward path, as shown in Alg. 1| starts from the leaf units and traverses the PC postorder to compute Yn, value(n] == [ar E supp(n)): afterwards, the backward path illustrated in Alg. 2 begins at the root unit n, and traverses the PC in preorder to
5

---

.000
CLT
HCLE
ns
n
:000
Tull-butch Mast betch EM
116
100
200
X1 - -a
Figure 2: non-deterministic PC can be modified as equivalent determin- istic PC with hidden variables.
Figure 3: Average train LL on MNIST using dif- ferent EM updates.
Figure 4: HCLT is con- structed by adding hidden variables in CLT [43
compute Vn, context 1 as well as V(n, c). f] (a)( By Def. 6 the time complexity for computing F (2)) with respect to all edges (n, c) in is O (1pl11120 (pl-)2)), where (D) is the size of dataset D. The correctness of[Alg. ajndd 2 are justified in Appendix A.6
The MLE parameters Op given dataset D can be computed using the flows [5]
V(n,c) c), 02 = Fn,c
E Σ esin(s) (D.c(D).
Define hyperparameter a (a: 2 0), for every sum unit n, Laplace smoothing regularizes its child parameters (i.e., nfn,e CE in(n))) by adding pseudocount a a/iin(n) to every child branch of n, which is equivalent adding a [in(n) the numerator Eq. (3) and a to its denominator.
Non-deterministic PCs As justified by Peharz et al. 400 every non-deterministic PC can be augmented deterministic PC with additional hidden variables. For example, in Fig. 2] the left PC is not deterministic since the support of both children of n1 (i.e., f2 and ftz) contains T2.2. The right PC augments the left one by adding input units correspond Z1, which retains determinism by "dividing" the overlapping support x 22 into I 22 Esupp(n2) (222 and x 2 i E supp(ns3). Under this interpretation, parameter learning of non-deterministic PCs equivalent to learning the parameters of deterministic PCs given incomplete data (we never observe the hidden variables), which can be solved by Expectation-Muxinnn is the default parameter learning algorithm for non -ooo-meeermiiitic PCs [13 10]
hidden variable
(EM) 41 42 In fact, EM
Under the latent variable model view of non-deterministic PC, its EM updates be computed using expected flows [10]. Specifically, given observed variables X and (implicit) hidden variables Z, the expected flow of edge (n,c) c) given dataset ' is defined
flows
EF FFnno(D: 0) = Eew (-=::)))) Fn,, (x, [x)=
where 0 is the set of parameters, and (- ac; 0) is the conditional probability over hidden variables Z given specified by the PC rooted unit Similar to flows, the expected flows can be computed via a forward and backward pass of the PC (Alg. 5) Jland the Appendix). As shown by Choi et al. [0] for non-deteriiiistic PC, its parameters for the next EM iteration are given by
g(new) = (D; n.c
Σ cEin(n)
EF EF,,,((;;))
(4)
This paper uses hybrid EM algorithm, which uses mini-batch EM updates to initiate the training process, and switch to full-batch EM updates afterwards. Specifically, in mini-batch EM, 0 ((ne)) are computed using mini-batches of samples, and the parameters are updated towards the taget with a step size yy: (+++1)
())) + (neeww); when using full-batch EM, iteratively compute the updated parameters (inew) using the whole dataset, Fig. 3 demonstrates that this hybrid approach offers faster convergence speed compared to using full-batch or mini batch EM only.
4.2 Regularizing Deterministic PCs
We demonstrate how the intuitive ideas for regularizing distributions presented in Sec. (i.e., data softening and entropy regularization) can be efficiently applied to deterministic PCs.
Data softening As hinted by Fg.. (1) we need exponentially many samples to represent a softened
dataset, which makes parameter learning intractable even for the simple logistic regression model
(Thm 1), let alone more complex probabilistic models such as VAEs [44 and GANs [45). Despite

---

Algorithm 3 PC Entropy regularization
Input: A deterministic PC pi flow (D) for every edge (n, c) in pi hyperparameter 7.
2: Output: A set of rrg-parmetees, {Pn.e (n, c) E p). which are the solution of Eq. (2)
3: Vn, node vud__prob[n] [n] +- 0: node pode_prob[nr] f- //n, the root node of p
4: while not converge do
5: Vn, entropy(n) < The entropy of the sub-PC rooted at n (see Alg. 4 in Appendix A.2
6: foreach sum unit n traversed in preorder (parent before children) do
7: de + Fn, (D)/
= T node_prob(n)] [[(ce in(n) is the set of children of n
Solve for (fn,c, |lin(o)] in the following set of equations (y is variable):
8:
-b. die - b. Pn,c, + entropyla] = y (Vi (L,...,,/i(nn)))) [lin(n)) @Pni =1
(5)
9:
for each E in(n) and each in(c) do //Update node, node_prob of grandchildren thode_probjng f- moodepprobllle + efnie node_ code_ppro(11
10:
this negative result, the MLE parameters of a PC p w.r.t DB can be computed in time O(pl)-|D) which is linear w.r.t. the model size as well as the size of the original dataset.
Theorem 3. Let fa(e) 3-33-lee 1[z E supp(n)] + (1- & supp(n)] in Alg. 1, Given deterministic PC p. boolean dataset D. and hyperparameter 3 E (0.5, 1]. the set of all flows {F (Fn,e(Dg) { Y edge (n, ()) w.r.t. the softened dataset D3 can be computed by Alg. 7 [nadd] within (lP) time.
Proof of this theorem is provided in Appendix A.I Since the MLE parameters (Eq. (3) w.r.t. D3 can be computed in O(pl)) time using the Hows, the overall time complexity compute the MLE parameters is again ((p)) (PI).
Entropy regularization the entropy of a deterministic PC can be exactly computed in (Ipl) time 66 However, it is still unclear whether the entropy regularization objective LLent (0; D, 7) (Eq. (2) can be tractably maximized. We answer this question with a mixture of positive and negative results: while the objective is multi-modee and the global optimal is hard to find, we propose an efficient algorithm that (i) guarantees convergence to a stationary point, and (ii) achieves high convergence rate in practice. We start with the negative result.
The hope for tractable PC entropy regularization comes from the fact that
Proposition 1. There exists deterministic PC p. hyperparameter T, and a dataset 'D such that LL ( D.T) r) Eq. (2) is non-concave and has multiple local maximas.
Although global optimal solutions are generally infeasible, we propose an efficient algorithm that guarantees to find a stationary point of LLent (0; T). Specifically, Alg. takes as input a deterministic PC p and all its edge flows w.r.t. D. and returns set of learned log-parameters that correspond to a stationary point of the objective [ In its main loop (lines 4-10), the algorithm alternates between two procedures: (i) compute the entropy of the distribution encoded by every node w.r.t. the current parameters (line 5) and (ii) update PC parameters with regard to the computed entropies (lines 6-10). Specifically, in the parameter update phase (i.c., the second phase), the algorithm traverses every sum unit n. in preorder and updates its child parameters by maximizing the entropy regularization objective (LLeut (0: ()) with all other parameters fixed. This done by in EEq (5) using Newton's 's method (lines 7-8) In addition to the child nodes' entropy computed the first phase. [iq. (5) jsess the top-down probability of every unit n (i.e.,
Proof is given in Appendix A.7
solving the set of equations
node_pros node_prob(n]), (n]), which is progressively updated in lines 9-10.
Theorem 4.
Alg. converges monotonically to a stationary point of LLent (0; T,)) Eq. (2)
Proof. The high-level idea of the proof is to show that the parameter update phase (lines 6-10) opti- mizes a concave surrogate objective of LLent 0 D, T), which is determined by the entropies computed
We compute parameters in the logarithm space for numerical stability.
This can he done by Alg. shown in Appendix A.2 Lem. proves that Alg. 4 takes ((pl)) time.
"Details for solving Eq. (5) given Appendix B.2

---

Dnta sottning
inrroveeee
Entropo reap lkribaattto
AVNO 1HE aet Improvennn
Data coban Enenpy
Data softening
Entrocy reg.
Percenage
Data softening Entropy reg.
12
6a
02
03
06
Degres
coarliting
Degine overfitiigg
Aveg. test improverennt
Figure 5: Both data softening and entropy regularization effectively improve the test set bog-likelihood (LL) across various datasets [39 and PC structures [17]. LL improvement (higher is better) represents
the gain of test set L.L. compared to Laplace smoothing. The test-set LLS reported in Table 3
in line Specifically, we show that whenever the surrogate objective is improved, LLeut (0; D, 7) is also improved. Since the surrogate objective is concave, it can be easily optimized. Therefore, Alg. converges to a stationary point of LL (0; D, r). The detailed proof is in Appendix A.5
Alg. 3 can be regarded as a EM-like algorithm, where the E-step is the entropy computation phase (line 5) and the M-step the parameter update phase (lines 6-10). Specifically, the E-step constructs concave surrogate of the true objective (LLeur (0; DD r)), and the M-step updates all parameters by maximizing the concave surrogate function. Although Thm. plrovidess no convergence rate analysis, the outer loop typically takes 3-5 iterations to converge in practice. Furthermore, [Eq. ( can be solved with high precision a few (< 10) iterations. Therefore, compared to the computation of all flows w.r.t. D, which takes (1pl DI) time, Alg. 3 takes a negligible ((pl) time.
In response to the motivation in Sec. 3) we show that both proposed methods can overcome the imbalanced regularization problem of Laplace smoothing. Again consider the example PC in Fig. T a), we conceptually demonstrate that both data softening and entropy regularization will not over-regularizztion 01 compared to 012- First, data softening essentially add no prior to the parameters, and only soften the evidences the dataset. Therefore, will not over-regularize children with small support sizes. Second, entropy regularization will add much higher prior to 012. Suppose n=10, 10, consider maximizing Eq. (2) with an empty dataset (i.e., we maximize ENT (pn,) directly), the optimal parameters would be 0n R 0.002 and 012 A 0.998. Therefore, entropy regularization will tend to add a higher prior to children with large support sizes. More fundamentally. the reason why both proposed approaches do not add biased priors to PCs is that they are designed to be model-agnostie i.., their definitions as shown in Sec. 2 are independent with the model they apply to.
Empirical evaluation We empirically evaluate both proposed regularization methods on the twenty density estimation datasets (39. Since we are only concerned with parameter learning, we adopt PC structures (defined by its DAG) learned by Strudel [17]. 16 PCs with different sizes were selected for each of the 20 datasets. For all experiments, we performed a hyperparameter search for all three regularization approaches (Laplace smoothing, data softening, and entropy regularization f using the validation set and report results on the test set. Please refer to Appendix for more details.
First look at the scatter plots on the left. The x x-axis represents the degree of overfitting, which is computed as follows: denote LLtrain and LLval as the average train and validation log-likelihook under the MLE estimation with Laplace smoothing (a = 1.0), the (fttrran)/LLouu which roughly captures how much the
Results are summarized in Fig. 5
degree of overfitting is defined as (LLpa! dataset/model pair suffers from overfitting. The y-axis represents the improvement on the average test set liglliiel compared to Laplace smoothing. As demonstrated by the scatter plots, despite few outliers, both proposed regularization methods steadily improve the test set LL over various datasets and PC structures, and the LL improvements are positively correlated with the degree of overfitting, Furthermore, as shown by the last scatter plot and the histogram plot, when combining data softening and entropy regularization, the LL improvement becomes much higher compared to using the two regularizers individually.
4.3 Regularizing Non-Deterministie PCs
By viewing every non-deterministic PC as a deterministic PC with additional hidden variables (Sec. 4.1), the regularization techniques developed in Secc can be directly adapted. Specifically,
SSpecifically, {0.1, 0.4, 1.0, 4.0, 10.0). (0.9996, 0.999, 0.996). 0.0001,0001,011
8

---

Table 1: Test set log-likelihood in 20 density estimation benchmarks. We compare our method (HCLT) with the best performance (Best PSDD) over 2 deterministic PC learner: Strudel [T7] and LeamnPSDD T6 as well as the best performance (Best SPN) over 4 SPN learning algorithms: EinSumNet [33 LearnSPN 18. ID-SPN (47. and RAT-SPN 48 With the help of data softening and entropy regularization (a = 3 0.998, and T = 0.001), HCLT achieved the best performance over 10 out of datasets. All experiments for HCLT were repeated 5 times, and the average and
standard deviation are reported.
Dataset
HCLT
Best PSDD
Best SPN
Dataset
HCLT
Best PSDD
Best SPN
accidents
-2.744-0.33
-28.29
-26.98
jester
-52.46+-0.01
-54.63
-52.56
-16.07-0.06
-16.52
-19.00
kdd
-2.18:0..00
-2.17
-2.12
baudio
-39.77=0.01
41.51
-39.79
kosarek
-10.66:0.01
-10.98
-00.60
bbc
-251.04=+1119
-258.96
-248.33
msnhe
-6.05++0.01
-6.04
-6.03
bnetflix
-56.27=0.01
-58.53
-56.36
msweb -9.98-10.05
-9.33
-9.73
hook
-33.83-0.01
-35.77
-34.14
nites
-5.99+0.01
+6.03
-6.01
c20ng
-153.40-13.83
-160.43
-151.47
plants
-14.26.10.16
-13.49
-12.54
er52
-86.26=3.667
92.38
-83.35
pumbs*
23.64::..25
25.28
-22.40
cwehkb
-152.77+1.07
-160.5
-151.84
tmovie
-50.81+0.12
-55.41
-51.51
dna -7.105-0.117
-82.03
-81.21
tretail
-10.84.10.01
-10.90
-10.85
data softening can be regarded as injecting noise in both observed and hidden variables. Since the dataset provides no information about the hidden variables anyway, data softening essentially still "perturbs" the observed variables only. On the other hand, entropy regularization will have different behaviors when applied to non-deterministic PCs. Specifically, since it is coNP-hard compute the entropy of a non-deterministic PC [6) it is infeasible optimize the entropy regularization objective
LLent ( D, r) EEq. (2).. However, we can still regularize the entropy of the distribution encoded by a non-deterministic PC over both of its observed and hidden variables, since explicitly representing the hidden variables renders the PC deterministic (Sec. 4.1).
On the implementation side, data softening is performed by modifying the forward pass of the algorithm used compute expected flows A.e...ll.... Saand the Appendix). Entropy regularization is again performed by Alg. 3 at the M-step of each min- min-batch/iiii basch/full-bateee EM update, except that the input flows (i.e., F) are replaced by the corresponding expected flows (i.e.. EF).
Empirical evaluation We use simple yet effective PC structure, hidden Chow-Liu Tree (HCLT), demon- strated in Fig. 4 Specifically, on the left is a Bayesian network representation of Chow-Liu Tree (CLT) over 5 variables. For any CLT over variables {X; we can modify
-158
189
d-171
HCLT through the following steps. First, we introduce a set of latent variables {2c }= Next, we replace all observed variables the CLT with corresponding latent variable (i.c., Vi, X, is replaced by 2,). Finally, we add edge from every latent variable its corresponding observed variable (i.c., Vi, add an edge Z, X,). The HCLT structure then compiled into PC that encodes the same probability distribution. We used the hybrid mini-batch + batch EM described in [Sec. 4.1 PCs with 100 mini-batch EM epochs and 100 full-batch EM epochs. Please refer to Appendxxx B for hyperparameters related to the HCLT structure and the parameter learning process. Similar to Sec. 4.2] we perform hyperparameter search for all methods using the validation set, and report results on the test set.
-18
Laplace smoothing
-176
Data softening Entrogy req.
-175
50
120
150
700
Epoch
Figure Average (#std) test LL over trials on the protein dataset.
For all experiments, we trained the
We first examine the performance on a protein sequence dataset 29 that suffers from severe overfitting. Specifically, the training LL is typically above -100 while the validation and set LL are around - 170. Fig. shows the test LL for Laplace smoothing and the hybrid regularization approach as training progresses. With the help of data softening and entropy regularization, we were able to obtain consistently higher test set LL. Next, we compare our HCLT model (with regularization) with the tate-offthe--e PSDD (Strudel [17 and LearnPSDD [6) and SPN (EinSumNet [I],
LearnSPN [8] ID-SPN 47 and RAT-SPN 48 learning algorithms. Results are summarized Table I With proper regularization, HCLT out-performed all baselines in 10 out 20 datasets.
Comparing with individual baselines, HCLT out-performs both PSDD learners all datasets; HCLT

---

achieved higher log- ligeliield on 18, 19, 10, and 17 datasets compared to EinSumNet, LearnSPN, ID-SPN, and RAT-SPN, respectively.
Conclusions
This paper proposes two model-agnostic distribution regularization techniques: data softening and entropy regularization. While both methods are infeasible for many machine learning models, we theoretically show that they can be efficiently implemented when applied to probabilistic circuits. On the empirical side, we show that both proposed regularizers consistently improve the generalization performance wide variety of PC structures and datasets.
This work is partially supported by NSF grants #IIS- 1943641, # 1956441, #CCF-1837129, DARPA grant 1-6600-177---002, Sloan Fellowship, Intel, and Facebook.
Acknowledgement
References
[1] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. 2020.
[2] Meihua Dang, Pasha Khosravi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. Juice:
A julia package for logic and probabilistic circuits. In Proceedings of the 35th AAAI Conference on Artificall Intelligence (Demo Track), 2021.
[3] Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM (JACM), 50(3):280-305 2003.
[4] Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference Computer Vision Workshops (ICCV Workshops), pages 689-690. IEFE, 2011.
[5] Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In Proceedings of the 14th international conference principles of knowledge representation and reasoning (KR), pages 1-10, 2014.
[6] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A composi- tional atlas of tractable circuit operations: From simple transformations to complex information- theoretic queries. arXiv preprint arXiv:2102.061333 2021.
[7] Pasha Khosravi, YooJung Choi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. On tractable computation of expected predictions. In Advances in Neural Information Processing Systems 32 (NeurIPS), dec 2019.
[8] Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pages
Citeseer, 2016.
[9] Yitao Liang and Guy Van den Broeck. Towards compact interpretable models: Shrinking of learned probabilistic sentential decision diagrams. In IJCAI 2017 Workshop on Explainable Artificial Intelligence (XAI), August 2017.
[10] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group fairness by probabilistic modeling with latent fair decisions. arXiv preprint arXiv:2009.09031, 2020.
[11] YooJung Choi, Golnoosh Farnadi, Behrouz Babaki, and Guy Van den Broeck. Learning fair naive bayes classifiers by discovering and eliminating discrimination patterns. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 34, pages 10077-10084, 2020.
[12] Alejandro Molina, Antonio Vergari, Karl Stelzner, Robert Peharz, Pranav Subramani, Nicola Di Mauro, Pascal Poupart, and Kristian Kersting. Spflow: An easy and extensible library for deep probabilistic learning using num-produce networks. arXiv preprint 1901::901103304. 2019.
[13] 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. International Conference on Machine Learning, pages 7563-7574, PMLR, 2020.
10

---

[14] Nitish Srivastava, Geoffre Hinton, Alex Krizhevsky, Ilya Sutskever, and Ruslan Salakhutdinov. Dropout: a simple way to prevent neural networks from overfitting. The journal of machine learning research, (5(1):1929-1958 2014.
[15] Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In International conference on machine learning, pages 448 148-456. PMLR, 2015.
[16] Yitao Liang, Jessa Bekker, and Guy Van den Broeck. Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
[17] Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: Learning structured- decomposable probabilistic circuits. arXiv preprint arXiv:2007.09331 2020.
[18] Robert Gens and Domingos Pedro. Learning the structure of com-product networks. In International conference machine learning, pages 873-880. PMLR, 2013.
[19] Hei Chan and Adnan Darwiche. On the revision of probabilistic beliefs using uncertain evidence.
Artificial Intelligence, 163(1)67--9,, 2005.
[20] Rong Pan, Yun Peng, and Zhongli Ding. Belief update in bayesian networks using uncertain evidence. In 2006 18th IEEE International Conference on Tools with Artificial Infelligence (ICTAP'0), pages 441-444. IEEE, 2006.
[21] Ethan Goan and Clinton Fookes. Bayesian neural networks: An introduction and survey. In Case Studies in Applied Bayesian Data Science pages 45-87. Springer, 2020.
[22] Nicola Di Mauro, Antonio Vergari, and Floriana Esposito. Learning accurate cutset networks by exploiting decomposability, In Congress of the Italian Association for Artificial Intelligence, pages 221-232. Springer, 2015.
[23] Yarin Gal and Zoubin Ghahramani. Dropout as a bayesian approximation: Representing model uncertainty in deep learning. In international conference on machine learning, pages 1050-1059, PMLR, 2016.
[24] Luis Perez and Jason Wang. The effectiveness data augmentation in image classification using deep leamning arXiv preprint arXiv: 1712.::71..04221 2017.
[25] Christian Szegedy, Vincent Vanhoucke, Sergey Ioffe, Jon Shlens, and Zbigniew Wojna. Re- thinking the inception architecture for computer vision. In Proceedings of the IEEE conference on computer vision and pattern recognition, pages 2818 2818-288 1818-2826, 2016.
[26] Pascal Vincent, Hugo Larochelle, Yoshua Bengio, and Pierre-Antoine Manzagol. Extracting and composing robust features with denoising autoencoders. In Proceedings of the 25th international conference on Machine learning, pages 1096-1103, 2008.
[27] Richard C Jeffrey. The logic of decision. University of Chicago press, 1990.
[28] Judea Pearl. Probabilistic reasoning in intelligent systems: networks of plausible inference. Elsevier, 2014.
[29] William Russ, Matteo Figliuzzi, Christian Stocker, Pierre Barrat-Charlaix, Michael Socolich, Peter Kast, Donald Hilvert, Remi Monasson, Simona Cocco, Martin Weigt, et al. An evolution- based model for designing chorismate mutase enzymes. Science, 3696650)::44-445,, 2020.
[30] Yves Grandvalet and Yoshua Bengio. Entropy regularization. 2006.
[31] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros. Unpaired image-to-image translation using cycle-consistent adversarial networks. In Proceedings the
the IEEE international
conference on computer vision, pages 2023,,232, 2017.
[32] Yihao Feng, Dilin Wang, and Qiang Liu. Learning to draw samples with amortized stein variational gradient descent. arXiv preprint arXiv:1707.0666 2017.
[33] Antonio Vergari. Nicola Di Mauro, and Floriana Esposito. Simplifying, regularizing and strengthening sum-product network structure learning. In Joint European Conference on Machine Learning and Knowledge Discovery in Databases, pages 343-358. Springer, 2015.
[34] Robert Peharz, Robert Gens, and Pedro Domingos. Learning selective sum- sum-product networks.
In LTPM workshop, volume 32, 2014.

---

[35] Jun Mei, Yong Jiang, and Kewei Tu. Maximum posterioni inference in sum-product networks.
In Proceedings of the AAAI Conference on Artificial Intelligence, volume 32, 2018.
[36] Arthur Choi and Adnan Darwiche. On relaxing determinism in arithmetic circuits. In Interna-
tional Conference on Machine Learning pages 825-833. PMLR, 2017.
[37] David Heckerman. A tutorial on learning with bayesian networks. Innovations in Bayesian networks, pages 33-82, 2008.
[38] Greg M Allenby and Peter E Rossi. Hierarchical bayes models. The handbook of marketing research: Uses, misuses, and future advances, pages 418 418-440, 2006.
[39] Jan Van Haaren and Jesse Davis. Markov network structure learning: A randomized feature gen- eration approach. In Proceedings of the AAAI Conference Artificial Intelligence, volume 26, 2012.
[40] Robert Peharz, Robert Gens, Franz Pernkoff, and Pedro Domingos. On the latent variable interpretation in sum-produc networks. IEEE transactions on pattern analysis and machine intelligence, 39(10):003-22444 2016.
[41] Adnan Darwiche. Modeling and reasoning with Bayesian networks. Cambridge university press, 2009.
[42] Arthur P Dempster, Nan M Laird, and Donald B Rubin. Maximum likelihood from incomplete data via the em algorithm. Journal of the Royal Statistical Society: Series B (Methodological), 39(1):1-22, 1977.
[43] CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions Information Theory, 14(3):662-45 1968.
[44] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[45] Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron C Courville, and Yoshua Bengio. Generative adversarial nets. In NIPS, 2014.
[46] Andy Shih and Stefano Ermon. Probabilistic circuits for variational inference in discrete graphical models. In Advances in Neural Information Processing Systems 33 (NeurIPS), december 2020.
[47] Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning, pages 710-718. PMLR, 2014.
[48] Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random sum- cum-product networks: A simple and effective approach to probabilistic deep learning. Uncertainty Artificial Intelligence, pages 334-344. PMLR, 2020.
[49] Guy Van den Broeck, Anton Lykov, Maximilian Schleich, and Dan Suciu. On the tractability of SHAP explanations. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, Feb 2021.
Checklist
The checklist follows the references. Please read the checklist guidelines carefully for information how to answer these questions. For each question, change the default [TODO] to [Yes], [No], or [N/A]. You are strongly encouraged include justification to your answer, either by referencing the appropriate section of your paper or providing a brief inline description. For example:
Did you include the license to the code and datasets? [Yes] See Section X.
Did you include the license to the code and datasets? [No] The code and the data are proprietary.
Did you include the license to the code and datasets? [N/A]
Please do not modify the questions and only use the provided macros for your answers. Note that the Checklist section does not count towards the page limit. In your paper, please delete this instructions block and only keep the Checklist section heading above along with the questions/answers below.
12

---

1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes] Contributions clearly stated in lines 42-52 and match the referred theorems and algorithms.
(b) Did you describe the limitations of your work? [Yes] Sec. 4.2
discusses the limitation of TTh. Sec. 4.3) discusses the limitation of applying entropy regularization to non-deterministic PCs.
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] All theorems in the main text formally state all assumptions.
(b) Did you include complete proofs of all theoretical results? [Yes] All proofs are included in the appendix. We added a reference to the corresponding proof after each theorem statement.
3. If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or a URL)? [Yes] Code and instructions to reproduce the experimental results are included in the supplementary material.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] All details for reproducibility specified in Appendices B.3 and
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes] Error bars and standard deviations over 5 runs reported in Fig. and Table 1 respectively.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes] Details about computing resources can be found in Appendix B.3
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes] We cited all PC learning algorithms well the datasets/benchmarkk
adopted in Sec. 4
(b) Did you mention the license of the assets? [Yes] We specified both the used algorithm and data are publicly available [nce.. 4
(c) Did you include any new assets either in the supplemental material as URL? [Yes] We included our code the supplementary material.
(d) Did you discuss whether and how consent was obtained from people whose data you're using/curating? [N/A]
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
(b) Did you describe any potential participant risks, with links Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "zhY4V9YxOuv", "reviewer": "Reviewer_HNkH", "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.  ", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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. \n \nOverall, 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.\n\nComments:\n1. 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.\n2. Proof of theorem 3 was quite involved. It would help if a high-level sketch is given first and then details are presented. \n3. 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?  ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "14"}, "extra_text": {}}, {"review_id": "TiIx2yZVILx", "reviewer": "Reviewer_F3ZK", "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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.\n\nThis 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.\n\nThe 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\n\nThe 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.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "1"}, "extra_text": {}}, {"review_id": "O_T_Qfi711W", "reviewer": "Reviewer_EufT", "summary": "In the context of Probabilistic Circuits (PCs), recent developments of large-scale models point to the increasing need of regularization. \nHaving large models with millions of parameters is inherently a challenge, but more so for models with structural restrictions that favor tractability.\nIn this paper, the authors present regularization techniques for probabilistic circuits including non-deterministic models.\nThe 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.\nAnd demonstrate empirically that the approach is beneficial.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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.\n\nThe paper is well-written and technically sound, and very relevant and significant for the tractable probabilistic models community.\nThe 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.\n\nThere are minor clarifications that I believe could help readers better understand the paper:\n- 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).\n- In line 141, maybe you want to add the word “exact”, as you can compute approximates for the non-deterministic variant.\n\nA 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.\nA comparison here would help the reader better understand the impact of your approach, even if they are orthogonal.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors have not mentioned societal impact, but I believe there are no conflicts or points to raise.", "review_text": "", "extra_scores": {"ethical_concerns": "No ethical concerns.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "7mjmiU86p34", "reviewer": "Reviewer_DV79", "summary": "The paper deal with the problem of regularization of Probabilistic Circuits (PCs).", "questions": "", "limitations": "", "rating": 7, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "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": "", "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.\n\nSome theorems are presented in order to prove the tractability of the learning algorithms.\n\nTable 1 is not referenced in the paper.\n\nAs 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. \n\nIt is not clear why a simple CLT has been used for non-deterministic PCs instead of learning a more complex one.\n\nThe experimental evaluation proves the validity of the proposed approaches.\n\nConcluding, the paper is well written, the idea is novel for PCs, and the results, both theoretical and empirical, are good.\n\n[1] Learning accurate cutset networks by exploiting decomposability, 2015 \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "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_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

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)