Understanding Entropy Coding With Asymmetric Numeral Systems (ANS): a Statistician's Perspective
Entropy coding is the backbone data compression. Novel machine-learning based compression methods often use a new entropy coder called Asymmetric Numeral Systems (ANS) [Duda et al., 2015], which provides very close to optimal bitrates and simplifies [Townsend et al., 2019] advanced compression techniques such as bits-back coding. However, researchers with a background in machine learning often struggle to understand how ANS works, which prevents them from exploiting its full versatility. This paper is meant as an educational resource to make ANS more approachable by presenting it from a new perspective of latent variable models and the so-called bits-back trick. We guide the reader step by step to a complete implementation of ANS in the Python programming language, which we then generalize for more advanced use cases. We also present and empirically evaluate an open-source library of various entropy coders designed for both research and production use. Related teaching videos and problem sets are available online.
Code (2)
Tasks
BIG-bench Machine LearningData CompressionSimilar Papers 제목 키워드 기반
A tutorial on the range variant of asymmetric numeral systems
This paper is intended to be an accessible introduction to the range variant of Asymmetric Numeral Systems (rANS). This version of ANS can be used as a drop in replacement for traditional arithmetic coding (AC). Implemen…
Range Asymmetric Numeral Systems-Based Lightweight Intermediate Feature Compression for Split Computing of Deep Neural Networks
Split computing distributes deep neural network inference between resource-constrained edge devices and cloud servers but faces significant communication bottlenecks when transmitting intermediate features. To this end, …
Annotating and Inferring Compositional Structures in Numeral Systems Across Languages
Numeral systems across the world's languages vary in fascinating ways, both regarding their synchronic structure and the diachronic processes that determined how they evolved in their current shape. For a proper comparis…
Bit-Swap: Recursive Bits-Back Coding for Lossless Compression with Hierarchical Latent Variables
The bits-back argument suggests that latent variable models can be turned into lossless compression schemes. Translating the bits-back argument into efficient and practical lossless compression schemes for general latent…