Integer Discrete Flows and Lossless Compression

By Emiel Hoogeboom, Jorn W. T. Peters, Rianne van den Berg, Max Welling. 2019

187 citations recorded by the source corpus.

Lossless compression methods shorten the expected representation size of data without loss of information, using a statistical model. Flow-based models are attractive in this setting because they admit exact likelihood optimization, which is equivalent to minimizing the expected number of bits per message. However, conventional flows assume continuous data, which may lead to reconstruction errors when quantized for compression. For that reason, we introduce a flow-based generative model for ordinal discrete data called Integer Discrete Flow (IDF): a bijective integer map that can learn rich transformations on high-dimensional data. As building blocks for IDFs, we introduce a flexible transformation layer called integer discrete coupling. Our experiments show that IDFs are competitive with other flow-based generative models. Furthermore, we demonstrate that IDF based compression achieves state-of-the-art lossless compression rates on CIFAR10, ImageNet32, and ImageNet64. To the best of our knowledge, this is the first lossless compression method that uses invertible neural networks.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Signal Processing

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Signal Processing

Citations in the corpus

Fast Lossless Neural Compression with Integer-Only Discrete Flows (2022, methodology): “Different from IDF (Hoogeboom et al., 2019; van den Berg et al., 2020) which model x , z both with discrete integers, Ho et al. (2019b) dicretize continuous variables and propose a local bits back (LBB) scheme for compression with a general class of NFs which model x , z as continuous.”
Normalizing Flows for Probabilistic Modeling and Inference (2019, methodology): “Hoogeboom et al. (2019a) proposed a discrete flow for U = X = ZD based on affine autoregressive flows (section 3.”
Maximum Likelihood Training of Score-Based Diffusion Models (2021, background): “Since better likelihoods are useful for applications including compression [21, 20, 51], semi-supervised learning [10], adversarial puriﬁcation [47], and comparing against likelihood-based generative models, we seek a training objective for score-based diffusion models that is as efﬁcient as score…”
A RAD approach to deep mixture models (2019, background): “Similar to Rolfe (2017), the learning of discrete variables is achieved by relying on the the continuous component of the model, and, as opposed to other approaches (Bengio et al., 2013; Raiko et al., 2015; Jang et al., 2017; Maddison et al., 2017; Grathwohl et al., 2018; Tucker et al., 2017; Tran e”
Argmax Flows and Multinomial Diffusion: Towards Non-Autoregressive Language Models (2021, background): “In addition flows for ordinal discrete data (integers) have been explored in (Hoogeboom et al., 2019; van den Berg et al., 2020).”
Analog Bits: Generating Discrete Data using Diffusion Models with Self-Conditioning (2022, background): “Discrete ﬂows (Tran et al., 2019; Hoogeboom et al., 2019; Lindt & Hoogeboom, 2021) introduce invertible transformations of random variables in discrete space without the need of computing the log-determinant of Jacobian.”
iVPF: Numerical Invertible Volume Preserving Flow for Efficient Lossless Compression (2021, methodology): “Hoogeboom et al [15] approached this problem by proposing a discrete flow for integers (IDF).”
iFlow: Numerically Invertible Flows for Efficient Lossless Compression via a Uniform Coder (2021, methodology): “To resolve this issue, Integer Discrete Flows (IDF) [18, 4] (Fig.”
Normalizing Flows: An Introduction and Review of Current Methods (2020, background): “[43] models bijections on Z directly with additive coupling layers.”
Latent Variable Models (2019, methodology): “On the other hand, fully observed models, as well as the flow based models of Hoogeboom et al. (2019) and Ho et al. (2019), do not require bits back coding, and therefore do not have to pay the one-off cost of starting a chain.”
Variational Causal Networks: Approximate Bayesian Inference over Causal Structures (2021, methodology): “be obtained by combining with normalising flows for discrete variables [35, 18].”
IDF++: Analyzing and Improving Integer Discrete Flows for Lossless Compression (2020, methodology): “We follow Hoogeboom et al. [19] and augment the Cifar-10 dataset with horizontal ﬂipping, reﬂect-padding and random cropping during training.”
Discrete Flows: Invertible Generative Models of Discrete Data (2019, background): “Most recently, Hoogeboom et al. (2019) proposed integer discrete ﬂows, a concurrent unpublished work with similar ideas as discrete ﬂows but with a ﬂow transformation for ordinal data and applications to image compression and image generation.”
HiLLoC: Lossless Image Compression with Hierarchical Latent Variable Models (2019, methodology): “On the other hand, fully observed models, as well as the flow based models of Hoogeboom et al. (2019) and Ho et al. (2019), do not require bits back coding, and therefore do not have to pay the one-off cost of starting a chain.”
Deep Generative Modelling: A Comparative Review of VAEs, GANs, Normalizing Flows, Energy-Based and Autoregressive Models (2021, methodology): “Integer discrete flows (IDF) achieve this using additive coupling layers, rounding translation values to the nearest integer and approximating gradients with the straight-through estimator [93]; discrete flows [219] apply affine coupling layers in modulo space”
Reducing the Computational Cost of Deep Generative Models with Binary Neural Networks (2020, background): “…useful result for any real-world application of these generative models. such as learned lossless compression (Townsend et al., 2019; Kingma et al., 2019; Townsend et al., 2020; Ho et al., 2019b; Hoogeboom et al., 2019), which could be made practical with these reduced memory and compute benefits.”
Argmax Flows and Multinomial Diffusion: Learning Categorical Distributions (2021, background): “In addition ﬂows for ordinal discrete data (integers) have been explored in (Hoogeboom et al., 2019; van den Berg et al., 2020).”