Lossless Compression with Probabilistic Circuits
Lossless Compression with Probabilistic Circuits
复制标题
DOI：
--
复制
发表时间：
2021-11
期刊：
影响因子：
--
通讯作者：
Anji Liu;S. Mandt;Guy Van den Broeck
中科院分区：
文献类型：
--
作者：
Anji Liu;S. Mandt;Guy Van den Broeck
尽管在图像生成方面取得了广泛的进展，但常见的深度生成模型架构并不容易应用于无损压缩。例如，VAE由于其潜在变量而遭受压缩成本开销。这种开销只能部分消除精心设计的方案，如比特回编码，往往导致单样本压缩率差。为了克服这些问题，我们建立了一类新的易处理的无损压缩模型，允许有效的编码和解码：概率电路（PC）。这是一类神经网络，涉及$|p| $计算单元，支持对$D$特征维度的任意子集进行有效边缘化，从而实现高效算术编码。我们推导出有效的编码和解码方案，它们的时间复杂度都是$\mathcal{O}（\log（D）\cdot| p|）$，其中，朴素方案的线性成本为$D$和$|p| $，使该方法具有高度可扩展性。根据经验，我们基于PC的（解）压缩算法比实现类似比特率的神经压缩算法快5-40倍。通过扩展传统的PC结构学习管道，我们在MNIST等图像数据集上获得了最先进的结果。此外，PC可以自然地与现有的神经压缩算法集成，以提高这些基础模型在自然图像数据集上的性能。我们的研究结果强调了非标准学习架构可能对神经数据压缩产生的潜在影响。
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.