PaperlayerView exact revision on arXiv

Source-linked AI summary

DeepCABAC: A Universal Compression Algorithm for Deep Neural Networks

Simon Wiedemann, Heiner Kirchoffer, Stefan Matlage, Paul Haase, Arturo Marban, Talmaj Marinc, David Neumann, Tung Nguyen, Ahmed Osman, Detlev Marpe, Heiko Schwarz, Thomas Wiegand, Wojciech Samek

arXiv:1907.11900v1cs.LGcs.ITmath.IT

TL;DR

Growing neural-network parameter counts make memory demands and deployment more challenging. DeepCABAC applies CABAC to network parameters and uses quantization that accounts for accuracy. Experiments report higher compression gains than prior coders on average for pretrained and sparsified models.

  • Problem

    Growing neural-network parameter counts increase model memory complexity, complicating deployment and motivating compression methods that preserve task performance.

    Source: §I · p. 1, D. Model compression vs. source coding · p. 5

  • Method

    DeepCABAC applies CABAC to network parameters and uses a quantization scheme that minimizes an accuracy-aware rate-distortion objective.

    Source: B. Contributions · p. 2, A. DeepCABAC’s coding procedure · p. 7, §VI · p. 12

  • Results

    DeepCABAC compresses pretrained models by x18.9 on average and sparsified models by x50.6, with higher compression performance than previously proposed coders.

    Source: §VI · p. 13

  • Takeaways & Limitations

    CABAC captures correlations between network parameters, allowing compression beyond the entropy limit of codes that assume a stationary distribution.

    Source: §VI · p. 13

Abstract

from arXiv · show

The field of video compression has developed some of the most sophisticated and efficient compression algorithms known in the literature, enabling very high compressibility for little loss of information. Whilst some of these techniques are domain specific, many of their underlying principles are universal in that they can be adapted and applied for compressing different types of data. In this work we present DeepCABAC, a compression algorithm for deep neural networks that is based on one of the state-of-the-art video coding techniques. Concretely, it applies a Context-based Adaptive Binary Arithmetic Coder (CABAC) to the network's parameters, which was originally designed for the H.264/AVC video coding standard and became the state-of-the-art for lossless compression. Moreover, DeepCABAC employs a novel quantization scheme that minimizes the rate-distortion function while simultaneously taking the impact of quantization onto the accuracy of the network into account. Experimental results show that DeepCABAC consistently attains higher compression rates than previously proposed coding techniques for neural network compression. For instance, it is able to compress the VGG16 ImageNet model by x63.6 with no loss of accuracy, thus being able to represent the entire network with merely 8.7MB. The source code for encoding and decoding can be found at https://github.com/fraunhoferhhi/DeepCABAC.

I. INTRODUCTION

Growing neural-network parameter counts increase memory demands and complicate deployment on resource-constrained devices and distributed training. The paper motivates adapting video-coding techniques to neural-network compression, then introduces DeepCABAC and its accuracy-aware quantization approach.

I. INTRODUCTION

  • Growing parameter counts raise memory requirements, slow runtimes, and increase energy consumption, while complicating deployment on resource-constrained devices and federated learning.The paper notes that network parameters must cross limited-capacity communication channels in federated learning.Source: §I · p. 1

A. Entropy coding in video compression

  • CABAC is presented as an adaptable video-coding technique for neural-network compression, with high throughput and compression as design goals.The paper identifies the H.265/HEVC transform-coefficient coding process as a source of potentially suitable techniques.Source: A. Entropy coding in video compression · pp. 1–2

B. Contributions

  • DeepCABAC adapts CABAC to neural-network parameters and quantizes them with a rate-distortion objective that accounts for accuracy; experiments report higher compression performance than previously proposed coders.The paper also states that the quantization scheme avoids relying on expensive retraining or large amounts of data.Source: B. Contributions · p. 2

II. SOURCE CODING

  • Source coding separates encoding into quantization to an integer and binarization, while decoding recovers a reconstruction value that need not invert the quantizer.For model compression, the paper emphasizes predictive performance of the quantized model rather than distance between original and quantized parameters.Source: §II · p. 2

A. Lossless coding

Lossless coding seeks compact representations without changing the input, with entropy providing a lower bound on average code length. Huffman coding offers an optimal tree-based code, but scalar variants can be redundant and cannot exploit conditional dependencies.

A. Lossless coding

  • Lossless coding requires exact reconstruction, and the average code length of any code exceeds the source entropy.The paper notes that some codes can approach the theoretical minimum with up to one bit of redundancy.Source: A. Lossless coding · p. 3

1) (scalar) Huffman coding:

  • Huffman coding assigns shorter tree paths to more probable samples, but its tree can grow quickly for large input dimensions.Scalar Huffman codes are suboptimal and limited to stationary processes because they do not model conditional dependencies.Source: 1) (scalar) Huffman coding · p. 3

2) Arithmetic coding:

Arithmetic coding represents a sequence with a probability-sized interval, enabling compact codes when the source distribution is known. Universal coding adapts when it is not, and CABAC combines context updates with binary arithmetic coding.

2) Arithmetic coding:

  • Arithmetic coding successively narrows an interval for each symbol, and the final interval width equals the probability of the sequence.The paper states that an ideal arithmetic coder requires up to two bits more than the minimum possible code length.Source: 2) Arithmetic coding · p. 4

B. Universal coding

  • Universal codes update a general decoder probability model as samples arrive, seeking adaptable, low-redundancy coding with high encoding and decoding throughput.Two-part Huffman coding must also encode its empirical probability estimate, which can add many bits.Source: B. Universal coding · p. 4

1) CABAC:

  • CABAC binarizes each value using a decision tree, updates per-bin probability contexts from local data statistics, and arithmetic-codes each bin.Its backward-adaptive contexts let the decoder update probability models without receiving encoded probability estimates.Source: 1) CABAC · pp. 4–5

C. Lossy coding

Lossy source coding balances code length against distortion between original and reconstructed values, while model compression instead measures distortion through the quantized model’s prediction performance. DeepCABAC’s setup motivates quantization that accounts for both coding cost and predictive performance.

C. Lossy coding

  • Scalar quantizers measure distortion independently per sample; vector quantizers group samples, though their greater complexity makes scalar quantization more common in practice.Scalar quantizers can retain some coding dependence across samples through correlations in binarization.Source: C. Lossy coding · p. 5

1) Scalar Lloyd algorithm:

  • The Lloyd algorithm seeks a local optimum by approximating quantized-sample code length with the empirical distribution’s entropy and greedily optimizing quantization points.It substitutes code length with −log2 of the empirical probability of each quantized sample.Source: 1) Scalar Lloyd algorithm · p. 5

2) CABAC-based RD-quantization:

  • CABAC-based rate-distortion quantization assumes fixed quantization points, but neural-network compression lacks a known relationship between quantization strength and those points.In video coding, quantization points are predefined by quantization strength.Source: 2) CABAC-based RD-quantization · p. 5

D. Model compression vs. source coding

1) Relaxation of the model compression problem into a source coding problem:

The paper relaxes model compression into a rate-distortion problem by approximating predictive divergence with a Fisher-information-weighted distortion. DeepCABAC uses this framework to quantize and CABAC-code network weights, with a diagonal-FIM approximation to reduce computational demands.

1) Relaxation of the model compression problem into a source coding problem:

  • For pre-trained models with satisfactory accuracy, the paper replaces task loss with KL divergence from the original model and approximates it with the Fisher Information Matrix when output distributions are close.This produces a rate-distortion objective whose distortion is measured approximately in output-distribution space rather than Euclidean parameter space.Source: 1) Relaxation of the model compression… · p. 6
  • Estimating the full Fisher Information Matrix and minimizing the resulting objective are often computationally infeasible, so the method uses efficiently estimated diagonal elements.The diagonal approximation simplifies the objective for practical use.Source: 1) Relaxation of the model compression… · p. 6

III. DEEPCABAC

  • The proposed coder’s desiderata include minimal redundancy, universality, high coding efficiency, configurable error-versus-compression strength, and data efficiency.The decoder should adapt without prior knowledge of the incoming network’s parameter distribution.Source: §III · pp. 6–7

A. DeepCABAC’s coding procedure

  • DeepCABAC scans weights layer by layer, chooses β-defined quantization points, minimizes weighted rate-distortion, applies adapted CABAC, then evaluates the reconstructed model.Repeating the process across β values selects accuracy-versus-size trade-offs; the paper says only one model evaluation is required, reducing the data needed compared with training.Source: Figure 5 · p. 7, A. DeepCABAC’s coding procedure · p. 7

B. Lossless coder of DeepCABAC

DeepCABAC adapts CABAC to weight distributions by context-coding significant, sign, and magnitude-threshold bits, then coding the remainder with Exponential-Golomb. Its lossy stage separates quantization assignments from quantization points and uses equally spaced points to simplify their selection.

B. Lossless coder of DeepCABAC

  • DeepCABAC scans quantized weight tensors in row-major order, with convolutional layers converted to matrix form according to [22].The significance bit identifies zero weights; nonzero weights then receive a sign bit.Source: B. Lossless coder of DeepCABAC · p. 7
  • CABAC context-codes significance, sign, and magnitude-threshold bits to adapt probability estimates to weight distributions around zero; Exponential-Golomb codes the remainder.The fixed-length part of the remainder is not context-coded, approximating its distribution as uniform.Source: B. Lossless coder of DeepCABAC · pp. 7–8

C. Lossy coder of DeepCABAC

  • The quantizer separates assignment Q from reconstruction points Q−1, which are selected to minimize the loss function because network performance was more sensitive to Q−1.The authors report this sensitivity difference as empirical motivation for optimizing the two independently.Source: C. Lossy coder of DeepCABAC · p. 8

1) The quantization points:

  • Equally spaced quantization points qk = ∆Ik simplify the search and encourage fixed-point representations for lower-complexity inference.The step size ∆ sets the spacing between points.Source: 1) The quantization points · pp. 8–9

2) The assignment:

DeepCABAC assigns weights to quantization points by minimizing a weighted rate-distortion function, then searches hyperparameters for the desired accuracy–size trade-off. DC-v1 uses FIM-diagonal estimates, while DC-v2 searches without them but cannot adapt one global step size to layer sensitivities.

2) The assignment:

  • The assignment Qβ uses β = (∆, λ) to assign each weight to a quantization point by minimizing weighted rate-distortion, with code length estimated by CABAC.∆ defines the points and λ the quantization strength.Source: 2) The assignment · p. 9

3) DeepCABAC-version1 (DC-v1)

  • DC-v1 estimates FIM diagonals with a fully factorized Gaussian posterior and uses Fi = 1/σi^2 in the weighted objective.The method interprets each parameter's standard deviation as a measure of robustness to perturbations.Source: 3) DeepCABAC-version1 (DC-v1) · p. 9
  • DC-v1 derives step sizes from σmin and wmax, allowing one global S while assigning different step sizes by layer and accounting for parameter sensitivity.The considered S values are 0 through 256.Source: 3) DeepCABAC-version1 (DC-v1) · p. 9

4) DeepCABAC-version2 (DC-v2):

  • DC-v2 first uses nearest-neighbor quantization to identify step sizes that do not considerably harm accuracy, then applies the weighted assignment with Fj = 1.It avoids the computational cost of estimating FIM diagonals but uses one global step size and cannot adapt to layer sensitivities.Source: 4) DeepCABAC-version2 (DC-v2) · p. 9

1) Trained scalar quantization:

  • Trained scalar quantizers can attain high compression but require costly training iterations over large datasets, whereas DeepCABAC requires neither retraining nor access to the full training dataset.Source: 1) Trained scalar quantization · p. 9

2) Non-trained scalar quantization methods:

  • Non-trained quantization is less computationally expensive, but its gains are limited by unquantized parameter distributions; DeepCABAC explicitly optimizes hyperparameters against network accuracy.Source: 2) Non-trained scalar quantization… · p. 10

B. Lossless neural network compression

DeepCABAC targets redundancy in quantized network parameters with a universal lossless code, and is designed to improve quantization and lossless-compression stages in compression pipelines. Across tested networks, it reports higher average compression gains than weighted Lloyd and uniform quantization.

1) Fixed-length numerical representations:

  • Fixed-length numerical representations reduce parameter bit length but can leave network representations highly redundant; scalar Huffman coding can incur up to 1 bit of redundancy per parameter.For VGG16's 138 million parameters, the passage estimates about 17MB of such redundancy.Source: 1) Fixed-length numerical… · p. 10, 2) Scalar Huffman code · p. 10

3) Compressed matrix representations:

  • Compressed matrix formats such as CSR, CER, and CSER address compression and execution efficiency, but the representations may remain redundant relative to the reachable entropy limit.Source: 3) Compressed matrix representations · p. 10

C. Compression pipelines/frameworks

A. General compression benchmark

  • The benchmark applied DeepCABAC to pretrained VGG16, ResNet50, MobileNet-v1, Small-VGG16, LeNet-300-100, and LeNet5 networks.The architectures were trained on ImageNet, CIFAR10, or MNIST.Source: A. General compression benchmark · p. 10
  • One reported result with a higher compression ratio did not reach accuracy within ±0.5 percentage points of the original, so the authors did not treat it as the best result.Source: A. General compression benchmark · p. 10
  • The comparison included DC-v1 and DC-v2, nearest-neighbor quantization, weighted Lloyd, and scalar Huffman, CSR-Huffman, and bzip2 coding candidates.For Lloyd and nearest-neighbor quantization, the reported results used the best of the listed lossless coders.Source: A. General compression benchmark · p. 11, Table I · p. 11
  • x18.9 for pretrained models and x50.6 for sparsified models were DeepCABAC's average compression gains, versus x13.6 and x47.3 for Lloyd and x5.7 and x25.0 for uniform quantization.Table I reports compression ratios at no loss of accuracy.Source: A. General compression benchmark · p. 11, Table I · p. 11

B. Assignment vs. quantization points

DeepCABAC combines neural-network quantization with CABAC lossless coding. The experiments report better compression than uniform quantization and prior coding techniques, with quantizer trade-offs depending on step size.

B. Assignment vs. quantization points

  • DeepCABAC always compressed better than uniform quantization, while DC-v1 outperformed DC-v2 at small step sizes by accounting for parameter robustness.The comparison selected networks with accuracies within ±0.1 percentage point of uniform quantization.Source: B. Assignment vs. quantization points · p. 12
  • DC-v2 attained similar or higher compression gains than DC-v1, particularly for pretrained networks, while exploring more step sizes for accuracy–bit-size trade-offs.As step size increased, DC-v2 approached DC-v1, and the specific rate-distortion expression became less relevant.Source: B. Assignment vs. quantization points · p. 12

C. Lossless coding

  • CABAC achieved higher compression gains across all tested quantized Small-VGG versions, sometimes producing code lengths below the EPMD entropy.The compared quantized models stayed within ±0.1 percentage point of the original accuracy.Source: C. Lossless coding · p. 12, Table III · p. 12

VI. CONCLUSION

  • x18.9 on average for pretrained networks and x50.6 for sparsified versions; DeepCABAC consistently outperformed prior coding techniques with similar characteristics.The conclusion also states that DeepCABAC can capture parameter correlations and compress beyond the entropy limit of codes assuming a stationary distribution.Source: §VI · pp. 12–13

APPENDIX A EXPERIMENT DETAILS

The appendix specifies quantization and hyperparameter-selection procedures for uniform quantization, Lloyd variants, and DeepCABAC. It also reports that MobileNet v1 did not meet the target accuracy threshold despite increasing its cluster count.

A. Uniform quantization

  • Uniform quantization uses one weighted-Lloyd step with no importance measure or cluster-center update, but quantizes layer-wise rather than across the whole network.For the reported experiment, cluster counts began at 256 for un-sparsified and 32 for sparsified networks, doubling until accuracy was within ±0.5 percentage points; sparse models also used CSR-Huffman coding.Source: A. Uniform quantization · p. 15

B. Lloyds hyperparameter selection

  • Lloyd hyperparameter selection iteratively searched cluster counts and λ values, choosing adjacent accuracy-qualified λ values with the smallest entropies for further refinement.The procedure typically needed two refinement rounds; Table V lists cluster counts and λ values.Source: B. Lloyds hyperparameter selection · p. 15, Table V · p. 15

C. DeepCABAC’s hyperparameter selection

D. DC-v1

  • The DC-v1 experiment searched a predefined hyperparameter set, including a geometric sequence of λ values.The supplied λ expression specifies 100 indexed values beginning at 0.0001.Source: D. DC-v1 · p. 15

E. DC-v2

  • MobileNet v1 and its sparse counterpart failed to reach the ±0.5 percentage-point accuracy threshold even after their cluster counts were increased.The appendix introduces a DC-v2 hyperparameter search but gives no search values in the supplied passage.Source: E. DC-v2 · p. 15

APPENDIX B APPROXIMATIONS TO THE FISHER INFORMATION MATRIX

The appendix connects a variational sparsification procedure to rate-distortion quantization and motivates using FIM diagonals as importance weights. It also describes the prior procedure underlying that connection.

APPENDIX B APPROXIMATIONS TO THE FISHER INFORMATION MATRIX

  • Prior work [26] uses a log-scale uniform prior and factorized Gaussian posterior, approximates the KL divergence, and minimizes the objective with scalable sampling techniques.The posterior mean and standard deviation are interpreted here as parameter values and robustness to perturbations, respectively.Source: Appendix B · p. 16, A. Connection between pruning and… · p. 16

A. Connection between pruning and quantization

  • The scalar rate-distortion objective generalizes the cited pruning scheme: with identity reconstruction and a spike-and-slab decoder, Lloyd optimization recovers that scheme as a special case.Choosing FIM diagonals from inverse variances motivates the importance weights used in the experiments.Source: A. Connection between pruning and… · p. 16
  • Figure 8 presents rate-accuracy curves for pretrained LeNet5 quantized with the weighted Lloyd algorithm using different importance measures.Source: Figure 8 · p. 16

B. Connection between variances, Hessian, and FIM-diagonals

The appendix relates estimated variances, signal-to-noise ratios, and FIM diagonals through a second-order loss approximation. In practice, variance-weighted quantization was more stable than Hessian-weighted quantization in the reported LeNet5 comparison.

B. Connection between variances, Hessian, and FIM-diagonals

  • The Fisher information matrix is a semipositive approximation of the loss Hessian, and a second-order expansion links estimated variances to FIM diagonals and the Hessian.The resulting relationship also connects parameter variance with signal-to-noise ratio.Source: B. Connection between variances,… · p. 16

C. Hessian-weighted vs. variance-weighted quantization

  • Variance-weighted quantization produced more stable rate-accuracy curves and better compression than Hessian-weighted quantization on pretrained LeNet5.Source: C. Hessian-weighted vs.… · p. 17

APPENDIX C PSEUDOCODES

The appendix provides pseudocode for Huffman code generation, encoding and decoding, plus weighted Lloyd and uniform quantization algorithms.

APPENDIX C PSEUDOCODES

  • Huffman encoding replaces each message symbol with its codeword and concatenates the resulting bits into an encoded sequence.The input is a message and a symbol-to-bitstring code; the output is a bit sequence.Source: Appendix C · p. 17
  • Huffman decoding scans the bit sequence for a codeword prefix, appends its symbol to the message, and removes the consumed bits.The decoder takes the encoded bits and the same symbol-to-codeword mapping as input.Source: Appendix C · p. 17
  • Huffman code generation enqueues message symbols with positive frequencies, repeatedly combines the two smallest-frequency nodes, then assigns codewords by tree traversal.The traversal appends 0 on left branches and 1 on right branches.Source: Appendix C · p. 17
  • Weighted Lloyd’s algorithm assigns parameters to clusters using importance measures and minimizes a Lagrangian loss that includes a cluster-probability term.It takes clusters, parameters, importance measures, and a multiplier as input, initializes cluster probabilities uniformly, and repeats assignment and cluster-reset steps until convergence.Source: Appendix C · p. 18
  • Uniform quantization assigns weights in each neural-network layer to that layer’s cluster centers by minimizing a per-weight criterion.The pseudocode takes the layers’ weights and cluster centers as input and returns cluster assignments.Source: Appendix C · p. 18

Related papers

Loading 1907.11900v1…