Tractable Regularization of Probabilistic Circuits
Year: 2022

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.

text: 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.

heading: 1 Introduction
text: Probabilistic Circuits (PCs) [1, 2] are considered to be the lingua franca for Tractable Probabilistic Models (TPMs) as they offer a unified framework to abstract from a wide variety of TPM circuit representations, such as arithmetic circuits (ACs) [3], sum-product networks (SPNs) [4], and probabilistic 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, 7, 8]. The ability to answer these queries leads to successful applications in areas such as model compression [9] and model bias detection [10, 11]. At the same time, PCs are analogous to NNs since their evaluation is also carried out using computation graphs. By exploiting the parallel computation power of GPUs, dedicated implementations [2, 12] can train a 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 [13].
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
However, such advances make PCs more prone to overfitting. Although parameter regularization has been extensively studied in both the PGM and NN communities [14, 15], 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 in 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 L1 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 class of PCs (i.e., deterministic PCs) can learn the maximum-likelihood estimation (MLE) parameters given a softened dataset in O(|p| · |D|) 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 O(|p| · |D|) 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 multi-modal and a global optimum cannot be found in general, we propose an algorithm that is guaranteed to converge monotonically towards a stationary point.
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., x). Analogously, we use bold uppercase letters (e.g., X) and bold lowercase letters (e.g., x) for sets of variables and their joint assignments, respectively.

heading: 2 Two Intuitive Ideas for Regularizing Distributions
text: A common way to prevent overfitting in machine learning models is to regularize the syntactic representation of the distribution. For example, L1 and L2 losses add mutually independent priors to all parameters of a model; other approaches such as Dropout [14], Bayesian Neural Networks (BNNs) [21], and Bayesian parameter smoothing [22] incorporate more complex and structured priors into the model [23]. 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 performance 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 a 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, as a function of how similar they are to a training data point.
Consider boolean variables1 as an example: after noise injection, a sample X=1 is represented as a distribution over all possible assignments (i.e., X=1 and X=0), where the instance X=1, which is “similar” to the original sample, gets a higher probability: P (X= 1) =β. Here β∈ (0.5, 1] is a hyperparameter that specifies the regularization strength — if β=1, no regularization is added; if β approaches 0.5, the regularized sample represents an (almost) uniform distribution. For a sample x with K variables X :={Xi}Ki=1, where the kth variable takes value xk, we can similarly ‘soften’ x
1We postpone the discussion on regularizing samples with non-boolean variables in Appendix B.1.
by independently injecting noise into each variable, resulting in a softened distribution Px,β :
∀x′∈val(X), Px,β(X=x′) := K∏ i=1 Px,β(Xi=x ′ i) = K∏ i=1 ( β ·1[x′i=xi] + (1−β)·1[x′i 6=xi] ) .
For a full dataset D :={x(i)}Ni=1, this softening of the data can also be represented through a new, softened dataset Dβ . Its empirical distribution is the average softened distribution of its data. It is a weighted dataset, where weight(Dβ ,x) denotes the weight of sample x in Dβ :
Dβ := {x |x∈val(X)} and weight(Dβ ,x) = 1
N N∑ i=1 Px(i),β(X = x). (1)
This softened dataset ensures that each possible assignment has a 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 to soft evidence [27] and virtual evidence [28], which both define a framework to incorporate uncertain evidence into a distribution.
Entropy regularization Shannon entropy is an effective indicator for overfitting. For a 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 a much larger entropy, since it assigns positive probability to exponentially more assignments near the training samples. Concretely, for the protein sequence density estimation task [29] 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 Pθ parametrized by θ and a dataset D :={x(i)}Ni=1, we define the following entropy regularization objective:
LLent(θ;D, τ) := 1
N N∑ i=1 logPθ(x (i)) + τ · ENT(Pθ), (2)
where ENT(Pθ) :=− ∑ x∈val(X) Pθ(x) logPθ(x) denotes the entropy of distribution Pθ, and τ 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 Eq. (2), these methods regularize the entropy of a parametric [30, 31] or non-parametric [32] output space of the model.
Although both ideas for regularizing distributions are 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, a single neuron) given softened data is #P-hard.
Theorem 2. Computing the Shannon entropy of a normalized logistic regression model is #P-hard.
Proof of Thm. 1 and 2 are provided in Appendices A.3 and A.4. Although data softening and entropy regularization are infeasible for many models, we will show in the following sections that they are tractable to use when applied to Probabilistic Circuits (PCs) [1], a class of expressive TPMs.

heading: 3 Background and Motivation
text: Probabilistic Circuits (PCs) are a collective term for a wide variety of TPMs. They present a unified set of notations that provides succinct representations for TPMs such as Probabilistic Sentential Decision Diagrams (PSDDs) [5], Sum-Product Networks (SPNs) [4], and Arithmetic Circuits (ACs) [3]. We proceed by introducing the syntax and semantics of a PC.
Definition 1 (Probabilistic Circuits). A PC p that represents a probability distribution over variables X is defined by a parametrized directed acyclic graph (DAG) with a single root node, denoted nr. The DAG comprises three kinds of units: input, sum, and product. Each leaf node n in the DAG corresponds to an input unit; each inner node n (i.e., sum and product units) receives inputs from its
children, denoted in(n). Each unit n encodes a probability distribution pn, defined as follows:
pn(x) :=  fn(x) if n is an input unit,∑ c∈in(n) θn,c · pc(x) if n is a sum unit,∏ c∈in(n) pc(x) if n is a product unit,
where fn is a univariate input distribution (e.g., boolean, categorical or Gaussian), and θn,c represents the parameter corresponds to edge (n, c). Intuitively, a sum unit models a weighted mixture distribution over its children, and a product unit encodes a 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., ∑ c∈in(n) θn,c=1). We further assume w.l.o.g. that a PC alternates between sum and product layers [33]. The size of a PC p, denoted |p|, is 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-posterior (MAP) inferences (e.g., PSDDs [5], selective SPNs [34]); (ii) PCs that only permit linear-time computation of MAR queries (e.g., SPNs [4]). The borders between these two types of PCs are defined by their structural properties, i.e., constraints imposed on a PC. First, in order to compute MAR queries in linear time, both classes of PCs should be decomposable (Def. 2) and smooth (Def. 3) [1]. 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 2 (Decomposability). A PC is decomposable if for every product unit n, its children have disjoint scopes: ∀c1, c2 ∈ in(n) (c1 6= c2), φ(c1) ∩ φ(c2) = ∅. Definition 3 (Smoothness). A PC is smooth if for every sum unit n, its children have the same scope: ∀c1, c2 ∈ in(n), φ(c1) = φ(c2).
Next, determinism is required to guarantee efficient computation of MAP inference [35].
Definition 4 (Determinism). Define the support supp(n) of a PC unit n as the set of complete variable assignments x ∈ val(X) for which pn(x) has non-zero probability (density): supp(n) = {x | x∈val(X), pn(x)>0}. A PC is deterministic if for every sum unit n, its children have disjoint support: ∀c1, c2 ∈ in(n) (c1 6= c2), supp(c1) ∩ supp(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 in the second PC class as nondeterministic 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, 13] and theoretical [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.
Motivation Laplace smoothing is widely adopted as a PC regularizer [16, 17]. Since it is also the default regularizer for 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
Algorithm 1 Forward pass 1: Input: A deterministic PC p; sample x 2: Output: value[n]:=(x∈supp(n)) for each unit n 3: foreach n traversed in postorder do 4: if n isa input unit then value[n]←fn(x) 5: elif n isa product unit then 6: value[n]← ∏ c∈in(n) value[c]
7: else //n is a sum unit 8: value[n]← ∑ c∈in(n) value[c]
Algorithm 2 Backward pass 1: Input: A deterministic PC p; ∀n, value[n] 2: Output: flow[n, c] := (x ∈ (γn∩γc)) for each
pair (n, c), where n is a sum unit and c∈ in(n) 3: ∀n, context[n]←0; context[nr]←value[nr] 4: foreach sum unit n traversed in preorder do 5: foreach m ∈ pa(n) do (denote g←pa(m)) 6: f← value[m]
value[g] · context[g]
7: context[n] += f; flow[g,m] = f
smoothing provides good priors to BNs and HBMs, its uniform prior could add unwanted bias to PCs. Specifically, for every sum unit n, Laplace smoothing assigns the same prior to all its child parameters (i.e., {θn,c | c∈ in(n)}), while in many practical PCs, these parameters should be given drastically different priors. For example, consider the PC shown in Fig. 1(a). Since c2 has an exponentially larger support than c1, it should be assumed as prior that θ12 will be much larger than θ11.
We highlight the significance of the above issue by examining the fraction of sum units with imbalanced child support sizes in PCs learned by Strudel, a state-of-the-art structure learning algorithm for deterministic PCs [5]. We examine 20 PCs learned from the 20 density estimation benchmarks [39], respectively. All sum units with ≥3 children and with a support size ≥128 are recorded. We measure “imbalanceness” of a sum unit n by the fraction of the maximum and minimum support size of its children (i.e., maxc1∈in(n) |supp(c1)|minc2∈in(n) |supp(c2)| ). As demonstrated in Fig. 1(b), more than 20% of the sum units have imbalanceness ≥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.

heading: 4 How Is This Tractable And Practical?
text: 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 (Sec. 4.2) and non-deterministic (Sec. 4.3) PCs.

heading: 4.1 Learning the Parameters of PCs
text: Deterministic PCs Given a deterministic PC p defined on variables X and a datasetD = {x(i)}Ni=1, the maximum likelihood estimation (MLE) parameters θ∗D :=argmaxθ ∑N i=1 log p(x
(i);θ) can be learned in closed-form. To formalize the MLE solution, we need a few extra definitions.
Definition 5 (Context). The context γn of every unit n in a PC p is defined in a top-down manner: for the base case, context of the root node nr is defined as its support: γnr := supp(nr). For every other node n, its context is the intersection of its support and the union of its parents’ (pa(n)) contexts:
γn := ⋃
m∈pa(n) γm ∩ supp(n).
Intuitively, if an assignment x is in the context of unit n, then there exists a path on the PC’s DAG from n to the root unit nr such that for any unit m in the path, we have x∈ supp(m). Circuit flow extends the notation of context to indicate whether a sample x is in the context of an edge (n, c).
Definition 6 (Flows). The flow Fn,c(x) of any edge (n, c) in a PC given variable assignments x∈val(X) is defined as 1[x∈γn∩γc], where 1[·] is the indicator function. The flow Fn,c(D) w.r.t. dataset D={x(i)}Ni=1 is the sum of the flows of all its samples: Fn,c(D) := ∑N i=1 Fn,c(x (i)).
The flow Fn,c(x) for all edges (n, c) in a PC p w.r.t. sample x can be computed through a forward and backward path that both take O(|p|) time. The forward path, as shown in Alg. 1, starts from the leaf units and traverses the PC in postorder to compute ∀n, value[n] :=1[x∈supp(n)]; afterwards, the backward path illustrated in Alg. 2 begins at the root unit nr and traverses the PC in preorder to
compute ∀n, context[n] :=1[x∈γn] as well as ∀(n, c), flow[n, c] :=Fn,c(x). By Def. 6, the time complexity for computing Fn,c(D) with respect to all edges (n, c) in p is O(|p|·|D|), where |D| is the size of dataset D. The correctness of Alg. 1 and 2 are justified in Appendix A.6. The MLE parameters θ∗D given dataset D can be computed using the flows [5]:
∀(n, c), θ∗n,c = Fn,c(D)/ ∑
c∈in(n) Fn,c(D). (3)
Define hyperparameter α (α ≥ 0), for every sum unit n, Laplace smoothing regularizes its child parameters (i.e., {θn,c | c∈ in(n)}) by adding a pseudocount α/|in(n)| to every child branch of n, which is equivalent to adding α/|in(n)| to the numerator of Eq. (3) and α to its denominator. Non-deterministic PCs As justified by Peharz et al. [40], every non-deterministic PC can be augmented as a 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., n2 and n3) contains x1x̄2. The right PC augments the left one by adding input units correspond to hidden variable Z1, which retains determinism by “dividing” the overlapping support x1x̄2 into x1x̄2z1∈supp(n2) and x1x̄2z̄1∈ supp(n3). Under this interpretation, parameter learning of non-deterministic PCs is equivalent to learning the parameters of deterministic PCs given incomplete data (we never observe the hidden variables), which can be solved by Expectation-Maximization (EM) [41, 42]. In fact, EM is the default parameter learning algorithm for non-deterministic PCs [13, 10].
Under the latent variable model view of a non-deterministic PC, its EM updates can be computed using expected flows [10]. Specifically, given observed variables X and (implicit) hidden variables Z, the expected flow of edge (n, c) given dataset D is defined as
EFn,c(D;θ) := Ex∼D,z∼pc(·|x;θ)[Fn,c(x, z)], where θ is the set of parameters, and pc(· | x;θ) is the conditional probability over hidden variables Z given x specified by the PC rooted at unit c. Similar to flows, the expected flows can be computed via a forward and backward pass of the PC (Alg. 5 and 6 in the Appendix). As shown by Choi et al. [10], for a non-deterministic PC, its parameters for the next EM iteration are given by
θ(new)n,c = EFn,c(D;θ)/ ∑
c∈in(n) EFn,c(D;θ). (4)
This paper uses a 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, θ(new) are computed using mini-batches of samples, and the parameters are updated towards the taget with a step size η: θ(k+1)←(1− η)θ(k) + ηθ(new); when using full-batch EM, we iteratively compute the updated parameters θ(new) 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.

heading: 4.2 Regularizing Deterministic PCs
text: We demonstrate how the intuitive ideas for regularizing distributions presented in Sec. 2 (i.e., data softening and entropy regularization) can be efficiently applied to deterministic PCs.
Data softening As hinted by Eq. (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 1: Input: A deterministic PC p; flow Fn,c(D) for every edge (n, c) in p; hyperparameter τ . 2: Output: A set of log-parameters, {ϕn,c : (n, c) ∈ p}, which are the solution of Eq. (2). 3: ∀n, node_prob[n]← 0; node_prob[nr]← 1 //nr is the root node of p 4: while not converge do 5: ∀n, 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: di ← Fn,ci(D)/|D|; b = τ · node_prob[n] //{ci}in(n)i=1 is the set of children of n 8: Solve for {ϕn,ci}|in(n)|i=1 in the following set of equations (y is a variable):{
die −ϕn,ci − b · ϕn,ci + b · entropy[ci] = y (∀i ∈ {1, . . . , |in(n)|})∑|in(n)| i=1 e ϕn,ci = 1 (5)
9: for each c ∈ in(n) and each m ∈ in(c) do //Update node_prob of grandchildren 10: node_prob[m]← node_prob[m] + eϕn,c · node_prob[n]
this negative result, the MLE parameters of a PC p w.r.t. Dβ can be computed in time O(|p|·|D|), which is linear w.r.t. the model size as well as the size of the original dataset. Theorem 3. Let fn(x) = β ·1[x ∈ supp(n)] + (1−β) ·1[x 6∈ supp(n)] in Alg. 1. Given a deterministic PC p, a boolean dataset D, and hyperparameter β ∈ (0.5, 1], the set of all flows {Fn,c(Dβ) | ∀ edge (n, c)} w.r.t. the softened dataset Dβ can be computed by Alg. 1 and 2 within O(|p|·|D|) time.
Proof of this theorem is provided in Appendix A.1. Since the MLE parameters (Eq. (3)) w.r.t. Dβ can be computed in O(|p|) time using the flows, the overall time complexity to compute the MLE parameters is again O(|p|·|D|). Entropy regularization The hope for tractable PC entropy regularization comes from the fact that the entropy of a deterministic PC p can be exactly computed in O(|p|) time [6, 46]. However, it is still unclear whether the entropy regularization objective LLent(θ;D, τ) (Eq. (2)) can be tractably maximized. We answer this question with a mixture of positive and negative results: while the objective is multi-modal 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. Proposition 1. There exists a deterministic PC p, a hyperparameter τ , and a dataset D such that LLent(θ;D, τ) (Eq. (2)) is non-concave and has multiple local maximas.
Proof is given in Appendix A.7. Although global optimal solutions are generally infeasible, we propose an efficient algorithm that guarantees to find a stationary point of LLent(θ;D, τ). Specifically, Alg. 3 takes as input a deterministic PC p and all its edge flows w.r.t. D, and returns a set of learned log-parameters that correspond to a stationary point of the objective.2 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),3 and (ii) update PC parameters with regard to the computed entropies (lines 6-10). Specifically, in the parameter update phase (i.e., the second phase), the algorithm traverses every sum unit n in preorder and updates its child parameters by maximizing the entropy regularization objective (LLent(θ;D, τ)) with all other parameters fixed. This is done by solving the set of equations in Eq. (5) using Newton’s method (lines 7-8).4 In addition to the child nodes’ entropy computed in the first phase, Eq. (5) uses the top-down probability of every unit n (i.e., node_prob[n]), which is progressively updated in lines 9-10. Theorem 4. Alg. 3 converges monotonically to a stationary point of LLent(θ;D, τ) (Eq. (2)).
Proof. The high-level idea of the proof is to show that the parameter update phase (lines 6-10) optimizes a concave surrogate objective of LLent(θ;D, τ), which is determined by the entropies computed
2We compute parameters in the logarithm space for numerical stability. 3This can be done by Alg. 4 shown in Appendix A.2. Lem. 1 proves that Alg. 4 takes O(|p|) time. 4Details for solving Eq. (5) is given in Appendix B.2.
in line 5. Specifically, we show that whenever the surrogate objective is improved, LLent(θ;D, τ) is also improved. Since the surrogate objective is concave, it can be easily optimized. Therefore, Alg. 3 converges to a stationary point of LLent(θ;D, τ). 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 is the parameter update phase (lines 6-10). Specifically, the E-step constructs a concave surrogate of the true objective (LLent(θ;D, τ)), and the M-step updates all parameters by maximizing the concave surrogate function. Although Thm. 4 provides no convergence rate analysis, the outer loop typically takes 3-5 iterations to converge in practice. Furthermore, Eq. (5) can be solved with high precision in a few (<10) iterations. Therefore, compared to the computation of all flows w.r.t. D, which takes O(|p|·|D|) time, Alg. 3 takes a negligible O(|p|) 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. 1(a), we conceptually demonstrate that both data softening and entropy regularization will not over-regularization θ11 compared to θ12. First, data softening essentially add no prior to the parameters, and only soften the evidences in the dataset. Therefore, it will not over-regularize children with small support sizes. Second, entropy regularization will add a much higher prior to θ12. Suppose n=10, consider maximizing Eq. (2) with an empty dataset (i.e., we maximize ENT(pn1) directly), the optimal parameters would be θ11≈0.002 and θ12≈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-agnostic, i.e., 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)5 using the validation set and report results on the test set. Please refer to Appendix B.3 for more details.
Results are summarized in Fig. 5. First look at the scatter plots on the left. The x-axis represents the degree of overfitting, which is computed as follows: denote LLtrain and LLval as the average train and validation log-likelihood under the MLE estimation with Laplace smoothing (α=1.0), the degree of overfitting is defined as (LLval − LLtrain)/LLval, which roughly captures how much the dataset/model pair suffers from overfitting. The y-axis represents the improvement on the average test set log-likelihood compared to Laplace smoothing. As demonstrated by the scatter plots, despite a 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.

heading: 4.3 Regularizing Non-Deterministic PCs
text: By viewing every non-deterministic PC as a deterministic PC with additional hidden variables (Sec. 4.1), the regularization techniques developed in Sec. 4.2 can be directly adapted. Specifically,
5Specifically, α ∈ {0.1, 0.4, 1.0, 2.0, 4.0, 10.0}, β ∈ {0.9996, 0.999, 0.996}, τ ∈ {0.001, 0.01, 0.1}.
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 to compute the entropy of a non-deterministic PC [6], it is infeasible to optimize the entropy regularization objective LLent(θ;D, τ) (Eq. (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 to compute expected flows (i.e., Alg. 5 and 6 in the Appendix). Entropy regularization is again performed by Alg. 3 at the M-step of each min-batch/full-batch EM update, except that the input flows (i.e., F) are replaced by the corresponding expected flows (i.e., EF).
Empirical evaluation We use a simple yet effective PC structure, hidden Chow-Liu Tree (HCLT), as demonstrated in Fig. 4. Specifically, on the left is a Bayesian network representation of a Chow-Liu Tree (CLT) [43] over 5 variables. For any CLT over variables {Xi}ki=1, we can modify it as a HCLT through the following steps. First, we introduce a set of k latent variables {Zi}ki=1. Next, we replace all observed variables in the CLT with its corresponding latent variable (i.e., ∀i,Xi is replaced by Zi). Finally, we add an edge from every latent variable to its corresponding observed variable (i.e., ∀i, add an edge Zi→Xi). The HCLT structure is then compiled into a PC that encodes the same probability distribution. We used
the hybrid mini-batch + full-batch EM as described in Sec. 4.1. For all experiments, we trained the PCs with 100 mini-batch EM epochs and 100 full-batch EM epochs. Please refer to Appendix B.4 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.
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 test set LL are around −170. Fig. 6 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 state-of-the-art PSDD (Strudel [17] and LearnPSDD [16]) and SPN (EinSumNet [13], LearnSPN [18], ID-SPN [47], and RAT-SPN [48]) learning algorithms. Results are summarized in Table 1. With proper regularization, HCLT out-performed all baselines in 10 out of 20 datasets. Comparing with individual baselines, HCLT out-performs both PSDD learners on all datasets; HCLT
achieved higher log-likelihood on 18, 19, 10, and 17 datasets compared to EinSumNet, LearnSPN, ID-SPN, and RAT-SPN, respectively.

heading: 5 Conclusions
text: 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 over a wide variety of PC structures and datasets.
Acknowledgement This work is partially supported by NSF grants #IIS-1943641, #IIS-1956441, #CCF-1837129, DARPA grant #N66001-17-2-4032, a Sloan Fellowship, Intel, and Facebook.

Review summaries:
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.  

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.

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.