PaperlayerView exact revision on arXiv

Source-linked AI summary

Integer Discrete Flows and Lossless Compression

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

arXiv:1905.07376v4cs.LGcs.CVstat.ML

TL;DR

Lossless compression needs discrete, exactly invertible modeling, while conventional continuous flows can introduce reconstruction errors after quantization. The paper proposes Integer Discrete Flows with integer coupling layers and demonstrates competitive generative modeling and state-of-the-art lossless compression across three image datasets.

  • Problem

    Conventional flow models assume continuous data, so quantization for compressing discrete media can cause reconstruction errors that are unsuitable for lossless compression.

  • Method

    Integer Discrete Flows use bijective integer maps for ordinal discrete data, with integer discrete coupling layers as building blocks and an entropy coder for compression.

  • Results

    IDFs achieve state-of-the-art lossless compression performance on CIFAR10, ImageNet32, and ImageNet64, while remaining competitive with other flow-based generative models.

  • Takeaways & Limitations

    IDFs provide a lossless compression method based on invertible neural networks for ordinal discrete data and support progressive decoding that maintains global image structure.

Abstract

from arXiv · show

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.

1 Introduction

Lossless compression benefits from likelihood-based statistical modeling, but continuous flow models are poorly suited to discrete media because quantization can cause reconstruction errors. The paper introduces Integer Discrete Flows to provide invertible transformations for ordinal discrete data and reports strong compression and generative-modeling performance.

  • Motivation: Lossless compression preserves information while reducing representation size by exploiting data patterns and structure.Its optimization is linked to likelihood maximization through Shannon’s source coding theorem.
  • Motivation: High-dimensional data makes designing and optimizing statistical models for compression difficult.Deep generative models address this modeling challenge by learning complicated distributions from data.
  • Problem: Continuous flow models offer exact likelihood optimization and efficient decoding, but quantizing their latent space can produce image reconstruction errors.Digital media is stored discretely, such as 8-bit pixels with 256 possible values.
  • Contribution: Integer Discrete Flows are proposed as invertible transformations for ordinal discrete data, including images, video, and audio.The paper also introduces integer discrete coupling layers as IDF building blocks and a neural compression method based on IDFs.
  • Results: IDF-based compression achieves state-of-the-art lossless compression performance on CIFAR10, ImageNet32, and ImageNet64.The paper additionally reports competitive generative-modeling results with other flow-based methods and progressive decoding that maintains global image structure.

2 Background

Normalizing flows use invertible maps and tractable likelihoods, while coupling and factor-out layers make these models computationally practical and hierarchically structured. Entropy coding connects the learned probability model to near-optimal lossless message lengths.

  • Flow-based models: A normalizing flow composes invertible functions to map data to a simpler prior distribution while enabling exact likelihood evaluation.The change-of-variables formulation evaluates the prior at the transformed observation and accounts for the Jacobian determinant.
  • Flow layers: Coupling layers partition the input, transform one subset using neural-network outputs conditioned on the other, and provide an analytical inverse.Their Jacobian determinant is easy to compute, and invertibility requires the scale transformation to remain nonzero.
  • Flow layers: Factor-out layers remove subsets of dimensions at intervals so later flow computations operate on lower-dimensional data.They also support a factored prior with conditional dependence between latent subsets.
  • Entropy encoding: Lossless coding assigns shorter representations to probable inputs, with optimal code length governed by the negative log probability and entropy.When the encoder is optimal, maximizing model log-likelihood minimizes expected bits per message.
  • Entropy encoding: Stream coders can approach Shannon’s entropy lower bound, and the experiments use rANS for computationally efficient coding.The coder encodes sequences of random variables with different probability distributions.

3 Integer Discrete Flows

Integer Discrete Flows are bijective integer maps for ordinal discrete data, built from invertible coupling layers and paired with discretized logistic priors. Their exact invertibility supports lossless compression through entropy coding and error-free reconstruction.

  • Integer Discrete Flows: IDFs define bijective maps from Z^d to Z^d, allowing rich probability models for high-dimensional ordinal discrete data without Jacobian re-normalization.Stacking bijective layers preserves closure on Z^d and makes inversion well-defined.
  • Integer Discrete Coupling: Integer discrete coupling copies x_a and adds a rounded neural translation to x_b, preserving integer-valued outputs and invertibility.The transformation is z_a = x_a and z_b = x_b + ⌊t(x_a)⌉.
  • Integer Discrete Coupling: The 75%–25% input split reduces the dimensions affected by rounding while conditioning transformations on more dimensions, empirically improving performance.Multiplicative coupling is omitted because it would not preserve mappings whose image equals Z.
  • Tractable Discrete Distribution: The discretized logistic prior assigns integer values probability over unit intervals and captures the inductive bias that nearby ordinal values are related.Its flexibility can be increased with mixtures, for which K = 5 is usually sufficient for image density modeling.
  • Lossless Source Compression: IDF compression maps x to z, entropy-encodes z under p_Z, and reconstructs x with the inverse IDF without information loss.An escape bit handles rare cases in which the compressed representation exceeds the original size.

4 Architecture

The IDF architecture is organized into levels containing squeeze, flow, and factor-out operations. Unlike continuous flows, increasing depth can eventually hurt discrete-flow performance because each layer adds rounding-induced gradient bias.

  • Architecture: Each IDF level applies a squeeze operation, D integer flow layers, and a factor-out layer, with the final level mapping directly to z_L.Each integer flow layer combines a fixed permutation with an integer discrete coupling layer.
  • Architecture: Fixed permutation layers are initialized once and retained during training and evaluation, while architecture details vary across experiments.The architecture discussion evaluates how network depth affects performance when rounding operations are present.
  • Depth and Performance: Additional IDF depth introduces more rounding operations and gradient bias, so adding flow layers eventually hurts performance.This creates a complexity–gradient-bias trade-off unlike the usual depth trend in continuous normalizing flows.

5 Related Work

The paper distinguishes IDFs from continuous flows, autoregressive likelihood models, VAEs, hand-designed integer transforms, and concurrent discrete-flow work. These alternatives differ in data type, likelihood treatment, computational cost, or compression scope.

  • Related Work: Continuous flows may produce reconstruction errors when latent representations are quantized and inverted back to image space.IDFs instead target ordinal discrete data directly.
  • Related Work: PixelCNNs use ordered conditional decompositions and are generally computationally expensive for sampling and decoding, while VAEs optimize a likelihood lower bound.These properties contrast with exact likelihood optimization and efficient decoding in flow-based models.
  • Related Work: GANs are not suited to lossless compression because they do not optimize likelihood, which is directly connected to expected message length.Their strength in generating high-quality images does not provide the likelihood objective required here.
  • Related Work: Hand-designed reversible integer transforms, including reversible wavelets in JPEG2000, are difficult to tune for data requiring complicated nonlinear transformations.IDFs address this limitation with learned invertible transformations.
  • Related Work: Concurrent discrete-flow work focused on categorical data, whereas this paper targets ordinal data and additionally presents compression results on larger-scale image datasets.The paper also connects its approach to source coding and provides a compression algorithm.

6 Experiments

IDFs achieve state-of-the-art lossless compression across CIFAR10, ImageNet32, and ImageNet64, generalize across datasets, and remain effective on medical images. They also support progressive rendering and competitive generative modeling.

  • 6.1 Image Compression: IDFs achieve state-of-the-art lossless compression on CIFAR10, ImageNet32, and ImageNet64, measured in bits per dimension and compression rate.Performance is evaluated on test data against established lossless compression methods.
  • 6.1 Image Compression: An ImageNet32-trained IDF still outperforms competing methods on CIFAR10 and ImageNet64, with only a slight compression decrease relative to source-trained models.For ImageNet64, each image is split into four 32 × 32 patches.
  • 6.2 Tuneable Compression: IDFs considerably outperform FLIF, JPEG2000, and JP2-WSI on the ER + BCa histology dataset despite compressing images independently in 80 × 80px patches.The model is trained on random patches because the original images are 2000 × 2000 pixels.
  • 6.3 Progressive Image Rendering: IDFs support progressive rendering by decoding received variables and sampling remaining dimensions, with global image structure visible using approximately 15% of the bitstream.ImageNet64 demonstrations use approximately 15%, 30%, 60%, and 100% of the stream.
  • 6.4 Probability Mass Estimation: IDFs achieve competitive generative modeling performance on CIFAR10, ImageNet32, and ImageNet64 despite a relatively simple architecture.Performance is measured in bits per dimension using negative log2-likelihood and compared with RealNVP, Glow, and Flow++.

7 Conclusion

Integer Discrete Flows support deep generative modeling and neural lossless compression for ordinal discrete data. The paper also develops coupling transformations that preserve invertibility while limiting rounding-related gradient bias and computational cost.

  • Integer Discrete Flows are flows for ordinal discrete data that support deep generative modeling and neural lossless compression.
  • IDFs achieve state-of-the-art lossless compression performance on CIFAR10, ImageNet32, and ImageNet64.
  • Lower Triangular Coupling: The paper introduces Lower Triangular Coupling to increase layer flexibility without increasing the number of rounding operations.
  • Lower Triangular Coupling: Lower Triangular Coupling transforms x_b using a strictly lower triangular matrix conditioned on x_a and rounds the combined transformation once.
  • Lower Triangular Coupling: The transformation is guaranteed to be invertible, with its inverse found using a modified forward-substitution procedure.
  • Lower Triangular Coupling: Local triangular matrices allow spatial parallelization, while the inverse requires c_b iterations with spatially parallelized matrix operations.

C Quantizing a Continuous Flow

Quantizing a continuous flow requires separately encoding quantized latents and reconstruction residuals to preserve the original input. Across bin sizes, this trade-off remains unfavorable for lossless compression.

  • Quantizing the latent space can produce reconstruction errors, so FLIF encodes the residual errors alongside the quantized latent variables.
  • Large bins reduce latent encoding bits but increase residual bits, whereas small bins increase latent bits but reduce residual bits.
  • The combined bits for quantized latents and residuals remain large, so the quantized flow performs poorly on lossless compression.

D Experimental details

The experiments use DenseNets to parameterize the coupling and factor-out layers. These networks have 512 intermediate channels and depth 12, without normalization layers.

  • The coupling and factor-out layers are parameterized using DenseNets with n = 512 intermediate channels and depth d = 12.
  • Unlike standard DenseNets, the experimental networks do not use normalization layers.

D.2 IDF architecture

The experiments specify architecture and optimization settings for each model and dataset. The implementation uses an equivalent scaled integer representation that works better with standard initialization and optimization methods.

  • Training uses Adamax with standard parameters, a decaying learning rate, and dataset-specific preprocessing procedures.
  • The exact IDF architecture and optimization parameters are specified separately for each experiment.
  • The implementation represents integers as Z/256, which is functionally equivalent to the method described in the main text.

D.3 Dataset preparation

The experiments use defined train, validation, and test splits for CIFAR10, ImageNet32, and ImageNet64, with a patient-disjoint split for the ER + BCa dataset. Implementations use PyTorch, released model code, an rANS coder, and four Nvidia GTX 1080Ti GPUs.

  • Dataset splits: CIFAR10 is split into 40000 training, 10000 validation, and 10000 test images.The validation set consists of the last 10000 images from the original training set.
  • Dataset splits: ImageNet32 and ImageNet64 contain roughly 1230000 training, 20000 validation, and 50000 test images.The original validation images are used for testing, while 20000 images are randomly selected for validation.
  • Dataset splits: The ER + BCa dataset is split into 114 training and 28 test images, with patient identifiers restricted to one split.This prevents the same patient IDs from appearing in both training and test sets.
  • Implementation: Experiments use PyTorch, model implementations based on the codebase from [40], an rANS coder from [38], and four Nvidia GTX 1080Ti GPUs.These tools and hardware support the reported experiments.
Loading 1905.07376v4…