PaperlayerView exact revision on arXiv

Source-linked AI summary

The Description Length of Deep Learning Models

Léonard Blier, Yann Ollivier

arXiv:1802.07044v5cs.LG

TL;DR

Deep models’ ability to generalize despite their many parameters remains incompletely understood. The paper measures their data compression using MDL methods, including prequential coding. It finds that deep networks compress data well, while variational methods give much poorer codelengths than simple incremental coding.

  • Problem

    Deep models can generalize despite many parameters, but their complexity in relation to that ability is not well understood.

    Source: §1 · p. 1

  • Method

    The authors measure compression using MDL-based bounds, including variational methods and prequential coding on standard learning.

    Source: §1 · p. 2, §3.4 · p. 6

  • Results

    Deep networks compress data despite their many parameters, while prequential coding gives much better codelengths than variational inference.

    Source: §1 · p. 2

  • Takeaways & Limitations

    The number of parameters is not an obstacle to compression, but understanding variational inference’s codelength limitation remains future work.

    Source: §4 · p. 8, §5 · p. 9

    Prequential codes can have an early catch-up lag: large architectures may need many samples before cumulative codelength beats uniform coding.

    Source: §3.4 · p. 7

Abstract

from arXiv · show

Solomonoff's general theory of inference and the Minimum Description Length principle formalize Occam's razor, and hold that a good model of data is a model that is good at losslessly compressing the data, including the cost of describing the model itself. Deep neural networks might seem to go against this principle given the large number of parameters to be encoded. We demonstrate experimentally the ability of deep neural networks to compress the training data even when accounting for parameter encoding. The compression viewpoint originally motivated the use of variational methods in neural networks. Unexpectedly, we found that these variational methods provide surprisingly poor compression bounds, despite being explicitly built to minimize such bounds. This might explain the relatively poor practical performance of variational methods in deep learning. On the other hand, simple incremental encoding methods yield excellent compression values on deep networks, vindicating Solomonoff's approach.

1 Introduction

The paper uses compression to examine deep-model complexity and generalization, including why networks can fit random labels without learning. It finds that deep networks compress data despite their many parameters, while variational methods give inefficient codelengths and prequential coding performs better.

1 Introduction

  • Deep models’ ability to generalize despite many parameters remains poorly understood, although prior measures suggest they are simpler than parameter counts imply.Source: §1 · p. 1
  • MDL evaluates a model by the bits needed to encode both the data and the model itself.Source: §1 · p. 1
  • Networks can reach 100% training accuracy on random labels yet fail to compress them, with no information in the parameters and no learning.Source: §1 · p. 2
  • Variational inference yields inefficient codelengths for deep models despite explicitly minimizing description length, which might explain its often-suboptimal test performance.Source: §1 · p. 2
  • Prequential coding on top of standard learning yields much better codelengths than variational inference and correlates better with test-set performance.The authors report that deep networks compress data well even when the cost of describing the model is included.Source: §1 · p. 2

2 Probabilistic Models, Compression, and Information Theory

The section frames supervised classification as encoding labels given inputs, with the model’s codelength accounting for both fit and model description. It introduces uniform coding as a baseline and relates any compression gain over that baseline to input–output mutual information.

2 Probabilistic Models, Compression, and Information Theory

  • The setup treats supervised classification as encoding labels y for a recipient who already has the inputs x, using MNIST and CIFAR10 as examples.Source: §2 · p. 3

2.1 Definitions and notation

  • A model is a conditional distribution p(y|x), while an architecture is a parameterized set of such models.Source: §2.1 · p. 3

2.2 Models and codelengths

  • Shannon–Huffman coding sends labels using the model’s cross-entropy, but this bound assumes sender and receiver know the model in advance.The assumption is problematic when the model must be learned from the data.Source: §2.2 · p. 3

2.3 Uniform encoding

  • Uniform coding provides a baseline of 199 kbits for MNIST and 166 kbits for CIFAR10.Source: §2.3 · p. 4

2.4 Mutual information between inputs and outputs

  • The gain over uniform coding is limited by input–output mutual information, and successful label compression directly estimates that quantity.Source: §2.4 · p. 4

3 Compression Bounds via Deep Learning

The section compares ways to encode deep-learning models and labels under MDL, including the cost of describing the model. Variational codes give weaker practical compression than prequential codes, which encode data incrementally without directly transmitting weights.

3.1 Two-Part Encodings

  • 32-bit float encoding costs 32 Mbits for a million-parameter model, 200 times the uniform encoding on CIFAR10.Two-part codes add parameter-description cost to the codelength for labels given inputs.Source: §3.1 · p. 5

3.2 Network Compression

  • Existing trained-network encodings still yield label codelengths above the uniform bound for image classification.The section also considers low-dimensional affine-subspace encodings, where the subspace can be transmitted via a pseudorandom seed.Source: §3.2 · p. 5

3.3 Variational and Bayesian Codes

  • Variational model selection favored smaller networks than cross-validation, but its best-codelength models had low test accuracy on MNIST and CIFAR.The reported variational codelengths were 24.1 kbits on MNIST and 89.0 kbits on CIFAR.Source: §3.3 · p. 6

3.4 Prequential or Online Code

  • The prequential code encodes labels using successive predictors trained on previously transmitted data, without directly encoding the weights.Its codelength depends on the training algorithm’s ability to generalize from earlier data to later data.Source: §3.4 · pp. 6–7
  • 6 times smaller on MNIST and twice smaller on CIFAR, prequential codelengths are than the corresponding variational codelengths.The best prequential results used an 8-layer convolutional network on MNIST and VGGb on CIFAR.Source: §3.4 · p. 7
  • 4.10 kbits (compression ratio 0.021) on MNIST and 45.3 kbits (ratio 0.27) on CIFAR were the best prequential codelengths, with 99.5% and 93% test accuracy, respectively.The MNIST result used a depth-8 convolutional network; the CIFAR result used VGGb.Source: §3.4 · p. 7
  • Model switching addresses prequential catch-up: VGGb needed 5,000 CIFAR samples to reach cumulative compression ratio below 1, though per-label cost beat uniform after 1,000.Switching also improved practical bounds when choosing among copies of the same model trained for different numbers of steps.Source: §3.4 · p. 7

4 Discussion

The discussion argues that deep networks can compress data despite their parameter counts, while variational codes perform poorly relative to prequential coding. It relates prequential compression to generalization and notes that the observed gap between coding methods remains unexplained.

4 Discussion

  • Deep networks compress data well with prequential coding, despite their large parameter counts.The discussion contrasts this with variational coding, which compresses with worse prediction performance.Source: §4 · pp. 7–8
  • Prequential coding shows that models generalizing well at every dataset size also compress well, with coding efficiency directly due to generalization at each time.Figure 2 reports CIFAR codelength, test accuracy, cumulative codelength relative to uniform encoding, and compression ratio across five models during online training.Source: §4 · p. 8, Figure 2 · p. 8
  • The usual asymptotic equivalence among two-part, Bayesian, and prequential codes assumes identifiable models, data generated by the model, a suitable prior, and other technical conditions.The authors note deep-learning models usually do not satisfy these hypotheses, and their prequential codes use standard regularized training rather than maximum-likelihood estimates.Source: §4 · p. 8
  • Variational methods perform poorly on image-classification codelengths compared with prequential codes, despite optimizing a description-length objective.The authors say this makes their relatively poor test-time results less surprising.Source: §4 · pp. 8–9
  • The reason variational codelengths lag prequential codelengths remains an open problem, with imperfect optimization, posterior-family mismatch, or Bayesian underfitting among possible contributors.The authors report similar results across tested Gaussian priors, so they do not expect prior choice to be a key factor.Source: §4 · pp. 8–9

5 Conclusion

Deep learning models can encode data together with the model in fewer bits than a naive encoding despite their many parameters. The authors report that variational inference gives poor codelengths compared with simple incremental coding, leaving the reason for this limitation as future work.

5 Conclusion

  • Deep learning models can represent data and model together in fewer bits than a naive encoding, while simple incremental coding gives better codelengths than variational inference.Understanding variational inference's observed limitation remains future work.Source: §5 · p. 9

A Fake labels are not compressible

The appendix formalizes why random labels generally cannot be compressed, even when a coding procedure can depend on the inputs. With high probability, their codelength is nearly the uniform encoding length.

A Fake labels are not compressible

  • The appendix defines a code as a program that outputs the label sequence, with input-conditioned codes allowed to use the inputs.This sets the meaning of codelength L(y1:n) or L(y1:n|x1:n).Source: A Fake labels are not compressible · p. 12
  • For iid uniform labels in K classes, any coding procedure has codelength at least n log2 K − δ − 1 with probability 1 − 2^-δ.The result holds for any coding procedure, including ones depending on the inputs.Source: A Fake labels are not compressible · p. 12
  • A counting argument shows that fewer than 2^-δ|A|−1 sequences can be encoded below the stated length, so most sequences cannot be compressed by any algorithm.Here A is the set of all K^n possible label sequences.Source: A Fake labels are not compressible · p. 12

B Technical details on compression bounds with random affine subspaces

The random-affine-subspace method encodes a model by optimizing parameters within a shared random subspace, then sends those parameters and the labels. The reported compression bounds omit label-coding cost and could improve if precision were optimized.

B Technical details on compression bounds with random affine subspaces

  • The method shares a random affine subspace, optimizes its parameter vector, and transmits that vector at precision ε along with labels encoded by the resulting model.The parameter cost is k × log2 ε; the label cost is −log2 ˜pφ*(y1:n|x1:n).Source: B Technical details on compression… · p. 12
  • For MNIST, LeNet's 290-dimensional intrinsic dimension yields a 9,280-bit model description and a 0.05 compression ratio, excluding label-coding cost.The reported model reaches 90% accuracy, the threshold used in the cited work.Source: B Technical details on compression… · p. 13
  • For CIFAR, LeNet's intrinsic dimension of 2,900 yields a 92,800-bit model description and a 0.05 compression ratio, excluding label-coding cost.Source: B Technical details on compression… · p. 13
  • The reported bounds are not precision-optimized; coarser parameter precision lowers parameter cost but makes label encoding more expensive, so an optimal ε could improve the bound.The authors leave this optimization for future work.Source: B Technical details on compression… · p. 13

C Technical Details on Variational Learning for Section 3.3

The variational experiments use diagonal-covariance Gaussian posteriors and optimize the variational bound with gradient descent and Monte Carlo estimates. The appendix also specifies the network architectures and test-time prediction procedure.

C Technical Details on Variational Learning for Section 3.3

  • The posterior family is multivariate Gaussian with diagonal covariance, parameterized by μ and ρ, with σ_i = log(1 + exp(ρ_i)).The covariance matrix has diagonal entries σ_i^2.Source: C Technical Details on Variational… · p. 13
  • The variational bound is optimized over the posterior parameters with gradient descent, using Monte Carlo estimates of its value and gradient.The Gaussian prior and posterior make the KL term explicit; the Monte Carlo estimate uses one sample in practice.Source: C Technical Details on Variational… · p. 13
  • For CIFAR and MNIST, the experiments use two-hidden-layer fully connected networks of width 256, trained with SGD at learning rate 0.005 and batch size 128.The authors report that fully connected models compressed better than convolutional models in these experiments.Source: C Technical Details on Variational… · p. 13
  • The alternative LeNet-like architecture has two convolutional layers with 6 and 16 filters, followed by three fully connected layers.The convolutional layers use kernels of size 5 and are followed by ReLU and max-pooling; the first two fully connected layers have dimensions 120 and 84.Source: C Technical Details on Variational… · p. 13
  • At test time, predictions use parameters sampled from the learned distribution rather than the averaged model, and the authors note this lowers MNIST accuracy relative to Blundell et al. (2015).The stated objective was to evaluate the model used for compression, not to obtain the best prediction score.Source: C Technical Details on Variational… · p. 14

D Technical details on prequential learning

The prequential experiments compare a uniform label code with neural-network predictors on MNIST and CIFAR. The appendix lists the model variants, training settings, and timestep schedules used for the comparisons.

D Technical details on prequential learning

  • For MNIST, the prequential experiments include a uniform label predictor, an MLP with two 512-unit hidden layers, a shallow network of width 5000, a tinyCNN, and VGG variants.The tinyCNN has four convolutional layers and two 256-unit fully connected layers; VGG uses 13 convolutional layers, with VGGb adding batch normalization and data augmentation.Source: D Technical details on prequential… · p. 14
  • For CIFAR, the listed predictors include a uniform label model, an MLP with two 256-unit hidden layers, and a VGG-like convolutional network.The neural networks use dropout probability 0.5 and Adam with learning rate 0.001; the timestep schedule runs from 8 to 32768.Source: D Technical details on prequential… · p. 14
  • The MNIST prequential schedule runs from 10 to 40960 samples, and VGGb was selected as the best prequential model for Table 1.The appendix states that the VGG-like network was selected for the CIFAR prequential results in Table 1.Source: D Technical details on prequential… · p. 14

E.1 Switching between model classes

The switch code encodes a sequence of model switches and then uses the selected predictors prequentially. On CIFAR10, switching among models lowers codelength by more than 11 kbits relative to the alternatives described; on MNIST it makes little difference.

E.1 Switching between model classes

  • Prequential encoding starts with a uniform code for the first block, then encodes each later block using a predictor trained on the preceding data.The algorithm transmits the random seed when stochastic optimization is used.Source: §E.1 · p. 15
  • Table 2 reports codelengths that include model description cost, compression ratios relative to the uniform code, and test accuracy.For variational and prequential codes, the table uses the model and hyperparameters giving the best compression bound.Source: Table 2 · p. 15
  • The switch code first encodes a switching sequence, then uses the prequential code with the model selected by that sequence at each time.The procedure requires an agreed model set and prior over switching sequences.Source: §E.1 · p. 15
  • On CIFAR10, switching among models saves more than 11 kbits, reaching 34.6 kbits and a compression ratio of 0.21; on MNIST, switching makes little difference.The cost of encoding the switch sequence is reported as negligible.Source: §E.1 · p. 15

E.2 Self-Switch: Switching between variants of a model or hyperparameters

Self-switching chooses among training-time variants of one architecture, avoiding the need to keep multiple architectures in parallel. It addresses the early prequential catch-up problem and achieves compression close to full model switching.

E.2 Self-Switch: Switching between variants of a model or hyperparameters

  • Self-switch uses stopping-time variants of the same model family, a form of regularization via early stopping.Source: §E.2 · pp. 15–16
  • Figure 3 shows that self-switch resolves early high codelengths for both CIFAR models, when standard training initially performs below the uniform predictor.The early disadvantage covers the first 1280 labels for VGGb and the first 10000 labels for the shallow network.Source: Figure 3 · p. 16, §E.2 · p. 16
  • At each prequential step, self-switch evaluates up to 10 training epochs on the next data block and switches to the epoch with the lowest loss.The additional cost is encoding the selected epoch at each step.Source: §E.2 · p. 16
  • Self-switch achieves similar compression bounds to full switching while storing one network; on CIFAR it is only 300 bits (0.006 bit/label) worse, with no observable difference on MNIST.Source: §E.2 · p. 16

Related papers

Loading 1802.07044v5…