We propose a set of modifications that improve training time and likelihood estimation of hierarchical mixture models implemented via Probabilistic Circuits (PCs). Our proposal reduces the complexity of mutual information estimation in the structure learning step of PCs from quadratic to linear in the number of inputs, without sacrificing likelihood estimation performance on image datasets. We repurpose invertible transformations from the lossless compression community to improve likelihood estimation by a factor of up to 25% on benchmark image datasets, making PCs competitive with current standard codecs on low-resolution datasets. Despite our improvements, experiments with low- and high-resolution image datasets indicate that the advantage of lossless neural compression and PCs over standard codecs, such as WebP, disappears as the image size increases, motivating future work on practical lossless neural compression.

Current methods which compress multisets at an optimal rate have computational complexity that scales linearly with alphabet size, making them too slow to be practical in many real-world settings. We show how to convert a compression algorithm for sequences into one for multisets, in exchange for an additional complexity term that is quasi-linear in sequence length. This allows us to compress multisets of independent and identically distributed symbols at an optimal rate, with computational complexity decoupled from the alphabet size. The key insight is to avoid encoding the multiset directly, and instead compress a proxy sequence, using a technique called ‘bits-back coding’. We demonstrate the method experimentally on two tasks which are intractible with previous optimal-rate methods: compression of multisets of images and JavaScript Object Notation (JSON) files. Code for our experiments is available at https://github.com/facebookresearch/multiset-compression.