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 . The connections between information theory and machine learning have long been known to be deep, and indeed the two fields are so closely related that they have been described as 'two sides of the same coin' BID18 . One particularly elegant connection is the essential equivalence between probabilistic models of data and lossless compression methods. The source coding theorem BID22 can be thought of as the fundamental theorem describing this idea, and Huffman coding BID13 , arithmetic coding BID28 and the more recently developed asymmetric numeral systems BID3 ) are actual algorithms for implementing lossless compression, given some kind of probabilistic model.The field of machine learning has experienced an explosion of activity in recent years, and we have seen a number of papers looking at applications of modern deep learning methods to lossy compression. BID7 discusses applications of a deep latent Gaussian model to compression, with an emphasis on lossy compression. BID0 , BID23 , BID1 , and BID19 all implement lossy compression using (variational) auto-encoder style models, and BID24 train a model for lossy compression using a GAN-like objective. Applications to lossless compression have been less well covered in recent works. We seek to advance in this direction, and we focus on lossless compression using latent variable models.The lossless compression algorithms mentioned above do not naturally cater for latent variables. However there is a method, known as 'bits back coding' BID27 BID10 , first introduced as a thought experiment, but later implemented in BID5 and BID4 , which can be used to extend those algorithms to cope with latent variables.Although bits back coding has been implemented in restricted cases by BID4 , there is no known efficient implementation for modern neural net-based models or larger datasets. There is, in fact, a fundamental incompatibility between bits back and the arithmetic coding scheme with which it has previously been implemented. We resolve this issue, describing a scheme that instead implements bits back using asymmetric numeral systems. We term this new coding scheme 'Bits Back with ANS' (BB-ANS). Our scheme improves on existing implementations of bits back coding in terms of compression rate and code complexity, allowing for efficient lossless compression of arbitrarily large datasets with deep latent variable models. We demonstrate the efficiency of BB-ANS by losslessly compressing the MNIST dataset with a variational auto-encoder (VAE), a deep latent variable model with continuous latent variables BID15 BID20 . As far as we are aware, this is the first time bits back coding has been implemented with continuous latent variables.We find that BB-ANS with a VAE outperforms generic compression algorithms for both binarized and raw MNIST, even with a very simple model architecture. We extrapolate these results to predict that the performance of BB-ANS with larger, state of the art models would be significantly better than generic compression algorithms. Probabilistic modelling of data is a highly active research area within machine learning. Given the progress within this area, it is of interest to study the application of probabilistic models to lossless compression. Indeed, if practical lossless compression schemes using these models can be developed then there is the possibility of significant improvement in compression rate over existing methods.We have shown the existence of a scheme, BB-ANS, which can be used for lossless compression using latent variable models. We demonstrated BB-ANS by compressing the MNIST dataset, achieving compression rates superior to generic algorithms. We have shown how to handle the issue of latent discretization. Crucially, we were able to compress to sizes very close to the negative ELBO for a large dataset. This is the first time this has been achieved with a latent variable model, and implies that state-of-the-art latent variable models could be used in conjunction with BB-ANS to achieve significantly better lossless compression rates than current methods. Given that all components of BB-ANS are readily parallelizable, we believe that BB-ANS can be implemented to run on GPU hardware, yielding a fast and powerful lossless compression system.
We do lossless compression of large image datasets using a VAE, beat existing compression algorithms.
{"src": "scitldr-AIC_train", "paper_id": "ryE98iR5tm"}