Lossless Compression with Probabilistic Circuits
Authors: Anji Liu
Stephan Mandt
Guy Van den Broeck
Venue: ICLR 2022 Spotlight (2022)

Abstract: Despite extensive progress on image generation, common deep generative model architectures are not easily applied to lossless compression. For example, VAEs suffer from a compression cost overhead due to their latent variables. This overhead can only be partially eliminated with elaborate schemes such as bits-back coding, often resulting in poor single-sample compression rates. To overcome such problems, we establish a new class of tractable lossless compression models that permit efficient encoding and decoding: Probabilistic Circuits (PCs). These are a class of neural networks involving $|p|$ computational units that support efficient marginalization over arbitrary subsets of the $D$ feature dimensions, enabling efficient arithmetic coding. We derive efficient encoding and decoding schemes that both have time complexity $\mathcal{O} (\log(D) \cdot |p|)$, where a naive scheme would have linear costs in $D$ and $|p|$, making the approach highly scalable. Empirically, our PC-based (de)compression algorithm runs 5-40 times faster than neural compression algorithms that achieve similar bitrates. By scaling up the traditional PC structure learning pipeline, we achieve state-of-the-art results on image datasets such as MNIST. Furthermore, PCs can be naturally integrated with existing neural compression algorithms to improve the performance of these base models on natural image datasets. Our results highlight the potential impact that non-standard learning architectures may have on neural data compression.

Published as a conference paper at ICLR 2022
LOSSLESS COMPRESSION WITH PROBABILISTIC CIRCUITS
Anji Liu
Stephan Mandt
Guy Van den Broeck CS Department UCLA guyvdbêcs. ucla.c. edu
CS Department
CS Department University of California, Irvine mandt Suuttuucieede
UCLA
1 liuanji @cs. .ulla edu
ABSTRACT
Despite extensive progress on image generation, common deep generative model architectures are not easily applied to lossless compression. For example, VAEs suffer from compression cost overhead due to their latent variables. This over- head can only be partially eliminated with elaborate schemes such bits-back coding, often resulting poor single-sample compression rates. overcome such problems, establish permit efficient encoding and decoding: Probabilistic Circuits (PCs). These are a class of neural networks involving [p) computational units that support efficient marginalization over arbitrary subsets of the D) feature dimensions, enabling effi- cient arithmetic coding. We derive efficient encoding and decoding schemes that both have time complexity (log(D) (p)), where a naive scheme would have linear costs in D and pp). making the approach highly scalable. Empirically, our PC-based (de) comppeessio algorithm runs 5-40 times faster than neural compres- sion algorithms that achieve similar bitrates. By scaling up the traditional PC structure learning pipeline, we achieve state-of-the-art results on image datasets such as MNIST. Furthermore, PCs can naturally integrated with existing neural compression algorithms to improve the performance of these base models nat- ural image datasets. Our results highlight the potential impact that non-s non-standard learning architectures may have neural data compression.
class of tractable lossless compression models that
INTRODUCTION
Thanks their expressiveness, modern Deep Generative Models (DGMs) such as Flow-based models (Dinh et al. 2014), Variational Autoencoders (VAEs) (Kingma & Welling 2013). and Generative Adversarial Networks (GANs) (Goodfellow et al. 2014) achieved state-of tta results on generative tasks such as creating high-quality samples Vahdat & Kautz 2020) and learning low-dimensional representation data (Zheng & Sun 2019). However, these successes have not been fully transferred (Yang al. 2022) for recent survey. Specifically, GANs
into neural lossless compression; cannot be used for lossless compression due to their inability to assign likelihoods to observations. Latent variable models such VAEs rely on rate estimates obtained by lower-bounding the likelihood of the data, i.c., the quantity which is theoretically optimal for lossless compression: they furthermore rely on sophisticated schemes such bits-back coding (Hinton & Van Camp rates, oftentimes resulting in poor single-sampi compression ratios (Kingma et al. 2019).
1993) realize these
Therefore, good generative performance does not imply good compression performance for lossless compression, as the model needs to support efficient algorithms to encode and decode close to the model's 's theoretical rate estimate. While both Flow- and VAE-based compression algorithms (Hoogeboom et al.) 2019; Kingma et al.) 2019) support efficient and near-optimal compression under certain assumptions (e.g., the existence of an additional source random bits), we show that Probabilistic Circuits (PCs) (Choi et al. 2020) are also suitable for lossless compression tasks. This class of tractable models has a particular structure that allows efficient marginalization of its random variables property that, we introduce PCs as backbone models and develop (de)compression algorithms that achieve high compression ratios and high computational efficiency.
show, enables efficient conditional entropy coding. Therefore,

---

Published as a conference paper at ICLR 2022
Similar to other neural compression methods, the proposed lossless compression approach operates in two main phases - (i) learn good PC models that approximate the data distribution, and (ii) compress and decompress samples with computationally efficient algorithms. The proposed lossless compression algorithm has four main contributions:
A new class of entropy models. This is the first paper that uses PCs for data compression. In contrast to other neural compression algorithm, we leverage recent innovations in PCs to automatically learn good model architectures from data. With customized GPU implementations and better training pipelines, we are the first to train PC models with competitive performance compared to deep learning models on datasets such as raw MNIST.
A new coding scheme. We developed a provably efficient (Tm.. lossless compression algorithm for PCs that take advantage of their ability efficiently compute arbitrary marginal probabilities. Specifically, we first show which kinds of marginal probabilities are required for (de)compression. The proposed algorithm combines an inference algorithm that computes these marginals efficiently given a learned PC and SoTA streaming codes that use the marginals for en- and decoding.
Competitive compression rates. Our experiments show that on MNIST and EMNIST, the PC-based compression algorithm achieved So bitrates. On more complex data such as subsampled ImageNet, we hybridize PCs with normalizing flows and show that PCs can significantly improve the bitrates of the base normalizing flow models.
Competitive runtimes. Our (de)comprsssor runs 5-40x faster compared to available implementations of neural lossless compressors with near SoTA performance datasets such MNIST Our open-source implementation of the PC-based (de)coopression algorithm can be found at https ?
//github. com/ Saeam/Juiieeaa iiwiiccee1/PreesedJu...
11
Notation We denote random variables by uppercase letters (c.g., X) and their assignments by lowercase letters (e.g., 2)). Analogously, we use bold uppercase (e.g., X) and lowercase (e.g., a)) letters to denote sets of variables and their joint assignments, respectively. The set of all possible joint assignments to variables X is denoted val(X).
2 TRACTABILITY MATTERS IN LOSSLESS COMPRESSION
The goal of lossless compression is to map every input sample to an output codeword such that (i) the original input can be reconstructed from the codeword, and (ii) the expected length of the codewords minimized. Practical (neural) lossless compression algorithms operate in two main phases learning and compression Yangg et al. 2022). In the learning phase, a generative model p(X) is learned from a dataset D:= (x)) Ji=1- According to Shannon's 's source coding theorem (Shannon nower-bounded by the negative cross-entropy between the
1948). the expected codeword length data distribution 'D and the model distribution p(X) (i.e., - ED log p( xz) rendering it a natural
and widely used objective to optimize the model (Hoogeboom et al. 2019 Mentzer et al. 2019).
In the compression phase, compression algorithms take the learned model p and samples and generate codewords whose expected length approaches the theoretical limit (i.e., the negative cross-entropy between D and p). Although there exist various close-to- cosstmml- compression schemes (c.g.. Huffman Coding (Huffman 1952) and Arithmetic Coding (Rissanen) 1976)), a natural question to ask is what the requirements on the model p such that compression algoritmms can utilize it for encoding/decoding in computationally efficient manner? In this paper, we highlight the advantages of tractable probabilistic models for lossless compression by introducing concrete class of models that are expressive and support efficient encoding and decoding.
input
To encode sample ær standard streaming code operates by sequentially encoding every symbol s;; into a bitstream b, such that x; occupies approximately log p( -., xx-1)) bits in b. As a result, the length of 6 is approximately
log p(z). For example, Arithmetic Coding (AC) encodes the symbols {xt) (define D= [X] as the number of features) sequentially by successively refining an interval that represents the sample, starting from the initial interval [0, 1). To encode 2,, the algorithm
Note that there exists compression algorithms optimized particularly for speed by using simple entropy models (Towssed et al. 2019), though that also leads worse bitrates. See 3.3 for detailed discussion.
2

---

Published as a conference paper at ICLR 2022
partitions the current interval [a, using the left and right side cumulative probability of xy;
(zz) := p(X; < 1i....,, x4-1)),
hz(24) := p(X, Sx / 21,...,,;;--........ xi-1).
(I)
Specifically, the algorithm updates la.b) b) to the following: [a + -1 a ( (b-a)-b-
which is sub-interval of (a, b). Finally, AC picks number within the final interval that has the shortest binary representation. This number is encoded as a bitstream representing the codeword of æ. decoded sequentially: at iteration i, we decode variable
Upon decoding, the symbols [= X; by looking up its value x such that its cumulative probability (i.e., 4xx)) matches the subinterval specified by the codeword and æ1,..... 24-1 (Rissanen 1976); the decoded symbol z; is then used to compute the following conditional probabilities (i.e., (z) for j > i). Despite implementation differences, computing the cumulative probabilities (xr and (x: are required for many other streaming codes (e.g., rANS). Therefore, for most streaming codes, the main computation cost of both the encoding and decoding process comes from calculating (x) and h, (x)..
The main challenge for the above (de)coompression algorithm is to balance the expressiveness of and the computation cost of (1:(x). [r) On the one hand, highly expressive probability models such as energy-based models (Lecun et al. 2006 Ranzato et al., (007) can potentially achieve high compression ratios at the cost of slow runtime, which is due to the requirement of estimating the model's 'ss normalizing constant. On the other hand, models that make strong independence assumptions (e.g.. n-gram, fulty-factorized) are cheap to evaluate but lack the expressiveness to model complex distributions over structured data such images
This paper explores the middle ground between the above two extremes. Specifically, we ask: are there probabilistic models that are both expressive and permit efficient computation of the conditional probabilities in Eg.. (1) This question can be answered in the affirmative by establishing a new class of tractable lossless compression algorithms using Probabilistic Circuits (PCs) (Choi al. (020)). which are neural networks that can compute various probabilistic queries efficiently. In the following, we overview the empirical and theoretical results of the proposed (de)compression algorithm.
We start with theoretical findings: the proposed encoding and decoding algorithms enjoy time complexity (log(D) . (p), where |p| 2 D the PC model size. The backbone of both algorithms. formally introduced in Sec. 3] is an algorithm that computes the 2 x D conditional probabilities (1(x), (e( given any x efficiently, as justified by the following theorem.
Theorem 1 (informal). Let be a D-dimensional sample, and let p be PC model of size [pl as proposed in this paper. We then have that computing all quantities (4(11)) h((x))2 takes (D) (pl) time. Therefore, en- or decoding x with a streaming code (e.g., Arithmetic Coding) takes Olog DD-lpl + D) = Oloog( (loog(D).1p) D)-(p)) time.
The properties of PCs that enable this efficient lossless compression algorithm will be described in [Sec. 3.1 and the backbone inference algorithm with (llog(D) (pl) time complexity will later be shown as Alg. I Table provides (incomplete) summary of our empirical results. First, the PC-based lossless compression algorithm is fast and competitive. As shown in Table I the small PC model achieved near-SoTA bitrate while being 15x faster than other neural compression algorithms with a similar bitrate. Next, PCs can be integrated with Flow-/VAE. based compression methods. As illustrated in Table right,, the integrated model significantly improved performance on sub-sampled ImageNet compared to the base IDF model.
3 COMPUTATIONALLY EFFICIENT (DE)COMPRESSION WITH PCS
In the previous section, we have boiled down the task of lossless compression to calculating con- ditional probabilities (1( (xx)):) given p and 24. This section takes PCs into consideration and demonstrates how these queries can be computed efficiently. In the following, we first introduce relevant background on PCs (Sec. 3.1), and then proceed to introduce the PC-based (de)cooprsni algorithm (Sec. 3.2). Finally, we empirically evaluate the optimality and speed of the proposed compressor and decompressor (Sec. 3.3).
2 FFlow-mode model- based neural compression algorithms adopt defined on mutually independent latent variables (denoted Z). and improve expressiveness by learning bijection functions between Z and X (i.c., the input space). This is orthogonal to approach of directly learn better p. Furthermore, can naturally integrate the proposed expressive p with bijection functions and achieve better performance as demonstrated in Sec.
3

---

Published as a conference paper at ICLR 2022
Table 1: An (incomplete) summary of our empirical results. "Comp." stands for compression.
MNIST (10,000 test images)
ImageNet32
ImageNer64
Method
Method
Theoretical bpd Comp. bpd En- & decoding time
Theoretical hpd Theoretical bpd
PC (small)
1.26
1.30
.33
PC+IDF
3,99
3.71
PC (large)
1.20
1,24
168
IDF
4.15
3.90
IDF
1.90
1.96
880
RealNVP
4.28
3.98
BitSwap
1.27
1.31
904
Glow
4.09
3.81
3.1 BACKGROUND; PROBABILISTIC CIRCUITS
Probabilistic Cireuits (PCs) are an umbrella term for a wide variety of Tractable Probabilistic Models (TPMs). They pro- vide a set of succinct definitions for popular TPMs such as Sum-Product Networks (Poon & Domingos 2011), Arithmetic Circuits (Shen et al., 2016), and Probabilistic Sentential Deci- sion Diagrams (Kisa al. 2014). The syntax and semantics of a PC are defined as follows.
0.0
0.28
X
LO
0,066
X.
Definition 1 (Probabilistic Circuits), A PC p(X) represents probability distribution over X via parametrized directed acyclic graph (DAG) with a single root node n,,. Similar to neu- ral networks, every node of the DAG defines computational unit. Specifically, each leaf node corresponds to an input unit; each inner node n represents either sum or a product unit that receives inputs from its children, denoted in(n). Each node n encodes probability distribution Pn, defined as follows:
example structured- decomposable PC. The feedfor- ward order is from left to right; in- puts assumed to be boolean vari- ables; parameters are labeled on the corresponding edges. Probability of each unit given input assignment in W2254 labeled blue next to the corresponding unit.
Figure
(x)
if is an input unit, if n. sum unit,
Pn. = Eecin(n) On,e Pe(x) [TTEi(N)) (x if n is product unit,
where (.) is univariate input distribution (e.g., Gaussian, Categorical), and On.. denotes the parameter that corresponds to edge (n.cc. Intuitively, sum and product units encode weighted mixtures and factorized distributions of their children's 's distributions, respectively. To ensure that a PC models a valid distribution, we assume the parameters associated with any sum unit are normalized: Eeennnn i, = We further assume w.l.o.g. that PC alternates between sum and product units before reaching an input unit. The size of a PC p. denoted [p], is the number of edges in its DAG.
This paper focuses on PCs that can compute arbitrary marginal queries time linear in their size, since this is necessary to unlock the efficient (de (de)compression algorithm. In order to support efficient marginalization, PCs need to be decomposable (Def. 2 which is a property of the (variable) scope ((n) of PC units n, that is, the collection of varialls defined by all its descendent input units.
Definition 2 (Decomposaailltty). A PC is decomposable if for every product unit its children have disjoint scopes: Ver, 62 E in(n)) (ci + c2), d(ci) n ((c2)= Ø.
All product units in Fig. are decomposable. For example, each purple product unit (whose scope is (X,,XX ) has two children with disjoint scopes {X1} and (X2). respectively. In addition to Def. 2] we make use of another property, structured decomposabilliy, which is the key to guaranteeing computational efficiency of the proposed (de)compression algorithm.
PC is structured-decct deccuureddecomppsabbee (i) it is decom- posable and (ii) for every pair of product units (m, n) with identical scope (i.e., o(m) d(n)). we have that [in(m)] = [in(n)) and the scopes of their children are pairwise identical: Vi E (1,..., (....)!i((m)) [in(m)]] d(cm.)) = ((en)), where cm; and en, are the ith child unit of m and n.
Definition 3 (Structured decomposability).
3 'nnother property called smoothness is also required to compute marginals efficiently. However, since enforcing smoothness any dinccpubeddeccommpabllll PC only imposes most almost-linear increase in its size (Shih al. 2019), we omit introducing it here (all PCs used in this paper are stucttrad-deccoppssbbe))
4

---

Published as a conference paper at ICLR 2022
Encoder
Decoder
Image patch, <.g., 2x2
p | 1a
Sereaming code
Same PC
(eg. rANS)
Group #1
p(ra [.n,,ss)
N
Pixel born seme Pixel being seat
Group #3
Bitstream
Streaming code (eg, FANS)
All nodes in groups #1, #2, and #3 do not need to be explicilly evaluated.
Group #2
Reconstructed patch
Figure 2: Overview of the PC-based (de)compressor. The encoder's 's side sequentially compresses variables one-by-one using the conditional probabilities given all sent variables. These probabilities computed efficiently using Alg. I Finally, streaming code uses conditional probabilities to compress the variables into a bitstream. On the decoder's ' side, a streaming code decodes the bitstream reconstruct the image with the conditional probabilities computed by the PC.
The PC shown in Fig. is drructuredddccompsatbe because for all three groups of product units with the same scope (grouped by their colors), their children divide the variable scope in the same way. For example, the children of both orange units decompose the scope (X1,, X2, X3, X4} into {X1, 32) and {X3, X4).
As key sub-routine in the proposed algorithm, we describe how to compute marginal queries given smooth and (structured- (strrctureddxdecooppssse ydecomposable PC in O(Ip)) time. First, we assign probabilities to every input unit: for an input unit defined variable X, if evidence is provided for X in the query (e.g., X =
or X <x),, we assign to n the corresponding probability (e.g., p(X px==x) =), p(X <x)) according to Jn do feedforward (children before parents) traverse of inner PC units and compute their probabilities following [Fq. (2) The probability assigned to the root unit is the final answer of the marginal query. Concretely, consider computing p( , x4) for the PC in Fig. 1 This is done by (i) assigning probabilities to the input units w.r.t. the given evidence T1, Ø2, and Za (assign to the imput unit labeled X₂ and -X, as they contradict the given evidence; all other input units are assigned probability 1). and (ii) evaluate the probabilities of sum/product units following Eq. (2). Evaluated probabilities are labeled next to the corresponding units, hence the marginal probability at the output is p(a1, 22, v4) 0.056.
in Eq. (2) if evidence of X is not given, probability 1 is assigned to n.. Next,
3.2 EFFICIENT (DE-) COMPPESSNNN WITH STRUCTURED--DECOMPSSAN
PCs
The proposed PC-based (de)compresiion algorithm is outlined in Fig. 2 Consider compressing an 2-by-2 image, whose four pixels are denoted as x,,..., As discussed in See. 2] the encoder converts the image into bitstream by encoding all variables autoregressively. For example, suppose we have encoded 1 22- To encode the next variable 23, we compute the left and right side cumulative probability of 23 given 21 and T2, which are defined as (2(13) and ha (xz)) in Sec. 2] respectively. streaming code then encodes T3 into a bitstream using these probabilities. Decoding is also performed autoregressiveel. Specifically, after x; and 22 decoded, the same streaming code uses the information from the bitstream and the conditional distribution p(r3 æ1, x22 to decode Iz.
Therefore, the main computation cost of the above en- and decoding procedures comes from calculat- ing the 2D conditional probabilities {4, (æ), hx(x)) P w.r.t. any æ. Since every conditional probability can be represented as the quotient of two marginals, it is equivalent to compute the two following sets of marginals: F(x)= == [p(#),... x and G(æ) == {p(c,,...,, Iz-1, X;< <
As a direct application of the marginal algorithm described in Sec. 3.1 for every val(X), computing the 2/) marginals (F(x), G(=)) takes O(D-(pl) time. However, the linear dependency on 1 would render compression and decompression extremely time-consuming.
We can significantly accelerate the en- and decoding times if the PC is structured-decoopssabbe (see Definition 3). To this end, we introduce an algorithm that computes F(x) and G(z)) in (log(D). (p]) time (instead of D(D-Ipl) given a smooth and dew.uurdddddecoossbllllee PC p. For ease of presentation, we only discuss how to compute F(x) the values G(x) can be computed analogously
Before proceeding with formal argument, we give a high-level explanation of the accelcration. In practice, we only need to evaluate small fraction of PC units compute each of its D marginals.
"The only difference hetween the computation of the ith term of F(x) and the ith term of ((x) is in the value assigned to the inputs for variable X, (i.c., probabilities pm (X, =x)) vs. pa (X, <.))).
5

---

Published as a conference paper at ICLR 2022
Algorithm 1 Compute F(x) (see Alg. 3 for details)
I: Input: A smooth and www.utuurdd-ccoopssateee PC p. variable instantiation æ
2: Output: Fr. Fz((z) = {p(zz..... ... R=)
3: Initialize: The probability p(n) of every unit n is initially set to 1
4:
Vi, eval: t- the set of PC units n that need to be evaluated in the ith iteration
for i= to do
6: Evaluate PC units in eval, in bottom-up manner and compute p(z
This is different from regular neural networks and the key to speeding up the computation of (a)). In contrast to neural networks, changing the input only slightly will leave most activations unchanged for -edeoooodddecompoabbbll PCs. We make use of this property by observing that adjacent marginals in F(x=) only differ in one variable - the ith term only adds evidence æ;; compared to the (i - 1)th term. We will show that such similarities between the marginal queries will lead to an algorithm that guarantees (log D)- (pl) overall time complexity.
An informal version of the proposed algorithm shown in Alg. In the main loop (lines 5-6), the D terms in F(x) are computed one-by-one. Although the D iterations seem to suggest that the algorithm scales linearly with D, we highlight that each iteration on average re-evaluates only log(D) Log( of the PC. Therefore, the computation cost of Alg. I scales logarithmically w.r.t. D. The set of PC units need to be re-evaluated, eval,, is identified in line 4, and lines evaluates these units in feedforward manner to compute the target probability (i.e., p(x1...... 2:)).
Specifically, to minimize computation cost, at iteration i, we want to select a set of PC units oval; that (i) guarantees the correctness of the target marginal, and (ii) contains the minimum number of units. We achieve this by recognizing three types of PC units that can be safely eliminated for evaluation. Take the PC shown in Fig. 2 as an example. Suppose
want to compute the third term in F(xr) (i.c.. p(z1, Z2, æ3)). First, all PC units in Group #1 do not need to be re-evaluated since their value only depends on Ii and 12 and hence remains unchanged. Next, PC units in Group #2 evaluate 1. This can be justified from the two following facts: (i) input units correspond to X4 have probability 1 while computing p(11, F2, 23); (ii) for any sum or product unit, if all its children have probability 1, it also has probability 1 following Eq. (2) Finally, although the activations of the PC units in Group #3 will change when computing p 22 43), we do not need to explicitly evaluate these units - the root node's probability can be equivalently computed using the weighted mixture of probabilities of units in eval,. The correctness of this simplification step is justified in Appx. A.1
The idea of partially evaluating PC originates from the Partial Propagation (PP) algorithm (Butz ctt al., 2018). However, PP can only prune away units in Group #2. Thanks to the specific structure of the marginal queries, we are able to also prune away units in Groups #1 and #3.
Finally, we provide additional technical details to rigorously state the complexity of Alg. First, we need the variables X to have specific order determined by the PC p. To reflect this change, generalize F(z) to (x) := { Iz, ) where π defines some variable order over X, i.e., the ith variable in the order defined by ι is X n.. Next, we give a technical assumption and then formally justify the correctness and efficiency of Alg. 1 when using an optimal variable order x².
Definition 4. For smooth menctured-decomposaae nodes(p, Φ) as the set of PC units in p whose scope is ø. We say p is balanced if for every scope d' that is equal to the scope of any unit n in p, we have |nodes(p, g') O(pl/D).
PC p over D variables, for any scope Φi denote
Theorem 1. For a smooth seweeturedddccoopsseee ar there exists a variable order n²", s.I. Alg. 3 correctly computes Fz. (x) in (log(D) (pl) time.
balanced PC over D variables X and a sample
Proof. First note that Alg. iss a detailed version of Alg. I The high-level idea of the proof is to first show how to compute the optimal variable order 'T" for any smooth and
PC. Next, we justify the correctness of Alg. 3 byy showing (i) we only need to evaluate units that satisfy the criterion in line of 3 and (ii) weighing the PC units with the top-down probabilities (Appx. T) always give the correct result. Finally, we use induction (on D) to demonstrate Alg. computes Ologg( D) Ipl) PC units in total if xt is used. See Appx. A.2 for further details.
While Def. 4 may seem restrictive at first glance, we highlight that most existing PC structures such as EiNets (Peharz et al. 2020a), RAT-SPNs (Peharz et al. 2020b) and HCLT' (Sec. 4.1 are balanced
SSee Appx. A.1 for the formal algorithm and its detailed elaboration.

---

Published as a conference paper at ICLR 2022
Table 2: Efficiency and optimality of the (de)compressor. The compression (resp. decompression) time are the total computation time used to encode (resp. decode) all 10,000 MNIST test samples on single TITAN RTX GPU. The proposed (de)compressor for pruucureed-dcomposatee faster than IDF and BitSwap and only leads to negligible increase in the codeword bpd compared to the theoretical bpd. HCLT is a PC model that will be introduced in [Sec. 4.1,
PCs is 5-40x
Method
parameters
Theoretical bpd Codeword bpd Comp. time (8) Decomp. time (s)
PC (HCLT, M = 16)
3.3M
1.26
1.30
9
44
PC (HCLT. 24)
5.IM
1.22
1.26
15
86
PC (HCLT, M 32)
7.0M
1.20
1.24
26
142
IDF
24.1M
1.90
1.96
288
592
BitSwap
2.8M
1.27
1.31
578
326
(see Appx. A.3 for justifications). Once all marginal probabílities are calculated, samples æ can be en- or decoded autoregressively with any streaming codes in time (log D)- Dplp)) Specifically, our implementation adopted the widely used streaming code rANS (Duda 2013)
3.3 EMPIRICAL EVALUATION
We compare the proposed algorithm with competitive
(IDF by Hoogeboom et al. (2019)) and VAE-based (BitSwap by Kingma et al. (2019) neural compression algorithms using the MNIST dataset. We first evaluate bitrates. As shown in Table 2 the PC (de)compressor achieved compression rates close to its theoretical rate estimate codeword bpds only have ~0.04 loss w.r.t. the corresponding theoretical bpds. We note that PC and IDF have an additional advantage: their reported bitrates were achieved while compressing one sample a time; however, BitSwap needs to compress sequences of 100 samples to achieve 1.31 codeword bpd (Kingma et al. 2019
Next, focus efficiency. While achieving better codeword bpd (i.e., 1.30) compared to IDF and BitSwap, a relatively small PC model (i.c., HCLT, M = 16) encodes (resp. decodes) images 30x (resp. 10x) faster than both baselines." Furthermore, bigger PC model (M = 32) with 7M parameters achieved codeword bpd 1.24, and is still 5x faster than BitSwap and IDF. Note that at the cost of increasing the bitrate, one can significantly improve the en- and decoding efficiency, For example, by using a small VAE model. Townsend et al. (2019) managed to compress and decompress 10,000 binarized MNIST samples in 3.26s and 2.82s, respectively.
Related work As hinted by Sec. 2 we seek to directly learn probability distributions pl (X that are expressive and support tractable (de)compression. In contrast, existing Flow-based (van den Berg et 2020 Zhang et al. 202Tb) and VAF-based (Townsend et al., 2019 Kingma et al.] 2019 et al. 2019) neural lossless compression algorithms are based on an orthogonal idea: they adopt simple (oftentimes fully factorized) distributions over a latent space to ensure the tractability
encoding and decoding latent codes 2, and learn expressive neural networks that "transmit" probability mass from Z to the feature space X to compress samples æ indirectly. We note that both ideas can be integrated naturally: the simple latent distributions used by existing neural compression algorithms can be replaced by expressive PC models. We will further explore this idea in Sec. 5)
4 SCALING UP LEARNING AND INFERENCE OF PCs
Being equipped with an efficient (de)compressor, our next goal is to learn PC models that achieve good generative performance on various datasets. Although recent breakthroughs have led to PCs that can generate CelebA and SVHN images (Peharz et al.) 2020a). PCs have not been shown have competitive (normalized) likelihoods on image datasets, which directly influence compression rates. In this section, we show that Hidden Chow-Liu Trees (HCLTs) (Liu Van den Broeck] [02T)) PC model initially proposed for simple density estimation tasks containing binary features, can be scaled up to achieve state-of-the-ar performance on various image datasets. the following, we first introduce HCLTs and demonstrate how to scale up their learning and inference (for compression) in Sec. 4.1 before providing empirical evidence in Sec. 4.2
4.1 HIDDEN CHOW-LIU TREES
Hidden Chow- Trees (HCLT') are smooth and structured- deciuueeddddecoopsbabllle PCs that combine the ability of Chow-Liu Trees (CLTs) (Chow& & Liu 1968) capture feature correlations and the extra
6HCTT will be introduced in Sec. 4.1 all algorithms use CPU implementation of rANS as codec. See Appx. for more details about the experiments.
7

---

Published as a conference paper at ICLR 2022
(b)
(c)
(d)
Replace X, by 7,
Atlach X back to 7,
Equivalent
Figure 3: An example of constructing a HCLT PC given a dataset D with features. (a): Construct the Chow-Liu Tree over variables ,,,..., X4 using D. (b): Replace every variable X, by its corresponding latent variable Z, (c): Attach all X; back to their respective latent variables Zμ (d): This PGM representation of HCLT is compiled into equivalent PC.
Table 3: Compression performance of PCs MNIST, NNST,, and EMNIST in bits-per- dimension (bpd). For all neural compression algorithms, numbers in parentheses represent the corresponding theoretical bpd (i.e., models' test-set likelihood in bpd).
Dataset
HCLT (ours)
IDF
BitSwap
BB-ANS
JPEG2000
WebP
McBits
MNIST
1.24 (1.20)
1.96 (1.90)
1.31 (1.27)
1.42 (1.39)
3.37
2.09
(1.98)
MNSST
3.37 (3.34)
3.50 (3.47)
3.35 (3.28)
3.69 (3.66)
3.93
4.62
(3.72)
EMNIST (I (Letter)
1.84 (1.80)
2.02 (1.95)
1.90 (1.84)
2.29 (2.26)
3.62
3.31
(3.12)
EMNIST (ByClass)
1.89 (1.85)
2.04 (1.98)
1.91 (1.87)
2.24 (2.23)
3.61
3.34
(3.14)
expressive power provided by latent variable models. Every HCLT can be equivalently represented as a Probabilistic Graphical Model (PGM) (Koller & Friedman 2009) with latent variables. Specifically, Fig. 3[a)-()) demonstrate how to construct the PGM representation of an example HCLT. Given
dataset D containing 4 features X= 1 X4, we first learn a CLT w.r.t X (Fig. 3 ()). To improve expressiveness, latent variables are added to the CLT by the two following steps: (i) replace observed
variables X; by their corresponding latent variables Zj. which are defined to be categorical variables with M (a hyperparameter) categories (Fg.. b)): (ii) connect observed variables X; with the corresponding latent variables Z, by directed edges Z; X2 This leads to the PGM representation of the HCLT shown in Fig. 3c).. Finally, we left with generating PC that represents an equivalent distribution w.r.f. the PGM in Fig. 3(c). which is detailed in Appx. B.2 Fig. 3/d) illustrates an HCLT
that is equivalent to the PGM shown in Fig. 3(c) (with M 22)).
Recent advances in scaling up learning and inference of PCs largely rely on the regularity of the PC architectures they used (Peharz et al. 2020aa b) the layout of the PCs can be easily vectorized, allowing them to use well-developed deep learning packages such as PyTorch (Paszke et al. (019). However, due to the irregular structure of learned CLTs, HCLTs cannot be easily vectorized. To overcome this problem, we implemented customized kernels for parameter learning and marginal query computation (i.e., Algg,
(Ale.,All.. 3) based on Juice.jl (Dang et al. 202T), an open-source Julia package. The kernels automatically segment PC units into layers such that the computation in every layer can be fully parallelized. As a result, we can train PCs with millions of parameters in less than an hour and en- or decode samples very efficiently. Implementation details can be found in Appx. B.3
Related work Finding good PC architectures has been a central topic in the literature CChoi et al., 2020). A recent trend for learning smooth and models with pre-defined architecture, which is mainly determined by the variable ordering strategies. For example, RAT-SPNs (Peharz et al. (2200b) and EiNets (Peharz et al., 2020a) use random variable orders, Gens & Domingos (2013) proposes an effective variable ordering for image data, and other works propose dete-dependent orderings based certain information criterion (Rooshenas & Lowd 2014) or clustering algorithms (Gens & Domingos) 2013). Alternatively, researchers have focused on methods that iteratively grow PC structures to better fit the data (Dang et al. 2020 Liang et al.)
deeeuured>deccomosbbbllee PCs is to construct large
2017].
4.2 EMPIRICAL. EVALUATION
Bringing together expressive PCs (i.e., HCLTs) and our (de)compressor, we proceed to evaluate the compression performance of the proposed PC-based algorithm. We compare with 5 competitive lossless compression algorithm: JPEG2000 (Christopoulos et al. 2000): WebP; IDF (Hoogeboom et al. 2019), ) a Flow- bwsdd lossless compression algorithm; BitSwap (Kingma et al. 2019), BB-ANS (Townsend et al. 2018), and McBits (Ruan et al. (20II, three VAE-based lossless compression meth- ods. All methods were tested on 4 datasets, which include MNIST (Deng 2012), MNSSI
8

---

Published as a conference paper at ICLR 2022
Frow lyyer Paoo
Fow layer
Sallt prior
Squies Luezz
Flow loyer
Flow layer
Squeeze
Fi Flow layer
pirior
Level Figure 4: Using PCs as prior distributions of the IDF model (Hoogeboom et 2019). to represent the l sets of latent variables {zi
pla)
Level
Level
PCs are used
(Xiao et al., 2017), and two splits of EMNIST (Cohen et al. 2017). As shown Table 3 the proposed method out- performed all 5 baselines in 3 out of 4 datasets. On FashionMNIST, where the proposed approach did not achieve a state-of-the-art result, it was only 0.02 bpd worse than BitSwap.
5 PCS AS EXPRESSIVE PRIOR DISTRIBUTIONS OF FLOW MODELS
As hinted by previous sections, PCs can be natu- rally integrated with existing neural compression algorithms: the simple latent variable distributions used by Flow- and VAE-based lossless compres- sion methods can be replaced by more expressive distributions represented by PCs. In this section,
Table 4: Theoretical bpd of Flow-based gener- ative models three natural image datasets.
Model CIFARIO
ImageNet32 ImageNet64
RealNVP
3.49
4.28
3,98
Glow
3.35
4.09
3.81
IDF
3.32
4.15
3,90
we take IDF (Hoogeboom et al. 2019). a Flow- based lossless compression model, as example to demonstrate the effectiveness of such model integration. IDF was chosen because its authors provided open-source implementation GitHub. In theory, PC can be integrated with any VAE- and Flow-based model.
IDF++
3.24
4.10
3,81
PC+IDF
3.28
3,99
3.71
The integrated model is illustrated in Fig. Following Hoogeboom et al. (2019). IDF model contains & levels. Each level contains a squeeze layer (Dinh et al. (016)) followed by several integer flow layers and a prior layer. Each level outputs a of latent variables 2;, which are originally defined as a set of mutually independent discretized logistic variables (Kingma et al. 2016). Instead, we propose model every set of latent variables 2; with PC p(z.). Specifically, we adopted the EiNet codebase (Peharz et al.] (222a)) and used a PC structure similar to the one proposed by Gens) Domingos (2013). We adopted the discretized logistic distribution for all leaf units in the PCs. Given a sample æ, the log-likelihood of the model is the sum of the k PCs' output log-likelihood: log 1(z) Σ p(z; æ). Since both IDF and the PC models fully differentiable, the PC+IDF model can be trained end-to-end via gradient descent. Details regarding model architecture and parameter learning are provided in Appx. B.5
We proceed to evaluate the generative performance of the proposed PC+IDF model on 3 natural image datasets: CIFARIO 10, ImageNet32, and ImageNet64. Results are shown in Table First, compared to baselines (i.e., IDF, IDF++ (van den Berg et al. 2020)). Glow (Kingma & Dhariwal 2018). and RealNVP (Dinh al. 2. PC+IDF achieved the best bpd on ImageNet32 and ImageNet64. Next, PC+IDF improved over its base model IDF by 0.04, 0.16, and 0.19 bpd on three datasets, respectively. This shows the benefit of integrating PCs with IDFs. Although not tested in our experiments, we conjecture that the performance could be further improved by integrating PCs with better Flow models (e.g., IDF++). Concurrently, Zhang et al. (2021a) proposes an autoregressive model-based compressor NeLLoC, which achieved SoTA results natural image datasets including CIFAR- 10.
Compression and decompression with the PC+IDF model can be done casily: we can adopt the high- level compression algorithm of IDF and replace the parts of en- or decoding latent variables with the proposed PC (de)compressor. Improving the compression performance of these hybrid models is left for future work. Note that Thm. only applies to the PC component, and the compression time still depends linearly on the size of the neural network.
CONCLUSIONS
This paper proposes to use Probabilistic Circuits (PCs) for lossless compression. We develop a eeoortiially-grrouneed grounded (de)compresiion algorithm that efficiently encodes and decodes close to the model's 's theoretical rate estimate. Our work provides evidence that more "niche" generative model architectures such PCs can make valuable contributions neural compression.

---

Published as a conference paper at ICLR 2022
Acknowledgements Guy Van den Broeck acknowledges funding by NSF grants #IIS- 194364,, 118S-194444, #CCF-1837129, DARPA grant #N66001-17-224033. and a Sloan Fellowship. Stephan Mandt acknowledges funding by NSF grants #IIS- 201-42044488 and MIIS-2007719, We thank Yibo Yang for feedback on the manuscript's final version.
Ethics and Reproducibility Statement We are not aware of any ethical concerns of our re- search. To facilitate reproducibilityy, we have uploaded our code to the following GitHub repo: http://iiieii//reeeeeeeeeeeeeeee
j1 In addition, we have provided de- tailed algorithm tables aables|Ag... 2 and for all proposed algorithms, and elaborated each step in detail in the main text (Sec. 3). Formal proofs of all theorems, and details of all experiments (e.g., hardware specifications, hyperparameters) are provided in the appendix.
/tttps:/githhu
REFERENCES
Cory Butz, Jhonatan S Oliveira, André E Santos, André L Teixeira, Pascal Poupart, and Agastya Kalra. An empirical study of methods for spn learning and inference. In International Conference on Probabilistic Graphical Models, pp. 49-60. PMLR, 2018.
YooJung Choi, Antonio Vergari, and Guy Van den Broeck. Probabilistic circuits: A unifying framework for tractable probabilistic models. 2020.
YooJung Choi, Meihua Dang, and Guy Van den Broeck. Group faimess by probabilistic modeling with latent fair decisions. In Proceedings of the 35th AAAI Conference on Artificial Intelligence, Feb 2021.
CKCN Chow and Cong Liu. Approximating discrete probability distributions with dependence trees. IEEE transactions Information Theory, 14(3):462-44) 467, 1968.
Charilaos Christopoulos, Athanassios Skodras, and Touradj Ebrahimi. The jpeg2000 still image coding system: overview. IEEE transactions consumer electronics, 46(4): 100--11777 2000.
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and Andre Van Schaik. Emnist: Extending mnist to handwritten letters. In 2017 International Joint Conference Neural Networks (IJCNN), pp. 2921-2926. IEEE, 2017.
Meihua Dang, Antonio Vergari, and Guy Broeck. Strudel: Learning structured dructturedddccompssabeee probabilistic circuits. International Conference on Probabilistic Graphical Models. pp. 137-148 PMLR, 2020.
Meihua Dang, Pasha Khosravi, Yitao Liang, Antonio Vergari, and Guy Van den Broeck. Juice: A julia package for logic and probabilistic circuits. In Proceedings of the 35th AAAI Conference on Artificial Intelligence (Demo Track), 2021.
Li Deng. The mnist database of handwritten digit images for machine learning research. IEEE Signal Processing Magazine, 29(6): 141-144 2012.
Laurent Dinh, David Krueger, and Yoshua Bengio. Nice: Non-linear independent components estimation. arXiv preprint arXiv::410.88 16, 2014.
Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio. Density estimation using real nvp. In International Conference on Learning Representations, 2016.
Jarek Duda. Asymmetric numeral systems: entropy coding combining speed of huffman coding with compression rate of arithmetic coding. arXiv preprint arXiv:131 1.2540, 2013.
Robert Gens and Pedro Domingos. Learning the structure of sum num-product networks. In International conference on machine learning, pp. 873-880. PMLR, 2013.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farke Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. Advances neural information processing systems, 27, 2014.
10

---

Published as a conference paper at ICLR 2022
Geoffrey E Hinton and Drew Van Camp. Keeping the neural networks simple by minimizing the description length the weights. In Proceedings of the sixth annual conference on Computational learning theory, pp. 5-13, 1993.
Jonathan Ho, Evan Lohn, and Pieter Abbeel. Compression with flows via local bits-back coding, In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 1879-3888, 2019.
Emiel Hoogeboom, Jorn Peters, Rianne van den Berg, and Max Welling, Integer discrete flows and lossless compression. Advances in Neural Information Processing Systems, 32:12134-12144 2019.
David A Huffman. A method for the construction of minimum-redundanee codes. Proceedings of the IRE, 40(9): 1098-1101, 1952.
Diederik P Kingma and Prafulla Dhariwal. Glow: generative flow with invertible 1x I convolutions. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 10236-10245, 2018
Diederik P Kingma and Max Welling. vrXiv:1312.66 14, 2013.
Auto-encoding variational
bayes. arXiv preprint
Diederik P Kingma, Tim Salimans, Rafal Jozefowicz, Xi Chen, Ilya Sutskever, and Max Welling, Improved variational inference with inverse autoregressive flow. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 4743 4751, 2016.
Friso Kingma, Pieter Abbeel, and Jonathan Ho. Bit-swap: Recursive bits-back coding for lossless compression with hierarchical latent variables. In International Conference on Machine Learning, pp. 3408-3417. PMLR, 2019.
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), pp. 1-10, 2014.
Daphne Koller and Nir Friedman. Probubilistic graphical models: principles and techniques. MIT press, 2009.
Yann Lecun, Sumit Chopra, Raia Hadsell, Marc Aurelio Ranzato, and Fu Jie Huang. A tutorial on energy-based learning. Predicting structured data, 2006.
Yitao Liang, Jessa Bekker, and Guy Van den Broeck. Learning the structure of probabilistic sentential decision diagrams. In Proceedings of the 33rd Conference on Uncertainty in Artificial Intelligence (UAI), 2017.
Anji Liu and Guy Van den Broeck. Tractable regularization of probabilistic circuits. Advances in Neural Information Processing Systems 35 (NeurIPS), dec 2021.
Fabian Mentzer, Eirikur Agustsson, Michael Tschannen, Radu Timofte, and Luc Van Gool. Practical full resolution learned lossless image compression. In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pp. 10629- 10638, 2019.
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, al. Pytorch: an imperative style, high- performance deep learning library. In Proceedings of the 33rd International Conference on Neural Information Processing Systems, pp. 8026-8037, 2019.
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 International Conference on Machine Learning, pp. 7563-7574. PMLR, 2020a.
Robert Peharz, Antonio Vergari, Karl Stelzner, Alejandro Molina, Xiaoting Shao, Martin Trapp, Kristian Kersting, and Zoubin Ghahramani. Random product networks: A simple and effective approach to probabilistic deep learning. In Uncertainty Artificial Intelligence, pp. 334-344. PMLR, 2020b.
11

---

Published as a conference paper at ICLR 2022
Hoifung Poon and Pedro Domingos. Sum-produce networks: new deep architecture. In 2011 IEEE International Conference on Computer Vision Workshops (ICCV Workshops), pp. 689-690. IEEE, 2011.
Marc' Aurelio Ranzato, Y-Lan Boureau, Sumit Chopra, and Yann LeCun. A unified energy-based framework for unsupervised learning. In Artificial Intelligence and Statistics, pp. 371-379. PMLR, 2007.
Jorma Rissanen. Generalized kraft inequality and arithmetic coding. IBM Journal of research and development, (0(3):198-203. 1976.
Amirmohammad Rooshenas and Daniel Lowd. Learning sum-product networks with direct and indirect variable interactions. In International Conference on Machine Learning, pp. 710-718.
PMLR, 2014.
Yangjun Ruan, Karen Ullrich, Daniel Severo, James Townsend, Ashish Khisti, Arnaud Doucet, Alireza Makhzani, and Chris Maddison. Improving lossless compression rates via monte carlo bits-back coding. In International Conference on Machine Learning, 2021.
Claude Elwood Shannon. mathematical theory of communication. The Bell system technical journal, 27(3):379-4233 1948.
Yujia Shen, Arthur Choi, and Adnan Darwiche. Tractable operations for arithmetic circuits of probabilistic models. In Proceedings of the 30th International Conference on Neural Information Processing Systems, pp. 3943-3951. Citeseer, 2016.
Andy Shih, Guy Van den Broeck, Paul Beame, and Antoine Amarilli. Smoothing structured de- composable circuits. Advances in Neural Information Processing Systems, 22:11416-1426, 2019.
James Townsend, Thomas Bird, and David Barber. Practical lossless compression with latent variables using bits back coding. In International Conference on Learning Representations, 2018.
James Townsend, Thomas Bird, Julius Kunze, and David Barber. HiLLoC: lossless image com-
pression with hierarchical latent variable models. In International Conference on Learning Representations, 2019.
Arash Vahdat and Jan Kautz. Nvae: deep hierarchical variational autoencoder. arXiv preprint arXiv:2007.03899, 2020.
Rianne van den Berg. Alexey A Gritsenko. Mostafa Dehghani, Casper Kaae Sønderby, and Tim Salimans. Idf++: Analyzing and improving integer discrete flows for lossless compression. In International Conference Learning Representations, 2020.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07747, 2017.
Yibo Yang, Stephan Mandt, and Lucas Theis. An introduction to neural data compression. arXiv preprint arXiv:2202.066: 06533, 2022.
Mingtian Zhang, Andi Zhang, and Steven McDonagh. On the out-of-distribution generalization of probabilistic image modelling. arXiv preprint 2tti::22000026699 2021a
Shifeng Zhang, Chen Zhang, Ning Kang, and Zhenguo Li. iVPF: Numerical invertible volume preserving flow for efficient lossless compression. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 620-629, 2021b.
Zhilin Zheng and Li Sun. Disentangling latent space for vae by label relevant//rrelevan dimensions. In Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition, pp. 12192-12201, 2019.
12

---

Published as a conference paper at ICLR 2022
Supplementary Material
A ALGORITHM DETAILS AND PROOFS
This section provides additional details about the algorithm used to compute the conditional probabil- ities (a) (i.e. Alg. 1 and the full proof of the theorems stated in the main paper.
A.1 DETAILS OF ALG.
This section provides additional technical details of Alg. Specifically, we demonstrate (i) how to select the set of PC units eval, (cf. Alg. line 5) and (ii) how to compute p(.1...., 224)
weighted mixture of P. (cf. Alg. T Ilin 7). Using the example in Inni.g 5] we aim to provide an intuitive illustration both problems. As extension to Alg. rigorous and executable pseudocode for the proposed algorithm can be found in Alg. 2] and 3
The key to speeding up the naive marginalization algorithm is the observation that we only need to evaluate a small fraction of PC units to compute each of the D marginals in Fx Fx()). Suppose we want to compute (z) given the pructured-decomppe
PC shown in Fig. S(a,, where D @, and @ denote sum, product, and input units, respectively. Model parameters are omitted for simplicity. Consider using the variable order T= (X,, X2, X3) Fig. 5(b)). We ask the following question: what is the minimum set of PC units that need to be eva walluted in order to compute p( (X1 =x1) (the first term in Fx (x)))? First, every PC unit with scope {X1} } (i.e., the two nodes colored blue) has to be evaluated. Next, every PC unit that is not an ancestor of the two blue units (i.e.. "non-ancestor units" in Fig. S(b)) must have probability since (i) leaf units correspond to X2 and X3 have probability 1 while computing pXX1 =21), ), and (ii) for any sum product unit, if all its children have probability 1, it also has probability 1 following Eq. (2) Therefore, we do not need to evaluate these non- non-ancestor units. Another way to identify these non-ancestor units is by inspecting their variable scopes - if the variable scope of PC unit n does not contain X1, it must has probability while computing p(X, -1). Finally, following all ancestors of the two blue units (i.e., "ancestor units" in Fig. 5))),, we can compute the probability of the root unit, which is the target quantity =(X)= At a first glance, this seems to suggest that we need evaluate these ancestor units explicitly. Fortunately, as we will proceed to show, the root unit's probability can be equivalently computed using the blue units' probabilities weighted by a set of cached top-down probabilities.
For ease of presentation, denote the two blue input units as n2 and n22 respectively. A key observation that the probability of every ancestor unit of (m, n2) (including the root unit) can be represented the probabilities assigned to ni and 122, respectively. The reason is that for each decomposable product node m, only distributions defined on disjoint variables shall be multiplied. Since n1 and ne have the same variable scope, their distributions will not be multiplied by any product node. Following the above intuition, the top-down probability Paowa (n) of PC unit n is designed to represent the "weight" of w.r.t. the probability of the root unit. Formally, Paown (n) is defined as the sum of the probabilities of every path from n to the root unit n,, where the probability of a path is the product of all edge parameters traversed by it. Back to our example, using the top-down probabilities, we can compute p(X) = Ei= Pdown (n+) Pn, (I1) without explicitly evaluating the ancestors of n2 and n22, The quantity Pelonn (n) of all PC units n can be computed by Alg. in ((p)) time. Specifically, the algorithm performs a top-down traversal over all PC units n. and updates the top-down probabilities of their children in()) along the process.
as weighted mixture over Pr; (ar) and Png (ar), (z)(
Therefore, we only need to compute the two PC units with scope {X1} in order to calculate p(X] = a.). Next, when computing the second term p( X; = 21, X² = x22), as illustrated in Fig. 5(b), we can reuse the evaluated probabilities of n1 and n2, and similarly only need to evaluate the PC units with scope {X2), Xx), or {X1, X2, X2} (i.e., nodes colored purple). The same scheme can be used when computing the third term, and we only evaluate PC units with scope {Xa}. {X2, or (X,, Xz) (i.e., all red nodes). As result, we only evaluate 20 PC units in total, compared to 3 (p) = 39 units required by the naive approach.
This procedure is formalized in Alg. 3) which adds additional technical details compared to Alg. In the main loop (lines 5-9), the D terms in Fz (x) are computed one-by-one. While computing each term, we first find the PC units that need to be evaluated (line O computing their probabilities
13

---

Published as a conference paper at ICLR 2022
(b) Variable onder. X + >x > X5
(c) Variable onder. X3 3x,
Ancestr unis
Non--nncstor unis
X1
OOOO
N Na-raa) N Ny Xa-ra))
M Xy oa J Mymas X2
X X X
Need to evaluate + +9++9= PC units total.
Need evaluate 2 6 6-5 13 PC units in total.
Figure 5: Good variable orders lead to more efficient computation of F* (ar). Consider the PC p shown in (a). (b): If variable order X1, X2, X3 is used, need to evaluate 20 PC units in total. (c):
The optimal variable order X3, X2, X1 allows us to compute Fa (a:) by only evaluating 13 PC units.
Algorithm 2 PC Top-down Probabilities
1: Input: A smooth and structured- desfuuurddddecoopsabbbbbe PC
2: Output: The top-down probabilitics Pdown (n) of all PC units n
For every PC unit in p. initialize Poown (n) <-
foreach unit n traversed in preorder (parent before children) do
5: if n the root node p then Paown (n) +-
6: clif
unit then foreach E in(n) do Paown (c) Pdown (c) Pdown (n)) On.c
7: elif is product unit then foreach E in(n1) do Påown (c) Pdown (c) Pdlown (n)
in bottom-up manner (line 7), additionally the pre-computed top-down probabilities to obtain the target marginal probability (lines 8-9).
The previous example demonstrates that even without careful choice of variable order, we can significantly lower the computation cost by only evaluating the necessary PC units. We now show that with an optimal choice of variable order (denoted iT"), the cost can be further reduced. Consider using order π = (X3, X2, X1), as shown in Fig. 5/c). we only need to evaluate 2+6+5= 13 PC units in total when running Alg. This optimal variable order is the key to guaranteeing Olog( D)- lp]) computation time. In the following, we first give technical assumption and then proceed to justify the correctness and efficiency Alg. when using the optimal variable order π²
A.2 PROOF OF THROREM
As hinted by the proof sketch given in the main text, this proof consists of three main parts ii) construction of the optimal variable order x¹ given a smooth and peretureddeeoompssseee PC, (ii) justify the correctness of [lg. 3] and (iii) prove that F.. (xx) can be computed by evaluating more than Ologg( (K) (pl) PC units (i.e., analyze the time complexity of Alg. 3
Construction of optimal variable order smooth and structured-decomppssas children. Fig. 6 illustrates this transformation on any product node with than two children. Note that this operation will not change the number of parameters in a PC, and will only incur at most 2-(p) edges.
For ease of illustration, we first transform the original PC into an equivalent PC where every product node has two
We are now ready to define the variable tree (vtree) (Kisa et al. 2014) of a smooth and structured- decomposable PC. Specifically, a viree is binary tree structure whose leaf nodes are labeled with a PC's input features/variable X (every leaf node is labeled with one variable). A PC conforms to vtree for every product unit n, there is corresponding vtree node v such that children of split the variable scope ((n) in the same way as the children of the vtree node v. According to its definition, every smooth and structured dew.ccuredddeoomoobbbblll PC whose product units all have two children must conform to vtree (Kisa et al. 20144). For example, the PC shown in Fig. 7(a) conforms to the vtree illustrated in Fig. 7). Similar to PCs, we define the scope d(v) of vtree node as the set of all descendent leaf variables of u.
We say that a unit n in a smooth and sencturedddecomposaal PC conforms to a node u in the PC's corresponding vtree if their scopes are identical. For ease of presentation, define sp(p, v) the set of PC units that conform to vtree node v. Additionally, we define &aum (p, v) and Pproa (p, v) as the set of sum and product units in sep, v), respectively.
14

---

Published as a conference paper at ICLR 2022
Algorithm 3 Compute (x)
I: Input: A smooth and struetured- PC p, variable order म, variable instantiation
2: Output: (x) = {p(Za)..... f=.)K=
3: Initialize: The probability p(n) of every unit is initially set to
4: Pdown f- the top-down probability of every PC unitm (i.e.
5: for i= D do # Compute the ith term in (z)x::
6: eval; <- the set of PC units n. with scopes ((r)) that satisfy at least one of the following conditions:
(i) (xx;)
(ii) r a sum unit and at least one child c n needs evaluation, i... CE eval.; (iii) is product unit and XT, Ed(n) and f in(n) such that
7:
Evaluate PC units in eval; in bottom-up manner to compute {px (a) n E
8:
head, + the set of PC units in eval, such that none of their parents are in eval.
9:
p( Ux. 4 Lnchond, Pdown (n) Pr (a)
Next, we define an operation that changes vtree into an ordered viree, where for each inner node its left child has more descendent leaf nodes than its right child. SeelFig. 7c-d) as an example. The vtree in Fig. 7(b) is transformed into an ordered vtree illustrated in Fig. 7c); the corresponding PC (ig.. a)) converted into an ordered PC (Fig. d()). This transformation can performed by all PCs.
smooth and stractured-decompsalll
We are ready to define the optimal variable order. For a pair of ordered PC and ordered vtree, the optimal variable order n² is defined as the order the leaf vtree nodes (each corresponds to variable) are accessed following an inorder traverse of the vtree (left child accessed before right child).
Assume we have access to a smooth, structured-decomppsale and ordered PC p and its corresponding vtree. Recall from the above construction, the optimal variable order x is the order following an inorder traverse of the vtree.
Correctness of Algorithm] 3
We show that is sufficient to only evaluate the of PC units stated in line 6 of Alg. 3
Using our new definition of vtrees, we state line 6 in the following equivalent way. At iteration i (i.e., we want compute the ith term in Fx (z)) p(æx...... )), we need to evaluate all PC units that conform to any vtree node in the set Tp.s. Here Tp. is defined as the set of vtree nodes that satisfy the following condition: Xs, E ((v) and there does not exist a child of such that {Xa,, )/=1 E Φ(c). For ease of presentation, we refer to evaluate PC units (p,, v) when we say "evaluate a vtree node v".
First, we don't need to evaluate vtree units where X=, & ((v) because the probability of these PC units will be identical to that at iteration - (i.e., when computing p(zx)...... )),-))). Therefore, we only need cache these probabilities computed in previous iterations.
Second, we don't 't need to evaluate vtree units where least one of its children satisfy (X+, Viz <(c) because
obtain the target marginal probability p(Zmps-.-., Fxx;) following lines 7-9 of We proceed to show how this is done in the following.
Alg. 3.
Denote the "highest" in T as Ur (i.e., the parent of or,; is not in T, According to the variable order x", Drg uniquely exist for any i E [D]. According to Alg. 2 the top-down probabilities of PC units defined as follows
Poown (n,) 1, where n, is the PC's root unit.
For any product unit Paown (n) E Emepar(m) Pdown (m) mm where par(n) is the set of parent (sum) units of
For any sum unit n. Peoon (n) = Emepar(n) (m), where par(n) is the set of parent (product)
units of n.
We now prove that
Σ
Pdown (n)) Pu
n (p.0)
holds when Ur.i-
15

---

Published as a conference paper at ICLR 2022
+
71
f2
Tu3
1/2
Figure 6: Convert product unit with children into an equivalent PC where every product node has two children.
(4)
(b)
(c)
(d)
+
X1
X1
X X;
Xi
Xi
X2
X3
X2
X3
X X Xs X3
X
X
Xs X5
Figure 7: (a-b): An example structuredddeccoppoablee PC and a corresponding viree. (c-d): Convert- ing (b) into an ordered vtree. (d) The converted ordered PC that is equivalent (a).
Base case: If is the vtree node correspond ny., then &Pum (p,v) (n,} and it is easy to verify that
p(z........ In,)) Pdown (ny) Pry (x)
Pdown (n) (x)
REp
Inductive case: Suppose is an ancestor of By and the parent vtree node up of satisfy Eq. (3)
We have
p Fat)
Pdown (m) Pm (x:)
Σ p (p.up) nEin(m)
Σ
Pdown (mo Omn Pro (x)(x)
Σ
Σ
Pdown (m) Om, Pe Pn(x))
nEvppred (p.oy) mEpar(n)
Petown (11)
Σ
Pdoon (n) Pr
nEsprodd (p.ug)
(b)
Σ
Σ
Pdown (n) po(x)
nē up of (o:oEinn))) (2,))
Σ
Σ
Pdown (n) (x())
oE (p.n) nEpar(()
Pdowa(o)
16

---

Published as a conference paper at ICLR 2022
Σ
Pdown (0) po(ar)
oE
where (a) reorders the terms for summation; (b) holds since Vn E 2r (p, up). Pa(a)) Tooinn()) (a( and Vo E in(n) such that {x ( 2, po(x) (c) holds because
U
(o:0E in(n), {x]})=1 E x Paum (p. v).
n2 PEP (P..)))
Thus, we have prove that Eq. (3) holds for -rri and hence the probability p aa In,) can be computed by weighting the probability of PC units (aum (p. vy.;) (line Alg. 3 with the corresponding top-down probabilities (line 9 in Alg. 3).
Efficiency of following the optimal variable order We proceed to show that when using the optimal variable order x.' Alg. 3 evaluates no more than (log((D) ( (pl) PC units.
According to the previous paragraphs, whenever 3 evaluaaes PC unit n w.r.t. vtree node will evaluate all PC units in cop,, v). Therefore, we instead count the total number of vtree nodes need to be evaluated by Alg. 3) Since the PC is assumed to be balanced Def. 4 for every v, we have (pp, v) = ()p Therefore, we only need show that Alg. evaluates O(D log(D)) vtree nodes in total.
We start with the base case, which is PCs correspond to a single vtree leaf node v. In this case, F-- (z:) boils down to computing single marginal probability p(rx;), which needs to evaluate PC units (pp, v) once.
Define f(x) the number of vtree nodes need be evaluated given a PC corresponds vtree node with r descendent Icaf nodes. From the base case we know that f
Next, consider the inductive case where is inner node that has æ descendent leaf nodes. Define the left and right child node of v as and C22 respectively. Let e₁ and e2 have y and a descendent leaf nodes, respectively. We want compute Fz. (z), which can be broken down into computing two following sets of marginals:
Set (p(#T])" " xxx)
Set 2: {p(=x]-" ,Zx; xx;) i=1+1
Since T² follows the in-order traverse of e, to compute the first term, we only need to evaluate ci and its descendents, that is, we need evaluate fly vtree nodes. This is because the marginal probabilities in set are only defined on variables in ((c1). To compute the second term, in addition to evaluating PC units corresponding to es (that f((z) vtree nodes total) we also need to
re-evaluate the PC units s(p, v)) every time, which means we need to evaluate more vtree nodes. In
summary, we need to evaluate
f(x) f()) + f(z) + 222zy+z=a
vtree nodes.
To complete the proof, we upper bound the number of vtree nodes need be evaluated. Define g(-) as follows:
g(x)
max y + g(u) + g(x - w)
yct (l..... =J)
It is not hard to verify that Vr EZ, g(x) 2 (x) Next, we prove that
Vx Z (z 2), g(z) < 3z log.r. First, we can directly verify that g(2) 3-2 log, 4.1. Next, for 3, g(x) = max y + g(y) + g(x y) ve(I.....5))
*This because the scope of these PC units does not contain any of variables [X,,)==1 As justified in the second part of this proof, all prohabilities of PC units that conform to descendents of c₁ will be unchanged when computing the marginals in 2. Hence only need eache these probabilities.
17

---

Published as a conference paper at ICLR 2022
y By log + 3(x y) log(æ x
y/
yEt [1.... [1
M(v)
(4)
S max
1+ 1) log(z - 1),
+
log
I
+
a
2
log
2. 1))
2
Σ max
1+ - log( - 1), [
x
+ +(x l)
2
3og.,
where (a) holds since according to its derivative, h(y) obtains its maximum value either y 1 or y [
For a muuctured-decompostee PC with D variables, g(D) S 3D log D vtree nodes need to be evaluated. Since each vtree node corresponds to O (gl PC units, we need evaluate (I)o(D))- PC units to compute Fx (æ).
A.3 HCLTs, EINETS, AND RAT-SPNS ARE BALANCED
Consider the compilation from PGM HCLT Sec. 4.1). We first note that each PGM node uniquely corresponds to a variable scope o of the PC, That is, all PC units correspond to g have the same variable scope. Please first refer to Appx. B.2 for details on how generate a HCLT given its PGM representation.
In the main loop of Alg. 4 (lines 5-10), for each PGM node g such that var(g) E Z, the number of computed PC units are the same (M product units compiled in line 9 and M sum units compiled line 10). Therefore, for any variable scopes Φ and Φ2 possessed by some PC units, we have [nodes(p, {(m)) s |nodes(p, ((n))]- Since there are in total ( different variable scopes in we have: for any scope ø' exists an HCLTT p. nodes(p, x²) (lpl/D).
EiNets and RAT-SPNs are also balanced since they also have an equivalent PGM representation of their PCs. The main difference between these models and HCLTs is the different variable splitting strategy in the product units.
B METHODS AND EXPERIMENT DETAILS
B.1 LEARNING HCLTS
Computing Mutual Information As mentioned in the main text, computing the pairwise mutual information between variables X is the first step to compute the Chow-Liu Tree. Since we are dealing with categorical data (e.g., 0-255 for pixels), compute mutual information by following its definition:
P(X P(X=i,y= 1(xY)) = ΣΣ P(X -, loga P(X -)P= =
Cx Cr
=1
where Cx and Cy are the number of categories for variables and Y, respectively. To lower the computation cost, for image data, we truncate the data by only using most-significant bits. That is, we treat the variables as categorical variables with 2 categories during the construction of the CLT. Note that we use the full data when constructing/learing the PC.
Training pipeline We adopt types of EM updates mini-batch and full-batch. In mini-batch EM, parameters are updated according step size 1y: (b++1) +- ( (7) where (leew) the EM target computed with a batch samples; full- batch EM updates the parameters by the EM target computed using the whole dataset. In this paper, HCLTs are trained by first running batch EM with batch size 1024 and 77 changing linearly from 0.1 to 0.05; full-batch EM then used to finetune the parameters.
18

---

Published as a conference paper at ICLR 2022
Algorithm 4 Compile the PGM representation of HCLT into an equivalent PC
1: Input: A PGM representation of a HCLT 9 (e.g.. Fi.. 3());; hyperparameter M
2: Output: A smooth and structured pewutuureddecomossabeeee decomposable PC equivalent to 3: Initialize: cache +- dict() dictionary storing intermediate PC units
4: Sub-routines: PC Je_eea((X) returns a PC input unit of variable X PC.prod((na))))) (resp. PC sum(fn: (= returns product (resp. sum) unit over child nodes Ji--
5: foreach node traversed in postorder (bottom-up) of G do
6: if var(g) E X then cache[g] [PC.leaf( (va( for M]
7: else # That is, var(g) E [cache[c] for e in children(g)] # children(g) is the of children prod nodes +- PCC prod [[odes(() for nodes in chs cache]) for fori= 1 M] 10: cachelg] + [CC_sum (prod...oddde)) for = 1: MM)
8:
9:
return (9)
B.2 GENERATING PCs FOLLOWING THE HCLT STRUCTURE
After generating the PGM representation of HCLT model, we compiling the PGM representation of the model into an equivalent PC. Recall that we define the latent as categorical variables with M categories, where M hyperparameter. As demonstrated in Alg. 4] we incrementally compile every PGM node into an equivalent PC unit though bottom-up up traverse (line 5) of the PGM. Specifically, leaf PGM nodes corresponding variables X; are compiled into PC input units of X, (line 6), and inner PGM nodes corresponding to latent variables are compiled by taking products and sums (implemented by product and sum units) of its child nodes' PC units (lines 8- 8-1 Leaf units generated by PCJleaf
left with the final step of
variables {2.)== )
observed
can be any simple univariate distribution of X. We used categorical leaf units in our HCLT experiments. Fig. 3(d)
demonstrates the result PC after running Alg. with the PGM in Fig. 3 3(c) and A 2.
B.3 IMPLEMENTATION DETAILS OF THE PC LEARNING ALGORITHM
We adopted the EM parameter learning algorithm introduced in Choi et al. (021) which computes the EM update targets using expected flows. Following Liu & Van den Broeck (202T). use hybrid EM algorithm, which uses mini-batch EM updates to initiate the training process, and switch full-batch EM updates afterwards.
Mini-batch EM: denote (EM) the EM update target computed with mini-batch of samples. An update with step-size is: (A++1) <- (1 1)) - (EM).
Full-batch EM: denote (FM) as the EM update target computed with the whole dataset. Full-batch EM updates the parameters with (EM) at each iteration.
In our experiments, we trained the HCLTs with 100 mini-batch EM epochs and 20 full-batch EM epochs. During mini-batch EM updates, 1) was annealed linearly from 0.15 to 0.05.
B.4 DETAILS OF THE COMPRESION/DDECOMRESSSI EXPERIMENT
Hardware specifications All experiments are performed on server with 72 CPUs, 512G Memory, and 2 TITAN RTX GPUs. In all experiments, we only use single GPU on the server.
IDF We ran all experiments with the code in the GitHub repo provided by the authors. We adopted an IDF model with the following hyperparameters: 8 flow layers per level; 2 levels; densenets with depth and 512 channels; base learning rate 0.001; learning rate decay 0.999. The algorithm adopts CaU-based entropy coder rANS. For (de))ompression,
used the follow- ing script: /retps://gitien http://hhw..acoeooeeeeereeeeeeee discrete /itpe//e__daiteeeeeeeos/s/////// master cetterr/eperimmeen http:pperimmet__oddnn_____. coding.py.
com/ wccmm//oorngpteeriiiteeeeeee
cwwp://iitteeeeeiiieeeeeeeeeeee flows/blob/
BitSwap We trained all models using the following author-provided script: https:// train.pa The al-
github. cwm httpt//.......ttttttttttttttt/tt
19

---

Published as a conference paper at ICLR 2022
CPU-based entropy coder rANS. And we used the following code for www/ (de)compression: httppp////ttttbb......c/a.aaaaaa http://fw.aaaaaaaaaaaaaaaaaa//aa compress.py
gorithm adopts
BB-ANS All experiments were performed using the following official code: https::/github
com/bits- bas.ttssbac//bbs--aa....
B.5 DETAILS OF THE PC+IDF MODEL
The adopted IDF architecture follows the original paper (Hoogeboom et al. 2019). For the PCs, adopted EiNets (Peharz et al. 2020a) with hyperparameters K = 12 and R = 4. Instead of using random binary trees to define the model architecture, we used binary trees where "closer" latent variables in z will be put closer in the binary tree.
Parameter learning was performed by the following steps. First, compute the average log- log-likelihood over a mini-batch of samples. The negative average log-likelinne log-likelihood is the loss we use. Second, compute the gradients w.r.t. all model parameters by backpropagating the loss. Finally, update the IDF and PCs using the gradients individually: for IDF, following Hoogeboom et al. (2019), the Adamax optimizer was used; for PCs, following Peharz al. (2020a), use the gradients compute the EM target of the parameters and performed mini-bateh EM updates.
20


Reviews:
[{"review_id": "aS2zgIPBgv4", "reviewer": "Reviewer_T76k", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Overall, I felt that whilst this was a reasonably well written paper highlighting the interesting concept of PCs, that I was not previously aware of, the methodological contribution wasn't clear enough and that the experiments were presented in a way which was potentially misleading.\n\nMy main issues with the methodological contribution (specifically section 3.2), are that I felt it was relatively difficult to understand (i.e. the presentation could have been clearer), and that as a result I don't know how significant the contribution is. On a high level, it seemed like a couple of observations were made:\n\n(a) For many models, it is important to decode/encode data in an order which 'fits' the model, leading to computational efficiency.\n(b) Work sharing between encode/decode steps is necessary for efficiency.\n\nTo someone, such as myself, who is an expert on neural lossless compression, these are both obvious points. The O(log D |p|) computational efficiency didn't seem particularly radical to me either. However, I'm unfamiliar with the PCs literature, so maybe these are significant observations to that community, and it's possible that I missed something important, so please clarify.\n\nBefore I discuss the experiments, another significant issue with the overall framing was the statement in the second paragraph of the introduction that the methods presented here are 'tractible', with the implication being that other neural compression methods are not (in some sense). I understand where this came from, since tractibility is a key property in the PCs literature, but I still felt this could be misleading, since neural compression and decompression with existing methods, whilst they may have different performance characteristics to PCs, certainly _are_ tractible.\n\nI had two main issues with the experiments. The first relates to the presentation of the timings of the method. I think it's easy to be misled, and to mislead, with timings in machine learning (and the emerging field of neural lossless compression in particular), and my issue with timings in this work is that the paper is presented as though a significant breakthrough has been made in terms of runtime, but the PC method is only compared to slow implementations of existing methods, which were not optimized for speed. One example of a faster implementation of a neural compression method is BB-ANS with a small VAE (from Townsend et al., 2019), implemented at https://github.com/j-towns/craystack. Running the example code there on a CPU, the compression/decompression for the binarized MNIST test set (a slightly easier task than raw MNIST) is 3.26s/2.82s, an order of magnitude faster than the PC timings in the paper. For extra context, on the same machine gzip takes 0.22s to compress and 0.06s to decompress the raw MNIST test set, so in my opinion neither the Craystack BB-ANS implementation nor the 15s encode and 44s decode of the PCs implementation should be considered fast. This context should have been made clearer, rather than trying to imply that a genuine breakthrough had been made in runtime.\n\nMy other serious issue with the presentation of the experiments were the vague claims of \"state-of-the-art performance on natural image datasets\", in the abstract and at the very end of section 2, discussed in more detail in section 5. It's not at all clear on what task the authors are claiming state of the art performance. At the end of sec 5, the suggestive statement is made that compression/decompression of natural images \"can be done easily\" with the implemented method. Have the authors actually implemented this? If compression wasn't implemented then this should be stated and the authors should explain why not, if it was implemented this should be clearly stated. Unfortunately, even if compression was implemented, a claim of state of the art performance would still be incorrect, because the bitrates achieved in a recent paper by Zhang et al. (https://arxiv.org/abs/2109.02639) are significantly better.\n\nSome more minor points and suggestions:\n - At the beginning of sec 3.2, why does \\pi need to be 'random'? Don't you just mean to say that \\pi is \"some ordering\" (i.e. no need to suggest that it is a random variable).\n - In section 4.1 I think it's best to consistently use the word 'latent' rather than 'hidden', since this is the standard terminology in the deep generative modelling community.\n - It might be a good idea to combine the different related work sections in one place.\n - In 'related work' near the bottom of page 8, there's a slight grammatical error: replace \"grow PC structures to fit better the data\" -> \"grow PC structures to better fit the data\".", "summary_of_the_paper": "Probabilistic circuits are a formalism, developed relatively recently, for describing multivariate probability distributions. PCs are represented using directed acyclic graphs (DAGs), with an operational semantics, and it is relatively straightforward to deduce which operations (marginalization, maximisation, estimation of moments, etc.) are tractible based on the structure of the DAG and the locations of input variables.\n\nThis paper studies the application of PCs to lossless compression, identifying the specific type of marginalisation which is necessary for auto-regressive, arithmetic coding-style compression, and the necessary conditions a PC must satisfy in order for this marginalisation to be tractible. In section 3, a procedure is described for particularly efficient marginalisation by sharing computation.\n\nExperiments show that the approach is competitive in terms of compression rate with other recent 'neural compression' works, and results are presented showing that PCs can be much faster than some existing methods, although I have serious concerns about these (see below).", "summary_of_the_review": "I felt that whilst this was a reasonably well written paper highlighting the interesting concept of PCs, which I was not previously aware of, the methodological contribution wasn't clear enough and that the experiments were presented in a way which was potentially misleading.\n\nEDIT: Score changed to 6, see comment below.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "ZFU8TFz7HhT", "reviewer": "Reviewer_H7Ew", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "A strength of this paper is its clever use of PCs in compression. First, it highlights the importance of tractability in lossless compression, which is an unexplored perspective in related works. Then, PCs are presented as a class of models with tractable inference, while still being expressive enough. This balance between expressiveness and computational cost is key this manuscript's main contribution.\n\nIt is worth clarifying the significance of the technique for improving marginal inference from O(D.|p|) to O(log(D).|p|). This algorithm has relevant similarities with Partial Propagation described in [1]. Thus, a comment on differences here could highlight the novelty in Algorithm 2.\n\nSection 4 provides a practical way for scaling up the use of PCs in compression. However, it is not clear from the manuscript the contributions made in the scaling up process. That is, if there was any new required technique developed for applying Hidden Chow-Liu Tree to the specific problem of compression.\n\nExperimental results are encouraging and convincing.\n\n\nMinor comments:\n* There is a typo with \"p(i.e.,\" in Section 2\n* Theorem 1 significance is not clear from the manuscript and it seems incremental at a first glance. While there is no questioning of its practical implications, a formal treatment could highlight its broader applications.\n\n\n[1] C.J. Butz, J.S. Oliveira, A. dos Santos, A.L. Teixeira, P. Poupart, A. Kalra, An Empirical Study of Methods for SPN Learning and Inference, Ninth International Conference on Probabilistic Graphical Models (PGM), 49--60, 2018.", "summary_of_the_paper": "The manuscript addresses the question of using deep generative models in lossless compression. As highlighted by the authors, the main issue here is related to the cost of computing probabilistic queries or, in some cases such as GANs, the inability to compute them.\nThus, this paper suggest using Probabilistic Circuits (PCs) for lossless compression. PCs allow for tractable probabilistic inference, which enables efficient compression.\n\nExperimental results are favourable in two ways. First, PCs are faster for compression, achieving results from 5 to 20 times faster than competitor neural networks. Second, PCs achieve competitive compression rates on various datasets.", "summary_of_the_review": "The manuscript provides a class of tractable models for lossless data compression. These models are well defined and algorithms are shown. Parts of the work need clarifying for novelty and significance. However, experiment results with faster and competitive compression rates are very convincing.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "9o6JYz6OfEm", "reviewer": "Reviewer_mSD5", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThis paper provides a new probabilistic modelling framework named PC for lossless compression. This framework is new in AI lossless compression community and achieves desired compression ratio and compression bandwidth in MNIST. By incorporating PC with explicit generative models in which the prior can be replaced with PC, the model achieves SOTA compression ratio in real-color images.\n\nWeaknesses:\nThis work is somewhat hard to follow in the following aspects:\n1.\tIn the abstract, the authors highlighted the drawback of VAEs such that “bits-back coding brings poor single-sample compression rates”. However, the proposed PC seems have no relevant with bits-back coding. I wonder what is the advantage of PC over VAEs in terms of “bits-back coding”?\n2.\tThe authors claim that the complexity of PC is O(log D |p|) where |p| is number of neural network units. But I am not able to figure out how to incorporate neural networks with PC in O(log D |p|). In particular, consider flow models with PC, it just seems to replace the prior with PC, to what follows, the complexity seems to be O(log D + |p|). Moreover, for auto-regressive models, it seems that PC cannot reduce the complexity to O(log D |p|) but remains O(log D |p|). More discussions on how to incorporate generative models with PC with O(log D |p|) complexity is encouraged.\n3.\tThe PC framework is hard to follow. In Definition 2-4, it is better to give definitions on “scope of variable”, and examples on “Smoothness”, “Decomposability” and “SD”. For Fig. 1, detailed probability corresponding to the figure is recommended.\n4.\tFor Sec. 5, the compression bandwidth of PC+IDF compared with IDF is recommended.\n", "summary_of_the_paper": "This paper proposes a new probabilistic model named PC for efficient encoding and decoding. The authors claim that PC greatly reduces the time complexity for inference. Experiments show that PC achieves 5-20x faster than SOTA neural compression algorithms, and performs SOTA results on MNIST datasets.", "summary_of_the_review": "The idea of PC for lossless compression is new and interesting. However, following the main contribution of PC and the main idea of PC is somewhat difficult. Giving simple examples on PC for clarification is recommended.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "5a3byG6_yvb", "reviewer": "Reviewer_WvLE", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths:\nThe contributions of the paper are: (i) reducing the complexity with respect to D from linear to sub-linear and (ii) integration with existing neural compressors. The authors use Hidden Chow-Liu Tree (HCLT) , a PC model initially proposed for simple density estimation tasks containing binary features, to scale up to achieve state-of-the-art performance on various image datasets.  Furthermore since HCLTs cannot be easily vectorized, the authors implemented customized GPU kernels for parameter learning and marginal query computationbased on Juice.jl, an open-source Julia package. This way the authors were able to get significant improvement in the performance.\n\nWeaknesses:\n The baselines BitSwap and IDF, which are definitely NOT the state of the art in compression efficiency and compute time. The comparison that is missing is with respect to 'Improving Lossless Compression Rates via Monte Carlo Bits-Back Coding' (Ruan, Ullrich, Severo, et al.). In that paper, the authors claim to compress all 10,000 MNIST images in less than 100s (Figure 7). Comparison with BitSwap (and possibly IDF) should be done with caution. In BitSwap, the entropy coder runs on CPU while the model can be run on GPU or CPU. It's not clear what the experimental setup was here for BitSwap, PC, and IDF experiments. Exactly what setup the authors claim SOTA should also be clarified (e.g. model on GPU, compression on CPU).\n\n\nComments regarding writing\nPage 4: \n- Not clear what happens when 2 different input units have the same variable. This is exactly the case of Figure 1, where there are 2 input nodes for each of X1, X2, and X3.\n\nPage 5:\n- If the inputs are descendants of the same child unit, then doesn't this imply the opposite? That is, you definitely need to multiply them based on equation 2? It would be easier if the authors followed along with a concise and concrete example.\n- The example in Figure 1 does not help, as the distance from n1 and n2 to the root node is too short for the reader to properly follow along. \n\n", "summary_of_the_paper": "The paper showcases an application of Probabilistic Circuits to lossless compression, and achieves competitive compression performance to state of the art method. The PCs output a marginal distribution over the data, which the authors then use to compress with arithmetic coding or other methods. This has several advantages, one being that bits-back coding is not needed, enabling single-sample compression.\n\n", "summary_of_the_review": "Overall the work is interesting and timely and I am leaning towards an accept if the authors can convincingly address the points above.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper revisits lossless compression using deep architecture. In contrast to main stream approaches, it suggests to make use of probabilistic circuits, introducing a novel class of tractable lossless compression models. Overall, the reviews agree that this is an interesting direction and a novel approach. I fully agree. Actually, I like that the paper is not just saying well, we could use a probabilistic circuit for ensure tractability but also shows that there is still a benefit of different variable orderings for encoding and decoding. In any case, adding probabilistic circuits to the "compression family" is valuable and also paves the way to novel hybrid approaches, combining neural networks and probabilistic circuits. I have enjoyed reading the paper, reviews, and discussion.
Decision: Accept (Spotlight)