Sparse Probabilistic Circuits via Pruning and Growing
Authors: Meihua Dang
Anji Liu
Guy Van den Broeck
Venue: NeurIPS 2022 Accept (2022)

Abstract: Probabilistic circuits (PCs) are a tractable representation of probability distributions allowing for exact and efficient computation of likelihoods and marginals. There has been significant recent progress on improving the scale and expressiveness of PCs. However, PC training performance plateaus as model size increases. We discover that most capacity in existing large PC structures is wasted: fully-connected parameter layers are only sparsely used. We propose two operations: pruning and growing, that exploit the sparsity of PC structures. Specifically, the pruning operation removes unimportant sub-networks of the PC for model compression and comes with theoretical guarantees. The growing operation increases model capacity by increasing the dimensions of latent states. By alternatingly applying pruning and growing, we increase the capacity that is meaningfully used, allowing us to significantly scale up PC learning. Empirically, our learner achieves state-of-the-art likelihoods on MNIST-family image datasets and an Penn Tree Bank language data compared to other PC learners and less tractable deep generative models such as flow-based models and variational autoencoders (VAEs).

Sparse Probabilistic Circuits via Pruning and Growing
Meihua Dang Department UCLA
Anji Liu CS Department UCLA liuanji@cs ucla.
Guy Van den Broeck Department UCLA guyvdbacs. ucla. edu
mhdang@cs ucla.edu
Abstract
Probabilistic circuits (PCs) tractable representation of probability distributions allowing for exact and efficient computation of likelihoods and marginals. There has been significant recent progress improving the scale and expressiveness of PCs. However, PC training performance plateaus as model size increases. We dis- cover that most capacity in existing large PC structures is wasted: fully-connected parameter layers are only sparsely used. We propose two operations: pruning and growing, that exploit the sparsity of PC structures. Specifically, the pruning operation removes unimportant sub-networks of the PC for model compression and comes with theoretical guarantees. The growing operation increases model ca- pacity by increasing the size of the latent space. By alternatingly applying pruning and growing. we increase the capacity that is meaningfully used, allowing us significantly scale up PC learning. Empirically, our learner achieves tatte-of-theaar likelihoods on MNIST-family image datasets and on Penn Tree Bank language data compared to other PC learners and less tractable deep generative models such as flow-based models and variational autoencoders (VAEs).
Introduction
44 3 are uni- fying framework to abstract from a multitude of tractable probabilistic models. The key property that separates PCs from other deep generative models such flow-based mod- els 31 and VAEs [19 is their tractability. It enables them compute various queries, in- cluding marginal probabilities, exactly and ef- ficiently [45). Therefore, PCs are increasingly used in snference-demandee
Probabilistic circuits (PCs)
0.5
0.001
Percentage
0.3
0,01 (76%)
0.2
applications such making
0.05 (5%)
as enforcing algorithmic faimess predictions under missing data 6 18
23 data
0.0
compression
26 and anomaly detection
13
0.00
0.01
Parameter Values
0.02
0.03
0.04
0.05
Recent advancements in PC learning and reg- ularization 40
Figure 1: Histogram of parameter values for a state- of-the-art PC with 2.18M parameters MNIST. 95% of the parameters have close-to-zero values.
2 and efficient implementa- have been pushing the limits of PC'S expressiveness and scalability such that they can even match the performance of less tractable deep generative models, including flow-based models and VAEs. However, the performance of PCs plateaus as model size increases. This suggests that to further boost the performance of PCs, simply scaling up the model size does not suffice and we need to better utilize the available capacity.
tions
3
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

We discover that this might be caused by the fact that the capacity of large PCs is wasted. As shown in Figure !| most parameters in a PC with 2.18M parameters have close-to-zero values, which have little effect on the PC distribution. Since existing PC structures usually have fully-connected parameter layers 22 36], this indicates that the parameter values are only sparsely used.
In this work, we propose to better exploit the sparsity of large PC models by two structure learning primitives pruning and growing. Specifically, the goal of the pruning operation is to identify and remove unimportant sub-networks of a PC. This is done by quantifying the importance of PC parameters w.r.t. a dataset using circuit flows, a peporeticallyggronndee drop of logllikel caused by pruning. Compared to LI regularization, the proposed pruning operator is more informed by the PC semantics, and hence quantifies the global effects of pruning much more effectively. Empirically. the proposed pruning method achieves a compression rate of 80-98% with at most 1 % drop in likelihood on various PCs.
metric that upper bounds the
The proposed growing operation increases the model size by copying its existing components and injecting noise. In particular, when applied to PCs compressed by the pruning operation, growing produces larger PCs that can be optimized to achieve better performance. Applying pruning and growing iteratively can greatly refine the structure and parameters of a PC. Empirically, the log- likelihoods metric can improve by 2% to 10% after a few iterations. Compared to existing PC learners as well as less tractable deep generative models such as VAEs and flow-based models, our proposed method achieves state-of-the density estimation results on image datasets including MNIST, EMNIST, FNSH, and the Penn Tree Bank language modeling task |
2 Probabilistic Circuits
K model probability distributions with a structured computation graph. They are an umbrella term for a large family of tractable probabilistic models including arithmetic circuits ( 10), sum sum- uum-product networks (SPNs) 35). cutset networks [36], and-or search The syntax and semanties of PCs are
Probabilistic circuits (PCs)
spaces 23 and probabilistic sentential decision diagrams defined as follows.
Definition (Probabilistic Cireuit). A PC CC= (G, 0) represents a joint probability distribution p(X) over random variables X through directed acyclic (computation) graph (DAG) ς parameterized by O. Similar to neural networks, each node in the DAG defines a computational unit. Specifically, the DAG G consists of three types of units input, sum, and product. Every leaf node in G is an input unit; every inner unit n (i.e., sum or product) receives inputs from its children in(n), and computes output, which encodes a probability distribution pr. defined recursively as follows:
fn(#:)
if n is an input unit,
Pa (x)
if n is product unit, Eecin(n) Oej Pe(ar) if m a sum unit,
[o (x(
where (x) a univariate input distribution (e.g. Gaussian, Categorical), and Oejn denotes the parameter that corresponds to edge (n,c)) in the DAG. For every sum unit n. its input parameters sum up to one, i.c., Ecein(n) Pej = 1. Intuitively, a product unit defines factorized distribution over its inputs, and sum unit represents mixture over its input distributions with weights {f..n E in(n)): }. Finally, the probability distribution of PC (i.e., pc) is defined as the distribution represented by its root unit r (i.e., p, (x)), that is, its output neuron. The size of PC, denoted [C] |@) is the number of parameters in C. We assume w.L.o.g. that a PC alternates between layers of sum and product units before reaching its inputs. Figure shows an example of a PC.
Computing the (log)likelihood of a PC C given a sample x is equivalent to evaluating its computation units in G in feedforward manner following Equation I The key property that separates PCs from other deep probabilistic models such as flows [4] and VAES [19] is their tractability, which is the ability to exactly and efficiently answer various probabilistic queries. This paper focuses PCs that support linear time (w.r.t. model size) marginal probability computation, as they are increasingly used in downstream applications such data compression 26 and making predictions under missing
data [1]. and also achieve on-par expressiveness [26 25 24 To support efficient marginal inference, PCs need to be smooth and decomposable.
'Code and experiments are available https: /ttps://github. http:p///gthhhbb.omm//UUS//////s

---

-z-B(,0)
0.8
N88
279
xx,B(.8)
0.1
0.4
Xy.)((1)
D66
0.0
D.9
X,-x((2)
X3 B(.3) X1 B(.T)
(b)
Figure 2: A smooth and decomposable PC (b) and an equivalent Bayesian network (a). The Bayesian network is over 4 variables X {X X2, X3, X4} and 2 hidden variables Z [Z Z2} with = hidden states. The feedforward computation order is from left to right: O are input Bernoulli distributions, 8 product units, and b sum units; parameter values are annotated in the box.
The probability of each unit given input assignment {X1 = 0, X₂ = X3=0, 0, x1= = 1 is labeled red.
(a) PC with fully connected layers
(b) PC after pruning operation
(c) PC after growing operation
3b the red edges are pruned. From 3b to 3c the nodes are doubled, and each parameter is copied times.
Figure 3: demonstration of the pruning and growing operation. From 3a
The scope d(n) of PC unit is the set of input variables that it depends on; then, (1) product unit is decomposable if its children have disjoint scope; (2) unit is smooth if its children have identical scope. A PC is decomposable if all of its product units are decomposable; a PC is smooth if all of its sum units are smooth.
Definition 2 (Smoothness and Decomposability
Decomposability ensures that every product unit encodes well-defined factorized distribution over disjoint sets of variables; smoothness ensures that the mixture components of every sum units are well-defined over the same set of variables. Both structural properties will be the key to guaranteeing the effectiveness of the structure learning algorithms proposed in the following sections.
Probabilistic Circuit Model Compression via Pruning
Figure shows that most parameters in large PC are very close to zero. Given that these parameters are weights associated with mixture (sum unit) components, the corresponding edges and sub-circuits have little impact the unit output. Hence, by pruning away these unimportant components, is possible to significantly reduce model size while retaining model expressiveness, Figure 3b illustrates the result of pruning five (red) edges from the PC in Figure 3a Given a PC and dataset, our goal is to efficiently identify a set of edges to prune, such that the log- likelhood gap between the pruned PC and the original PC on the given dataset is minimized.
Pruning by parameters. The parameter value statistics in Figure I suggest that natural criterion is to prune edges by the magnitude of their corresponding parameter. This leads to the EPARAM (edge parameters) hcuristic, which selects the set of edges with the smallest parameters. However, edge parameters themselves are insufficient to quantify the importance of inputs to a sum unit in the entire PC's distribution. The parameters of a sum unit are normalized to so they only contain local information about the mixture components. Specifically, d.jn merely defines the relative importance of edge (n,, e) in the conditional distribution represented by its corresponding sum unit n, not the joint distribution of the entire PC. Figure 4 illustrates what happens when the edge with the smallest parameter is pruned from the PC in Figure
3

---

Bl.2 .2 X1 B(.1)
A X2 B(.1)
X2-
X.-B((8)
X. Ku-B((8)
Xy
U.6
0.2
1.0
0.9
xxx)((2)
X₂ kgnBB(22)
Xa-B((3 X X1-B(.7)
X(,.((3) X1 X)-B(.7)
(a) EPARAM removes the edge with 0-1.1
(b) EFLOW removes edge with 000.2
Figure 4: A case study comparing pruning heuristics (EPARAM and F.F.LW) on the PC in Figure given sample (X, 1, X,; 11=13.
The pruned edges are dashed and parameters are re-normalized. Compared to the likelihood computed in Figure the changed likelihoods are in red, showing that pruning by flows results less likelihood decrease.
Algorithm 1: PC sampling
Input :a PC representing joint probability pc px(
Output tan instance sampled from pe
Function SAMPLE(N)
a an input wnit then
Fin (X) < univariate distribution of n; return sample x fr (X) else n is a product unit then
Te f- SAMPLE(() foreach in(n); return Concatenate (are is sum unit
sample an input proportional to [0gnnoeiinnn) return SAMPLE(C")
return SAMPLE()) where is the root of PC C
However, as shown in Figure 4b pruning another edge delivers better likelihoods as it accounts more for the "global influence" of edges the PC's output. This global influence is highly related the probabilistic "circuit flow" semantics of PCs. We will introduce circuit flows later in this section, along with their corresponding heuristies EFL.ww. Before that, we first introduce intermediate concept based on the notion of generative significance of PCs.
Pruning by generative significance. A more informed pruning strategy needs to consider the global impact of edges on the distribution represented by the output of the PC. To achieve this, instead of viewing the distribution Pe in feedforward manner following Equation I quantify the significance from the PC. Indeed, if the presence of an edge is hardly process, removing it will not significantly affect the PC's distribution.
unit or edge by the probability that it will be "activated" when drawing samples
relevant to the generative sampling
Algorithm I shows how to draw samples from a PC distribution through a recursive implementation: (I) for an input unit n defined on variable X (line 3 the algorithm randomly samples value æ according to its input univariate distribution; (2) for product unit (line 5). by decomposability its children have disjoint scope, thus we draw samples from all input units and then concatenate the unit (line 7 by smoothness its children have identical scope, thus we first randomly sample one of its input units according to the categorical distribution defined by sum parameters (0... E in(n)). }. and then sample from this input unit recursively. Besides actually drawing samples from the PC, we can also compute the probability that n will be visited during the sampling process. This provides good measure of the importance of unit n to the PC distribution a whole, which we define as the top-down probability.
samples together; (3) for
Definition 3 (Top-down Probability). The top-down probability of each unit n in PC with parameters is defined recursively as follows, assuming alternating sum and product layers:
if is the root unit, if a sum unit, Σ Emcaut(a) Onm (mm; 0)
q(n; 0)
Σ EmEout(n) ((m;; 0)
if is a product unit, where out(n) are the units that take n as input in the feedforward computation. Moreover, the top-down probability of sum edge (n, c) is defined as q(n, c; 0) -ein qq(;; 0).

---

-100
0.15
Log- Log-lkkllhoods
eRand
After Prune
Init PC
eFlow
Percentage
-110
eParams
0.05
-120
0
40 Pruning %
80
0.0
0.5
1.0
Parameter Values
(a)
Comparison of heuristics ERAND, EPARAM, and EFLOW. Heuristic EFLOW can prune up 80% of the parameters without much loglikelihoods decrease.
(b) Histogram of parameters before (the same as in Figure M and after pruning. The parameter values take higher significance after pruning.
Figure 5: Empirical evaluation of the pruning operation.
The top-down probability of the root is always 1; a product unit passes its top-down probability to all its inputs, and a unit distributes its top-down probability to its inputs proportional to the corresponding edge weights. Therefore, the top-down probability non-root unit summing over all probabilities it receives from its outputs.
The top-down probability all PC units and sum edges can be computed in single backward pass over the PC's computation graph. Following the intuition that the top-down probability defines the probability that units will be visited during the sampling process, pruning edges with the smallest top-down probability constitutes reasonable pruning strategy.
Pruning by circuit flows. The top-down probability q(n; 0) represents the probability of reaching unit n in an unconditional random sampling process. Despite its ability to capture global information of PC parameters, the top-down probability is not tailored specific dataset. Therefore, further utilize the dataset information, we can measure the probability of reaching certain units/edges in the sampling process conditioning on some instance being sampled. To bridge this gap, we define circuit flow as a sample-dependent version of the top-down probability.
Definition 4 (Cireuit Flow For a given PC with parameters 0 and example æ. the circuit flow of unit example æ is the probability that will be visited during the sampling procedure conditioned on x being sampled. This can be computed recursively as follows, assuming alternating sum and product layers:
if n. is the root unit,
Fx
Em Eout(i)) Fm (x)
if r. is sum unit,
E Em
P. (m) if r is a product unit.
(m)
Similarly, the edge flow (x))(w) on sample is defined by Fn,((x) Oejn pe(x)/pm( (x)) - Fx))). We further define F Fn.e(() EEED Fn,e(2)) as the aggregate edge flow over dataset D.
Effectively, we can think of 0 a/m == Onim Pr (x) (mm (x:) as the posterior probability of component n
in the mixture of sum unit m conditioned on observing sample æ. Then, circuit flow is the top- down probability under this 0a reparameterization of the circuit: F, (x( = q(n; 0T) and F Fn,c(x))
q(n, c; 0²).
Circuit flow F (x) defines the probability of reaching unit n in the top-down sampling procedure of Algorithm given that the sampled instance is æ. Therefore, edge flow F Fz,.(z)) is a natural metric of the importance of edge (n, c) given Intuitively, the aggregate circuit flow measures how many expected samples "flow" through certain edges. We write EFLOW to refer to the heuristic that prunes edges with the smallest aggregate circuit flow.
Empirical Analysis. Figure 5a compares the effect of pruning heuristics EPARAM, EFLOW, as well an uninformed strategy, prune randomly, which we denote as ERAND. It shows that both EPARAM and EFLOW are reasonable pruning strategy, however, as we increase the percentage of
Earlier work defined "circuit flow" or "expected circuit flow" in the context of parameter learning 4 25 without observing the connection to sampling. We contribute its more intuitive sampling semantics here.
5

---

pruned parameters, EFLOW has less log-likelihoods drop compared with EPARAM. Using EFLOW heuristics we can pruning up 80% of the parameters without much log-likelihoods drop. As shown in Figure 5b the parameter distribution is more balanced after pruning compared to Figure D indicating a higher significance of each edge. Section g will provide more empirical results. Before that, we first theoretically verify the effectiveness of the EFL.O heuristic in the next section.
4 Bounding and Approximating the Loss of Likelihood
In this section, theoretically quantify the impact of edge pruning model performance. In particular, we establish an upper bound on the log-likelihood drop ALC on a given dataset 'D by comparing (i) the original PC C and (ii) the pruned PC C,E caused by pruning away edges &
&CE CC(DCC)
(2)
We start from the case of pruning edge (i.e., | in Equation 2 In this case, the loss of likelihood can be quantified exactly using flows and edge parameters:
Theorem 1 (Log-liken lioelhood drop of pruning one edge). For PC C and datasel D, the loss of log-likelihood by pruning away edge (n)c)) is
1 - Oc/n
ACC(D,C, ((n,))))
log
log (1nFFF,((x))
[D]
1-0 +0 Fn (x) Fn (x))
D
mED
MED
we can pick the edge with the smallest log- likeliiodoood drop. Additionally, the third term characterizes the log-likelihood drop without re-normalizing parameters of 8.jn. It suggests pruning the edge with the smallest edge flow. key insight from Theorem is that the log-likelihood drop depends explicitly on the edge flow (2))(2)) and unit flow F..(2)). This matches the intuition from Section and suggests that the circuit flow heuristic proposed the previous section is a good approximation of the derived upper bound.
See proof in Appendix
B. By computing the second term in Theorem 1
Next, we bound the log- likelihood drop of pruning multiple edges.
Theorem 2 likelioil drop of pruning multiple edges). Ler C be PC and D be dataset. For 1, the log- likelikhihood drop by pruming away &
any set of edges& & in C, Va D, ((me)ee Fn,((x) <
is bounded and approximated by
Σ DD]
1
log(1
Σ F Fn,c(x)) (n,C)E
1
Σ (n,)(D)-
D
(3)
(m,C)E
Proof of this theorem is provided in Appendix
B.2 We
first look at the second term of Equation 3 Although it provides an upper bound to the performance drop, cannot be used as a pruning heuristic since the bound does not decompose over edges. And hence finding the set of edges with the lowest score requires evaluating the bound exponentially many times with respect to the number of pruned edges. Therefore, approximation step of the bound via Taylor expansion, which leads to the third term of Equation proximation matches the EFLOW heuristic by constant factor 1/|2), which theoretically justifies the effective- ness of the heuristic. Figure empirically compares the actual ligelikelihood drop and the quantity computed from the circuit flow heuristic (that is, the approximate upper bound) for different percentages of pruned parame- ters. We see that the approximate bound matches closely the actual log- likelihod drop.
Loo like ihoods
eF
10a
20
10
do additional
50
100
This ap-
Pruning %
Figure 6: Comparing the actual loglikeli- hood drop (ALL) and EFLOw heuristics (the approximated upper bound in Equa- tion B3. The approximate bound matches closely to the actual loglikelihood drop.
5 Scalable Structure Learning
The pruning operator improves two aspects of PCs. First, as shown in Figure 5b more balanced after pruning. Second, pruning removes sub-circuits with negligible contributions
model parameters

---

to the model's distribution. If we treat PCs as hierarchical mixtures of components, pruning can be regarded as an implicit structure learning step that removes the "unimportant" components for each mixture. However, since pruning only decreases model capacity, it is impossible to get more expressive PC than the original one. To mitigate this problem, we propose growing operation to increase the capacity of PC by introducing more components for each mixture. Pruning and growing together define a scalable structure learning algorithm for PCs.
Growing. Growing is an operator that increases model size by copying its existing components and injecting noise. As shown in Figure 3 after applying the grow- ing operation on the original PC in Figure 3b] we can get a new grown PC as in Figure 7 Specifically, the growing operation is applied to units, edges, and parameters respec- tively: (I) for units, growing operates on every PC unit n and creates another copy n=*;; (2) for edges, the sum edge (n, c) from the original PC (Figure Bb are copied three times to the grown PC (Figure 7 from new parent to new child (1dev, , ) from old parent to new child (n, c and from new parent to old child (n c); product edges are added to connect the copied version of a product unit and its copied inputs; (3) a new parameter 6apo is a noisy
n new
nev
Figure 7: Growing operation. Each unit is doubled, and each parameterized edge is copied times: (n"eN caee) (orange), (ne00 e) (purple), and (n, caeM) (green).
copy of an old parameter Oejas that is 6mex f- e 9:jo. where (V( and o² controls the Gaussian noise variance. Gaussian noise is added the copied parameters ensure that after apply the growing operation, parameter learning algorithms can find diverse parameters for different copies. After growing operation, the PC size is 4 times the original PC size. Algorithm in appendix shows feedforward implementation of the growing operation.
Structure Learning through Pruning and Growing. The proposed pruning and growing algo- rithms can be applied iteratively to refine the structure and parameters of an initial PC. Specifically, since the growing operator increases the number of PC parameters by factor of 4, applying growing after pruning 75% of the edges from an initial PC keeps the number of parameters unchanged. We propose joint structure and parameter learning algorithm for PCs that uses these two operations. Specifically, starting from an initial PC, we apply 75% pruning, growing, and parameter learning iteratively until convergence. We utilize HCLTss 25 as initial PC structure as it has the state-of-the-an art likelihood performance. Note that this structure learning pipeline can be applied to any PC structure.
Parameter Estimation. We use stochastic mini- version of Expectation Motiiionaaiiiiiiiiiiaoo optimization (2. Specifically, at each iteration, we draw a mini-batch of samples DB, compute aggregated circuit flows F Fn,c(Da, and F, (DB) of these samples (E-step), and then compute new parameter quee F (DD) Fz (Dx)- The parameters are then updated with learning rate as @r-1 affee + (1 )0 (M-step). Empirically this approach converges faster and is better regularized compared full-batch EM.
Parallel Computation. Existing approaches to scaling up learning and inference with PCs, such as Einsum networks [33], utilize fully connected parametrized layers (Figure Bab of PC structures such as HCLT (55 and RatSPN 34). These structures can be easily vectorized to utilize deep learning packages such as PyTorch. However, the sparse structure learned by pruning and growing is not easily vectorized as a dense matrix operation. We therefore implement customized GPU kernels to parallelize the computation of parameter learning and inference based Juice.jl [8). open-source Julia package for learning PCs. The kernels segment PC units into layers such that the units in each layer are independent. Thus, the computation can be fully parallelized on the GPU. As a result, we can train PCs with millions of parameters in less than half an hour.
Experiments
We now evaluate our proposed method pruning and growing on two different sets of density estimation
benchmarks: (1) the MNIST-family image generation datasets including MNIST 22). EMNIST 5
and FashionMNIST 46 (2) the character-level Penn Tree Bank language modeling task [27]
7

---

Section 6.1 first reports the best results we get on image datasets and language modeling tasks via the structure learning procedure proposed in Section [] Section 6.2 then shows the effect of pruning and growing operations via two detailed experimental settings. It studies two different constrained optimization problems: finding the smallest PC for a given likelihood via model compression and finding the best PC of a given size via structure learning.
Settings. For all experiments, we use hidden Chow-Liu Trees (HCLTs) 25 with the number of latent states in {16, 32, 64, 128} as initial PC structures. We train the parameters of PCs with stochastic mini-batch EM (cf. Section S). We perform early stopping and hyperparameter search using validation set and report results the test set. Please refer Appendix C for more details. We use mean test set bits telss-eerdimmssionn (bpd) as the evaluation criteria, where (Dd((,)) = - (C(D,C)/(log/ m) and m is the number of features in dataset D.
6.1 Density Estimation Benchmarks
Image Datasets. The MNIST-famill datasets contain gray-scale pixel images size 28 x 28 where each pixel takes values in j0, 255]. We split out 5% of training data validation set. We compare
with two competitive PC learning algorithms: HCLT [25] and RatSPN 34 one flow-based model:
IDF [17], and three VAE-based methods: BitSwap 20 BB-ANS AI, and McBits
FS For
fair comparison, we implement RatSPN structures ourselves and use the same training pipeline and EM optimizer our proposed method. Note that EinsumNet 33 also uses RatSPN structures but with a Py Torch implementation so its comparison is subsumed by comparison with RatSPN. All 7 methods tested on MNIST, 4 splits of EMNIST and FashionMNIST.. As shown in Table the best results are bold. We see that our proposed method significantly outperforms all other baselines on all datasets, and establishes new state-of-the-an results among PCs, flows, and VAE models. More experiment details are in Appendix
Table 1: Density estimation performance AINIST-famlly datasets in test set bpd.
Dataset
||
Sparse PC (ours)
HCLT
RatPNN
IDF
BitSwap
BB-ANS
McBits
MNIST EMNIST(MNIST)
1.14
1.20
1.67
1.90
1.27
1.39
1.98
1.52
1.77
2.56
2.07
1.88
2.04
2.19
EMNIST( Letters)
1.58
1.80
2.73
1.95
1.84
2.26
3.12
(aaase((
1.60
1.82
2.78
2.15
1.96
2.23
2.88
EMNIST((BClass)
1.54
1.85
1.98
1.87
2.23
3.14
FNSHionMNIST
3.27
3.34
4.29
3.47
3.28
3.66
3.72
Language Modeling Task. We use the Penn Tree Bank dataset with standard processing from Mikolov et al. (29], which contains around 5M characters and a character-level vocabulary size of 50. The data is split into sentences with maximum sequence length of 288. We compare with three competitive normalizing-flow-baae AF/SCF and IAF/SCF, since they are the only comparable work with non-autoregressive language modeling. As shown in Table the proposed method outperforms all three baselines.
models: Bipartite flow [42] and latent flows 4A including
Table 2: Character-level language modeling results on Penn Tree Bank in test set bpd.
Dataset
Sparse PC (ours) Bipartite flow (4
AF/SCF (48]
IAF/SCF 4%
Penn Tree Bank
1.35
1.38
1.46
1.63
6.2 Evaluating Pruning and Growing
What is the Smallest PC for the Same Likelihood? We evaluate the ability of pruning based on circuit flows
effective model compression by iteratively pruning a k-fraction of the PC parameters and then fine-tuning them until the final training log-likelihood does not decrease by more than 1%. Specifically, we take pruning percentage from (0.05, 0.1, 0.3). As shown in Figure g can achieve compression rate of 80-98% with negligible performance loss PCs. Besides, by

---

fixing the number of latent parameters (x-axis) and comparing bpp across different numbers of latent states (legend), we discover that compressing large PC to a get smaller PC yields better likelihoods compared to directly training an HCLT with the same number of parameters from scratch. This can be explained by the sparsity of compressed PC structures, as well as a smarter way of finding good parameters: learning better PC with larger size and compressing it down to smaller one.
amisid mriet
perrect letters
Pmorec telanced
emrret byclaos
tychlormetd
Irain bpan bod
9,67
0,37
1D TD
Farameters
Figure 8: Model compression via pruning and finetuming. We report the training set bpd (y-axis) in terms of the number of parameters (x-axiş for different numbers of latent states. For each curve, compression starts from the right (initial PC #Params (Crini() and ends at the left (compressed PC #Params ( ); compression rate (I - [ / /Caanae) is annotated next to each curve.
What is the Best PC for the Same Size? We evaluate structure learning that combines pruning and growing as proposed in Section S Starting from an initial HCLT, we iteratively prune 75% of the parameters, grow again, and fine-tune until meeting the stopping criteria. As shown in Figure 2 our method consistently improve the likelihoods of initial PCs for different numbers of latent states among all datasets.
matiz
emnict Jetters
bealaced
emnist bycass
Techionmnst
200
LG
32
35
123
14
121
135
23
52
135
Figure 9: Structure learning via 75% pruning, growing and finetuning. We report bpd (y-axis) on both train (red) and test set (green) in terms of the number of latent states (x-axis). For each curve, training starts from the top (large bpd) and ends at the bottom (small bpd).
7 Related Work
Improving the expressiveness of PCs has been a central topic in the literature. Predominant works focus the structure learning algorithms that iteratively modify PC structures progressively fit the data 7 24 15). Alternatively, recent trend is to construct PCs with good initial structures and only perform parameter learning afterwards [36] 47 For example, EiNets
[M4] and XPCs 12 use randomly generated structures, HCLTs 25 and ID-SPNs 37 define PCs dependent on the pairwise correlation on variables, and learn direct and indirect variable correlations among variables. There are also a few works that boost PC performance with the expressive power of neural networks. CSPNs
333, RAT-SPNs
33 harness neural networks learn expressive conditional density estimators, 40 utilizes neural networks for better PC regularization.
and HyperSPN
Pruning and growing have been introduced in deep neural networks to exploit sparsity [16] Similar strategies can be adopted in probabilistic circuits. Patil et al. 32 prune decision trees according to validation accuracy reduction. ResSPNs uses the lottery ticket hypothesis for weight pruning to gain more compact PCs 4K]. However, the neural network pruning methods and above PC pruning methods mainly focus pruning by parameters. In contrast to these, our work develops better pruning strategies based on semantic properties of PCs.
8 Conclusions
We propose structure learning probabilistic circuits by combining pruning and growing operations to exploit the sparsity of PC structures. We show significant empirical improvements in the density estimation tasks of PCs compared to existing PC learners and competing flow-based models and VAFs. All our Sparse-PC PC learning and inference algorithms available as GPU-parallel implementations.

---

Ackmowledgements This work was funded in part by the DARPA Perceptually-enabled Task Guidance (PTG) Program under contract number HR001 NSF grants #1IS-1943641, #IIS- 1956441, #CCF-1837129 Samsung. CISCO, a Sloan Fellowship, and UCLA Samueli Fellowship. We thank Honghua Zhang for proofreading and insightful comments on this paper's final version.
References
[1] Tameem Adel, David Balduzzi, and Ali Ghodsi. Learning the structure of sum sum-product networks via svd-based algorithm. In Proceedings of the 31st Conference on Uncertainty in Artificial Intelligence ( (UAI), 2015.
[2] 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 34th AAAI Conference on Artificial Intelligence, 2020.
[3] YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. Technical report, 2020.
[4] YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group fairness by probabilistic modeling with latent fair decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, 2021.
[5] Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference on Neural Networks (IJCNN, 2017.
[6] Alvaro Correia, Robert Peharz, and Cassio P de Campos. Joints in random forests. In Advances in Neural Information Processing Systems 33 (NeurIPS), 2020.
[7] Meihua Dang, Antonio Vergari, and Guy Van den Broeck. Strudel: Learning structured- decomposable probabilistic circuits. In Proceedings of the 10th International Conference Probabilistic Graphical Models (PGM), 2020.
[8] Mcihua Dang, Pasha Khosravi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. Juice: julia package for logic and probabilistic circuits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (Demo Track), 2021.
[9] Adnan Darwiche. A logical approach to factoring belief networks. In Proceedings of the 8th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2002.
[10] Adnan Darwiche. A differential approach to inference in bayesian networks. Journal of the ACM, 2003.
[11] Adnan Darwiche and Pierre Marquis. A knowledge compilation map. Journal of Artificial Intelligence Research, 2002.
[12] Nicola Di Mauro, Gennaro Gala, Marco lannotta, and Teresa M.A. Basile. Random probabilistic circuits. In Proceedings of the 37th Conference Uncertainty in Artificial Intelligence (UAI), 2021.
[13] Marc Dietrichstein, David Major, Martin Trapp. Maria Wimmer, Dimitrios Lenis, Philip Winter, Astrid Berg, Theresa Neubauer, and Katja Bühler. Anomaly detection using generative models and sum-product networks in mammography scans. In MICCAI Workshop on Deep Generative Models, 2022.
[14] Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation. arXiv preprint arXiv: 1418.5 16, 2014.
[15] Robert Gens and Domingos Pedro. Learning the structure of sum-product networks. In Proceedings of the 30th International Conference Machine Learning (ICML), 2013.
10

---

[16] Torsten Hoefler, Dan Alistarh, Tal Ben-Nun. Nikoli Dryden, and Alexandra Peste. Sparsity in deep learning: Pruning and growth for efficient inference and training in neural networks. Journal of Machine Learning Research, 2021.
[17] Emiel Hoogeboom, Jorn Peters, Rianne Van Den Berg, and Max Welling. Integer discrete flows and lossless compression. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[18] Pasha Khosravi, Yoolung Choi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. On tractable computation of expected predictions. Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[19] Diederik P Kingma and Max Welling. Auto-encoding variational bayes. arXiv preprint arXiv:1312.6114, 2013.
[20] Friso Kingma, Picter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
[21] Doga Kisa, Guy Van den Broeck, Arthur Choi, and Adnan Darwiche. Probabilistic sentential decision diagrams. In Proceedings of the 14th International Conference on Principles of Knowledge Representation and Reasoning (KR), 2014.
[22] Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http:/yawn.leccu..oomeedddd
2, 2010.
[23] Wenzhe Li, Zhe Zeng, Antonio Vergari, and Guy Van den Broeck. Tractable computation of expected kernels. In Proceedings of the 37th Conference Uncertainty in Aritifical Intelligence (UAI), 2021.
[24] 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 (UAT), 2017.
[25] Anji Liu and Guy Van den Broeck. Tractable regularization of probabilistic circuits. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.
[26] Anji Liu, Stephan Mandt, and Guy Van den Broeck. Lossless compression with probabilistic circuits. In Proceedings of the 10th International Conference on Learning Representations (ICLR), 2022.
[27] Mitchell P. Marcus, Mary Ann Marcinkiewicz, and Beatrice Santorini. Building a large annotated corpus of english: The penn treebank. Computational Linguistics, 1993.
[28] Radu Marinescu and Rina Dechter. And/or branch-and-bount for graphical models. In Pro- ceedings of the 19th International Joint Conference on Artificial Intelligence (IJCAI), 2005.
[29] Tomáš Mikolov, Ilya Sutskever, Anoop Deoras, Hai-Son Le, and Stefan Kombrink. Subword lan- guage modeling with neural networks. preprint http://wwwwf...uubbccc/mm/////md 2012.
[30] 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 sum-product networks. arXiv preprint arXiv: 1901 9074003744 2019.
[31] George Papamakarios, Eric Nalisnick, Danilo Jimenez Rezende, Shakir Mohamed, and Balaji Lakshminarayanan. Normalizing flows for probabilistic modeling and inference. Journal of Machine Learning Research, 2021.
[32] Dipti D Patil, VM Wadhai, and Gokhale. Evaluation of decision tree pruning algorithms for complexity and classification accuracy. International Journal of Computer Applications, 2010.
11

---

[33] Robert Peharz, Steven Lang. Antonio Vergari, Karl Stelzner, Alejandro Molina, Martin Trapp. Guy Van den Broeck, Kristian Kersting, and Zoubin Ghahramani. Einsum networks: Fast and scalable learning of tractable probabilistic circuits. In Proceedings of the 37th International Conference on Machine Learning (ICML., 2020.
[34] Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp. Kristian Kersting, and Zoubin Ghahramani. Random sum num-product networks: A simple and effective approach to probabilistic deep learning. In Proceedings of the 36th Conference on Uncertainty in Aritifical Intelligence (UAI), 2020.
[35] Hoifung Poon and Pedro Domingos. Sum-product networks: A new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), 2011.
[36] Tahrima Rahman, Prasanna Kothalkar, and Vibhav Gogate. Cutset networks: A simple, tractable, and scalable approach for improving the accuracy of chow-liu trees. In Joint European confer- ence on machine learning and knowledge discovery in databases, 2014.
[37]
Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In Proceedings of the 31 International Conference on Machine Learning (ICML), 2014.
[38] Yangjun Ruan, Karen Ullrich, Daniel S Severo, James Townsend, Ashish Khisti, Arnaud Doucet, Alireza Makhzani, and Chris Maddison. Improving lossless compression rates via monte carlo bits-back coding. In Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
[39] Xiaoting Shao, Alejandro Molina, Antonio Vergari. Karl Stelzner, Robert Peharz, Thomas Liebig, and Kristian Kersting. Conditional sum-product networks: Modular probabilistic circuits via gate functions. International Journal of Approximate Reasoning, 2022.
[40] Andy Shih, Dorsa Sadigh, and Stefano Ermon. Hyperspns: Compact and expressive probabilistic circuits. In Advances Neural Information Processing Systems 34 (NeurIPS). 2021.
[41] James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In Proceedings of the 6th International Conference Learning Representations (ICLR), 2018.
[42] Dustin Tran, Keyon Vafa, Kumar Agrawal, Laurent Dinh, and Ben Poole. Discrete flows: Invertible generative models of discrete data. In Advances in Neural Information Processing Systems 32 (NeurIPS), 2019.
[43] Fabrizio Ventola, Karl Stelzner, Alejandro Molina, and Kristian Kersting, Residual sum- cum-product networks. In Proceedings of the 10th International Conference on Probabilistic Graphical Models (PGM), 2020.
[44] Antonio Vergari, YooJung Choi, Robert Peharz, and Guy Van den Broeck. Probabilistic circuits: Representations, inference, learning and applications. AAAI Tutorial, 2020.
[45] Antonio Vergari, YooJung Choi, Anji Liu, Stefano Teso, and Guy Van den Broeck. A composi- tional atlas of tractable eircuit operations for probabilistic inference. In Advances in Neural Information Processing Systems 34 (NeurIPS), 2021.
[46] Han Xiao, Kashif Rasul, and Roland Vollgraf. fushion-mnist a novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv: 1XX8:17708.0747777 2017.
[47] Honghua Zhang, Brendan Juba, and Guy Van den Broeck. Probabilistic generating circuits. In Proceedings of the 38th International Conference Machine Learning (ICML), 2021.
[48] Zachary Ziegler and Alexander Rush. Latent normalizing flows for discrete sequences. In Proceedings of the 36th International Conference on Machine Learning (ICML), 2019.
12


Reviews:
[{"review_id": "mIBIXY6eHG3", "reviewer": "Reviewer_QUWk", "summary": "The authors present an algorithm to distill probabilistic circuits (PCs). In this particular case, they present pruning and growing operations, removing nodes that are not significant for the estimator and adding nodes where needed.\n\nThe authors present and prove multiple variants for pruning, describe structure learning via pruning and growing and parameter estimation via stochastic mini-batch EM.\nFurthermore, the strong empirical results indicate that this approach can have significant impact in the learning of PCs.\n\nThis approach also allows practitioners to control between model size and performance.\n\n", "questions": "Although this paper proposes a very strong approach as shown by the empirical results. There are some important aspects open. \n\nI'm wondering about the impact of the pruning and growing operations with respect to the impact they have in PCs on their performance as density estimators.\n\nConsider starting with a large trained PC. Is the removal of a particular node via your pruning, something that increases the likelihood? Or are those extra nodes simply overlapping other parts of the distribution but have no negative impact (other than size) by being there? In 6.2 you mention that it is better than starting from a smaller size, but you do not mention what happens if you start big, but prune and optimize without growing. \n\nIs the improvement in the performance all due to the growing operation? I could understand that if the model lacks capacity in a particular node then it would be very beneficial to extend there. But is that the operation responsible for the improvement? \nOr is the improvement coming from the noise injected by the growing operation? This could potentially push the optimizer into regions it hasn't explored well before.\n\nIn short, more insights or experiments on what is causing the improvement would make the paper even stronger.", "limitations": "no negative societal impact.", "rating": 9, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a solid contribution as shown by the empirical evaluation, pushing state-of-the-art in PCs.\n\nThe paper is well-written and technically sound. \n\nThere are some minor weaknesses:\nIn [1] the authors propose a pruning approach based on the lottery ticket hypothesis for PCs, I believe this might be relevant here.\nThere is no comparison to other methods that work on regularization of PCs such as [2]. \n\n[1] Ventola, Fabrizio, et al. \"Residual Sum-Product Networks.\" International Conference on Probabilistic Graphical Models. PMLR, 2020.\n[2] Shih, Andy, Dorsa Sadigh, and Stefano Ermon. \"HyperSPNs: compact and expressive probabilistic circuits.\" Advances in Neural Information Processing Systems 34 (2021): 8571-8582.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "SjOJq-C5YHV", "reviewer": "Reviewer_Y5Dn", "summary": "This work suggests a method for exploiting sparsity in probabilistic circuits (PCs). The authors motivate the paper by showing PC parameters being close to zero in the majority of PCs' sum edges. Thus, these models could be reduced with a potentially negligible loss in representation (log-likelihood). The paper suggests two methods for compressing a PC while minimizing its representation loss: pruning and growing. Pruning identifies and removes parts of the PC that can be shown as non-important under the PC-represented distribution. Similarly, growing mitigates representation loss by adding new edges with noisy parameters, which can be optimized to achieve better performance. Applying \"pruning and growing\" can significantly reduce the model's size while not losing much performance.", "questions": "* It would be interesting to investigate if any of these relevance metrics could be applicable in other models, such as the competitors in Table 1 since the metrics are either magnitude or sampling-based.\n* In the literature, PC architectures with intractable parts can be found either at the leaf level or internal nodes. Could the metrics suggested here be adapted or used in such architectures?\n* Although the work is well-motivated, a suggestion for improvement would be to relate this work's results to real-world applications and previous literature practical results. For instance, the compression gains with minor likelihood loss could be associated with specific application scenarios. Moreover, referencing previous works' struggles with model size might further ground the paper's results.", "limitations": "This paper does not explicitly discuss its limitations. Since the experimental results are a crucial draw for this work, it could be beneficial to add a short discussion on how the metrics used to measure exploiting sparsity benefit or hurts the different models being evaluated.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Some of this work's strengths are its comprehensive solution and clear, practical relevance. Regarding the comprehensive solution, this paper puts forth the problem of computation sparsity in PCs. This problem involves both tasks of removing unnecessary parts of this computation while minimizing loss in performance. The solution suggested in this manuscript tackles both tasks by providing modular techniques called pruning and growing. These techniques allow for fine-tuning the gains and losses of compression and log-likelihood, respectively, and they are individually grounded on theoretical results. For instance, the pruning technique called eFlow is a good approximation for the upper bound of the log-likelihood drop when removing edges, as shown in Theorem 1 and 2. These comprehensive discussions of the sparsity problem, including theoretical analysis, strengthen the work here.\nThis paper's practical relevance is evident in its motivation and provides state-of-the-art results on benchmark experiments. Indeed, the manuscript emphasizes the impact of sparsity in the model size, as depicted in Figure 1, while also showing methods for maximizing efficiency, as discussed in Section 5. Thus, the work being suggested here is relevant for practical applications. This premise is confirmed with state-of-the-art results in challenging datasets. Furthermore, the extended discussion in Section 6.2 is exciting, and it shows the capabilities of pruning-growing operations on fine-tuning the trade-off between PC size and accuracy.\n\nOne minor weakness in this paper's presentation lies in the intuition behind the \"theoretically-grounded metric\" for the importance of PC edges. The manuscript says that the \"global influence of edges on the PC's output\" is \"highly related to PC semantics.\" This point is positive for the use of PCs compared to other models, such as some competitors in Table 1, since PC's semantics are a differentiator characteristic. However, theoretical discussions in Section 4 are focused on one pruning method, EFlow, which bases itself on PC's sampling process. Thus, it is unclear from the text how the theoretical analysis uses PC's unique semantics.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "HSvJQQ5ZWeR", "reviewer": "Reviewer_YPFA", "summary": "An approach to pruning and growing probabilistic circuits is proposed, which is empirically shown to be useful for achieving higher effective utilization of the weights of the circuit and thus better likelihoods on various datasets.", "questions": "The approach of evaluating the probability of reaching some node of a probabilistic tree feels certain to have been used before in other settings. Can we find prior work that this would connect with?\n\nTable 1: How many parameters are used by each of these models? How robust is the method (std devs of ~10 fits)? How long does each method take to fit?\n\nSec 6.2: The criteria of \"log likelihood does not decrease by more that 1%\" seems a little arbitrary, like a sliding scale. Is this commonly done in the model compression/pruning literature? I've seen results about changes in top-1/top-5 % accuracy after pruning. To put it differently: a change from 1.6 bpd to 1.7 bpd is more significant than a change from .16 to .17, and Fig 6 is comparing at least three different scales (1.2, 1.8, 3.4).\n\nSec 7: Can we say anything about model selection / Bayes information criterion for PCs? Does the pruning/growing approach give us a way of finding a BIC-optimal PC?", "limitations": "line 229 addresses a limitation - sparse PC is not vectorization-friendly and requires custom GPU kernels. These are provided in OSS.\n\nNo societal impact noted by authors or reviewer.", "rating": 8, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Originality\nThe approach to pruning ends up being quite simple, evaluating the probability of sampling along any given branch of the circuit's tree and using that as an upper bound for the influence that portion of the tree can have on the overall joint density, then pruning out low-influence branches. I have not seem similar work in PCs, but would not be surprised to be able to find something related if looking at work in trees, graphs, etc. In fact, it would be nice if we could point to some work on decision trees or graph/network flow as algorithmically related work in this space. Relative to other approaches to learning PC structure, the prune and grow approach seems possibly simpler, and the empirical results suggest it is more robust.\n\nQuality\nThe work is well done and experiments seem typical for the PCs + density estimators space (MNIST family + PTB). The overall construction of the paper is sound, approach is well explained.\nThe paper needs proofreading. Multiple misspellings, grammar issues (lines 30, 31, 38, 59, 87, 105, 198, 240, 279). Rather than \"term\" on lines 171, 172, 181, 185, perhaps \"expression\" would be a better word. Line 194, isn't it impossible to get a more expressive PC by pruning (not just \"difficult\")? Line 271, I would use \"k portion\" or \"k fraction\" instead of \"k%\" because k% makes it ambiguous whether k% of .1 means .1 fraction or .001 fraction.\n\nClarity\nPresentation is clear, and the experiments demonstrate the value incremental to multiple competitive baselines. Presumably these results would also map to more effective lossless PC-based compression, which might have been a nice story to tag onto the experiments.\n\nSignificance\nThis work is important in the space of density estimation & probabilistic circuits, which historically has been of interest to a broad swath of conference participants. Achieves new SoTAs in this class for bpd. The technique is also relevant in the wider space of model pruning, which is also of broad interest.", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "3exYL06wxkQ", "reviewer": "Reviewer_BazA", "summary": "This work addresses the scalability issue of the probabilistic circuits. They propose a technique of pruning and growing to scale and improve the expressiveness of the PCs. For pruning, they propose pruning edges based on the probability that it will be `activated’ during sampling (eFlow strategy in Alg.1). To counter the reduction in the model capacity done by the pruning step, they introduce a Grow (Alg.2) strategy. To obtain a compressed PC, they alternate between the pruning & growing operations based on optimizing for the log-likelihood. ", "questions": "Questions &  Suggestions:\n1. I found the definition of root node confusing initially. Usually, a DAG will have sources and sinks. I understand that if the nomenclature followed in the previous works states the same but if not, please update the naming. \n2. (Line 105) thee -> the\n3. The datasets used in this paper are still small in size IMO. Will be helpful to see the scaling on larger datasets. Alternatively, if the authors can report the limitations of their approach for larger datasets, that will be appreciated as well. \n4. What is the intuition in using the hidden Chow-Liu Tree as the initial PC structure for the experiments? \n5. (Viewing as a structure learning algorithm for the PC) I suspect that after compressing the initial PC structure, one would end up with a larger (due to the grow operation) but a sparser (due to prune) structure. Then the choice of initial PC structure will play a key role. The grow operation will increase the params by a factor of 4, so please share your thoughts on using 75% pruning? \n6. How many iterations (between grow + prune) are needed for convergence for the MNIST and PTB tasks?\n", "limitations": "As mentioned above, will be good to know the scale of the data this method can currently handle. ", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros & Cons:\n1. It is a well-written paper. I appreciate the authors introducing the literature and prior work about PCs in a concise and efficient manner. \n2. The formulation of pruning by circuit flows is a natural follow-up question to the pruning by generative significance. The sampled conditioned parameterization is one approach which the authors introduced in this work. This may introduce a bias/overfitting for the training data? I wonder if there are other approaches that can better handle the same problem. What if we do unconditional sampling and then measure the probability of observing the sampled data with the observed data. Use this information to weigh the flow?\n\nThis is good work, although I feel the scalability performance is still far from using it on larger datasets (at least from the experiments added in the paper). \n", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept