PaperlayerView exact revision on arXiv

Source-linked AI summary

Practical Lossless Compression with Latent Variables using Bits Back Coding

James Townsend, Tom Bird, David Barber

arXiv:1901.04866v1cs.LGcs.AIcs.ITstat.COstat.ML

TL;DR

Practical lossless compression with modern latent-variable models was not yet available despite the potential of deep generative models. The paper introduces BB-ANS, which implements bits-back coding with asymmetric numeral systems, and demonstrates superior compression to generic algorithms on MNIST using a simple VAE. The authors argue that larger models and parallel implementations could further improve compression rates.

  • Problem

    Practical lossless compression using modern neural latent-variable models lacked an efficient implementation.

  • Method

    BB-ANS implements bits-back coding with asymmetric numeral systems and uses a VAE as the latent-variable model.

  • Results

    BB-ANS with a VAE outperforms generic compression algorithms on both binarized and raw MNIST, and achieves rates very close to the negative ELBO for a large dataset.

  • Takeaways & Limitations

    BB-ANS provides a practical route to lossless compression with deep latent-variable models and could support substantially better rates with state-of-the-art models.

  • Takeaways & Limitations

    The current implementation is pure Python, CPU-only, unparallelized, and orders of magnitude slower in coding than in computing model probabilities.

Abstract

from arXiv · show

Deep latent variable models have seen recent success in many data domains. Lossless compression is an application of these models which, despite having the potential to be highly useful, has yet to be implemented in a practical manner. We present `Bits Back with ANS' (BB-ANS), a scheme to perform lossless compression with latent variable models at a near optimal rate. We demonstrate this scheme by using it to compress the MNIST dataset with a variational auto-encoder model (VAE), achieving compression rates superior to standard methods with only a simple VAE. Given that the scheme is highly amenable to parallelization, we conclude that with a sufficiently high quality generative model this scheme could be used to achieve substantial improvements in compression rate with acceptable running time. We make our implementation available open source at https://github.com/bits-back/bits-back .

1 INTRODUCTION

The paper addresses the lack of practical lossless compression with modern latent-variable models by introducing BB-ANS, an efficient bits-back scheme using asymmetric numeral systems. It demonstrates the scheme with a VAE on MNIST, where it outperforms generic compression algorithms even with a simple model.

  • Modern deep learning has been widely applied to lossy compression, but practical lossless compression with latent-variable models remained unresolved.
  • Bits-back coding extends lossless coding methods to handle latent variables, but previous implementations were restricted and inefficient for modern neural networks or larger datasets.
  • BB-ANS resolves the incompatibility between bits-back coding and arithmetic coding by implementing bits back with asymmetric numeral systems.
  • The scheme improves compression rate and code complexity while supporting efficient lossless compression of arbitrarily large datasets with deep latent-variable models.
  • BB-ANS with a VAE outperforms generic compression algorithms on both binarized and raw MNIST, despite using a very simple model architecture.

2 BITS BACK CODING

Bits back coding uses latent-variable models for lossless compression by recovering the auxiliary bits spent to sample latents. BB-ANS implements chaining with ANS, avoids AC’s per-iteration overhead, and extends the approach to continuous latents while identifying practical efficiency limits.

  • Coding with observed models: Arithmetic coding and ANS encode data near its information content, but differ because AC decodes FIFO while ANS decodes LIFO.Both methods have message length approximately h(s) plus a small overhead; ANS’s stack-like order is central to bits-back chaining.
  • Bits back coding: Bits back coding samples a latent y from q(y | s), encodes s under p(s | y) and y under p(y), then recovers the extra bits using q(y | s).The expected message-length increase is the negative ELBO, linking compression rate to variational inference objectives.
  • Chaining and its limitation: AC-based chaining incurs code-complexity and compression-rate costs because each iteration requires a flush, typically costing 2 to 32 bits.This per-iteration overhead motivates replacing AC in the bits-back construction.
  • Bits Back with ANS: BB-ANS implements chaining with ANS and zero compression-rate overhead per iteration because ANS is stack-like rather than queue-like.The scheme is presented as a way to resolve the incompatibility between bits back chaining and arithmetic coding.
  • Efficiency considerations: In practice, finite-precision probabilities, initialization, and imperfect auxiliary bits prevent BB-ANS rates from exactly matching the ELBO.For a one-datapoint batch, the message length equals the log joint; with more samples, initialization inefficiency is amortized, and MNIST experiments found rates typically close to the negative ELBO.
  • Continuous latent variables: Continuous latents can be coded by discretizing prior and posterior distributions with shared buckets, because the bucket-width terms cancel and smooth densities make the remaining error negligible.The paper presents this as the first bits-back implementation supporting continuous latents, up to arbitrary precision.

3 EXPERIMENTS

The experiments evaluate BB-ANS with VAEs on raw and binarized MNIST, comparing compression against benchmarks and the negative test ELBO. Achieved rates closely track the negative ELBO, with finite-precision and discretization effects producing only a small discrepancy.

  • 3 EXPERIMENTS: The VAE uses a standard Gaussian prior and diagonal Gaussian approximate posterior over a multidimensional latent.The model is trained with the usual ELBO objective before being used within BB-ANS.
  • 3 EXPERIMENTS: BB-ANS compresses trained VAE models on raw and stochastically binarized MNIST test data.The experiments use fully connected VAE networks with ReLU activations and task-specific output distributions.
  • 3 EXPERIMENTS: The binarized-MNIST VAE has 100-unit hidden layers and a 40-dimensional latent, while the full-MNIST VAE has 200-unit hidden layers and a 50-dimensional latent.The binarized model outputs Bernoulli pixel logits; the full-MNIST model uses a beta-binomial pixel distribution.
  • 3 EXPERIMENTS: A supply of around 400 clean bits initializes the BB-ANS chain in these experiments.The required number depends on the entropy of the discretized approximate posterior.
  • 3 EXPERIMENTS: BB-ANS outperforms benchmark compression schemes despite the relatively small network sizes and simple architectures.Compression rates are reported in bits per dimension for both MNIST variants alongside bz2, gzip, PNG, WebP, and VAE negative ELBO values.
  • 3 EXPERIMENTS: Achieved compression is very close to the negative test ELBO, with finite precision, latent discretization, and less-clean bits accounting for a discrepancy of around 1%.These effects do not appear to significantly affect the compression rate in the experiments.

4 DISCUSSION

The discussion considers extending BB-ANS to stronger latent-variable models and practical deployment. Predicted gains rely on a small ELBO-to-compression discrepancy, while time-series coding, computation speed, and model-parameter costs remain important boundaries.

  • 4.1 EXTENDING BB-ANS TO STATE-OF-THE-ART LATENT VARIABLE MODELS: PixelVAE results suggest BB-ANS may achieve significantly better compression than existing schemes on binarized MNIST and 64 × 64 ImageNet.These are predictions based on reported PixelVAE ELBOs rather than experimental BB-ANS results.
  • 4.1 EXTENDING BB-ANS TO STATE-OF-THE-ART LATENT VARIABLE MODELS: The PixelVAE predictions assume that the discrepancy between compression rate and ELBO remains small for larger models.Experimental verification is left to future work.
  • 4.1 EXTENDING BB-ANS TO STATE-OF-THE-ART LATENT VARIABLE MODELS: For time-series latent-variable models, a naive implementation may require extra bits that scale with sequence length, leading to highly sub-optimal compression in practice.The authors leave interleaving bits back with model time steps for future work because its feasibility is unclear.
  • 4.2 PARALLELIZATION OF BB-ANS: The current pure-Python, CPU-only implementation is not parallelized and runs orders of magnitude slower than the model-probability computations.The authors believe most algorithmic computation could be parallelized on GPUs.
  • 4.2 PARALLELIZATION OF BB-ANS: CDF and inverse-CDF computations are already available on GPUs for several relevant distributions, while ANS is known to be amenable to parallelization.The discussion identifies ANS parallel implementations as a route toward relieving the computational bottleneck.
  • 4.3 COMMUNICATING THE MODEL: Communicating and storing thousands of neural-network parameters may matter for large-scale BB-ANS systems, although this one-time cost can be amortized across many compressed images.Weight quantization is noted as a possible way to reduce this cost.

5 CONCLUSION

The paper motivates practical lossless compression with probabilistic latent-variable models and concludes that BB-ANS achieves near-optimal rates on MNIST while supporting scalable implementation.

  • Practical lossless compression with probabilistic models could significantly improve compression rates over existing methods.
  • BB-ANS compresses latent-variable models losslessly and achieves MNIST compression rates superior to generic algorithms.
  • BB-ANS compresses to sizes very close to the negative ELBO for a large dataset.
  • The scheme’s readily parallelizable components could support fast GPU-based lossless compression with state-of-the-art latent-variable models.

A BITS BACK CODING

Bits back coding uses an approximate posterior to recover auxiliary bits while encoding data through a latent-variable generative model. Its expected message length equals the negative ELBO, reaching the information-theoretic optimum when the exact posterior is available.

  • Recovering the auxiliary bits offsets the cost of sampling the latent, leaving the likelihood-related coding cost in the basic derivation.
  • The expected message length of bits back coding equals the negative ELBO, also called the model’s free energy.
  • The optimal posterior is q(y | s0) = p(y | s0), under which bits back reaches the sample’s information content and optimal message length.
  • Earlier latent-variable lossless approaches did not recover bits back, limiting the potential gains from this method.

B DISCRETIZATION

Because ANS requires finite alphabets, continuous latent variables must be discretized using shared, receiver-known buckets. BB-ANS uses equal-prior-mass buckets, though their posterior efficiency and optimality remain qualified.

  • ANS requires continuous latent variables to be restricted to a finite alphabet through discretization.
  • The discretization must suit coding densities, be shared by the prior and posterior, and be known to the receiver before decoding.
  • BB-ANS allocates buckets with equal mass under the prior, producing a receiver-known maximum-entropy discretization.
  • Figure 4 illustrates this discretization for a standard Gaussian prior using 16 buckets.
  • The prior-based discretization is efficient for prior coding, but its suitability for posterior coding is not obvious.
  • The VAE objective encourages the posterior to remain close to the prior, supporting the use of maximum-entropy prior discretization for posterior coding.

C BB-ANS PYTHON IMPLEMENTATION

The BB-ANS implementation represents coding as paired stack operations: append methods encode according to the posterior, likelihood, and prior, while pop methods invert them to decode and recover bits.

  • BB-ANS encoding and decoding use stack-like ‘append’ and ‘pop’ operations.
  • Each decoding pop precisely inverts its corresponding encoding append operation.
  • The append and pop functions may use any LIFO coding algorithm, provided each pop precisely inverts its corresponding append.
  • The encoding sequence samples y from q(y | s), encodes s with p(s | y), and encodes y with p(y).
  • Decoding reverses the sequence by popping y from the prior and s from the likelihood, then inverts the posterior operation.
Loading 1901.04866v1…